codeforces1141D题解(暴力+贪心)-白红宇

给出两个长度为 n(1≤n≤150000)的仅含有小写字母和'?'的字符串，询问两个字符串最多能有几对匹配的字符。

(每个字母都可以与和它相同的字符匹配，'?'可以与任意字符匹配，匹配与位置无关)

输出最大匹配对数，以及每一对中两个字符在字符串中的位置

/* * CF1141D * Created by hao on 2019/4/11. * 给出两个长度为 n(1≤n≤150000)的仅含有小写字母和'?'的字符串，询问两个字符串最多能有几对匹配的字符。 * （每个字母都可以与和它相同的字符匹配，'?'可以与任意字符匹配，匹配与位置无关） * 输出最大匹配对数，以及每一对中两个字符在字符串中的位置 */#include 
    
     #include 
     
      #include
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               using namespace std;#define ll long long#define mp make_pair#define ff first#define ss second#define pub push_back#define pob pop_back()#define pof pop_front()vector
               
                 l[250], r[250];vector
                
                 
                   > ans;int main() { ios::sync_with_stdio(false); int n; cin >> n; string s1, s2; cin >> s1 >> s2; //让每一个字符对应自己的位置(下表+1) for (int i = 0; i < s1.length(); i++) { l[(int) s1[i]].pub(i + 1); } for (int i = 0; i < s2.length(); i++) { r[(int) s2[i]].pub(i + 1); } //记录'?'对应的int值，防止'?'和'?'优先匹配 int q = (int) '?'; for (int i = 0; i < 250; i++) { //等于'?'时跳过，防止'?'优先匹配。 if (i == q) continue; //匹配相同的字符，比如'a','a','b','b' while (!l[i].empty() && !r[i].empty()) { ans.pub(mp(l[i].back(), r[i].back())); l[i].pob; r[i].pob; } //让第一个字符串的'?'和第二个字符串的任意字符匹配 while (!l[q].empty() && !r[i].empty()) { ans.pub(mp(l[q].back(), r[i].back())); l[q].pob; r[i].pob; } //让第一个字符串的任意字符和第二个字符串的'?'匹配 while (!l[i].empty() && !r[q].empty()) { ans.pub(mp(l[i].back(), r[q].back())); l[i].pob; r[q].pob; } } //在所有的除去'?'的字符都处理完之后，处理'?'和'?'的情况 while (!l[q].empty() && !r[q].empty()) { ans.pub({l[q].back(), r[q].back()}); l[q].pob; r[q].pob; } //输出匹配对数 cout << ans.size() << endl; //输出匹配的对数的相应的两个位置 for (int i = 0; i < ans.size(); i++) { cout << ans[i].ff << " " << ans[i].ss << endl; } return 0;}