#2357 拍卖会
对于选物品问题,可以将其转化为矩阵,然后在矩阵中满足限制条件进行 DP。
#2358 序列
区间 \([1,x]\) 中二进制下有奇数个 \(1\) 的整数有
\[\lfloor \frac{x}{2} \rfloor + (x\mod 2 \ \ ||\ \ popcount(x)\mod 2)
\]
int get(int x) {
return (x>>1)+(x&1||__builtin_popcount(x)&1);
}
#2359 清除病毒
需要数据结构的期望求法:加权概率。
需要 DP 的期望求法:
\[E(x+y)=E(x)+E(y)
\]