2002(div1+div2)

A. Distanced Coloring

你从一个神秘的来源收到了一个 $n \times m$ 网格。这个来源还给了你一个神奇的正整数常数 $k$ 。

消息来源告诉你用一些颜色给网格着色，要满足以下条件：

如果 $(x_{1}, y_{1})$ 、 $(x_{2}, y_{2})$ 是两个颜色相同的单元格，那么就是 $max (| x_{1} - x_{2} |, | y_{1} - y_{2} |) \geq k$ 。

您不喜欢使用过多的颜色。请找出给网格着色所需的最少颜色数。

猜的...

void solve() {
    int n, m, k;cin >> n >> m >> k;
    cout << min(k, n) * min(k, m) << '\n';
}

B. Removals Game

爱丽丝得到了 $[1, 2, \dots, n]$ 的排列 $a_{1}, a_{2}, \dots, a_{n}$ ，鲍勃得到了 $[1, 2, \dots, n]$ 的排列 $b_{1}, b_{2}, \dots, b_{n}$ 。他们将用这些数组玩一个游戏。

在每个回合中，会依次发生以下事件：

爱丽丝选择数组中的第一个或最后一个元素，并将其从数组中删除；
鲍勃选择自己数组中的第一个或最后一个元素，并将其从数组中移除。

游戏持续 $n - 1$ 轮，之后两个数组都将只剩下一个元素：数组 $a$ 中的 $x$ 和数组 $b$ 中的 $y$ 。

如果是 $x = y$ ，鲍勃获胜；否则，爱丽丝获胜。求如果双方都以最佳方式下棋，哪一方会赢。

若 $b$ 数组或者颠倒的 $b$ 数组是和 $a$ 数组相等的，则 $A$ win，否则 $B$ win, 还是比较容易看出来的.

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];
    vector<int> c(b);
    reverse(c.begin() + 1, c.end());
    int ok1 = 1, ok2 = 1;
    for (int i = 1;i <= n;i++) {
        if (a[i] != b[i]) {
            ok1 = 0;
        }
        if (a[i] != c[i]) {
            ok2 = 0;
        }
    }
    if (!ok1 && !ok2) {
        cout << "Alice\n";
    } else {
        cout << "Bob\n";
    }
}

C. Black Circles

二维平面上有 $n$ 个圆。其中 $i$ 个圆以 $(x_{i}, y_{i})$ 为圆心。最初，所有圆的半径都是 $0$ 。

圆的半径以每秒 $1$ 个单位的速度增加。

你目前在 $(x_{s}, y_{s})$ 处，你的目标是到达 $(x_{t}, y_{t})$ 处而不触及任何圆的周长（包括到达 $(x_{t}, y_{t})$ 处的时刻）。您可以朝任何方向移动。不过，你的速度限制为每秒 $1$ 个单位。

请判断这是否可行。

只需要判断到达终点时，终点是否被圆包围即可，其实和我刚开始的结论相同。

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> x(n), y(n);
    int sx, sy, tx, ty;
    for (int i = 0;i < n;i++)cin >> x[i] >> y[i];
    cin >> sx >> sy >> tx >> ty;
    int time = ((sx - tx) * (sx - tx) + (sy - ty) * (sy - ty));
    for (int i = 0;i < n;i++) {
        int dis = ((x[i] - tx) * (x[i] - tx) + (y[i] - ty) * (y[i] - ty));
        if (dis <= time) {
            cout << "NO\n";return;
        }
    }
    cout << "YES\n";
}

D1/2. DFS Checker (Easy Version)

给你一棵树 $^{†}$ ，由 $n$ 个顶点组成。顶点的编号从 $1$ 到 $n$ ，根顶点为 $1$ 。我们还给出了一个排列 $p$ 。

您需要回答 $q$ 个查询。每个查询都会给你两个整数 $x$ , $y$ ；你需要交换 $p_{x}$ 和 $p_{y}$ ，并确定 $p_{1}, p_{2}, \dots, p_{n}$ 是否是给定树的有效 DFS 顺序 $^{‡}$ 。

请注意，通过查询，交换是持久的。

DFS 序：

DFS 序并不是唯一的

dfs_order = []

function dfs(v):
    append v to the back of dfs_order
    pick an arbitrary permutation s of children of v
    for child in s:
        dfs(child)
dfs(1)

Solution

这里的 DFS 序代表的是先父亲节点，然后是子节点任意选择一个

这样的 DFS 序满足其节点的子节点一定在其之后，不然就不满足要求。

check 函数是用来检测节点 $u$ 其子树 $v_{i}$ 是否都满足要求： $[p o s_{v_{min}}, p o s_{v_{max}} + s i z_{v_{m a x}} - 1] \in [p o s_{u}, p o s_{u} + s i z_{u} - 1]$

即保证对于所有节点 $u$ ，其子树节点下标能达到的最小值和最大值都在父节点 $u$ 的子树范围内即可

void solve() {
    int n, Q;cin >> n >> Q;
    vector<int> fa(n + 1), p(n + 1), q(n + 1), siz(n + 1, 1);
    set<int> son[n + 1];

    for (int i = 2; i <= n; i++) cin >> fa[i];
    for (int i = n; i >= 2; i--) siz[fa[i]] += siz[i];
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        son[fa[p[i]]].insert(i);
        q[p[i]] = i;
    }

    auto check = [&](int x) ->int {
        if (son[x].size()) {
            return q[x] < *son[x].begin() &&
             *--son[x].end() + siz[p[*--son[x].end()]] <= q[x] + siz[x];
        } else {
            return 1;
        }
        };

    int cnt = 0;
    for (int i = 1; i <= n; i++) cnt += check(i);

    while (Q--) {
        int i, j;cin >> i >> j;
        int x = p[i], y = p[j];
        set<int> s;
        s.insert(x), s.insert(y), s.insert(fa[x]), s.insert(fa[y]);
        for (auto x : s) if (x) cnt -= check(x);
        son[fa[x]].erase(i);
        son[fa[y]].erase(j);
        swap(p[i], p[j]);
        swap(q[x], q[y]);
        son[fa[x]].insert(j);
        son[fa[y]].insert(i);
        for (auto x : s) if (x) cnt += check(x);
        cout << (cnt == n ? "YES" : "NO") << '\n';
    }
}

E. Cosmic Rays

给定一个整数数组 $s_{1}, s_{2}, \dots, s_{l}$ 后，宇宙射线每秒钟都会同时删除 $i = 1$ 或 $s_{i} \neq s_{i - 1}$ 中的所有 $s_{i}$ ，并将剩余部分串联起来，形成新的数组 $s_{1}, s_{2}, \dots, s_{l^{'}}$ 。

将数组的强度定义为数组变空所需的秒数。

给你一个由整数组成的数组，以 $n$ 对的形式压缩，从左到右描述数组。每一对 $(a_{i}, b_{i})$ 代表 $b_{i}$ 的 $a_{i}$ 份，即 $\underset{a_{i} times}{\underset{⏟}{b_{i}, b_{i}, \dots, b_{i}}}$ 。

对于每个 $i = 1, 2, \dots, n$ ，请找出前 $i$ 对所描述序列的强度。

Solution

单调栈

没怎么看懂，但也不再浪费时间了...

#define int long long
void solve() {
    int n;cin >> n;
    vector<pair<int, int>> stk(n + 1);
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        int a, b;cin >> a >> b;
        int len = 0;
        while (stk.size()) {
            if (stk.back().first == b) {
                len += stk.back().second;
                stk.pop_back();
            } else {
                if (a <= 0)break;
                int t = min(a, stk.back().second);
                a -= t;
                len += t;
                stk.back().second -= t;
                if (stk.back().second == 0)stk.pop_back();
            }
        }
        ans += a;len += a;
        stk.push_back({b,len});
        cout << ans << " \n"[i == n];
    }
}