- [AGC007A] Shik and Stone
有一个纵 $ H $ 行，横 $ W $ 列的格子状棋盘。开始时，棋盘左上角的格子有一个马（不是象棋意义的马）。Shik 将会操纵它上下左右移动，从而到达右下角的格子。此时，马能够经过同一个格子多次（含左上角和右下角的格子）。
给出 $ H $ 行字符串，如果第 $ i $ 行第 $ j $ 列的字符为 ' # ' ，则表示马在移动过程中至少通过了此格一次（左上角和右下角的格子一定会通过至少一次）。当 $ a_{i,j} $ 为 ' . ' 时，表示马在移动过程中并没有经过此格。
请判断：马是否可能每次移动都向下或向右。
签到题。
- [AGC007B] Construct Sequences
给你一段长度为n的数列\(P_1\),\(P_2\),,\(P_n\).
让你构造两个新的数列a与b,且满足：
- 1<\(a_i\),\(b_i\)<10^9
- \(a_1\)<\(a_2\)<…<\(a_n\)
- \(b_1\)>\(b_2\)>…>\(b_n\)
- \(a_{p_1}\)+\(b_{p_1}\)<\(a_{p_2}\)+\(b_{p_2}\)<…<\(a_{p_n}\)+\(b_{p_n}\)
求出满足条件的数列a,b；
考虑经典构造思路：先使其满足其中一个条件且另一个条件全部相等，再微调构造。
于是将 \(a_i\) 赋值为 \(n \times i\) ，\(b_i\) 赋值为 \(n\times (n-i)\)
微调则将 \(p_i\) 的 \(a\) 加上 \(i-1\)。
- [AGC007C] Pushing Balls
在一条直线上有 \(N\) 个球和 \(N+1\) 个洞。记每个球与相邻的洞的距离为 \(d_i \left( 1 \leq i \leq 2 \times N \right)\) 且 \(d_{i + 1} - d_i = x\)
要将 N 个球均推入洞中。当球滚过洞时，如果洞中还没有球，球将掉入洞中。否则，球将继续滚动。
每次会随机选择任一未进洞的球，并随机选择一个方向推球。
给定 \(N, d_1, x\) ，求出在不发生碰撞的情况下，每个球移动距离的期望（误差小于 \(10^{-9}\) ）
神秘题，赛时看到就直接跳了。
有严格推导和打表的做法，打表直接发现每次的期望都构成等差数列可以直接解决。
严格推导则是算出每一段下一次的期望是多少，这里不证了。
- [AGC007D] Shik and Game
Shik君在玩一个游戏。
初始时他在数轴的\(0\)位置，出口在\(E\)位置，并且数轴上还有\(n\)只小熊，第\(i\)只小熊在\(x_i\)位置。
Shik君拿着\(n\)块糖果出发，每走一个单位长度要花费一秒。到一个小熊的位置时，他可以送给这个小熊一块糖果，这个过程不花时间。小熊收到糖果后，\(T\)秒以后会在它所在的位置产生一个金币。
Shik君想知道，他从出发到收集了所有金币抵达出口，最少要花费多长时间。
简单队列优化DP，赛时读错题认为T不同于是不可做。
- [AGC007E] Shik and Travel
题意都没看懂，长大后再学习。
- [AGC007F] Shik and Copying String
Shikk的工作是复制。有一天，Shikk从他的上司那里拿到了一个由小写英文字母组成的长度为\(N\)的字符串\(S_{0}\)（假设这天是第\(0\)天）。这之后第\(i\)天的工作是把\(S_{i-1}\)复制到\(S_{i}\)。下文中的\(S_{i}[j]\)表示字符串\(S_{i}\)的第\(j\)个字母。
Shikk还不怎么习惯这个工作。每天，当Shikk从第一个字母开始按顺序复制字符串时，他有可能会写下和刚刚写下的字母相同的字母，而不是本来应该写下的字母。也就是说，\(S_{i}[j]\)要么与\(S_{i-1}[j]\)相同，要么与\(S_{i}[j-1]\)相同。（特别地，字符串开头的字母不可能出错。也就是说，\(S_{i}[1]\)必然与\(S_{i-1}[1]\)相同。）
输入两个字符串\(S_{0}\)和\(T\)，请求出使得\(S_{i}\)有可能与\(T\)相同的最小的整数\(i\)。如果这样的\(i\)不存在，请输出“-1”。
考虑将字符往后推的表建出来。
我们要贪心地去填表，即每次都要尽量靠右填。同时发现每个拐点都会向左下移动一格，于是用队列维护每个拐点。
答案即每一时间中 （队列长度 + 1）的最大值。