暑假集训CSP提高模拟1
唐完乐！
-
T1 Start
大模拟，之前还做过。
结果照样挂 90pts细节较多，比较坑的是除法要向下取整，而
/是向 \(0\) 取整。 -
T2 mine
这 \(DP\) 已经简单到不能在简单了。
设 \(dp_{i,0/1/2}\) 表示到第 \(i\) 位，\(0\) 后面不放雷，\(1\) 后面放雷，\(2\) 自己是雷。
转移显然。
-
小凯的疑惑
因为能被表示的数一定是 \(\gcd(x,y)\) 的倍数。
当 \(x,y\) 不互质时，有无数多个。
当 \(x,y\) 互质时，简单分析剩余系得 \(\ge xy-x-y\) 的数一定能被表示，这里为方便用 \(xy\) 即可。
考虑每举有几个 \(y\)，答案显然是 \(xy - \sum\limits_{i=0}^{x-1}( \left\lfloor \frac{xy-iy}{x} \right\rfloor + 1) + 1\)，最后加一是因为 \(0\) 被多减了。
其实 \(10^8\) 已经能过了，但还可以化简。
\[\begin{aligned} xy - \sum_{i=0}^{x-1}( \left\lfloor \frac{xy-iy}{x} \right\rfloor + 1) + 1 &= xy - \sum_{i=0}^{x-1} (y + 1 - \left\lceil \frac{iy}{x} \right\rceil) + 1\\ &= xy - x(y+1) + 1 + \sum_{i=0}^{x-1} \left\lceil \frac{iy}{x} \right\rceil\\ \end{aligned}\]设 \(t=\sum\limits_{i=0}^{x-1} \left\lceil \frac{iy}{x} \right\rceil\) 则
\[xt=\sum_{i=0}^{x-1} iy + \sum_{i=0}^{x-1} (x-(iy\bmod x)) \]考虑 \(x,y\) 互质，所以 \(\sum_{i=0}^{x-1} (iy\bmod x)\) 恰好是 \(\sum_{i=0}^{x-1} i\)，所以
\[xt=\sum_{i=0}^{x-1} iy + \sum_{i=0}^{x-1} (x-(iy\bmod x))=\frac{x(x-1)}{2}y+\frac{x(x+1)}{2} \]\[t=\frac{y(x-1)}{2}+\frac{x+1}{2} \]所以原式：
\[xy - x(y+1) + 1 + \frac{y(x-1)}{2}+\frac{x+1}{2}=\frac{xy-x-y+1}{2} \] -
春节十二响
从上往下不好做，考虑从下往上。
显然贪心，子树中从大到小匹配，取 \(\max\) 即可。
可以启发式合并维护。