- [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)的最大值。