https://codeforces.com/contest/1332/problem/C

 

 

 

 

 

题意：给一个长度为n的字符串，让你将它修改成n/k段相等的回文段，求最小的修改次数。

思路：我们先将字符串按k长度分区：

{XXX...XX}{XXX...XX}...{XXX...XX}

最后要求是回文串，所以每个分区都是完全一样的回文串，记录长度为[k/2]的分区的每个位置每个字母出现的次数就可以了，然后贪心，出现次数最多的字母不用改，其它字母全改掉。

 

 

 1 #include <bits/stdc++.h>
 2 typedef long long LL;
 3 const int INF=0x3f3f3f3f;
 4 const double eps =1e-8;
 5 const int mod=1e8;
 6 const int maxn=2e5+10;
 7 using namespace std;
 8  
 9 int a[maxn][30];
10 char str[maxn];
11  
12 int main()
13 {
14     #ifdef DEBUG
15     freopen("sample.txt","r",stdin);
16     #endif
17     
18     int T;
19     scanf("%d",&T);
20     while(T--)
21     {
22         int n,k;
23         scanf("%d %d %s",&n,&k,str);
24         for(int i=0;i<n;i++)
25             a[min(i%k,k-i%k-1)][str[i]-'a']++;
26         int ans=0;
27         for(int i=0;i<k;i++)
28         {
29             int num=0;
30             int MAX=0;
31             for(int j=0;j<26;j++)
32             {
33                 num+=a[i][j];
34                 MAX=max(MAX,a[i][j]);
35                 a[i][j]=0;
36             }
37             ans+=num-MAX;
38         }
39         printf("%d\n",ans);
40     }
41     
42     return 0;
43 }

 

 

 

 

 

 

 

 

-