这场CF打完心态有点崩…记录一下

(T2卡一小时 , T3 FST了解一下?)

先扔个比赛链接

T1不管

T2

Description

T2题意是给两个长度为 $n-1(n\leq 10^5)$ 的数列 $a,b$ ,值域 $0$~$3$

要求构造一个数列 $t$ 满足:

  • $a[i]=t[i]|t[i+1]$

  • $b[i]=t[i]\&t[i+1]$

若无解则输出$NO$

Solution

其实是一个挺简单的DP,注意值域只有两位二进制

$f[i][j]$ 表示 $t$ 数组填到第 $i$ 个且 $t_i=j$ 是否可行,然后在转移的时候记录是从哪里转移过来的就好了。输出时从最后一位倒着找回去。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
using namespace std;
int n,a[101000],b[101000],f[101000][10],fa[101000][10];
int ans[101000],res;
int main(int argc, char const *argv[]){
scanf("%d",&n);
for(int i=1;i<n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++) scanf("%d",&b[i]);
f[1][0]=f[1][1]=f[1][2]=f[1][3]=1;
for(int i=2;i<=n;i++)
for(int j=0;j<=3;j++)
for(int k=0;k<=3;k++)
if((a[i-1]==(j|k))&&(b[i-1]==(j&k)))
if(f[i-1][k]) f[i][j]=1,fa[i][j]=k;
res=0;
while(!f[n][res]&&res<=3) res++;
if(res==4) return puts("NO"),0;
puts("YES");
for(int i=n;i;i--)
ans[i]=res,res=fa[i][res];
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}

T3

Description

给两个数 $a,b\le 10^9$ 要求构造两个数列,使其和分别小于等于 $a,b$ 且数列中的数两两不相同

使两数列长度和最大,给出方案

Solution

贪心一下,先将 $a+b$ 拆成 $1+2+…+x$ + $y(x<y)$的形式

后用贪心地思想先将 $a$ 填完,再用剩下的数去填 $b$

Attention:$b$ 是有可能填不满的!!

代码写的太乱,就不贴了

T4

Description

给出一个 $n·n(n\leq 2000)$ 的字母矩阵,从 $(1,1)$ 走到 $(n,n)$ ,只能向下或向右走,有 $k$ 次机会将一个格子上的字母改成 'a'

求一种走法使得路径所经过的字母串的字典序最小

Input

4 2
abcd
bcde
bcad
bcde
5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw

Output

aaabcde
aaaepfafw

Solution

首先因为是字典序,所以改前面比改后面优秀,先DP求出所有能在改 $k$ 次及以内走到的点使得路径上全部都是'a'

如下图,黑色的格子是改 $k$ 次能走到的最远的点

1
1

显然,在红线以前的格子一定不是最优的,所以我们从红线上的黑格子开始平行于对角线向 $(n,n)$ 推进,以到当前斜线为止答案最优的点向右和下拓展,打上标记,然后从下一条斜线打了标记的点中选出字母最小的点继续进行标记。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,K,line,f[2010][2010];
int able[2010][2010]; //标记前面的路径是最优的
char g[2010][2010];
string ans;
int main(int argc, char const *argv[]){
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++)
scanf("%s",g[i]+1);
memset(f,0x3f,sizeof f);
f[0][1]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i-1][j],f[i][j-1])+(g[i][j]!='a');
//求出到每个点的最小更改次数
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(f[i][j]<=K){
line=max(i+j-1,line); //找到最远的一条斜线
able[i+1][j]=able[i][j+1]=1;
}
for(int i=1;i<=line;i++) ans+='a';
able[1][1]=1;
line++;
int nowmin;
while(line<n*2){
nowmin=1e9;
for(int i=1,j;i<=n;i++){
j=line-i+1;
if(j<1||j>n) continue;
if(able[i][j]) nowmin=min(nowmin,(int)g[i][j]);
}
ans+=nowmin; //找出每条斜线中的最小合法字母,计入答案
for(int i=1,j;i<=n;i++){
j=line-i+1;
if(j<0||j>n) continue;
if(nowmin==g[i][j]&&able[i][j]) able[i+1][j]=able[i][j+1]=1;
}
line++;
}
cout<<ans;
return 0;
}

写在最后

T2刚看到没注意到值域只有两位二进制想了半天,看到了之后又想着贪心构造,一点都没想着要DP,菜菜菜

T3听同学讲的题意,不知道拆出来数列和可以不等于那个数,就挂了。。

T4最后二十多分钟其实应该要码的出来的,还是挂了,心有点乱

心态真的是个大问题,见的题也少,T2显然的DP愣是没看出来,后面心态就崩了

总而言之,菜是原罪