2022寒假刷题计划

1.28

P4310 绝世好题
二进制小清新dp，\(O(n\log n)\)

CF618F Double Knapsack
神仙构造,大胆猜想，小心求证。
猜想一定存在两段连续的序列满足答案。
前缀和有 \(n+1\) 项，尝试构造值域为 \(n\) 以利用鸽巢定理。
\(suma[i1]-suma[j1]=sumb[i2]-sumb[j2]\) 可以转换为
\(sumb[i2]-suma[i1]=sumb[j2]-suma[j1]\)。
找到第一个大于等于 \(suma[i]\) 的 \(sumb[j]\)，此时因为 \(b[j]\in[1,n]\)，故 \(sumb[j]-suma[i]\in[0,n)\)，值域为 \(n\) ，利用鸽巢定理就可以找到解。

P2371 [国家集训队]墨墨的等式
同余最短路入门题。
同余最短路用来求 \(n\) 个数 \(a_1,a_2\cdots\) 在一定范围内能凑出多少数。
我们任意找一个 \(a_x\) 记为 \(x\)。
把所有自然数按对 \(x\) 取模分为 \(x\) 类。
我们只要找到每一类中第一个能被凑出的数 \(p\)，那么该类中后面的数都可以通过 \(p+k\times x\) 凑出来。
考虑如何找到每类中第一个能被凑出的数，建一张有 \(x\) 个点的图，每个点代表每一类数，那么每个点 \(i\) 连一条有向边 \((i,(i+a[j])\bmod x)\)，边权为 \(a[j]\)，\(j\) 从 \(1\) 到 \(n\)，代表从一类数变成另一类数需要加上 \(a[j]\)（此处复杂度 \(O(n x)\)）。然后只要从 \(0\) 跑一遍最短路，此时的最短路就代表每类中第一个能被凑出的数了。
然后我们选择 \(x\) 时如果选择最小的 \(x\) 就可以让点数最小，从而降低时间复杂度。
一篇优质博

BZOJ3687 简单题
神仙题bitset不是很会用。。。
因为 \(\sum a\le 2\times 10^6\)，所以简单地设 \(dp[i]\) 表示 \(i\) 这个数出现了几次。
对于子集考虑依次添加每个数，就相当于在原本的子集中加上这个数，也就是 \(dp[i+x]=dp[i+x]\bigotimes dp[i]\)。这样是 \(O(n\sum a)\)。由于 dp 是01数组且这一添加操作可以直接看做01串的右移，所以使用bitset优化就可以做到 \(O(\frac{n\sum a}w)\)，可以通过本题。
另外，怀疑本题数据有锅，使用快读会在 test2 T掉。

P2473 [SCOI2008] 奖励关
\(1\le n\le 15\) 所以考虑状压dp，设 \(dp[i][j]\) 表示第 \(i\) 轮，状态为 \(j\) 时的期望最大得分。状态数 \(O(2^n k)\)
正推不好想，容易想到倒推，枚举这次的宝物 \(k\)，根据 \(j\) 判断能不能选。
如果能选，那么 \(dp[i][j]+=\max(dp[i+1][j|(1<<(k-1))]+p[k],dp[i+1][j])/n\)；
如果不能选，那么 \(dp[i][j]+=dp[i+1][j]/n\)。
然后随便d一下就好了。

P4550 收集邮票

1.29

[P7520 [省选联考 2021 A 卷] 支配]

P7515 [省选联考 2021 A 卷] 矩阵游戏
值域限制下难以构造，考虑先随便构造一个再把它调整到合法状态。
注意到对某一列或某一行交替地加减 \(1\) 不会影响构造，所以我们设某一行交替加减 \(l[i]\)，某一列交替加减 \(c[i]\)。
于是有\(0\le a[i][j]\pm l[i]\pm c[j]\le 1\times 10^6\)，发现现在的 \(a[i][j]\) 其实已知，于是 \(-a[i][j]\le \pm l[i]\pm c[j]\le 1\times 10^6-a[i][j]\)，发现很像差分约束，但是可能会有 \(l\) 和 \(c\) 同号这不符合差分约束的形式。此时我们只要每行交替减加减加和加减加减，每列交替加减加减和减加减加，就可以保证 \(l\) 和 \(c\) 异号了。然后上差分约束板子就可以了。
注意 spfa 判负环时应统计被松弛次数是否大于总点数而不是进队次数。

P7517 [省选联考 2021 B 卷] 数对

简单题，感觉比今年noipT1还要简单。