• 题源：

• 题意：

• 知识点：

• 题解：

2020.7.25 牛客多校第六场

2020.7.27 牛客多校第七场

• 无

• codeforces round 656(div3)

• codeforces round 657(div2)

• codeforces round 658(div2)

• 题源：https://codeforces.com/contest/1385/problem/G

• 题意：给定两排数，每排都有$n$个数，每次操作可以交换一列的两个数，问能否存在一个最少的交换方案，使操作之后每一行都是$1$到$n$的一个排列。

• 知识点：dfs

• 题解：这题有点难想，大致是一个二分图的问题。首先遍历两行数，如果一个数的出现次数超过了2次，那么肯定不成立。如果所有数出现次数都是两次，那么一定有一种方案满足。现定四个数组$r1[n],r2[n],b1[n],b2[n],b$数组用于存放列数，$r$数组用于存放行数，如果对于一个数$i$,$b_{1i}=b_{2i}$,则不考虑这个点，因为肯定不会动这个点的。接下来对点染色，如果$b_{1i}≠b_{2i}$,考虑$r$数组，如果$r_{1i}≠r_{2i}$,则在$b_{1i}$和$b_{2i}$之间连一条权为0的边表示，两点染的色必须相同。反之，连一条权为$1$的边，表示两个点颜色相反，最后从每个点开始$dfs$经行染色即可,注意每次比对将开头的那个点染成$1$还是$0$，最后的结果会最优(即最少)。

• 无

• cf 659 div.2

* 题源：https://codeforces.com/contest/1384/problem/D

• 题意：Koa和KoalaKoala两人玩游戏，初始分均为$0$，每次两人从一个数组中选择一个数，选择后该数字会被从数组中删除，两人的分数异或上该数字的值为新的分数，问均采取最优策略谁能赢，规定KoaKoa先手。

• 知识点：博弈论

• 题解：这个题是博弈论的题： 分析一下： 设$p_i$表示$n$个数二进制位第$i$位为$1$的个数 若$p_i|2$那么先手和后手对$i$位的结果没有影响 从而我们需要找到$j$，使得$p_j|2=1$这样才能导致先后手的结果在第$j$位不同 现在我们的任务就是找打最大的$j$位，使结果最大化 若$\frac{P_j-1}{2}$是偶数，那么先手的就一定赢 - 先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。 若$\frac{P_j-1}{2}$是奇数，分两种情况 1. 若$n|1 = 1$先手就必输： - 先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。 2. 若$n|1$那么先手必赢 - 先手第一步选一个0，然后将状态转为$n|2=1$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。

• 无

• Codeforces Round 656 (Div. 3)

• cf 656 Problem-D:a-Good String
• 链接：https://codeforc.es/contest/1385/problem/D
  1. 题意：多组数据，给定长为n的字符串（n为2的整数次方），输出将其变成“a - good string”最少需要改动的字符数。以ch代指字母，“ch - good string”定义为：（1）长为1且字符为ch；（2）长大于一，且二分后左边字符全为ch，右边为“（ch+1）- good string”；（3）长大于一，且二分后右边字符全为ch，左边为“（ch+1）- good string”。
  2. 题解： 经典二分dfs，维护最小代价即可。

为什么这破题当初能卡那么久

#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int maxn = 2e5 + 5;
const double pi = acos(-1);
const int mod = 998244353;
 
int t, n;
char s[131074];
 
int cal(int l, int r, int c){
	int cnt = 0;
	for(int i = l; i <= r; ++i) if(s[i] != c) ++cnt;
	return cnt;
}
 
int dfs(int l, int r, char c){
	if(l == r) return s[l] != c;
	int res = 3e7;
	int mid = (l + r) >> 1;
	res = min(res, dfs(l, mid, c + 1) + cal(mid + 1, r, c));
	res = min(res, dfs(mid + 1, r, c + 1) + cal(l, mid, c));
	return res;
}
 
int main(){
	scanf("%d", &t);
	while(t--){
		scanf("%d\n", &n);
		scanf("%s", s + 1);
		printf("%d\n", dfs(1, n, 'a'));
	}
}