2020.7.18 牛客多校第三场

2020.7.20 牛客多校第四场

2020.7.23 codeforces team pratice

• 无

• codeforces round 656(div3)

• codeforces round 657(div2)

• codeforces round 658(div2)

• 题意：

• 知识点：

• 题解：

• 无

• cf 657 div.2

• 牛客第三次C题：
  1. 题意：给出20个点，这20个点构成了一只手，通过给定的信息判断这只手是左手还是右手
  2. 题解：这个题很新颖，导致很多之前做题的思路都用不上，开始做题时就死磕，想面积，边长…… 都没想到点上 反而浪费了挺多时间，我觉着这个题重再观察，并且读懂题意，我读题时忘记了手掌面积不变，直接导致了队友懵逼了半小时，这个题的具体解决思路也很简单，大拇指外侧的线长6，手掌底部的线长9，小拇指外侧的线长8。判断连续的三根或者两根线是否满足这个规律就行了，由于是浮点数，这题需要控制精度。$eps = 1e-5或更小都行$

• 无

• 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'));
	}
}