字符串处理经典题

字符串处理经典题

1.CF219C Color Stripe（要求修改后的串中相邻字符不相同，求最少修改次数）

Q: 给你一个长度为N 的字符串（由大写字母组成）和一个数量K，K是指可使用的不同的大写字母的个数。现要求修改源字符串，使得串中相邻的两个位置上的元素不同；一次只能更改一个字符，问你最少的修改次数是多少？并输出任意一个满足条件的答案字符串。

A：从字符串第二位开始逐个检查即可，每次维护num[i ]= SG(num[ i- 1 ]，num[ i+ 1])；即可。注意K= 2时可以特判，因为答案串只有"ABABABA...ABA"和"BABAB...BABAB"两种。

原题链接： http://codeforces.com/problemset/problem/219/C

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<map>
 7 using namespace std;
 8  
 9 char _sg(char a, char b)
10 {
11     int x= a- 'A';
12     int y= b- 'A';
13  
14     int ans;
15     for (int i= 0; i< 4; i ++)
16     {
17         if (i!= x&& i!= y)
18         {
19             ans= i;
20             break;
21         }
22     }
23     return ('A'+ ans);
24 }
25 char ss[1000010];
26 int main()
27 {
28     int n, k;
29     scanf("%d %d", &n, &k);
30     getchar();
31     scanf("%s", ss+ 1);
32     ss[0]= '#';
33     int len= strlen(ss);
34     ss[len]= '#';
35     len += 1;
36     int cnt= 0;
37     if (k>= 3)
38     {
39         for (int i= 2; i< len- 1; i ++)
40         {
41             if (ss[i]== ss[i- 1])
42             {
43                 ss[i]= _sg(ss[i- 1], ss[i+ 1]);
44                 cnt ++;
45             }
46         }
47     }
48     else
49     {
50         int cnt1= 0;
51         int cnt2= 0;
52         for (int i= 1; i< len- 1; i ++)
53         {
54             if (i% 2!= ss[i]- 'A') cnt1 ++;
55             else cnt2 ++;
56         }
57         if (cnt1<= cnt2)
58         {
59             cnt= cnt1;
60             for (int i= 1; i< len- 1; i ++)
61             {
62                 int cn= i% 2;
63                 ss[i]= 'A'+ cn;
64             }
65         }
66         else
67         {
68             cnt= cnt2;
69             for (int i= 1; i< len- 1; i ++)
70             {
71                 int cn= (i+1)% 2;
72                 ss[i]= 'A'+ cn;
73             }
74         }
75     }
76     printf("%d\n", cnt);
77     for (int i= 1; i< len- 1; i ++)
78     {
79         printf("%c", ss[i]);
80     }
81     printf("\n");
82     return 0;
83 }

View Code

秒客网

字符串处理经典题

相关文章