A. Cover in Water
题意：有n个格子，有些格子是好的，有些是坏的，你要给好格子都装上水，你可以花费一点价值让一个格子有水， 也可以把一个格子的水移到另一个格子，没有花费。如果一个格子是好格子并且两边的格子都有水，这个格子就会自己填满水。 问最少花费让所有好格子有水。
容易想到，如果有三个连续格子都是好格子，那么我们在两边放水中间就可以源源不断生水，我们就可以将他移到其他格子上，只需要两花费。如果没有，答案就是好格子数量。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
s = "#" + s + "#";
int ans = 0, max = 0;
for (int i = 0; i < s.size(); ++ i) {
int j = i + 1;
while (j < s.size() && s[j] == '.') {
++ j;
}
ans += std::min(2, j - i - 1);
max = std::max(max, j - i - 1);
i = j - 1;
}
if (max > 2) {
ans = 2;
}
std::cout << ans << "\n";
}
B. Laura and Operations
题意：有\(a\)个\(1\), \(b\)个\(2\), \(c\)个\(3\)， 每次可以选两个不同的数换另一个数，问每个数有没有可能操作到只剩这一个类型的数。
以留下\(1\)举例，我们可以先把\(bc\)都减到零， 然后在用\(1\)和多出来一个数操作到\(bc\)相等，然后就可以一起操作\(bc\)到零了，这个操作的可行性就是最后剩下的那个数是不是偶数，只有偶数才能操作到让这两个数相等，而剩下那个数的值为\(|b - c|\)， 所以判断\(|b - c|\)是不是偶数即可。\(bc\)同理。
点击查看代码
void solve() {
int a, b, c;
std::cin >> a >> b >> c;
std::vector<int> ans(3);
if ((a - b) % 2 == 0) {
ans[2] = 1;
}
if ((a - c) % 2 == 0) {
ans[1] = 1;
}
if ((b - c) % 2 == 0) {
ans[0] = 1;
}
for (int i = 0; i < 3; ++ i) {
std::cout << ans[i] << " \n"[i == 2];
}
}
C. Anji's Binary Tree
题意：一颗二叉树，你要去叶子节点。每个节点上有字符，代表你到了这个节点要去父亲节点还是左儿子还是右儿子。 你可以修改每个节点上的字符，问最少修改几个可以让你到叶子。
考虑\(f_u\)代表从根节点到\(u\)所需要的最小修改节点数，如果\(u\)是叶子，则更新答案，如果\(s_u\)是'\(U\)'，那么我们为了继续往下就得更改一次，\(f_u\)++。然后考虑到左儿子去，如果\(s_u\)是'\(R\)'那么\(f_{lson}\)是\(f_u + 1\)，否则是\(f_u\)，右儿子同理。dfs求解即可。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
std::vector<int> l(n), r(n);
for (int i = 0; i < n; ++ i) {
std::cin >> l[i] >> r[i];
-- l[i]; -- r[i];
}
int ans = n;
auto dfs = [&](auto self, int u, int val) -> void {
if (u == -1) {
return;
}
if (l[u] == -1 && r[u] == -1) {
ans = std::min(ans, val);
}
if (s[u] == 'U') {
++ val;
}
self(self, l[u], val + (s[u] == 'R'));
self(self, r[u], val + (s[u] == 'L'));
};
dfs(dfs, 0, 0);
std::cout << ans << "\n";
}
D. Small GCD
题意：\(f(a, b, c)\)是两个最小值的\(gcd\)，给你一个数组\(a\)，求\(\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=j+1}^{n} f(a_i, a_j, a_k)\)。
首先观察式子，发现就是任意选三个数求\(f(a, b, c)\)。
那么我们先从小到大排序，那么我们在\([1,i - 1]\)里选一个数和\(i\)所能构成得\(gcd\)可以贡献\((n - i)\)次，因为后面的数每个都可以选。
正着算很难，不如考虑倒过来，我们求有多少数和\(a_i\)的\(gcd\)是\(x\)，记为\(g_x\)，那么\(i\)的贡献就是\(\sum g_x (n - i)\)。如何求\(g_x\)，我们记\(f_k\)为\([1, i - 1]\)有\(k\)这个因子的数有多少个。那么我们令\(g_x = f_x\)， 但这样会算多，因为例如 \(2x\) 和 \(4x\)也都有\(x\)这个因子，但他们最大公约数是\(2x\)，所以我们要减去\(x\)的倍数对他的影响，于是我们从大到小枚举\(x\)，然后\(g_x - \sum g_y ,x | y\)。可以预处理因子，\(nlogn\)的时间复杂度。
点击查看代码
const int N = 1e5 + 5;
std::vector<int> factor[N];
void init() {
for (int i = 1e5; i >= 1; -- i) {
for (int j = i; j <= 1e5; j += i) {
factor[j].push_back(i);
}
}
}
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::sort(a.begin(), a.end());
std::vector<int> f(N), g(N);
i64 ans = 0;
for (int i = 0; i < n; ++ i) {
for (auto & x : factor[a[i]]) {
g[x] = f[x];
}
for (auto & x : factor[a[i]]) {
for (auto & y : factor[x]) {
if (x != y) {
g[y] -= g[x];
}
}
}
for (auto & x : factor[a[i]]) {
ans += (i64)g[x] * (n - i - 1) * x;
}
for (auto & x : factor[a[i]]) {
++ f[x];
}
}
std::cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
init();
int T = 1; std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
E. Transitive Graph
题意：给你一个无向图，每个点有点权。如果有\(a, b, c\)三个点满足\(a\)和\(b\)有边，\(b\)和\(c\)有边，但\(a\)和\(c\)没边，就连接\(a\)和\(c\)，一直操作直到没有这种情况为止。 问最后这个图里最长简单路径长度是多少，所有最长路径中权值最小的是多少。
我们画图发现，最后这个图就是如果原图\(a\)和\(b\)可达，那么他们可以直达，但这对我们的答案没有影响，因为我们求最长简单路径肯定尽量走更多的点。 如果\(a\)和\(b\)相互可达，也就是有环，这个环里的点最后会形成一个完全图，那么我们的路径如果经过这个环就可以走完这个环里所有点再出去，这提示我们缩点，把一个环里的点当成一个点，这样缩点后没有环，整个图变成了有向无环图，我们可以轻易求出最长路径和其最小权值。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector<std::vector<int> > adj(n);
for (int i = 0; i < m; ++ i) {
int u, v;
std::cin >> u >> v;
-- u, -- v;
adj[u].push_back(v);
}
std::vector<i64> dfn(n), low(n), id(n), w(n), cnt(n), in_stk(n), stk(n + 10);
int idx = 0, top = 0, scc_cnt = 0;
auto tarjan = [&](auto self, int u) -> void {
dfn[u] = low[u] = ++ idx;
stk[++ top] = u; in_stk[u] = 1;
for (auto & v : adj[u]) {
if (!dfn[v]) {
self(self, v);
low[u] = std::min(low[u], low[v]);
} else if (in_stk[v]) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
int v;
do {
v = stk[top -- ];
in_stk[v] = 0;
id[v] = scc_cnt;
w[scc_cnt] += a[v];
cnt[scc_cnt] += 1;
} while (v != u);
++ scc_cnt;
}
};
for (int i = 0; i < n; ++ i) {
if (!dfn[i]) {
tarjan(tarjan, i);
}
}
std::vector<std::vector<int> > adj1(scc_cnt);
std::vector<i64> f(scc_cnt), d(scc_cnt), deg(scc_cnt);
for (int u = 0; u < n; ++ u) {
for (auto & v : adj[u]) {
if (id[v] != id[u]) {
adj1[id[u]].push_back(id[v]);
++ deg[id[v]];
}
}
}
std::queue<int> q;
i64 maxd = 0, ans = 0;
for (int i = 0; i < scc_cnt; ++ i) {
if (!deg[i]) {
q.push(i);
f[i] = w[i];
d[i] = cnt[i];
}
}
while (q.size()) {
int u = q.front(); q.pop();
if (d[u] > maxd) {
maxd = d[u];
ans = f[u];
} else if (d[u] == maxd) {
ans = std::min(ans, f[u]);
}
for (auto & v : adj1[u]) {
if (d[v] < d[u] + cnt[v]) {
d[v] = d[u] + cnt[v];
f[v] = f[u] + w[v];
} else if (d[v] == d[u] + cnt[v]) {
f[v] = std::min(f[v], f[u] + w[v]);
}
if ( -- deg[v] == 0) {
q.push(v);
}
}
}
std::cout << maxd << " " << ans << "\n";
}