AtCoder Beginner Contest 460

ABC460 D

题目大意：有一个 $H$ 行 $W$ 列的网格，其中第 $i$ 行第 $j$ 列的单元格被称为单元格 $(i,j)$。所有单元格都被涂上了黑白两种颜色，网格被描述为 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,…,S_H$。如果 $S_i$ 的第 $j$ 个字符为 .，则单元格 $(i,j)$ 为白色；如果 $S_i$ 的第 $j$ 个字符为 #，则单元格 $(i,j)$ 为黑色。需要执行 $10^{100}$ 次操作。- 规则同时适用于所有单元格。- 对于一个白色的单元格，当且仅当它相邻的单元格中有一个是黑色，它就会变成黑色。

数据范围：$1\leq H\times W\leq10^6$，$|S_i| = W$，$S \in {\mathtt{.},\mathtt{#}}^*$。

思路：

 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
constexpr int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
constexpr int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void solve() {
    ll n, m;
    cin >> n >> m;
    vector<string> ma(n);
    rep(i, 0, n - 1) cin >> ma[i];
    vvi dis(n, vi(m, -1));
    queue<pii> q;
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            bool flag = false;
            rep(v, 0, 7) {
                int ax = i + dx[v], ay = j + dy[v];
                if (ax < 0 || ax >= n || ay < 0 || ay >= m || ma[ax][ay] == ma[i][j]) continue;
                flag = true;
            }
            if (flag) {
                dis[i][j] = 0;
                q.emplace(i, j);
            }
        }
    }
    if (q.empty()) {
        rep(i, 0, n - 1) {
            rep(j, 0, m - 1) cout << '.';
            cout << endl;
        }
        return;
    }
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        rep(i, 0, 7) {
            int ax = x + dx[i], ay = y + dy[i];
            if (ax < 0 || ax >= n || ay < 0 || ay >= m || dis[ax][ay] != -1 || ma[ax][ay] != ma[x][y]) continue;
            dis[ax][ay] = dis[x][y] + 1;
            q.emplace(ax, ay);
        }
    }
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (ma[i][j] == '#') {
                if (dis[i][j] & 1)
                    cout << '.';
                else
                    cout << '#';
            } else {
                if (dis[i][j] & 1)
                    cout << '#';
                else
                    cout << '.';
            }
        }
        cout << endl;
    }
    return;
}

ABC460 E

出处：ABC460 E

题目大意：对两个正整数 $a,b$，定义 $\operatorname{concat}(a,b)$ 为 $a,b$ 连接书写时得到的整数。严格来说， $\operatorname{concat}(a,b)$ 的定义如下： - 将 $a,b$ 在十进制下转换成的字符串 $A,B$ 顺次连接得到字符串 $C$。此时 $C$ 在十进制下转换成的整数即为 $\operatorname{concat}(a,b)$。给定正整数 $N,M$，需要求满足 $\operatorname{concat}(x,y)\equiv x+y \pmod{M}$ 的数对 $(x,y)(x,y\le N)$ 的个数除以 $998244353$ 的余数。

数据范围：$1\leq T\leq 10^4$，$1\leq N\leq 10^{18}$，$2\leq M\leq 10^9$。

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
const ll MOD = 998244353;
void solve() {
    ll n, m;
    cin >> n >> m;
    vector<i128> tem(20);
    tem[0] = 1;
    rep(i, 1, 19) tem[i] = tem[i - 1] * 10;
    ll ans = 0;
    rep(i, 1, 19) {
        ll tem2 = max((i128)0, min((i128)n, tem[i] - 1) - tem[i - 1] + 1);
        ll tem3 = (tem[i] - 1) % m;
        ans = (ans + tem2 % MOD * ((n / (m / __gcd(m, tem3)))%MOD) % MOD) % MOD;
    }
    cout << ans << endl;
    return;
}

ABC460 F

出处：ABC460 F

题目大意：有一棵有 $N$ 个节点的树，节点的编号为 $1,2,\dots,N$，第 $i$ 条边连接节点 $U_i$ 和 $V_i$。初始时所有节点都被涂上了黑色。需要按输入顺序处理 $Q$ 次询问。- 给定整数 $x(1\leq x \leq N)$，反转节点 $x$ 的颜色，然后求出最远的两个黑色节点间的距离。

数据范围：$3 \leq N \leq 10^5$，$1 \leq U_i, V_i \leq N$，$1 \leq Q \leq 10^5$，$1 \leq x \leq 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
 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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
// 重链剖分 HLD
// 用法：HLD hld(n); hld.add_edge(x, y); hld.work(root);
// hld.lca(x, y) 查询 LCA；hld.get_path(x, y) 返回若干段 DFS 序区间。
// hld.dfn[x]..hld.dfn[x]+hld.siz[x]-1 是 x 的子树区间。
struct HLD {
    int n, tim = 0;
    vector<vi> g;
    vi fa, dep, siz, son, top, dfn, rnk;

    HLD(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        g.assign(n, {});
        fa.assign(n, -1);
        dep.assign(n, 0);
        siz.assign(n, 0);
        son.assign(n, -1);
        top.assign(n, 0);
        dfn.assign(n, 0);
        rnk.assign(n, 0);
        tim = 0;
    }

    void add_edge(int x, int y) {
        g[x].push_back(y);
        g[y].push_back(x);
    }

    void work(int root = 0) {
        auto dfs1 = [&](auto&& self, int x, int p) -> void {
            fa[x] = p;
            siz[x] = 1;
            for (int y : g[x]) {
                if (y == p) continue;
                dep[y] = dep[x] + 1;
                self(self, y, x);
                siz[x] += siz[y];
                if (son[x] == -1 || siz[y] > siz[son[x]]) son[x] = y;
            }
        };
        auto dfs2 = [&](auto&& self, int x, int tp) -> void {
            top[x] = tp;
            dfn[x] = tim;
            rnk[tim++] = x;
            if (son[x] != -1) self(self, son[x], tp);
            for (int y : g[x]) {
                if (y == fa[x] || y == son[x]) continue;
                self(self, y, y);
            }
        };
        dfs1(dfs1, root, -1);
        dfs2(dfs2, root, root);
    }

    int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            x = fa[top[x]];
        }
        return dep[x] < dep[y] ? x : y;
    }

    int dist(int x, int y) {
        int z = lca(x, y);
        return dep[x] + dep[y] - 2 * dep[z];
    }

    vector<pii> get_path(int x, int y) {
        vector<pii> res;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            res.push_back({dfn[top[x]], dfn[x]});
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) swap(x, y);
        res.push_back({dfn[x], dfn[y]});
        return res;
    }
};
HLD* tot;
struct Info {
    ll x, y, ans;
    Info(ll x = -1, ll y = -1, ll ans = -1) : x(x), y(y), ans(ans) {}
};
Info operator+(const Info& a, const Info& b) {
    if (a.ans == -1) return b;
    if (b.ans == -1) return a;
    Info c;
    auto calc = [&](int x, int y) -> void {
        int tem = tot->dist(x, y);
        if (tem > c.ans) c = Info(x, y, tem);
    };
    calc(a.x, a.y);
    calc(b.x, b.y);
    calc(a.x, b.x);
    calc(a.x, b.y);
    calc(a.y, b.x);
    calc(a.y, b.y);
    return c;
}
template <typename T>
class SegmentTree {
    int n;
    vector<T> tree;
    T merge_val(T a, T b) const { return a + b; }  // 合并子树

    void maintain(int node) {  // 维护整棵树
        tree[node] = merge_val(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(const vector<T>& a, int node, int l, int r) {
        if (l == r) {
            tree[node] = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, node * 2, l, m);
        build(a, node * 2 + 1, m + 1, r);
        maintain(node);
    }  // 建树

    void update(int node, int l, int r, int i, T val) {
        if (l == r) {
            tree[node] = val;
            return;
        }
        int m = (l + r) / 2;
        if (i <= m)
            update(node * 2, l, m, i, val);
        else
            update(node * 2 + 1, m + 1, r, i, val);
        maintain(node);
    }  // 更新i处的值为val

    T query(int node, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return tree[node];
        int m = (l + r) / 2;
        if (qr <= m) return query(node * 2, l, m, ql, qr);
        if (ql > m) return query(node * 2 + 1, m + 1, r, ql, qr);
        T l_res = query(node * 2, l, m, ql, qr);
        T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
        return merge_val(l_res, r_res);
    }  // 查询[ql,qr]的值

    int find_first(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node].val < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_first(node << 1, l, m, ql, qr, val);
        if (res != -1) return res;
        return find_first(node << 1 | 1, m + 1, r, ql, qr, val);
    }
    // 若固定左端点，需要记录前缀分段最大值，并加被待求区间完全覆盖的剪枝

    int find_last(int node, int l, int r, int ql, int qr, T val) const {
        if (r < ql || l > qr) return -1;
        if (tree[node].val < val) return -1;
        if (l == r) return l;
        int m = (l + r) >> 1;
        int res = find_last(node << 1 | 1, m + 1, r, ql, qr, val);
        if (res != -1) return res;
        return find_last(node << 1, l, m, ql, qr, val);
    }

public:
    SegmentTree(int n, T init_val) : SegmentTree(vector<T>(n, init_val)) {}

    // 传入一个数组维护
    SegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) { build(a, 1, 0, n - 1); }

    void update(int i, T val) { update(1, 0, n - 1, i, val); }  // 更新i的值为val

    T query(int ql, int qr) const { return query(1, 0, n - 1, ql, qr); }  // 查询[ql,qr]的值

    T get(int i) const { return query(1, 0, n - 1, i, i); }  // 取出i处的值

    // 查询[ql,qr]中第一个满足条件的下标
    int find_first(int ql, int qr, T val) const { return find_first(1, 0, n - 1, ql, qr, val); }

    // 查询[ql,qr]中最后一个满足条件的下标
    int find_last(int ql, int qr, T val) const { return find_last(1, 0, n - 1, ql, qr, val); }
};
void solve() {
    ll n, x, y, q;
    cin >> n;
    vvi ma(n);
    HLD hld(n);
    tot = &hld;
    rep(i, 1, n - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        ma[y - 1].push_back(x - 1);
        hld.add_edge(x - 1, y - 1);
    }
    hld.work(0);
    vi co(n, 1);
    vector<Info> init(n);
    rep(i, 0, n - 1) init[hld.dfn[i]] = Info(i, i, 0);
    SegmentTree<Info> seg(init);
    cin >> q;
    rep(i, 0, q - 1) {
        cin >> x;
        x--;
        co[x] = (co[x] + 1) % 2;
        if (co[x])
            seg.update(hld.dfn[x], Info(x, x, 0));
        else
            seg.update(hld.dfn[x], Info());
        cout << seg.query(0, n - 1).ans << endl;
    }
    return;
}