Codeforces Round #658 (Div. 2) C2. Prefix Flip (Hard Version) (构造)

题意:给你两个长度为\(n\)的01串\(s\)和\(t\),可以选择\(s\)的前几位,取反然后反转,保证\(s\)总能通过不超过\(2n\)的操作得到\(t\),输出变换总数,和每次变换的位置.
题解:我们现将\(s\)串全部变成\(1\)或\(0\),确保\(s[n]=t[n]\),然后我们倒着遍历\(t\),若遇到相邻的两个字符不同,我们就对\(s\)中相应的位置执行一次操作,然后继续遍历,如下图:

代码:

int t;

int n;

char s[N],tmp[N];

vector<int> ans;

int main() {

    scanf("%d",&t);

     while(t--){

     	scanf("%d",&n);

     	scanf("%s %s",s+1,tmp+1);

     	ans.clear();

     	if(s==tmp){

     		printf("0\n");

     		continue;

     	}

     	for(int i=1;i<n;++i){

     		if(s[i]!=s[i+1]){

     			ans.pb(i);

     		}

     	}

     	if(s[n]!=tmp[n]){

     		ans.pb(n);

     	}

     	for(int i=n;i>=2;--i){

     		if(tmp[i]!=tmp[i-1]){

     			ans.pb(i-1);

     		}

     	}

     	printf("%d ",ans.size());

     	for(auto w:ans){

     		printf("%d ",w);

     	}

     	puts("");

     }

    return 0;

}

巴特西

Codeforces Round #658 (Div. 2) C2. Prefix Flip (Hard Version) (构造)

最新文章

热门文章