九月补题计划

暑假模拟赛（尤其是后半段题目难度上升）改题效率很低很低，隧导致咕了很多题没改，现在准备把暑假模拟赛的题只要是赛时没 AC 的再重新做一做写写题解，所以开启这个“九月补题计划”，简称“9B 计划”。

（共 27 场模拟赛）
目前进度：1 / 27。

CSP 提高 1

9.10

A.start

200 行的大模拟，没什么看头，代码就不重打一遍了。

B.mine

简单 dp？！但还是调了近 1 个小时。

定义 \(f_{i,0/1/2}\) 表示第 \(i\) 个格子要求后面有 0 个雷、有 1 个雷、当前格子是雷。进行状态转移即可。

C.小凯的疑惑

原题 NOIP2017

推点东西（

• 结论 1：若 \(x,y\) 不互质，那么不能用 \(ax+by\) 表示的一定有无限个。

  证明：反证法好证！\(x,y\) 不互质的时候，设 \(gcd(x,y) = g\)，可知 \(ax+by=kg,k \in \mathbb{N^+}\) ，所以能用 \(ax+by\) 表示的一定是 \(g\) 的倍数，那么不是 \(g\) 的倍数的话便不能用 \(ax+by\) 表示。

• 结论 2：保证 \(x,y\) 互质时，不能用 \(ax+by\) 表示的最大的数是 \(xy-x-y\)，不能用其表示的个数有 $\frac{(x-1) (y-1)}{2} $。

  证明不会，咕！背结论就行。

updated on 9.11

会了已经！知乎证的很详细，在机房加载不出图片的话爬一爬就好了。

写一下结论 2 的证明：

设 \(S=\) {\(s|s\not=ax+by\) }，保证 \(a\ge0,b\ge0,gcd(x,y)=1\)

设 \(p,q\in [0, y-1]\)，可证 \((px\%y)\) 构成 \(y\) 的完系，即若 \(p\not= q\)，有 \((qx\%y)\not= (qx\%y)\)。

证明：反证法。假设 \((px\%y)=(qx\%y)\)，那么设 \(px = k_1 y + u, qx = k_2y+u\)，可得 \(k_1-k_2=(q-p) \frac{x}{y}\)，由于 \(x,y\) 互质，那么 \(\frac{x}{y}\) 不为整数，且 \(q-p\) 一定不为 \(y\) 的倍数，那么上述柿子右边一定不是整数，但左边却是整数，矛盾，假设不成立。

那么设 \(m,n\in [0, y-1]\)，\(n\) 为整数的情况下，\(z=mx+ny\) 可以表示出任意整数。

可知在 \(n < 0\) 且 \(z \ge 0\) 的情况下满足 \(z\in S\)。

我们先求 \(z=mx+ny, n<0\) 的最大值，因为根据 \(m,n\) 的取值范围，可求得 \(z\) 最大为 \((y-1)\times x+(-1)\times y=xy-x-y\)，最大的不能用 \(ax+by\) 表示的数为 \(xy-x-y\) 得证。

我们设这个最大值为 \(G\)，\(S\) 集合的个数为 \(c\)，区间 \([0, G]\) 中不属于 \(S\) 的个数为 \(d\)。

已经知道，\([0,G]\) 中的每个整数都可以表示为 \(mx+ny\ (m\in [0,y-1])\)。

• 对于 \(S\) 中的每个元素 \(mx+ny\) 都有：\(G-(mx+ny) = (y-1-m)x+(-n-1)y\) 属于 \([0,G]\) 区间且不是 \(S\) 的元素。

那么显然有 \(c=d\)，所以 \([0,G]\) 中属于 \(S\) 集合的数有 \(\frac {(G+1)}2 = \frac{(x-1) (y-1)} 2\) 个，即为所求。

D.春节十二响

启发式合并，不难。

• 从 \(x\) 的每个子树各取一个点构成一个段，一定合法。

• 在合法的条件下，最大点与次大点存进一个段，一定最优。

对于每个点维护一个优先队列存以该点为根的子树中的所有段，每个段只维护其大小即包含的子程序所需内存的最大值即可。从下向上递归合并，把所有子树的队列都合并到其父亲节点的队列上。

考虑如何合并：每次从 \(x\) 的所有子树的队列中取最大值构成 \(x\) 的一个新段，那么这个新段的大小就是这些最大值中的最大值，存进 \(x\) 的队列中。最后把多出来的单独成段 和 \(x\) 自己单独成段 都存进去，便构成了 \(x\) 的队列。