题目大意:
给出两串n(1 ≤ n ≤ 200 000)个字母的字符串, 求出最多交换一对数, 使得不相同对数变少,求出不相同的对数以及交换的数的位置,若不需交换则输出-1,-1.
分析：
用矩阵记录两个串相同位置不同的字母,有三种情况，一种是交换后正好两个位置都对应相同，一种是交换后只有一个位置相同，还有就是交换也不能满足对应相同。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<iostream> 5 #include<queue> 6 #include<stack> 7 #include<string> 8 #include<algorithm> 9 #define maxn 200010 10 #define INF ~0u>>1 11 using namespace std; 12 int main() 13 { 14 int n,vist[30][30]; 15 char a[maxn],b[maxn]; 16 scanf("%d",&n); 17 scanf("%s",a); 18 scanf("%s",b); 19 memset(vist,0,sizeof(vist)); 20 int sum=0; 21 for(int i=0; i<n; i++) 22 { 23 if(a[i]!=b[i]) 24 { 25 sum++; 26 vist[a[i]-'a'][b[i]-'a']=i+1; 27 } 28 } 29 for(int i=0;i<26;i++) 30 { 31 for(int j=0;j<26;j++) 32 { 33 if(vist[i][j]&&vist[j][i]) 34 { 35 printf("%d ",sum-2); 36 printf("%d %d ",vist[i][j],vist[j][i]); 37 return 0; 38 } 39 } 40 } 41 for(int i=0;i<26;i++) 42 { 43 for(int j=0;j<26;j++) 44 { 45 if(vist[i][j]) 46 { 47 for(int k=0;k<26;k++) 48 { 49 if(vist[j][k]) 50 { 51 printf("%d ",sum-1); 52 printf("%d %d",vist[i][j],vist[j][k]); 53 return 0; 54 } 55 } 56 } 57 } 58 } 59 printf("%d ",sum); 60 printf("-1 -1 "); 61 return 0; 62 }