Codeforces Round 668 (Div. 2)

十月 27, 2020 10186

做题情况

7 分钟 A，23 分钟 B，然后想了一场 C，D 直接跳过不看，E 有了初步思路但不大会写

A. Permutation Forgery

解题思路

猜结论：直接把序列反转即可
手玩了一下确实是对的

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 100 + 10;

int n, aa[MAXN];

int main() {
    int T = read();
    while (T --> 0) {
        n = read();
        for (int i = 1; i <= n; ++i) aa[i] = read();
        std::reverse(aa + 1, aa + 1 + n);
        for (int i = 1; i <= n; ++i) printf("%d%c", aa[i], " \n"[i == n]);
    }
    return 0;
}

B. Array Cancellation

解题思路

仍然先手玩一下，发现一个初步性质：

对于一个正数，应把它转移到它后面的第一个负数，转移完后剩下的正数之和即为答案

紧接着发现这个性质可以变得更简单一些：

对于一个正数，也可以把它转移给它后面的第一个正数，然后让那个正数往后转移，答案不变

所以我们可以确定最终做法：

对于一个正数，应把它转移到它的下一个数，转移完后剩下的正数之和即为答案。

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e5 + 10;

struct Node {
    int num, id;
} node[MAXN];

int n;
long long int aa[MAXN];

int main() {
    int T = read();
    while (T --> 0) {
        n = read();
        for (int i = 1; i <= n; ++i) {
            aa[i] = read();
        }
        for (int i = 1; i < n; ++i) {
            if (aa[i] > 0) {
                aa[i + 1] += aa[i];
                aa[i] = 0;
            }
        }
        long long int ans = 0;
        for (int i = 1; i <= n; ++i) {
            // printf("%d%c", aa[i], " \n"[i == n]);
            if (aa[i] > 0) ans += 1ll * aa[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C. Balanced Bitstring

解题思路

手玩的时候可以发现一个很重要的性质（反正我没发现）：

一个字符串为 (0-indexed) k-Balanced Bitstring 的必要条件是：第 i 位与第 i mod k 位的字母相同。

这个性质比较好理解，因为如果 s[i..i + k - 1]这个区间内的字符串为 k-Balanced Bitstring 的话，那么这个窗口在往后移一格时，为了保证下一个区间也是 k-Balanced Bitstring，就需要满足扔掉的字符（s[i]）和加进来的字符（s[i + k]）相同，才能不改变 0 数和 1 数的关系。

有了这个性质，我们就可以从前往后扫一遍，将问号分成三类：需要填 0 的、需要填 1 的、不确定的。如果一个模 k 相等的位置同时需要填 0 和 1，就出现了矛盾直接 fail。最后统计一下，判断一下不确定的位置够不够用就行了。

代码实现

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
const int MAXN = 3e5 + 10;

int n, k;
char ss[MAXN];
int measure[MAXN];

int main() {
    std::ios::sync_with_stdio(false);
    int T; scanf("%d", &T);
    while (T --> 0) {
        scanf("%d %d", &n, &k);
        scanf("%s", ss + 1); 
        int cannot = 0, ones = 0;
        for (int i = 0; i < k; ++i) measure[i] = -1; // 不确定
        for (int i = 1; i <= n; ++i) {
            if (ss[i] == '1') {
                if (measure[i % k] == 0) {
                    goto fail;
                }
                measure[i % k] = 1;
            }
            if (ss[i] == '0') {
                if (measure[i % k] == 1) {
                    goto fail;
                }
                measure[i % k] = 0;
            }
        }
        for (int i = 0; i < k; ++i) {
            if (measure[i] == -1) ++cannot;
            else ones += measure[i];
        }
        if (ones <= (k >> 1) && (k >> 1) <= ones + cannot) {
            puts("YES"); continue;
        }
        fail:;
        puts("NO");
    }
    return 0;
}

D. Tree Tag

解题思路

先考虑初始情况，如果 Alice 一步就能到达 Bob 那就肯定没戏，即 da \geq \text{dis}(a, b) 。

再考虑极限情况。一条长为 \text{len} 的链时，Alice 肯定会不断把 Bob 往绝路逼，那么 Bob 只有一步跨过 Alice 才能有赢的机会，也就是 db > 2da ，否则就直接凉凉。另外，注意到如果 2da \geq \text{len} ，那么 Alice 两步可以到的点覆盖了整条链，Bob 无处可逃。

然后推广一下极限情况到树上。注意到树最长的链是（假设长为 \text{len} ）直径，那么如果 2da < \text{len} ，Bob 躲到直径上就可以一直逃脱 Alice 的追捕。反之，如果 2da \geq \text{len} ，那么 Alice 只要站到重心上，就可以覆盖整棵树，Bob 仍然无路可逃。

最后总结一下：当且仅当下列三个条件至少有一个满足时，Alice 一定胜利，否则 Bob 一定胜利。

  • da \geq \text{dis}(a, b)
  • 2da \geq 树的直径
  • 2da \geq db

那么代码就一个 DFS 就完事了。

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e5 + 10;

int n, a, b, da, db, farthest;
std::vector<int> G[MAXN];

int dep[MAXN];

void Dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    if(dep[u] > dep[farthest]) {
        farthest = u;
    }
    for(int v : G[u]) {
        if(v != fa) {
            Dfs(v, u);
        }
    }
}
int main() {
    int T = read();
    while(T --> 0) {
        n = read(); a = read(); b = read();
        for (int i = 1; i <= n; ++i) G[i].clear();
        da = read(); db = read();
        for(int i = 1; i < n; ++i) {
            int u = read(); int v = read();
            G[u].push_back(v); G[v].push_back(u);
        }
        if(db <= (da << 1)) { puts("Alice"); continue; }
        farthest = a; Dfs(a, 0);
        if(dep[b] <= da + 1) { puts("Alice"); continue; }
        Dfs(farthest, 0);
        if (dep[farthest] - 1 <= (da << 1)) {
            puts("Alice");
            continue;
        } else {
            puts("Bob");
            continue;
        }
    }
    return 0;
}

E. Fixed Point Removal

解题思路

手玩一下可以发现一个事：一次删除应是删除最后一个能删除的数，这样不会影响到前面可以删除的数字，后面的数字说不定也能删了，稳赚不亏

精确描述一下：

对于一个数 a_i ，它能被删除的条件是 i - a_i = 0 。（这里编号是随着删除而移动的）

那么我们干脆重定义并动态维护 a_i := i - a_i ，表示这个数被删的条件是在前面删几个数，如果是 0 就可以直接删，如果是负数就说明永远删不了，不妨令其为 n + 1。

怎么维护？

上面是我考场上想出的东西，下面是看题解才学会的东西。
其实可以直接拿线段树维护 a 。具体地，我们把操作离线下来，并按照左端点从大到小排序，依次考虑从左边加入一个数会造成什么影响。

对于我们加入的一个数 j ，

  • a_j = 0 ：可以删，把这个数设为已删的状态（ a_j := n ）并加入树状数组，后面所有数集体 -1
  • a_j > 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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 3e5 + 10;

int n, q;
int aa[MAXN];

struct BIT {
    int seq[MAXN];

    #define lb(x) ((x) & (-(x)))
    BIT() { memset(seq, 0, sizeof seq); }
    void insert(int s, int sz = 1) {
        while (s <= n) {
            seq[s] += sz; s += lb(s);
        }
    }
    int query(int s) {
        int ret = 0; while (s >= 1) {
            ret += seq[s]; s -= lb(s);
        }
        return ret;
    }
    int query(int x, int y) {
        return query(y) - query(x - 1);
    }
} bit;

int minn[MAXN << 2], tag[MAXN << 2];

#define ls (p << 1)
#define rs (p << 1 | 1)

void Update(int p) {
    minn[p] = std::min(minn[ls], minn[rs]);
}

void buildTree(int p, int l, int r) {
    if (l == r) {
        minn[p] = aa[l]; tag[p] = 0; return;
    } int mid = (l + r) >> 1;
    buildTree(ls, l, mid); buildTree(rs, mid + 1, r);
    Update(p);
}

void Add(int p, int k) {
    minn[p] += k; tag[p] += k;
}

void Pushdown(int p) {
    if (tag[p]) {
        Add(ls, tag[p]); Add(rs, tag[p]); tag[p] = 0;
    }
}

void Modify(int p, int l, int r, int ll, int rr, int k) {
    if (ll <= l && r <= rr) {
        Add(p, k); return;
    }
    Pushdown(p);
    int mid = (l + r) >> 1;
    if (ll <= mid) Modify(ls, l, mid, ll, rr, k);
    if (mid + 1 <= rr) Modify(rs, mid + 1, r, ll, rr, k);
}

void Work(int p, int l, int r, int ll, int rr) {
    if (minn[p] > 0) return; // 整段区间都没有能删的，继续递归没意义
    if (l == r) {
        // 找到一个可以删的数
        int pos = l;
        if (pos + 1 <= n) Modify(1, 1, n, pos + 1, n, -1); // 后面的都 -1
        bit.insert(pos); minn[p] = n; // 不能删了
        return;
    } Pushdown(p);
    int mid = (l + r) >> 1;
    if (ll <= mid) Work(ls, l, mid, ll, rr);
    if (mid + 1 <= rr) Work(rs, mid + 1, r, ll, rr);
    Update(p);
}

struct Queries {
    int l, r, id, ans; Queries(int _l = 0, int _r = 0, int _i = 0) {
        l = _l; r = _r; id = _i; ans = 0;
    }
    bool operator < (const Queries &th) const {
        return l > th.l;
    }
} queries[MAXN];

bool cmp1(const Queries &a, const Queries &b) {
    return a.id < b.id;
}

int main() {
    n = read(); q = read();
    for (int i = 1; i <= n; ++i) {
        aa[i] = i - read();
        if (aa[i] < 0) aa[i] = n + 1;
    }
    for (int i = 1; i <= q; ++i) {
        queries[i].l = read();
        queries[i].r = read();
        queries[i].id = i;
    } std::sort(queries + 1, queries + 1 + q);
    buildTree(1, 1, n);
    for (int i = 1, l = n; i <= q; ++i) {
        while (queries[i].l + 1 <= l) {
            // printf("i = %d, l = %d\n", i, l);
            Work(1, 1, n, l, n);
            --l;
        } queries[i].ans = bit.query(queries[i].l + 1, n - queries[i].r);
    }
    std::sort(queries + 1, queries + 1 + q, cmp1);
    for (int i = 1; i <= q; ++i) {
        printf("%d\n", queries[i].ans);
    }
    return 0;
}