題目鏈接：點擊查看

題目大意：給出兩個只由字母a和字母b所組成的字符串，我們記為s和t，現在我們可以交換兩個字符串任意位置的字母（只能在兩個串之間交換，不能在自己串中交換），現在問能否通過一定次數的交換使兩個字符串相等，如果可以求出最小交換次數

題目分析：其實這個題目挺簡單的，一開始想復雜了，其實我們抽象一下，就可以發現，對于每個位置i無非只有幾種情況：

a[i]==b[i]

a[i]!=b[i]

a[i]='a',b[i]='b'

a[i]='b',b[i]='a'

對于第一種情況我們就不用管了，因為已經是匹配好的狀態了，如果再去進行多余的操作一定不會是最優解，所以我們針對第二種情況討論一下，第二種情況向下還可以再分出兩種情況，如上面所示，我們稱作可操作對，顯然對于每個可操作對，肯定讓同類型的可操作對兩兩匹配一定是最優的，因為只有讓相同種類的兩兩匹配后才可以達到間接在本字符串中交換位置的目的，所以我們記q1為第一種情況的數目，q2為第二種情況的數目：

q1為偶數，q2為偶數：我們直接兩兩匹配即可

q1為奇數，q2為奇數：我們需要將一個q2放到q1中去，也就是執行一次swap(i,i)的操作，這樣就是第一種情況了

q1為奇數，q2為偶數：無解

q1為偶數，q2為奇數：無解

剩下的實現就好了，這里我選擇用deque容器實現上述操作，因為deque支持隨機訪問，操作起來方便一下，然后用vector+pair維護答案

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;string a,b;cin>>n>>a>>b;deque<int>q1,q2;vector<pair<int,int>>ans;for(int i=0;i<n;i++){if(a[i]!=b[i]){if(a[i]=='a')q1.push_back(i+1);elseq2.push_back(i+1);}}if((q1.size()+q2.size())&1)//特判情況3和情況4return 0*printf("-1\n");if(q1.size()&1)//情況2{int pos=q2.front();q2.pop_front();ans.push_back(make_pair(pos,pos));q1.push_back(pos);}while(q1.size()){ans.push_back(make_pair(q1[0],q1[1]));q1.pop_front();q1.pop_front();}while(q2.size()){ans.push_back(make_pair(q2[0],q2[1]));q2.pop_front();q2.pop_front();}printf("%d\n",ans.size());for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的CodeForces - 1215C Swap Letters(暴力+思维+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。