codeforces 1256f

題意

給出兩個長度相等的字符串，每次操作必須同時翻轉(zhuǎn)兩個字符串中相同長度的子串，求是否可以通過這種操作使得兩個串相等

題解

可以推出當兩個字符串的字符集相等，任一字符出現(xiàn)的次數(shù)不為一時，答案為YES。因為我們可以不斷地翻轉(zhuǎn)兩個的相同字符，同時令另一個字符串不斷地交換字符使得兩個字符串相等。
這樣我們可以把n優(yōu)化到26，然后暴力翻轉(zhuǎn)相鄰的兩個數(shù)即可，當翻轉(zhuǎn)次數(shù)為偶數(shù)時，輸出YES。

#include <bits/stdc++.h> using namespace std; #define no printf("-1\n"),exit(0) typedef long long ll; typedef pair<int,int> P; const int maxn=200050; const int inf=0x3f3f3f3f; const int mod=998244353;char a[maxn],b[maxn];int main() {int n,t,i,j,k;scanf("%d",&t);while(t--){scanf("%d",&n);scanf("%s %s",a,b);vector<int> k1(30,0),k2(30,0);for(i=0; i<n; i++){int x=a[i]-'a',y=b[i]-'a';k1[x]++,k2[y]++;}int f=0;for(i=0; i<26; i++)if(k1[i]!=k2[i])f=1;if(f){printf("NO\n");continue;}f=0;for(i=0; i<26; i++)if(k1[i]>1)f=1;if(f){printf("YES\n");continue;}int ans=0,l,r;for(i=0;i<n;i++){if(a[i]!=b[i]){for(j=i+1;j<n;j++)if(b[j]==a[i])break;for(k=j-1;k>=i;k--)swap(b[k],b[k+1]),ans++;}}if(ans%2==0)printf("YES\n");elseprintf("NO\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces 1256f的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。