etcScripts/C1332.cpp at master · s1lverfish/etcScripts · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t; cin >> t;
	while(t--)
	{
		int n, k; cin >> n >> k;

		string s; cin >> s;
		vector<string> ss;
		for(int i = 0; i < n; i+=k)
		{
			ss.pb(s.substr(i, k));
		}

		int x = ss.size();

		int maxApp = 0;
		vector<map<char, int>> pos(k/2+1);

		int changes = 0;

		for(int i = 0; i < k/2; i++)
		{
			int maxApp = 0;
			for(auto y : ss)
			{
				pos[i][y[i]]++;
				if(pos[i][y[i]] > maxApp) maxApp = pos[i][y[i]];
				pos[i][y[k-i-1]]++;
				if(pos[i][y[k-i-1]] > maxApp) maxApp = pos[i][y[k-i-1]];
			}

			changes += 2*x - maxApp;
		}

		if(k%2 == 1)
		{
			int i = k/2;
			int maxApp = 0;
			for(auto y : ss)
			{
				pos[i][y[i]]++;
				if(pos[i][y[i]] > maxApp) maxApp = pos[i][y[i]];
			}
			changes += x - maxApp;
		}

		cout << changes << '\n';
	}
	return 0;
}