題目鏈接：點擊查看

題目大意：給出兩個字符串s和t，兩個字符串中相同的字母可以匹配，問號可以和任意字符匹配，現在問兩個字符串最多能匹配多少個字符，并給出匹配的下標

題目分析：挺好玩的一道水題，大體思路就是先遍歷一遍兩個字符串，將所有的字符下標都分類儲存起來，按照以下順序匹配：

s串和t串中的普通字母

s串的問號和t串中的普通字母

t串的問號和s串中的普通字母

s串的問號和t串中的問號

按照上面的順序暴力就可以了

代碼：

#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=2e5+100;int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;string a,b;cin>>n>>a>>b;vector<int>aa[27];//0~25儲存字母，26儲存問號vector<int>bb[27];vector<pair<int,int>>ans;for(int i=0;i<a.size();i++){if(a[i]=='?')aa[26].push_back(i+1);elseaa[a[i]-'a'].push_back(i+1);}for(int i=0;i<b.size();i++){if(b[i]=='?')bb[26].push_back(i+1);elsebb[b[i]-'a'].push_back(i+1);}for(int i=0;i<26;i++)//優先匹配字母{while(aa[i].size()&&bb[i].size()){ans.push_back(make_pair(aa[i].back(),bb[i].back()));aa[i].pop_back();bb[i].pop_back();}}if(aa[26].size())//匹配a中的問號{for(int i=0;i<26;i++){while(aa[26].size()&&bb[i].size()){ans.push_back(make_pair(aa[26].back(),bb[i].back()));aa[26].pop_back();bb[i].pop_back();} }}if(bb[26].size())//匹配b中的問號{for(int i=0;i<26;i++){while(bb[26].size()&&aa[i].size()){ans.push_back(make_pair(aa[i].back(),bb[26].back()));aa[i].pop_back();bb[26].pop_back();} }}while(aa[26].size()&&bb[26].size())//匹配兩個串中的問號{ans.push_back(make_pair(aa[26].back(),bb[26].back()));aa[26].pop_back();bb[26].pop_back();}cout<<ans.size()<<endl;for(int i=0;i<ans.size();i++)printf("%d %d\n",ans[i].first,ans[i].second);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1141D Colored Boots(暴力+水题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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