Codeforces Round #911 (Div. 2) A~E_codeforces round 911 (div. 2)

A.Cover in Water（思维）

题意：

有一个$1\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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

B.Laura and Operations（思维）

题意：

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

分析：

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

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

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

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

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

1. 想要留下的数字出现次数不为0

2. 需要消除的两个数字出现次数已经相同

代码：

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

题意：

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

• 'U'：当你走到这个节点，你需要向这个节点的父节点移动

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

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

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

分析：

• 当前节点为'U'：想要向叶节点移动，遇到'U'就需要修改，此时不需要考虑节点被修改成了什么。

• 当前节点为'L'：此时往左子树走不需修改次数，往右子树走需一次修改次数，记录两者中的较小值

• 当前节点为'R'：此时往右子树走不需修改次数，往左子树走需一次修改次数，记录两者中的较小值

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

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

int 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;//走到叶节点，返回0
    if (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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

D.Small GCD（容斥）

题意：

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

求：$\sum _{i=1}^n\sum _{j=i+1}^n\sum _{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$个数)乘上后面的数字个数，即：$cnt[b]\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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

E. Transitive Graph(图论)

题意：

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

分析：

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

代码：

#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];
            } else
                for (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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

学习交流

以下学习交流QQ群，群号： 546235402，大家可以加群一起交流做题思路，分享做题技巧，欢迎大家的加入。