CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
======2020/08/01–2020/08/07周报（week13）======

=====本周推荐=====
====by iuiou====
  * **题源**：[[https://codeforces.com/group/azDPdoF24f/contest/290092/problem/A]]

  * **题意**：给$1-n$的一串数，有$m$次操作，每次操作给一段区间，如果左数大于右数，则将这段区间从大到小排序，如果左数小于右数，则将这段区间从小到大排序。

  * **知识点**:线段树，二分答案
 
  * **题解**：考虑二分答案（做的时候确实死也没想到），二分枚举中间的数，每次枚举后在序列中将所有大于等于枚举数的数标为1，剩余标为0，之后操作时只要对分一半$1$，分一半$0$即可。操作完之后看中间的点是否为1，是则扩大中间数，否则缩小中间数
 


=====团队训练=====
2020.8.1 牛客多校第七场

2020.8.3 牛客多校第八场

2020.8.6 加训第二场

=====范泽恒=====

====专题====
  * 01trie,可持久化01 trie

====比赛====
  * [[codeforces round 661(div3)]]
====题目====
 
=====恭天祥=====

====专题====
  * 无

====比赛====


  * [[cf 658 div.2]]

====题目====



=====刘怀远=====
====专题====
  *无
====比赛====
  * [[Codeforces Round 656 (Div. 3)]]
====题目====

  *cf 656 Problem-D:a-Good String
  *链接：https://codeforc.es/contest/1385/problem/D
    - 题意：多组数据，给定长为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”。
    - 题解： 经典二分dfs，维护最小代价即可。
<del>为什么这破题当初能卡那么久</del>
<hidden ac代码>
<code c++>
#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'));
	}
} 
</code>
</hidden>
CVBB ACM Team

用户工具

站点工具

页面工具
