Codeforces Round #600 (Div. 2)题解。论如何会做五道题，比赛时做出四道，还FST两道。

A. Single Push

        对于这种问题，我们暴力就可以。具体来说找出不一样的地方，然后暴力地判它合不合法。

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
#include <bits/stdc++.h>
using namespace std;
int a[100005], b[100005], n;
vector<int> vec;
inline bool isOk()
{
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i] - vec[i - 1] != 1)
            return false;
    }
    return true;
}
inline int isOk2()
{
    if (vec.size() == 0)
        return 1;
    if (vec.size() == 1 && b[vec[0]] > a[vec[0]])
        return 1;
    int s = b[vec[0]] - a[vec[0]];
    if (s < 0)
        return 0;
    for (int i = 1; i < vec.size(); i++) {
        if (b[vec[i]] - a[vec[i]] != s)
            return 0;
    }
    return 1;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", a + i);
        for (int i = 1; i <= n; i++)
            scanf("%d", b + i);
        vec.clear();
        for (int i = 1; i <= n; i++) {
            if (a[i] != b[i])
                vec.push_back(i);
        }
        if (isOk() && isOk2()) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
    // PAUSE;
    return 0;
}

B. Silly Mistake

        这个题，啊，FST了。
        其实就是一个模拟，这里注意一下由于题目没有最小化天数的要求，当我们发现所有人都走了的时候，就开始下一天，这样能保证正确性。

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
#include <bits/stdc++.h>
using namespace std;
int n, op[100005];
set<int> in, out;
vector<int> ans;
int main()
{
    // DEBUG;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", op + i);
    int num = 0;
    for (int i = 1; i <= n; i++) {
        if (in.empty()) {
            if (num)
                ans.push_back(num);
            num = 0;
            in.clear();
            out.clear();
        }
        if (op[i] > 0) {
            if (in.count(op[i]) || out.count(op[i])) {
                printf("-1");
                return 0;
            }
            in.insert(op[i]);
            ++num;
        }
        else {
            if (in.count(-op[i]) == 0) {
                printf("-1");
                return 0;
            }
            in.erase(-op[i]), ++num, out.insert(-op[i]);
        }
    }
    if (!in.empty()) {
        printf("-1");
        return 0;
    }
    if (num != 0)
        ans.push_back(num);
    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) {
        printf("%d ", ans[i]);
    }
    // PAUSE;
    return 0;
}

C. Sweets Eating

        这个题确实挺有意思的。
        可以看得出来，应该排个序，然后贪心。让甜度较大的尽可能在前面，甜度较小的在后面。
        不过题目要求整整$n$天的，这样做复杂度太高。
        注意到从第$k$个答案更新第$k+1$个时，变化的除了新加入的那一个值之外，还有所有“块”的最后一个（所谓块就是每一天的那$m$个连续的糖果），可以发现这些发生变化的糖果的序号呈公差为$m$的等差数列，并且和是前缀和的形式，这样我们维护一个前缀和，在加入糖果时更新，就可以$O(n)$地做这题。

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
#include <bits/stdc++.h>
using namespace std;
long long n, op[200005], m;
long long ans[200005];
vector<long long> vec[200005];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", op + i);
    sort(op + 1, op + n + 1);
    for (int i = 1; i <= m; i++) {
        long long s = 0;
        vec[i].push_back(0);
        for (int j = i; j <= n; j += m) {
            s += op[j];
            vec[i].push_back(s);
        }
    }
    int at, num;
    ans[1] = op[1];
    for (int i = 2; i <= m; i++) {
        ans[i] = ans[i - 1] + op[i];
    }
    at = 1, num = 1;
    for (int i = m + 1; i <= n; i++) {
        ans[i] = ans[i - 1] + op[i] + vec[at][num];
        if (at == m) {
            at = 1, ++num;
        }
        else
            ++at;
    }
    for (int i = 1; i <= n; i++)
        printf("%lld ", ans[i]);
    // PAUSE;
    return 0;
}

D. Harmonious Graph

        首先来一遍$DFS$染色。
        紧接着，从$n$开始倒着扫，找出它所在连通块的最小编号节点，假设为$s$，易知区间$[s,n]$中的所有点都应该与$n$连通，找出那些不连通的连通块数目，加到答案中，同时更新$s$，这样扫下去，直到遍历整个区间。
        连通性可以用并查集维护，复杂度$O(n)$。

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
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
    int next, to;
} edge[400005];
set<int> ssp;
int n, m, head[200005], cnt = 1, color[200005], ID, vis[200005];
int last[200005], fa[200005];
void DFS(int x)
{
    for (int i = head[x]; i; i = edge[i].next) {
        if (!vis[edge[i].to]) {
            vis[edge[i].to] = 1;
            color[edge[i].to] = color[x];
            DFS(edge[i].to);
        }
    }
}
 
inline void add(int x, int y)
{
    edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
int ff(int x)
{
    return fa[x] == x ? x : fa[x] = ff(fa[x]);
}
int main()
{
    // DEBUG;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    for (int i = n; i >= 1; i--) {
        if (!vis[i])
            vis[i] = 1, color[i] = ++ID, DFS(i);
    }
    for (int i = 1; i <= ID; i++)
        fa[i] = i;
    for (int i = 1; i <= n; i++) {
        if (last[color[i]] == 0)
            last[color[i]] = i;
    }
    int ans = 0;
    for (int i = n, up = last[color[n]];;) {
        int tmp = up;
        for (int j = up; j <= i; j++) {
            if (ff(color[j]) != ff(color[up]))
                ssp.insert(color[j]);
        }
        ans += ssp.size();
        i = up - 1;
        for (int a : ssp) {
            fa[ff(a)] = ff(color[tmp]);
            up = min(last[a], up);
        }
        ssp.clear();
        if (i < 1)
            break;
        if (up > i) {
            up = last[color[i]];
        }
    }
    cout << ans;
    // PAUSE;
    return 0;
}

E. Antenna Coverage

        稍微有一点难的$DP$（其实并没有）。
        首先明确这样一个观点：若一段区间是空白的（就是没有被覆盖），并且这一段空白的右侧有天线，我们应延长右侧的天线而非左侧。
        而对于右侧没有天线的空白，只能延长左侧的天线了。
        根据这个思想，我们可以列出这样一个状态：令$DP(x)$表示$[1,x-1]$都已经被覆盖，现在要覆盖$[x,m]$所需的最佳答案。
        那么就有这样的一个状态转移方程：

        当上式不存满足条件的$i$时，$DP(x)=m-x+1$。
        复杂度$O(nm)$。

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
#include <bits/stdc++.h>
using namespace std;
int n, m, s[100005], dp[100005];
struct P
{
    int a, b;
} p[85];
int DP(int x)
{
    if (x > m)
        return 0;
    if (~dp[x])
        return dp[x];
    if (s[x])
        return dp[x] = DP(x + 1);
    dp[x] = 0x3f3f3f3f;
    bool lk = true;
    for (int i = 1; i <= n; i++) {
        if (p[i].a - p[i].b > x) {
            lk = false;
            dp[x] =
                min(dp[x], p[i].a - x - p[i].b + DP(p[i].a + p[i].a - x + 1));
        }
    }
    if (lk) {
        dp[x] = m - x + 1;
    }
    return dp[x];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].a, &p[i].b);
    }
    for (int i = 1; i <= n; i++) {
        ++s[max(p[i].a - p[i].b, 1)];
        --s[min(m, p[i].a + p[i].b) + 1];
    }
    for (int i = 1; i <= m; i++)
        s[i] += s[i - 1];
    memset(dp, -1, sizeof(dp));
    cout << DP(1);
    // PAUSE;
    return 0;
}

F. Cheap Robot

        好题（我不会做的都是好题）。
        从$1$到$k$节点跑一个多源$Dijkstra$求最短路，可以求出点$u$到充电站的最近距离，记为$d_u$。
        注意到，若机器人在$u$处，其电量不会多于$c-d_u$。并且，当机器人电量少于$d_u$时，将无解。若机器人电量不少于$d_u$，它一定可以补充电量到$c-d_u$，因此我们可以认为机器人时时刻刻保持$c-d_u$的电量。
        如果机器人可以从$u$走到$v$并且答案可行，那么必有：

        等价于：

        这就是一条边合法的充要条件。
        于是我们重建图，将所有边的边权更新为$d_u+d_v+w$。问题转化为查询$a_i$到$b_i$的所有路径上最大值的最小值。
        这是一个经典为题。方式是求最小生成树，然后在树上求两点之间路径上的最大值，可以用倍增法也可以用树链剖分，甚至LCT都可以。

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
129
#include <bits/stdc++.h>
using namespace std;
struct Graph
{
    struct Edge
    {
        int next, to;
        long long v;
    };
    Edge e[500005 << 1];
    int cnt = 1, head[100005];
    inline void add(int x, int y, long long v)
    {
        e[cnt].next = head[x], e[cnt].v = v;
        e[cnt].to = y, head[x] = cnt++;
    }
} g;
struct E
{
    int from, to;
    long long dis;
    bool operator<(E e)
    {
        return dis < e.dis;
    }
};
struct Node
{
    int at;
    long long dis;
    Node(int a, long long s) : at(a), dis(s) {}
    bool operator<(const Node& s) const
    {
        return dis > s.dis;
    }
};
priority_queue<Node> pq;
vector<E> vec;
int n, m, k, q, fa[100005], gr[20][100005], dep[100005];
long long dis[100005], maxn[20][100005];
int ff(int x)
{
    return fa[x] == x ? x : fa[x] = ff(fa[x]);
}
void DFS(int x)
{
    for (int i = g.head[x]; i; i = g.e[i].next) {
        if (dep[g.e[i].to])
            continue;
        dep[g.e[i].to] = dep[x] + 1;
        gr[0][g.e[i].to] = x;
        maxn[0][g.e[i].to] = g.e[i].v;
        for (int j = 1; j < 20; j++) {
            gr[j][g.e[i].to] = gr[j - 1][gr[j - 1][g.e[i].to]];
            maxn[j][g.e[i].to] =
                max(maxn[j - 1][g.e[i].to], maxn[j - 1][gr[j - 1][g.e[i].to]]);
        }
        DFS(g.e[i].to);
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for (int i = 1, x, y, z; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        g.add(x, y, z);
        g.add(y, x, z);
    }
    for (int i = 1; i <= k; i++)
        g.add(n + 1, i, 0);
    for (int i = 1; i <= n + 1; i++)
        dis[i] = 1ll << 60;
    dis[n + 1] = 0, pq.push(Node(n + 1, 0));
    while (!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        if (t.dis != dis[t.at])
            continue;
        for (int i = g.head[t.at]; i; i = g.e[i].next) {
            if (dis[g.e[i].to] > dis[t.at] + g.e[i].v) {
                dis[g.e[i].to] = dis[t.at] + g.e[i].v;
                pq.push(Node(g.e[i].to, dis[g.e[i].to]));
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        for (int j = g.head[i]; j; j = g.e[j].next) {
            E e;
            e.from = i, e.to = g.e[j].to;
            e.dis = dis[i] + dis[g.e[j].to] + g.e[j].v;
            vec.push_back(e);
        }
    }
    sort(vec.begin(), vec.end());
    g.cnt = 1, memset(g.head, 0, sizeof(g.head));
    for (auto s : vec) {
        if (ff(s.from) != ff(s.to)) {
            fa[ff(s.from)] = ff(s.to);
            g.add(s.from, s.to, s.dis);
            g.add(s.to, s.from, s.dis);
        }
    }
    dep[1] = 1, DFS(1);
    while (q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (dep[b] < dep[a])
            swap(a, b);
        long long ans = 0;
        for (int i = 19; i >= 0; i--) {
            if (dep[gr[i][b]] >= dep[a])
                ans = max(ans, maxn[i][b]), b = gr[i][b];
        }
        if (a != b) {
            for (int i = 19; i >= 0; i--) {
                if (gr[i][a] != gr[i][b]) {
                    ans = max(ans, max(maxn[i][a], maxn[i][b]));
                    a = gr[i][a];
                    b = gr[i][b];
                }
            }
            ans = max(ans, max(maxn[0][a], maxn[0][b]));
        }
        printf("%lld\n", ans);
    }
    // PAUSE;
    return 0;
}