Div.2 A
Statement
给定 (n) 个正整数 (a_{1,2,...,n})，要求构造出 (n+1) 个长度不超过 (200) 的字符串 (s_1,s_2,...,s_{n+1})，使得 (forall 1 leq i leq n)，(s_i) 和 (s_{i+1}) 的最长公共前缀长度为 (a_i)。
Limits
多组数据，数据组数 (leq 100)，(1 leq n leq 100,0 leq a_i leq 50, sum n leq 100)
Solution
考虑构造出足够长的 (s_1)，然后对于每一个 (1 < i leq n+1)，将 (s_i) 的前 (a_i) 位构造得和 (s_{i-1}) 相同，后 (|s_{i-1}|- a_i) 位和 (s_{i-1}) 不同。
Code
# include <bits/stdc++.h>
# define rr
const int N=110,INF=0x3f3f3f3f;
char s[N];
int n;
int a[N];
char temp[N];
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
int main(void){
int T=read();
while(T--){
n=read();
for(rr int i=1;i<=n;++i){
a[i]=read();
}
a[n+1]=0;
for(rr int i=1;i<=100;++i){
s[i]='a',putchar('a');
}
puts("");
for(rr int i=1;i<=n;++i){
for(rr int j=1;j<=100;++j){
if(j<=a[i]){
temp[j]=s[j];
}else{
temp[j]=(s[j]=='z')?('x'):'z';
}
putchar(temp[j]);
}
puts("");
for(rr int j=1;j<=100;++j){
s[j]=temp[j];
}
}
}
return 0;
}
Div.2 B (Hard Version)
Statement
Koa 要从海岸游到岛上。海岸的位置是 (0)，岛的位置是 (n+1)。
除了海岸和岛上，在 ([1,n]) 之间的位置 (i) 都有一个深度 (d_i)。海里有潮汐，具体来讲，给定值 (k)，则有下标从 (0) 开始的数组 (p=[0,1,2,...,k-1,k,k-1,...,1])。在时间 (t)，海里的潮汐高度为 (p_{t mod 2k})。
在任意时间，如果 Koa 在位置 (x)，可以选择下一个时间停留位置 (x)，或游到位置 (x+1)。
Koa 能在时间 (t) 到达位置 (i) 当且仅当时间 (t) 的潮汐高度与位置 (i) 的深度之和不超过一个给定的值 (l)，即：(p_{t mod 2k}+d_i leq l)，否则她会溺水。海岸和岛上是安全的，不会受潮汐影响，所以在任何时间停留在那里都不会溺水。Koa 在游泳的时候不会受潮汐的影响（不会溺水）。
求出 Koa 是否能安全地到达岛上。
Limits
多组数据，数据组数 (t leq 10^4)，(1 leq n leq 3cdot 10^5,1 leq d_i,k,lleq 10^9)
Solution
如果存在 (d_i>l)，那么 Koa 一定会溺水，所以她无法到达岛上。这种情况可以通过简单的代码进行判断，在接下来，我们假设 (d_i leq l)。
我们定义一个位置是安全的，当且仅当任何时间停留在该位置都不会溺水，否则该位置是不安全的。根据定义，(0)，(d_i+k leq l) 的 (i) 以及 (n+1) 是安全的。
Koa 可以采用以下策略前进：
- 如果她在时间 (t) 处在一个不安全的位置 (x)，那么她需要在不溺水的前提下尽快到达 (x+1)。如果不可能存在这样的时间，那么她无法到达岛上。
- 如果她在时间 (t) 处在一个安全的位置 (x)，那么她需要等待一个时间 (t_0 geq t)，使得该时间潮汐高度在下降，且能安全地到达 (x+1)。在此前提下，使潮汐尽可能地高。
该策略可以证明。
首先，让我们证明，如果可以从一个安全位置 (i) 到达下一个安全位置 (j)，那么在她从 (i) 到 (j) 的过程中，潮汐高度至多下降一次。如果潮汐从 Koa 到达一个不安全的位置 (m(i+1<m<j)) 时开始再次开始下降，那么潮汐在上一秒高度为 (k)。如果 Koa 在上一秒所处的位置 (b) 时没有溺水，那么有 (p_{b}+k leq l)，(b) 将是一个安全的位置，于是这和定义矛盾。
根据上面的结论，显然在潮汐尽可能地高且在下降时从 (i) 出发最优。如果因为出发过早，当前潮汐过高而导致无法到达 (m (i<m<j))，那么我们可以在原地等待潮汐高度下降。但如果出发太晚，潮汐高度会提前开始上升，这会使到达后面的位置变得困难。
例如，(n=2,k=2,l=3,d=[2,3])。最优策略是在潮汐高度为 (2) 时离开位置 (0)，这样到达位置 (1) 时潮汐高度为 (1)。然而并不可以在潮汐高度为 (1) 时离开位置 (0) —— 这样会使到达位置 (1) 时潮汐高度提前开始上升，无法到达位置 (2)。
Code
# include <bits/stdc++.h>
# define rr
# define int long long
const int N=300010,INF=0x3f3f3f3f;
int n,k,l;
int d[N];
std::vector <int> safe;
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
signed main(void){
int T=read();
while(T--){
n=read(),k=read(),l=read();
safe.resize(0);
safe.push_back(0);
bool flag=false;
for(rr int i=1;i<=n;++i){
d[i]=read();
if(d[i]>l){
flag=true;
}else if(d[i]+k<=l){
safe.push_back(i);
}
}
if(flag){
puts("No");
goto End;
}
safe.push_back(n+1);
d[0]=d[n+1]=0;
for(rr int i=0;i<(int)safe.size()-1;++i){
int now=k,down; // 离开 i 时的高度尽可能地高
down=(now>0);
for(rr int j=safe[i];j<safe[i+1];++j){
if(j+1==n+1){ // 安全位置不受影响
puts("Yes");
goto End;
}else if(j+1==safe[i+1]){
break;
}else if(!down){ // 如果已经在上升 便不可能等待下降
if(now+1+d[j+1]>l){
puts("No");
goto End;
}
else
++now;
}else{
now=std::min(now-1,l-d[j+1]); // 等待最早能通过的时间
if(!now){//到达 0 便开始上升
down=0;
}
}
}
}
End:;
}
return 0;
}
Div.1 A
Statement
给定字符串 (A,B)，每次可以选择若干个满足 (A_{p_1},A_{p_2},...,A_{p_k}) 相等的 (p_1,p_2,...,p_n)