首页 > 其他 > 详细

TopCoder - 14744 OrAndSum

时间:2018-01-19 13:34:37      阅读:270      评论:0      收藏:0      [点我收藏+]

意:给你$pairOr,pairSum$两个含有$n$个非负整数数组,问你是否能构造出一个数组$x[0] \cdots x[n]$满足$\forall \ {0\leqslant i \leqslant n-1}, x[i] \or\ x[i+1] = pairOr[i] \ \wedge x[i] + x[i+1] = pairSum[i]$。

1.证明$a+b=a \ or \ b + a \ and \ b$

证:记$p_i,q_i$分别为$a,b$的第$k$位(二进制)。则

$$a+b=\sum_k(p_k+q_k)2^k$$

$$a \ or \ b=\sum_k(p_k\vee q_k)2^k$$

$$a \ and \ b=\sum_k(p_k \wedge  q_k)2^k$$

$$a+b-a \ or \ b - a \ and \ b = \sum_k(p_k+q_k-p_k \wedge q_k - p_k \vee q_k)2^k=0$$

TopCoder - 14744 OrAndSum

原文:https://www.cnblogs.com/p0ny/p/8316226.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!