题目链接：https://vjudge.net/contest/397850#problem/C 题意：将01字串a可以进行多少次操作变成b。 操作：将前缀i前面的数（包括i）是1的话变成0（是0的话变为1），然后再将其到前缀i之间的数反转。输出最少的操作数，并写出前缀i。 题解：因为需要反转，所以优先考虑后面的，又因为后面的b[i]是由a[0]变成的。所以需要判断是否需要先变a[0]。如果a[0]和b[i]相等的话，因为要由1变成0，所以需要先改变a[0]。然后再将其反转 代码：（复杂度（n*n））
#include<iostream> #include<cstdio> #include<string> #include<algorithm> #define maxn 1200 using namespace std; int a[maxn],b[maxn]; string aa,bb; int sol[3*maxn]; int n;//串的长度 void solve(int k) { for(int i=0;i<=k;i++) a[i]=1-a[i]; for(int i=0;i<=k/2;i++) swap(a[i],a[k-i]); } void duru() { scanf("%d",&n); getchar();//getline也读空行，所以需要吸收 //01字串是连着的，所以需要用字符来处理 getline(cin,aa); for(int i=0;i<n;i++) a[i]=(int)(aa[i]-'0'); getline(cin,bb); for(int i=0;i<n;i++) b[i]=bb[i]-'0'; } int main() { int t; scanf("%d",&t); while(t--) { int num=0;//操作数 duru(); for(int i=n-1;i>=0;i--) { if(a[i]==b[i]) continue; if(a[0]==b[i]) { num++; sol[num]=1;//先变第一个 } num++; sol[num]=i+1; solve(i); } printf("%d ",num); for(int j=1;j<=num;j++) printf("%d ",sol[j]); printf("\n"); } return 0; }hard版本n<=1e5,所以肯定会超时，所以简化修改交换值得那一步，然后用正序和逆序来代替。l,r表示最左侧和最右侧。
#include<iostream> #include<cstdio> #include<string> #include<algorithm> #define maxn 120000 using namespace std; int a[maxn],b[maxn]; string aa,bb; int sol[3*maxn]; int n;//串的长度 void duru() { scanf("%d",&n); getchar();//getline也读空行，所以需要吸收 //01字串是连着的，所以需要用字符来处理 getline(cin,aa); for(int i=0;i<n;i++) a[i]=(int)(aa[i]-'0'); getline(cin,bb); for(int i=0;i<n;i++) b[i]=bb[i]-'0'; } int main() { int t; scanf("%d",&t); while(t--) { int num=0;//操作数 duru(); int l=0,r=n-1;//最左侧，最右侧 int xu=1;//1表示正序，-1表示逆序 for(int i=n-1;i>=0;i--) { if(xu==1)//正序 { if(a[r]==b[i])//最右边的和他比较，所以是r和他比 { r--; continue; } if(a[l]==b[i]) { num++; sol[num]=1;//先变第一个 } num++; l++; sol[num]=i+1; xu=-1; } else if(xu==-1) { if(a[l]!=b[i])//此时逆序l是最右边，所以l和他比 { l++; continue; } if(a[r]!=b[i]) { num++; sol[num]=1;//先变第一个 } r--; num++; sol[num]=i+1; xu=1; } } printf("%d ",num); for(int j=1;j<=num;j++) printf("%d ",sol[j]); printf("\n"); } return 0; }