差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:manespace:2020_07_18-2020_07_24周报_week11 [2020/07/24 11:44]
intouchables [题目]
+++ 2020-2021:teams:manespace:2020_07_18-2020_07_24周报_week11 [2020/07/31 10:33] (当前版本)
quantumbolt
@@ 行 1: / 行 1: @@
-======2020/07/18–2020/07/24周报（week10）======
+======2020/07/18–2020/07/24周报（week11）======
+=====本周推荐=====
+====by iuiou====
+  * **题源**：[[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$，最后的结果会最优(即最少)。
 =====团队训练=====
 .7.18 [[牛客多校第三场]]
@@ 行 19: / 行 30: @@
   * [[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$，最后的结果会最优(即最少)。
@@ 行 57: / 行 70: @@
   *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

用户工具

站点工具

差别

页面工具