Codeforces Round #911 (Div. 2) A~E

A.Cover in Water（思维）

题意：

有一个 $\times n$ 的水池，里面有些格子可以加水，有些格子是被堵上的，你可以进行以下两种操作：

1.往一个空的格子里加水
2.移除一个有水的格子中的水，并将这些水添加到另一个格子中

且如果两个有水的格子中间都是空格子，那么水将覆盖中间所有的空格子。

问最少进行多少次操作1，才能使所有空格子中均有水。

分析：

不难发现，只要出现一段长度大于2的连续空格子，那么就可以在这段格子两端各使用一次操作1，然后这段格子中间就全部被水覆盖了，且无论怎么使用操作2，由于两端均有水，取完之后格子也不会变空，可以无限取，即一定只需要两次操作1.

如果没有任意一段连续的空格子长度大于2，那么只能对每个格子使用一次操作1，才能使所有格子都包含水，此时的操作1使用次数就是空格子的个数。

代码：

#include <bits/stdc++.h>
using namespace std;void solve() {int n;string s;cin >> n >> s;int ans = 0, cnt = 0;for (int i = 0; i < n; i++) {if (s[i] == '.') {cnt++;if (cnt > 2) {cout << 2 << endl;return;}} else {ans += cnt;cnt = 0;}}ans += cnt;//不要忘了加上最后一段cout << ans << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

B.Laura and Operations（思维）

题意：

给出 $a$ 个 $1$ ， $b$ 个 $2$ ， $c$ 个 $3$ ，每次可以选择 $\sim 3$ 中的两个不同数字，消除这两个数字，并产生一个新的数字，这个产生的数字与消除的两个数字均不同，问有没有方法可以使最后只剩下 $1, 2, 3$ 中的一种（能否剩下 $1, 2, 3$ 的可能性单独输出）

分析：

首先，如果想要剩下的全部都是 $1$ ,那么就需要先将 $2$ 和 $3$ 的数量变为相同的，再通过一直消除 $2$ 和 $3$ 使得只剩下 $1$ 。

那么要怎么让 $2$ 和 $3$ 数量相同呢？

可以先消除 $1$ 和出现较多的数，不难发现，如果此时没有 $1$ ，是无法完成消除操作的，此时无解。

而每次消除 $1$ 和出现较多的数字，每次进行消除，可以使较大出现次数和较小出现次数之间的差减少2(不用担心1是否不够用，通过消除 $2$ 和 $3$ 可以再获得 $1$ )，那么如果这两个数的出现次数差为奇数，是无法将这两个数完全消除的，此时也是无解。

结论：只要另外两个数的差为偶数，且满足以下两个要求之一，就可以完成消除操作：

想要留下的数字出现次数不为0
需要消除的两个数字出现次数已经相同

代码：

#include <bits/stdc++.h>
using namespace std;void solve() {int a, b, c;cin >> a >> b >> c;if (abs(b - c) % 2 == 0 && (min(c, b) != 0 || a != 0)) {cout << 1;} else {cout << 0;}if (abs(a - c) % 2 == 0 && (min(a, c) != 0 || b != 0)) {cout << ' ' << 1;} else {cout << ' ' << 0;}if (abs(a - b) % 2 == 0 && (min(a, b) != 0 || c != 0)) {cout << ' ' << 1;} else {cout << ' ' << 0;}cout << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

C.Anji’s Binary Tree（树形DP）

题意：

有一棵二叉树，树上每个节点均写着"ULR"中的一个字符，这三个字符的含义如下：

'U'：当你走到这个节点，你需要向这个节点的父节点移动
'L'：当你走到这个节点，你需要向这个节点的左孩子移动
'R'：当你走到这个节点，你需要向这个节点的右孩子移动

问：你最少需要修改多少次节点上的字符，能使你从根节点出法到达叶节点。

分析：

当前节点为'U'：想要向叶节点移动，遇到'U'就需要修改，此时不需要考虑节点被修改成了什么。
当前节点为'L'：此时往左子树走不需修改次数，往右子树走需一次修改次数，记录两者中的较小值
当前节点为'R'：此时往右子树走不需修改次数，往左子树走需一次修改次数，记录两者中的较小值

从根节点开始搜索，到达叶节点返回，记录最小的修改次数即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3fint n, L[300005], R[300005];
string s;int dfs(int x) {if (x == 0) return INF;//走到空节点了，返回极大值if (L[x] == 0 && R[x] == 0) return 0;//走到叶节点，返回0if (s[x - 1] == 'U') {return min(dfs(L[x]), dfs(R[x])) + 1;} else if (s[x - 1] == 'L') {return min(dfs(L[x]), dfs(R[x]) + 1);} else {return min(dfs(L[x]) + 1, dfs(R[x]));}
}void solve() {cin >> n >> s;for (int i = 1; i <= n; i++) cin >> L[i] >> R[i];cout << dfs(1) << endl;
}int main() {int Case;cin >> Case;while (Case--) {solve();}return 0;
}

D.Small GCD（容斥）

题意：

给出一个包含 $n$ 个元素的数组和一个函数 $f (a, b, c) = g c d (a, b)$ ，其中 $a < b < c$ 。

求： $\sum\limits_{i = 1}^{n}\sum\limits_{j = i + 1}^{n}\sum\limits_{k = j + 1}^{n}f(a_i, a_j, a_k)$ 。

分析：

由于每轮取得三个数实际上只有两个较小数字会对答案产生影响，因此可以先对输入的元素进行排序。

然后使用两层for循环对 $a_i,a_j$ 进行枚举，此时的 $gcd(a_i, a_j)$ 的答案对于任意一个 $k$ 都是成立的，即 $a_i,a_j$ 对答案产生的贡献为 $gcd(a_i, a_j) \times (n - j)$ 。

但是，此时的时间复杂度为 $O(n^2)$ ，是无法通过本题的，因此，需要对算法进行优化

优化

先考虑所有因数对答案的贡献，那么只需一层for循环，遍历到 $a_j$ 时，如果 $a_j$ 的因数 $b$ 在前面出现过，那么这个因数对答案的贡献就是在前面出现的次数(包含该因数的 $a_i$ 个数)乘上后面的数字个数，即： $\times (n - i)$ 。

而对于因数分解的时间复杂度是比较慢的，需要先对 $10^5$ 以内的数预处理所有因子。

求完所有因子产生的贡献后，需要考虑实际上求出的贡献计算了很多重复的情况，如因子为 $2$ 的贡献中包含了所有 $2$ 的倍数的贡献。需要将这些重复计算的贡献减去。

此时可以从后往前对因子进行遍历，每次先将所有由倍数产生的贡献减去，然后计算当前因子产生的贡献，即当前因子的出现次数乘上因子的值。

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;const int N = 1e5 + 5e2;int n, a[N];
ll sum[N], cnt[N];vector<int> fact[N];void init() {for (int i = 1; i < N; i++) {for (int j = i; j < N; j += i) {fact[j].push_back(i);//预处理因子}}
}void solve() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++) {int len = fact[a[i]].size();for (int j = 0; j < len; j++) {sum[fact[a[i]][j]] += cnt[fact[a[i]][j]] * (n - i);cnt[fact[a[i]][j]]++;}}ll ans = 0;for (int i = a[n]; i >= 1; i--) {for (int j = i + i; j < N; j += i) {sum[i] -= sum[j];}ans += sum[i] * i;}cout << ans << endl;
}int main() {init();int Case;cin >> Case;while (Case--) {//初始化memset(sum, 0, sizeof (sum));memset(cnt, 0, sizeof (cnt));solve();}return 0;
}

E. Transitive Graph(图论)

题意：

给定一个有向图，点有点权，重复进行如下操作：如果存在边 $a - > b$ ， $b - > c$ 但不存在 $a - > c$ 边，则添加边 $a - > c$ 。直到不存在这样的 $(a, b, c)$ 。做完操作后，询问点权之和最小且经过点数最多的简单路径的长度以及点权之和。

分析：

可以用强连通分离缩点,可以发现每个强连通分量在传递闭包中是一个完全图,因为我们需要的是最长路，所以只要走到这个强连通分量就必须走完分量中的所有点。
我们先用 $t a r jan$ 进行缩点，原图中的简单路径就是缩点后的 $D A G$ 的路径，在 $D A G$ 上跑双关键字的 $d p$ 即可。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int ver[maxn], next1[maxn], head[maxn], dfn[maxn], low[maxn];
int stack1[maxn], vis[maxn], c[maxn];
vector<int> scc[maxn]; // 强连通分量
ll tot, top, num, cnt;
ll a[maxn];
vector<int> g[maxn];
ll sum[maxn];
ll dis[maxn];
struct node {int sum, num;
} aa[maxn];void add(int x, int y) {ver[++tot] = y;next1[tot] = head[x];head[x] = tot;
}int n, m;
ll dp[maxn];void init() {num = 0;top = 0;for (int i = 0; i <= cnt; i++)scc[i].clear();cnt = tot = 0;for (int i = 1; i <= n; i++) {sum[i] = 0;dis[i] = 0;dp[i] = 0;head[i] = 0;g[i].clear();dfn[i] = low[i] = stack1[i] = vis[i] = c[i] = 0;}
}void tarjan(int x) {num++;dfn[x] = low[x] = num;top++;stack1[top] = x;vis[x] = 1;for (int i = head[x]; i; i = next1[i]) {int y = ver[i];if (!dfn[y]) {tarjan(y);low[x] = min(low[x], low[y]);} else if (vis[y]) {low[x] = min(low[x], dfn[y]);}}if (dfn[x] == low[x]) {cnt++;int tmp;do {tmp = stack1[top--];vis[tmp] = 0;c[tmp] = cnt; // 每个点所属于的强连通分量编号scc[cnt].push_back(tmp);sum[cnt] += a[tmp];} while (x != tmp);}
}int main() {int t;cin >> t;while (t--) {cin >> n >> m;init();for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;add(x, y);}for (int i = 1; i <= n; i++) {if (!dfn[i])tarjan(i);}// cnt就是强连通块数量for (int x = 1; x <= n; ++x) {for (int i = head[x]; i; i = next1[i]) {int y = ver[i];if (c[x] != c[y]) {g[c[x]].push_back(c[y]);}}}for (int i = 1; i <= cnt; i++) {aa[i].sum = sum[i];aa[i].num = scc[i].size();}for (int i = 1; i <= cnt; i++) {// 遍历出边if (g[i].empty()) {dis[i] = scc[i].size();dp[i] = sum[i];} elsefor (auto u: g[i]) {if (dis[u] + scc[i].size() > dis[i]) {dis[i] = dis[u] + scc[i].size();dp[i] = dp[u] + sum[i];} else if (dis[u] + scc[i].size() == dis[i]) {dp[i] = min(dp[i], dp[u] + sum[i]);}}}ll mlen = 0;for (int i = 1; i <= cnt; i++)mlen = max(mlen, dis[i]);ll ans = 1e18;for (int i = 1; i <= cnt; i++)if (dis[i] == mlen)ans = min(ans, dp[i]);cout << mlen << " " << ans << endl;}return 0;
}