Div. 2 A
Statement
求 \(a,b\) 两数列的最短公共子序列。
如果存在，输出 YES，第二行输出其长度以及该子序列；如果不存在，输出 NO。
\(|a|,|b| \leq 1000\)
Solution
如果存在，显然长度为 \(1\)。枚举即可。
Code
# include <bits/stdc++.h>
# define rr
const int N=1010,INF=0x3f3f3f3f;
int tota[N],totb[N];
int n,m;
int a[N],b[N];
int T;
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){
T=read();
while(T--){
memset(tota,0,sizeof(tota)),memset(totb,0,sizeof(totb));
n=read(),m=read();
for(rr int i=1;i<=n;++i){
a[i]=read(),++tota[a[i]];
}
for(rr int i=1;i<=m;++i){
b[i]=read(),++totb[b[i]];
}
int ans=-1;
for(rr int i=1;i<=1000;++i){
if(tota[i]&&totb[i]){
ans=i;
break;
}
}
if(~ans){
printf("YES\n1 %d\n",ans);
}else{
printf("NO\n");
}
}
return 0;
}
Div.2 B
Statement
给定 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 个。先后手轮流取，每次取编号最小非空堆，至少取一个。问最优操作下谁必胜。
\(n \leq 100000,a_i \leq 10^9\)
Solution
当 \(a_1>1\) 的时候，如果拿完第一堆必胜，那么先手会这么做；如果拿完第一堆必败，那么先手会留下一个，迫使后手拿完第一堆。综上，当 \(a_1 >1\) 时，先手必胜。
但如果前缀中有奇数个 \(1\)，那么胜负就会反转：后手会操作第一个 \(>1\) 的堆，按照上面的策略让自己胜利。
这样有一个特殊情况：所有的堆都只有一个石子。这样判断 \(n\) 的奇偶性即可。
Code
# include <bits/stdc++.h>
# define rr
const int N=100010,INF=0x3f3f3f3f;
int n;
int a[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();
bool flag=true;
int tot=0;
for(rr int i=1;i<=n;++i){
a[i]=read();
flag&=(a[i]==1);
if(flag){
++tot;
}
}
if(flag){
puts((n%2)?"First":"Second");
}else{
puts((tot%2)?"Second":"First");
}
}
return 0;
}
Div. 1 A (Hard Version)
Statement
给定长为 \(n\) 的 \(01\) 串 \(a,b\)。每次可以选择 \(a\) 的一个前缀，将其取反（\(1\) 变 \(0\)，\(0\) 变 \(1\)），然后该前缀翻转。
例如，\(a=001011\)，选择前缀为 \(3\) 的前缀操作，\(a\) 变为 \(011011\)。然后选择整个字符串操作，\(a\) 变成 \(001001\)。
使用不超过 \(2n\) 次操作将 \(a\) 变成 \(b\)。
Solution
前 \(n\) 次操作，考虑将 \(a\) 变成全 \(0/1\)。具体来讲，如果 \(a\) 具有相同颜色的最长前缀颜色长度为 \(i(i<n)\)，那么可以使用操作将该前缀的颜色取反，得到一个长度至少为 \(i+1\) 的具有相同颜色的最长前缀。
例如，\(a=01101\)。
- 将长度为 \(1\) 的前缀颜色取反，\(a=11101\)。
- 将长度为 \(3\) 的前缀颜色取反，\(a=00001\)。
- 将长度为 \(4\) 的前缀颜色取反，\(a=11111\)。
因为每取反一次，具有相同颜色的最长前缀的长度就增加 \(1\)，所以至多 \(n\) 次就可以将 \(a\) 变成全 \(0/1\)。
后 \(n\) 次操作，将 \(a\) 变成 \(b\)。例如，\(a=111111,b=011010\)。我们从后往前操作 \(b\) 中每一个具有相同颜色的连续段。
- \(b_6=0\)，于是我们将 \(a\) 全部取反，\(a=000000\)。
- \(b_5=1\)，将长度为 \(5\) 的前缀颜色取反，\(a=111110\)。
- \(b_4=0\)，将长度为 \(4\) 的前缀颜色取反，\(a=000010\)。
- \(b_{2,3}=1\)，将长度为 \(3\) 的前缀颜色取反，\(a=111010\).
- \(b_1=0\)，将长度为 \(1\) 的前缀颜色取反，\(a=011010\)。
可以想象在一个颜色板上不断地涂上新颜色的操作。
由于 \(b\) 中至多有 \(n\) 个不同的颜色段，所以至多 \(n\) 次就可以将 \(a\) 变成 \(b\)。
# include <bits/stdc++.h>
# define rr
const int N=200010,INF=0x3f3f3f3f;
char a[N],b[N];
int ans[N],cnt;
int 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();
scanf("%s",a+1);
scanf("%s",b+1);
char now=a[1];
int cnt=0;
for(rr int i=2;i<=n;++i){
if(a[i]!=now){
ans[++cnt]=i-1,now=a[i];
}
}
char suv=b[n];
int st=n;
for(rr int i=n-1;i;--i){
if(suv!=b[i]){
if(now!=suv){
ans[++cnt]=st;
now=suv;
}
suv=b[i];
st=i;
}
}
if(b[1]!=now){
ans[++cnt]=st;
}
printf("%d ",cnt);
for(rr int i=1;i<=cnt;++i){
printf("%d ",ans[i]);
}
puts("");
}
return 0;
}
Div.1 B
Statement
对于两个数组 \(a,b\)，定义 \(\text{merge}(a,b)\) 。
给定长为 \(2n\) 的排列 \(p\)，问是否存在长为 \(n\) 的 \(a,b\) 使得 \(\text{merge}(a,b)=p\)。
\(n \leq 2000\)
Solution
将 \(p\) 分段。设 \(p_{2n+1}=\infty\)，将 \(p_1,p_2,...,p_k(p_1=\max\{p_1,p_2,...,p_k\},p_{k+1}>p_1)\) 分在一起，然后从 \(p\) 中去除它们。
容易发现，每一段的数必须分在一个数组中。如果不这么做，一定会导致 \(\text{merge}(a,b)\) 的结果中，每一段中第一个数出现的位置比后面的数晚，因为第一个数是这一段的最大值。
求出每一段的长度，然后可以使用简单的动态规划来判断是否有若干段的长度和正好为 \(n\)。如果存在，那么就有至少一组合法解。
Code
# include <bits/stdc++.h>
# define rr
const int N=5010,INF=0x3f3f3f3f;
int T;
int val[N],dp[N];
int n;
int g[N],m;
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){
T=read();
while(T--){
n=read();
for(rr int i=1;i<=2*n;++i){
val[i]=read();
}
m=0;
g[++m]=1;
int now=val[1];
for(rr int i=2;i<=2*n;++i){
if(now>val[i]){
++g[m];
}else{
now=val[i],g[++m]=1;
}
}
memset(dp,0,sizeof(dp)),dp[0]=1;
for(rr int i=1;i<=m;++i){
for(rr int j=n;j>=g[i];--j){
dp[j]|=dp[j-g[i]];
}
}
puts(dp[n]?"YES":"NO");
}
return 0;
}