A：http://codeforces.com/contest/1382/problem/A
题意：
找出最短数组c[]，保证它同时是a[]和b[]的子序列
解析：
如果a[]和b[]存在相同数字，直接输出它
否则不存在
#include <bits/stdc++.h> #define ll long long using namespace std; const int MAX = 2e6+100; const int mod = 998244353; const double PI = 3.141592654; map <int , int > mm; int main (void) { int T; cin>>T; while(T--) { int x,y; cin>>x>>y; mm.clear(); for(int i=0; i<x; i++) { int t; cin>>t; mm[t] = 1; } int cnt = 0; int flag = 0; for(int i=0; i<y; i++) { int t; cin>>t; if(mm[t] != 0) { flag = 1; cnt = t; } } if(flag == 1) { cout<<"YES"<<endl; cout<<1<<" "<<cnt<<endl; } if(flag == 0) cout<<"NO"<<endl; } return 0; }
B：http://codeforces.com/contest/1382/problem/B
题意：
每堆石头数：a1~an
操作：
两人依次从最左边非0堆拿取任意石子
不能操作的人输掉
解析：
假设所有堆的石子数都>1，那么先手可以对结果进行任意的操控(具体他怎么拿才能赢不需要管)，通过对某个堆取完还是取到1进行结果的操控。
如果存在石子数==1的情况，
假设：1,1,1......1,a,b,c..... a>1
前面的1中，每次操作只能取1，所以先手和后手依次取。轮到谁拿a，谁就赢了，原理同上，只要某个堆>1，就可以对结果进行任意操控。
#include<iostream> #include<cstring> #include<string.h> #include<cmath> #include<map> using namespace std; typedef long long ll; const int maxn=1e5+10; const int mod=1e9+7; ll a[maxn]; int b[maxn]; int qk(ll a, ll b,ll c) { ll ans=1; a=a%c; while(b) { if(b%2==1) ans=(ans*a)%c; b=b/2; a=(a*a)%c; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n,x; int cnt1=0,cnt2=0; cin>>n; int k; int ok1=0; int ok2=0; for(int i=1;i<=n;i++) { cin>>x; if(x==1) { ok1=1; } if(x!=1&&!ok2) { k=i; ok2=1; } } if(!ok2) //全1 { if(n%2!=0) cout<<"First"<<endl; else cout<<"Second"<<endl;continue; } if(!ok1) //全>1 { cout<<"First"<<endl;continue; } if(k%2!=0) cout<<"First"<<endl; else cout<<"Second"<<endl; } }
C1：http://codeforces.com/contest/1382/problem/C1
题意：
01串s1,s2
操作s1：
每次找到x，前x进行0/1互换，然后倒置。
求s1==s2的操作数和过程（任意符合的结果）
解析：
k<=3n，从这里入手，每个字符操作3次
对于s1[x]!=s2[x]
先将前x进行0/1互换，倒置，再对s1[1]进行0/1互换，再对前x操作，可以使得s1[x]==s2[x]而且不影响之前的匹配。
#include<iostream> #include<cstring> #include<string.h> #include<cmath> #include<map> using namespace std; typedef long long ll; const int maxn=1e3+10; const int mod=1e9+7; char s1[maxn],s2[maxn]; ll a[maxn]; int b[maxn]; int qk(ll a, ll b,ll c) { ll ans=1; a=a%c; while(b) { if(b%2==1) ans=(ans*a)%c; b=b/2; a=(a*a)%c; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { // string s1,s2; int n; cin>>n; int tot=0; scanf("%s",s1+1); scanf("%s",s2+1); for(int i=1;i<=n;i++) { if(s1[i]!=s2[i]) { b[tot++]=i; b[tot++]=1; b[tot++]=i; } } cout<<tot<<" "; for(int i=0;i<tot;i++) cout<<b[i]<<" "; cout<<endl; } }
C2：http://codeforces.com/contest/1382/problem/C2
解析：
与C1唯一的区别就是k了，最多限制在2n
参照：https://www.cnblogs.com/lonely-wind-/p/13361589.html的思路：
考虑把s1变为全相等的一个串，最多n-1步完成，再将s1变成s2，可以在n步内完成
s1变为全相等，那么在从后往前遍历翻转的时候，就不用再考虑它前面的相对位置的变化，因为它们全相等。
#include<iostream> #include<cstring> #include<string.h> #include<cmath> #include<map> using namespace std; typedef long long ll; const int maxn=1e5+10; const int maxn2=3e6; const int mod=1e9+7; char s1[maxn],s2[maxn]; ll a[maxn]; int b[2*maxn2]; int qk(ll a, ll b,ll c) { ll ans=1; a=a%c; while(b) { if(b%2==1) ans=(ans*a)%c; b=b/2; a=(a*a)%c; } return ans; } int main() { int t; scanf("%d",&t); while(t--) { int n; cin>>n; scanf("%s",s1+1); scanf("%s",s2+1); int tot=0; for(int i=2;i<=n;i++) { if(s1[i]!=s1[i-1]) { b[tot++]=i-1; } } char md=s1[n]; for(int i=n;i>=1;i--) { if(s2[i]!=md) { b[tot++]=i; md=s2[i]; } } cout<<tot<<" "; for(int i=0;i<tot;i++) cout<<b[i]<<" "; cout<<endl; } }