暑假集訓CSP提高模擬1

唐完樂！

1. T1 Start

   大模擬，之前還做過。結果照樣掛 90pts

   細節較多，比較坑的是除法要向下取整，而 / 是向 \(0\) 取整。

2. T2 mine

   這 \(DP\) 已經簡單到不能在簡單了。

   設 \(dp_{i,0/1/2}\) 表示到第 \(i\) 位，\(0\) 后面不放雷，\(1\) 后面放雷，\(2\) 自己是雷。

   轉移顯然。

3. 小凱的疑惑

   因為能被表示的數一定是 \(\gcd(x,y)\) 的倍數。

   當 \(x,y\) 不互質時，有無數多個。

   當 \(x,y\) 互質時，簡單分析剩余系得 \(> 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\limits_{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} \]

4. 春節十二響

   從上往下不好做，考慮從下往上。

   顯然貪心，子樹中從大到小匹配，取 \(\max\) 即可。

   可以啟發式合并維護。