D
题面大意
$ n $ 个字母的字符串，选出 $ m $ 个子串（不一定连续，但每个字符串长度至少 $ 1 $）；
子串字母可随意交换；
让所有子串都是回文串，而且最短的那个尽可能长。求出最短那个的长度。
题面关键
让所有子串都是回文串
可随意交换
众所周知，回文串有两种：$ \texttt{abcba} $ 及 $ \texttt{abba} $ 式的。
解题思路
那么我们统计总共有多少对字母（记为 $ a $），及落单的字母数（记为 $ b $）
每个字符串先选 $ x = \lfloor \frac{a}{m} \rfloor $ 对，余下 $ a \bmod m $ 对归入 $ b $ 。
如果能每个字母配一个落单的字母（即此时的 $ b \geq m $ ），答案就是 $ x + 1 $ ，否则就是 $ x $ 。
思路要点
多测！多测！！多测！！！cnt 数组一定要清空！！！！
AC 代码
// Problem: D. Palindromes Coloring
// Contest: Codeforces - Codeforces Round #764 (Div. 3)
// URL: https://codeforces.com/contest/1624/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
int cnt[50];
int main() {
int t;
cin >> t;
while (t--) {
memset(cnt, 0, sizeof cnt);
int n, m;
cin >> n >> m;
string s;
cin >> s;
for (char c : s) {
cnt[c - 'a']++;
}
int pair2 = 0, pair1 = 0;
for (int i = 0; i < 26; i++) {
pair2 += cnt[i] / 2;
pair1 += cnt[i] % 2;
}
int len = pair2 / m * 2;
pair1 += (pair2 - pair2 / m * m) * 2;
if (pair1 >= m) {
printf("%d\n", len + 1);
} else {
printf("%d\n", len);
}
}
return 0;
}
E
题面大意
有 $ n + 1 $ 个长度为 $ m $ 的字符串，问第 $ n + 1 $ 个字符串能不能用前面 $ n $ 个字符串的，长度 $ \geq 2 $ 的子串连接起来表示。
题面关键
- 同样的内容可以用同一个子串
- 4 = 2 + 2, 5 = 2 + 3, 6 = 2 + 2 + 2 = 3 + 3, 7 = 2 + 2 + 3……
解题思路
由于长度 $ \geq 4 $ 的子串都能拆解成 $ 2 $ 和 $ 3 $ ，所以我们拿一个数组（或者 map 什么的）存每个长度 $ 2 \sim 3 $ 的子串的信息。
然后，dp 即可。
思路要点
一定要把初始状态和无解区分开！！！
AC 代码
// Problem: E. Masha-forgetful
// Contest: Codeforces - Codeforces Round #764 (Div. 3)
// URL: https://codeforces.com/contest/1624/problem/E
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
struct seg {
int id, st;
bool tp; // 2/3
seg(int _id = -1, int _st = -1, int _len = -1) {
id = _id;
st = _st;
if (_len == 2) {
tp = 0;
} else {
tp = 1;
}
}
} f[1005];
map<string, seg> mp;
int main() {
int t;
cin >> t;
while (t--) {
mp.clear();
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
if (j + 2 <= m) {
mp[s.substr(j, 2)] = seg(i, j, 2);
}
if (j + 3 <= m) {
mp[s.substr(j, 3)] = seg(i, j, 3);
}
}
}
string s;
cin >> s;
s = " " + s;
fill(f, f + m + 1, seg(-1, -1, 0));
f[0] = seg(-2, -2, 0);
for (int i = 1; i <= m; i++) {
if (i >= 2 && mp.count(s.substr(i - 1, 2)) && f[i - 2].id != -1) {
f[i] = mp[s.substr(i - 1, 2)];
}
if (i >= 3 && mp.count(s.substr(i - 2, 3)) && f[i - 3].id != -1) {
f[i] = mp[s.substr(i - 2, 3)];
}
}
if (f[m].id == -1) {
puts("-1");
continue;
}
vector<seg> ans;
int x = m;
while (x >= 0) {
ans.push_back(f[x]);
x = x - 2 - f[x].tp;
}
printf("%d\n", ans.size() - 1);
reverse(ans.begin(), ans.end());
for (seg y : ans) {
if (y.st == -2) {
continue;
}
printf("%d %d %d\n", y.st + 1, y.st + 2 + y.tp, y.id + 1);
}
}
}
G
题面大意
最小生成树，但这次不是 $ \sum _ {(u, v, w) \in E} w $ 最小，而是 $ | _ {(u, v, w) \in E} w $ 最小
题面关键
众所周知，bitmask 可以一位一位处理。
最高的位尽可能的小才是关键！
解题思路
从最高位遍历到最低位。
对于每一位，我们把它删掉，再看看符合条件的边能不能让图联通。
能，就删，不能，就留。
思路要点
多测题千万别 memset ！要用 fill ，fill 可以把握区域，就不会超时了。
P.S. “符合条件的边”不用真的用删除搞定，而是给 dfs 做个小改动。
AC 代码
// Problem: G. MinOr Tree
// Contest: Codeforces - Codeforces Round #764 (Div. 3)
// URL: https://codeforces.com/contest/1624/problem/G
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > graph[200005];
bool vis[200005];
void dfs(int u, int cur) {
if (vis[u]) {
return;
}
vis[u] = 1;
for (auto [v, w] : graph[u]) {
if ((w | cur) == cur) {
dfs(v, cur);
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
graph[i].clear();
}
int cur = INT_MAX;
for (int i = 0; i < m; i++) {
int a, b, x;
scanf("%d %d %d", &a, &b, &x);
a--, b--;
graph[a].emplace_back(b, x);
graph[b].emplace_back(a, x);
}
for (int i = 30; i >= 0; i--) {
fill(vis, vis + n, 0);
cur -= (1 << i);
dfs(0, cur);
for (int j = 0; j < n; j++) {
if (!vis[j]) {
cur += (1 << i);
break;
}
}
}
printf("%d\n", cur);
}
return 0;
}