DAY1T1
稍微有点难想,想了 \(50min\) A 掉但是感觉时间有点亏。
每个数位置的奇偶性不会变,最后剩的有一定是奇数位置,所以取原数列奇数位置上所有数的中位数即可
DAY1T2
毒瘤构造,打个部分分直接跑。
令 \(a\&b=0\) 修改操作相当于是将位置编号为 \(x\),\(a\&x=a\) 且 \(x\&a+b=x\) 的数取反。
考虑将所有数按照二进制下 \(1\) 的个数分层。第 \(i\) 层的数二进制下有 \(i\) 个 \(1\) 最高层只有 \(2^k-1\)。
设第 \(i\) 层的数的集合为 \(S_i\)。容易发现,可以通过对 \(S_i\) 中的一个数进行一次合适的操作使二进制下比它差一个 \(1\) 的数中的任意集合改变。
那么需要找到一个最小的集合 \(T_i\) 使操其中的数的影响范围可以覆盖 \(S_{i-1}\)。这样就只需对 \(T_i\) 中的数进行操作使第 \(i-1\) 层变成 \(T_{i-1}\),直到全部变成 \(0\)。
\(T_i\) 可以通过贪心预处理,这样上界为 \(157885\)。可以证明(就是不知道怎么证明)次数上界为 \(\frac{n\ln\ln n}{\ln n}\)。
DAY1T3
又是只有 \(20pts\) 的一道题...
考虑每次取两个不同种类宝石的限制,答案应该为 \(max(a,b,c,d,e,\frac{s+1}2)\),其中 \(s\) 为宝石总数。
那么相当于有绝对众数的时候答案取绝对众数的,否则为和的一半。
看到绝对众数,可以想到摩尔投票,至少是摩尔投票的思想。
考虑设 \(d_{i,j,k,s}\) 表示桌上两张牌为 \(i,j,i<j\),还剩 \(s\) 张 \(k\) 没有被消掉时最少消了多少次。\(f_{i,j,k,s}\) 表示桌上两张牌为 \(i,j,i<j\),还剩 \(s\) 张非 \(k\) 的牌没有消掉时最少消了多少次。