3.31 补题
A
\(5pts\)
\(n=2\) 时，\(\frac n 2=1\)，即为 nim 游戏。
\(30pts\)
对于 \((a_1,a_2,a_3,a_4,a_5,a_6)\) 这样的六元组，至多有 \(10^6\) 个。
记忆化搜索他们的 SG 值即可。
可能需要若干剪枝，因为复杂度其实是 \(10^6\times 6^3\) 的。
\(100pts\)
首先观察样例 2，合理猜测跟出现次数有关系。
首先打个 SG 函数的暴力，然后我们把 \(n=6,A\le 3\) 的所有 baobao 的点打出来
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 0 2
0 0 0 0 1 1
0 0 0 0 1 2
0 0 0 0 2 2
0 0 0 0 0 3
0 0 0 0 1 3
0 0 0 0 2 3
0 0 0 0 3 3
1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 2 2
1 1 1 1 1 3
1 1 1 1 2 3
1 1 1 1 3 3
2 2 2 2 2 2
3 3 3 3 3 3
注意到好像同样的数出现的次数都很多，然后我们合理猜测，只要某一个数出现 \(>\frac n 2\) 次，就是 baobao。
显然，这是错的：hack:0 1 1 1 1 2。
然后我们发现上面那些情况以 0 开头的比以 1 开头的多，更比以 2 开头的多。合理猜测，这个出现 \(> \frac n2\) 的数还必须是最小的数。
然后，这题就做完了，因为过样例了。
我们来考虑一下如何证明：
只要我们保证最小值的数量始终 \(\geq \frac n 2\) 就可以永远处于不败之地
显然，此时无论对方怎么选，都会使得一个最小值变小，并形成新的最小值。我们再让这个最小值存在 \(> \frac n 2\) 个即可。
此时后手就可以保证先手取的时候最小值永远有 \(\geq \frac n 2\) 个，必胜。
B
感觉典。
\(70pts\)
\(n^2\) 暴力，由于严重跑不满，而且 \(2.5 sec\) 所以可以过 \(n\le 3\times 10^4\)
\(90pts\)
发现特殊性质 A 其实是个区间和，用线段树或者分块维护。同时结合上述算法即可。
\(100pts\)
对于 \(a_ib_ic_id_ie_i\) 中的 \(a[i]\leftarrow a[i]+x\)，其实是最后的结果增加了 \(x b_i c_i d_i e_i\)。
但是你发现 \(b_ic_id_ie_i\) 照样不好维护，所以我们直接把 \(32\) 种（实际是 \(31\) 种）全部维护即可。
如果修改状压的第 \(i\) 位且修改值（增加了） \(x\)，则状压转移可以以如下性质表示：
\[F_s\leftarrow F_S+kF_{s-i}(i\in S) \]这个东西分块维护就可以了。
然后时间复杂度是 \(O(2^kkn\sqrt n)\)，也是 \(70pts\)。
这一坨可以用线段树维护，对于每一种状态分开来合并即可。
也就是
\[F_s\leftarrow F_S(lson)+F_S(rson) \]有很多细节，包括建树，包括这些状态之间的转移，总的时间复杂度是 \(O(2^kkn\log n)\)。
C
\(20pts\)
全排列。
\(70pts\)
jzy 的乱搞喵 orz
按照 a 从大到小、b 从小到大分别做一次取 min
显然是错的，但是 70pts 喵
\(40pts\)
其实是，\(\sum^n_{i=1}a_i+\min t\)。
\(t\) 的值只取决于 \((a_i,b_i)\) 这些二元组的”使用“顺序。
二元组的经典 tricks 是往 \(2\times n\) 的网格图上放，也就是 \((1,i)\) 的权值是 \(a_i\)，\((2,i)\) 的权值是 \(b_i\)。求 \((1,1)\to (2,n)\) 的权值和。
对于每个 \(i\)，我们考虑在什么时候交换 \(i\) 和 \(i+1\) 不劣。设 \(w_i\) 表示在第 \(i\) 列向下走的方案的权值和， \(v_i\) 为交换后的值，那么显然需要满足
\[\max(w_i,w_{i+1})\geq \max(v_i,v_{i+1}) \]两边做基本等式变化也就是
\[a_i+b_{i+1}+\max(b_i,a_{i+1})\geq a_{i+1}+b_i+\max (a_i,b_{i+1}) \]交换排序， \(O(n^2)\)。
\(100pts\)
式子再做转换，
\[\min(a_{i+1},b_i)\le \min(a_i,b_{i+1}) \]分类讨论以后，可以得到排序的策略是：
将 \(a_i\le b_i\) 的将 \(a_i\) 升序排在前面，反之将 \(b_i\) 降序排在最后。
D
\(20pts\)
\(O(n^2\log n)\) dp 暴力。
\(dp_i\) 表示前 \(i\) 项结尾当前的最大满意度。
然后就是
\[dp_i=\max_{j\le i-k+1} \{f_{j-1}+|^i_j a_j+\&^i_j a_j+\gcd^i_ja_j\} \]很好维护。
\(50pts\)
上述暴力可能可以莽过。
三个操作都有一个性质，就是他们的取值个数都是 \(\log\) 级别的。
所以对于一个确定的 \(r\) 会使得 $$calc(i,j)=|^i_j a_j+{AND}^i_j a_j+\gcd^i_j a_j $$ 不同的点只有 \(3\log\) 级别个。
我们枚举 \(l\) 的时候，可以跳过那些相等的点，直接维护在这一坨相等的 \(l\) 之中 \(f_{l-1}\) 的最大值，求这个区间的时候可以二分。
时间复杂度 \(O(n\log^2n)\)，显然对于 \(3\times 10^5,2sec\) 可以过了。
但是由于出题人的指示，这玩意只有 \(50pts\).
\(100pts\)
把上面那个二分考虑如何取缔掉。
对于一个 \(calc(l,r)\) 确定的 \(l\)，则当 \(r\) 增大时，这个区间一定不会被拆分，只可能与其他区间合并。
用链表维护，需要的时候合并即可，不需要二分。
标签：le,frac,log,max,最小值,3.31,维护,联考 From： https://www.cnblogs.com/wtc-qwq/p/18106877