首页 > 其他 > 详细

codeforce Error Correct System

时间:2015-03-26 23:21:10      阅读:336      评论:0      收藏:0      [点我收藏+]

题目大意:

给出两串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\n",sum-2);
36                 printf("%d %d\n",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\n",sum-1);
52                         printf("%d %d",vist[i][j],vist[j][k]);
53                         return 0;
54                     }
55                 }
56             }
57         }
58     }
59     printf("%d\n",sum);
60     printf("-1 -1\n");
61     return 0;
62 }

 

codeforce Error Correct System

原文:http://www.cnblogs.com/tsw123/p/4370305.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!