正睿省选模拟赛

不难发现这个东西可以分治 FFT 优化，复杂度变成了 \(\mathcal O(n\log^2n)\)
对于 ? 的情况，直接乘上一个组合数就可以了

B. 【2022省选十连测 Day 1】做菜

算法：dp
大毒瘤题
假设我们确定了顾客和 \(a\)，那么显然是应该按 \(b\) 从大到小来做
最后的答案肯定是一个 \(b_i\) 加上所有 \(b_i\) 比他大的 \(a_i\)
因此可以按 \(b_i\) 从小到大排序，用一个 dp 来解决这个东西
\(f_i=\max(f_{i-1},b_i)+a_i\)
这样的话，如果我们知道 \(a_i\)，这个东西同样是可以在 \(\mathcal O(n^2)\) 的时间内去求的
\(f_{i,j}=\min(f_{i-1,j},\max(f_{i-1,j-1},b_i)+a_i)\)
考虑到某一时刻如果 \(f_{i,j}，那么后面 \(f_{...,j}\) 是不会变化的
对于还有可能变化的部分，我们考虑他的差分 \(d_i\)
不难发现这个差分一直是单增的，即 \(f\) 是凸的
这样每次进行一个关于 \(a_i\) 的转移的时候相当于是在差分中插入了一项 \(a_i\)
同时我们发现 \(\Delta=b_i-b_{i-1}\),优先队列中前缀和 \(\leq \Delta\) 的项马上就变成 \( 的了
所以一次操作相当于先不停的删开头元素直到队列被删空或者 \(\Delta\) 被删完，然后再插入一个 \(a_i\)
做完之后第 \(i\) 个被弹出的就是 \(f_{...,j}\) 的最终答案
在知道 \(a_i\) 的情况下这个做法可以用一个优先队列维护 \(\mathcal O(n\log n)\) 解决
考虑对于所有的 \(a\) 的情况

我们用 \(f[i][j][l][r]\) 表示在最小花费 \(l\) 前面的有 \(i\) 个，现在优先队列在 \(x\) 前面的和为 \(j\) （包含 \(x\)），答案为 \(l\)，比 \(l\) 大的最小的是 \(r\)
首先我们进行删的操作

• \(\Delta\leq j-l,\to f[i][j-\Delta][l][r]\)
• \(j-l<\Delta
• \(j\leq \Delta\leq j+r,\to f[i][0][0][j+r-\Delta]\)
• \(j\leq \Delta \wedge r=\infty,\to f[i][0][0][\infty]\)
  这里在 \(\Delta>j+r\) 的时候不需要再转移的原因是当 \(l\) 被删掉之后我们就不再关心这种情况的答案了
  在后两类的时候还要顺便统计一下答案，后面的可以任选乘上一个 \(V\) 的幂即可
  然后我们进行选当前这个 \(a_x=p\)
• \(p\leq r,\to f[i+1][j+p][\max(p,l)][r]\)
• \(p>l,\to f[i][j][l][\min(p,r)]\)
  最后再统计一下答案即可
  总体复杂度是 \(\mathcal O(n^3V^4)\)，总之就是能过。。。

C. 【2022省选十连测 Day 1】树上路径

算法：dp 随机化
想到了随机化没想到 \(k=4\) 就不太懂。。。
\(k=3\) 的 \(\mathcal O(n^2)\) 非常简单，\(f[i][0/1/2]\) 表示 \(i\) 现在往上延伸多少的时候的最大价值
然后再一个点一次枚举子树，用 \(g[i]\) 表示现在子树中 0 和 1 的个数的差是多少
转移就是 \(\mathcal O(n^2)\) 的
对于 \(k=4\)，就是 0 和 2 的个数的差，和 1 的个数的奇偶性
发现我们最后只关心 \(g\) 的 \(-1,0,1\) 三个位置的值，所以我们把每个点的出边 random_shuffle 一下，每次用到的最大值就不算太多，所以这个时候取上界是 1000左右就差不多了