Educational Codeforces Round 54 (A-F)

发表于 | 更新于 | 分类于 | 阅读次数：

日常掉分..

D 被无良学弟 hack 了，这个故事告诉我们 CF 上不要写spfa...

E 比赛时候觉得挺难的（然后溜了），赛后仔细分析了下觉得还是挺妙的。

F 傻傻分析不清，然而题解分析的贼清楚..

最后一题日常不会..

地址

A. Minimizing the String

题意

删除一个字符使得字典序最小

分析

贪心呀，从前往后删第一个 s[i]>s[i-1]。或者最后一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
char s[N];
int n;
int main() {
    cin >> n >> s;
    int ans = n-1;
    for (int i = 0; i < n-1; i++) {
        if (s[i] > s[i+1]) {
            ans = i; break;
        }
    }
    for (int i = 0; i < n; i++) {
        if (i == ans) continue;
        cout << s[i];
    }
    cout << endl;
}

B. Divisor Subtraction

题意

给一个数字 n，每次减去其最小质因子，重复此步骤，问共几次减到 0

分析

如果 n 是质数，就一次。

如果 n 是偶数，就 n/2。

如果 n 是奇数，最小质因子 d 一定是奇数，故 (n-d)/2+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
ll n;
ll solve(ll n) {
    if (n%2 == 0) return n/2;
    for (ll i = 2; i*i <= n; i++)
        if (n%i == 0) return 1+(n-i)/2;
    return 1;
}
int main() {
    cin >> n;
    cout << solve(n) << endl;
}

C. Meme Problem

解一元二次方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
int t, d;
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &d);
        if (d*d-4*d < 0) puts("N");
        else {
            double a = (d+sqrt(d*d-4*d))/2;
            double b = (d-sqrt(d*d-4*d))/2;
            printf("Y %.9f %.9f\n", a, b);
        }
    }
}

D. Edge Deletion

题意

给你一张图，有边权。问你最多留下哪 k 条边，使得原图和新图中由 1 的最短路长度不变的点留下的最多

分析

先建由 1 出发的最短路树，把多余的边全删掉。

还不够的话，从叶子开始删边。（拓扑排序或者别的什么）

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+5;
const ll INF = 1e18;
struct Edge {
    int v;
    ll w;
    int id;
    bool operator < (const Edge& b) const {
        return w > b.w;
    }
};
vector<Edge> G[N];
void addedge(int u, int v, int w, int id) {
    G[u].push_back(Edge{v, w, id});
}
int pre[N], f[N];
ll d[N];
bool vis[N];
typedef Edge Node;
priority_queue<Node> Q;
void Dijkstra(int s, int n) {
    while (!Q.empty()) Q.pop();
    for (int i = 0; i <= n; i++) d[i] = INF, vis[i] = 0;
    d[s] = 0;
    Q.push(Node{s, 0});
    while (!Q.empty()) {
        Node tmp = Q.top(); Q.pop();
        int u = tmp.v;
        if (vis[u]) continue;
        vis[u] = 1;
        for (const auto& e : G[u]) {
            if (!vis[e.v] && d[e.v] > d[u] + e.w) {
                d[e.v] = d[u] + e.w;
                pre[e.v] = e.id;
                f[e.v] = u;
                Q.push(Node{e.v, d[e.v]});
            }
        }
    }
}
int n, m, k;
int cnt[N];
bool val[N];
queue<int> que;
void solve() {
    for (int i = 2; i <= n; i++) cnt[f[i]]++;
    for (int i = 1; i <= n; i++) {
        if (!cnt[i]) que.push(i);
    }
    while (!que.empty()) {
        int v = que.front(); que.pop();
        val[pre[v]] = 0;
        k++;
        if (k == 0) return;
        cnt[f[v]]--;
        if (!cnt[f[v]]) que.push(f[v]);
    }
}
vector<int> ans;
int main() {
	scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        addedge(u, v, w, i);
        addedge(v, u, w, i);
    }
    Dijkstra(1, n);
    for (int i = 2; i <= n; i++) val[pre[i]] = 1;
    for (int i = 1; i <= m; i++) {
        if (val[i]) k--;
    }
    if (k < 0) solve();
    for (int i = 1; i <= m; i++)
        if (val[i]) ans.push_back(i);
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) {
        printf("%d", ans[i]);
        if (i == ans.size()-1) puts("");
        else printf(" ");
    }
}

E. Vasya and a Tree

题意

给定一棵树和若干操作。操作 (v,d,x) 是 v 的子树中与 v 距离小于等于 d 的节点权值都加上 x

问所有操作结束后的每个点的权值。

分析

操作可离线。建一棵基于深度的线段树（或者树状数组），在 DFS 不断修改和查询。

单次修改相当于 区间 [dps(v), dps(v)+d] 加上 x 。

区间修改单点查询。

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

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5+5;
vector<int> G[N];
vector<pii> Q[N];
ll c[N];
void modify(int x, int num) {
    while (x < N) c[x] += num, x += x&-x;
}
ll sum(int x) {
    ll s = 0;
    while (x) s += c[x], x -= x&-x;
    return s;
}
ll ans[N];
int dps[N];
void DFS(int u, int pre) {
    dps[u] = dps[pre]+1;
    for (auto p : Q[u]) {
        int d = p.first, x = p.second;
        modify(dps[u], x);
        modify(dps[u]+d+1, -x);
    }
    ans[u] = sum(dps[u]);
    for (auto v : G[u]) {
        if (v == pre) continue;
        DFS(v, u);
    }
    for (auto p : Q[u]) {
        int d = p.first, x = p.second;
        modify(dps[u],-x);
        modify(dps[u]+d+1, x);
    }
}
int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int q; scanf("%d", &q);
    while (q--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        Q[a].push_back(pii(b, c));
    }
    DFS(1, 1);
    for (int i = 1; i <= n; i++) {
        printf("%lld", ans[i]);
        if (i == n) puts("");
        else printf(" ");
    }
}

F. Summer Practice Report

题意

魔改题意。有 n 个连续的区间，告诉你每个区间里需要放\(x_i\)个物体 a，(y_i\)个物体 b

问你是否有一种放置方法，能不出现连续 k 个以上的 a 或 b（可跨区间）。

分析

设 \(dp[i][0]\) 表示第 i 个区间， 若以 a 物体结尾，末尾最少的 a 物体数量。\(dp[i][1]\)类似。

最后判断 \(dp[n][0]\) 或 \(dp[n][1]\) 是否满足要求即可。

考虑 \(dp[i-1][0]\)转移至\(dp[i][0]\)：

​ 首先要满足 \(x_i \ge \lceil\frac{y_i}{k}\rceil\)，即每 k 个 b 物体后插入一个 a 。

​ 然后当 \(x_i \le y_i*k+1 - dp[i-1][0] \) 时，某尾 a 的数量始终为 1，即每个 b 前面插满 k 个 a ，包括上一段的。

​ \(x_i\)还多的话，则最少为 \(x_i-(y_i*k-dp[i-1][0])\)。

可同理考虑\(dp[i-1][1]\)转移至\(dp[i][0]\)，以及\(dp[i][1]\)的转移。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int n, k;
int x[N], y[N];
int dp[N][2];
int solve1(int pre, int x, int y) {
    if (pre > k) return k+1;
    if (x < (y+pre-1)/k+1) return k+1;
    if (x <= 1ll*y*k) return 1;
    return x-1ll*y*k;
}
int solve2(int pre, int x, int y) {
    if (pre > k) return k+1;
    if (x < (y-1)/k+1) return k+1;
    if (x <= 1ll*y*k-pre) return 1;
    return x-(1ll*y*k-pre);
}
bool solve() {
    for (int i = 1; i <= n; i++) {
        dp[i][0] = min(solve1(dp[i-1][1], x[i], y[i]), solve2(dp[i-1][0], x[i], y[i]));
        dp[i][1] = min(solve1(dp[i-1][0], y[i], x[i]), solve2(dp[i-1][1], y[i], x[i]));
    }
    return dp[n][0] <= k || dp[n][1] <= k;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &y[i]);
    if (solve()) puts("YES");
    else puts("NO");
}