2022多校补题
牛客2
C
Alice和Bob玩Nim游戏，必胜的人希望尽快结束，必输的人希望尽慢结束，求游戏要进行几轮以及第一个人有多少种方法达成游戏进行的轮数最大化
考虑\(n=2\)的情况，两堆石子，不妨设为\(x, x\)，那么必输者的最佳策略是调整为\(x-1,x\)，依此类推，让游戏进行\(2x\)轮
由上述观察启发，我们从先手必输者的角度考虑，假定后手选择一堆石子\(a_i\)，调整至\(a_{i}-1\)，反应在异或和\(s\)上
就是\(0\)变为\(a_i \oplus (a_i - 1)\)，也即把\(a_i\)的lowbit及以下的位进行翻转
现在，我们考虑必胜者的决策，他需要选择满足\(a_j \oplus a_i \oplus (a_i - 1) < a_j\)的\(a_j\)，这等价于选择\(lowbit(a_j) \leq lowbit(a_i)\)的\(a_j\)，如果我们选择\(lowbit(a_i)\)最小的\(a_i\)，那么对手选择满足\(lowbit(a_j)=lowbit(a_i)\)，此时，对手的决策为\(a_j \to a_j - 1\)
根据上述分析，必输者可以把局数控制在\(\sum a_i\)，这显然也是局数的上界
如果我们选择了一个\(lowbit(a_i)\)较大的值，有可能达到这个界吗？记\(l=lowbit(a_i)\)，对手可以选择的所有解为\(a_j \oplus (2^{l+1}-1) < a_j\)的\(a_j\)，也就是第\(l\)位为\(1\)的\(a_j\)，我们需要\(a_j \oplus (a_j - 1) = 2^{l+1}-1\)，在\(a_j\)的第\(l\)位为1时，这等价于\(a_j = 2^l\)
剩下的分析是平凡的
F
题目本身没啥意思，建Trie树删删减减就行
考场上感觉自己脑溢血，离线做的题写了个在线版本的根号做法，最后还剩了一点bug不想修了...
每次后半场比赛感觉自己都在做梦...
牛客3
B
把\(N\)个人分配给\(k\)个城市，其中第\(k\)个城市需要恰好被分配\(e_k\)个人，把\(i\)分配给\(j\)会产生\(c_{ij}\)的代价，求最小代价
\(N \leq 10^5, k \leq 10\)
很容易就能建出费用流的模型，不过点数太大，考虑模拟费用流
由于流量为\(1\)，因此每次都是找到若干个人\(a_1, a_2, ..., a_k\)，然后\(a_2\)移动到\(a_1\)所在的城市，\(a_3\)到\(a_2\)，最后由新点挤到\(a_k\)的位置，可以发现这对应了原题中\(k\)个汇点中\(a_1\)到新点的一个路径，用spfa求出这个最短路增广即可
H
给定字符串\(A\)和字符串\(B_1, ..., B_k\)以及序列\(v_1,...,v_m\)，对每个\(B_i\)，求出\(B_i[l, r]\)是\(A\)的字串并且\(v_l + ... +v_r\)最大的字串的权值
其实就是字串匹配和最大字段和糅合的一个题...不过卡SA...复习一下SAM...
后缀自动机每个点对应若干个串，不妨设\(i\)对应的字符串集合为\(S_i\)，那么有如下的参数
- \(endpos\)，表示\(S_i\)中的串在\(S\)中恰好以这些位置结尾
- \(minl, maxl\)，显然\(S_i\)中的串的长度是连续的，\(minl, maxl\)分别指代对应长度的最小/最大值
- \(endpos\)的集合会产生一棵树，记\(fa\)为\(i\)在这棵树上的父亲，\(fa\)的\(endpos\)集合包含\(i\)的集合，也不难想象\(minl(i) = maxl(fa) + 1\)
- \(son_{i, c}\)，表示\(i\)转移\(c\)之后到达的状态
现在我们考虑如何匹配，转移就是能转移就转移，否则跳父边
I
求\(\sum_{i=0}^n \binom{n}{i} D_{n-i} i^k / n!\)，对一个1000左右的质数取模
考场上好像把这个最开始的式子写错了，离大谱...
一看答案是个分数，玩不明白了...
把表打出来，进OEIS查一查，可以知道答案是\(\sum_{i=0}^k S(k, i)\)
题目里有个条件是\(k - n \leq 5000\)，我们可以把边边角角的斯特林数减掉，剩下的就是求贝尔数
剩下的部分感觉太科技了，学了感觉用不到，算了...
杭电4
123在玩木头人
1009
初始有\(s_0\)的体力和\(n\)个怪兽，打怪兽的顺序可以任意决定，打怪兽\(i\)时，你的体力会永久性改变\(d_i\)，之后，如果你的体力\(\geq s_i\)，那么你能得到一分，试问得分的最大值
感觉自己在看懂题解和看不懂题解的贪心之间徘徊，先咕着
牛客4
J
久违地复习一下set，以及感觉写代码真是处处漏洞
牛客5
这一场非常搞笑
I
每一组的人数可以看作\(x+ik\)，如果我们确定了\(\sum i\)，那么剩下的最优策略就是尽量均分，有一个\(O(1)\)的式子
注意到\(x < k\)，因此\(\sum x < mk\)，也就是说\(\sum i\)只有\(m\)种选择，对这\(m\)种选择一一讨论即可
杭电5
1007
第一次写分治NTT，果然写锅了，下次不会了（
老年人知道推式子的套路都推得慢人一步，呜呜呜
1002
计算\(\sum f(i)\)，\(n \leq 10^{12}\)
其中\(f(n)\)是一个积性函数，满足\(f(p^c)=p^c/c\)
标算是学过但没感觉弄明白（也感觉没啥大用）的\(PN\)，被教育了，学了下写法...
由于\(f(p) = p\)，因此我们构造\(h = id^{-1} * f\)，\(id^{-1}\)为\(id\)的狄利克雷逆元，也即\((\mu\times id)\)，具体的
\(h(p^c) = \sum_{d \leq c} (\mu\times id)(p^d) f(p^{c-d}) = p^c(\frac{1}{c} - \frac{1}{c-1})\)
然后套用\(PN\)就行
但感觉\(PN\)还是没啥大用...
后记
还是咕了，后面有印象的题不多了，感觉好题变少了