stl, 水题
题目意思：
两条字符串，长度都是n。 现在把两个相同的字符配对在一起，其中 ‘?’ 可以配对任意字符。
问最多可以配对多少对字符对，要求写出任意 一组配对方式。
本题要点：
1、用 vector 来存每一个字符在 字符串出现的下标。
2、用 vector<pair<int, int> > ans; 来存每一组配对。
3、配对策略：
先把完全配对的处理了;
再处理第1 条字符串的 ‘?’ 和第 2 条字符串剩下的非 ‘?’ 字符， 同理处理第 1条字符串的 ‘?‘和 第 1 条字符串剩下的非 ‘?’ 字符;
剩下的就是 第1 条字符串的 ‘?’ 和 第 2 条字符串剩下的’?’ ;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MaxN = 150010;
char s1[MaxN], s2[MaxN];
int n;
vector<int> v1[256];
vector<int> v2[256];
vector<pair<int, int> > ans;
vector<int> noMatch1, noMatch2;void sovle()
{
for(int i = 1; i <= n; ++i){
v1[s1[i] + 0].push_back(i);v2[s2[i] + 0].push_back(i);}int left1 = 0, left2 = 0; for(int i = 1; i < 256; ++i){
if(i == '?' + 0) continue;while(v1[i].size() && v2[i].size()){
left1 = v1[i][v1[i].size() - 1], left2 = v2[i][v2[i].size() - 1];ans.push_back(make_pair(left1, left2));v1[i].pop_back();v2[i].pop_back();}while(v1[i].size()){
noMatch1.push_back(v1[i][v1[i].size() - 1]);v1[i].pop_back();}while(v2[i].size()){
noMatch2.push_back(v2[i][v2[i].size() - 1]);v2[i].pop_back();}}while(v1['?' + 0].size() && noMatch2.size()){
left1 = v1['?' + 0][v1['?' + 0].size() - 1], left2 = noMatch2[noMatch2.size() - 1]; ans.push_back(make_pair(left1, left2));noMatch2.pop_back();v1['?' + 0].pop_back();}while(v2['?' + 0].size() && noMatch1.size()){
left1 = noMatch1[noMatch1.size() - 1], left2 = v2['?' + 0][v2['?' + 0].size() - 1];ans.push_back(make_pair(left1, left2));noMatch1.pop_back();v2['?' + 0].pop_back();} while(v1['?' + 0].size() && v2['?' + 0].size()){
left1 = v1['?' + 0][v1['?' + 0].size() - 1], left2 = v2['?' + 0][v2['?' + 0].size() - 1];ans.push_back(make_pair(left1, left2));v1['?' + 0].pop_back();v2['?' + 0].pop_back();}int size = ans.size();printf("%d\n", size);for(int i = 0; i < size; ++i)printf("%d %d\n", ans[i].first, ans[i].second);
}int main()
{
scanf("%d", &n);scanf("%s", s1 + 1);scanf("%s", s2 + 1);sovle();return 0;
}/* 7 abaca?b zabbbcc *//* 5 6 5 2 3 4 6 7 4 1 2 */