2002(div1+div2)

A. Distanced Coloring

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

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

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

猜的...

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

B. Removals Game

爱丽丝得到了 [1,2,,n] 的排列 a1,a2,,an ,鲍勃得到了 [1,2,,n] 的排列 b1,b2,,bn 。他们将用这些数组玩一个游戏。

在每个回合中,会依次发生以下事件:

游戏持续 n1 轮,之后两个数组都将只剩下一个元素:数组 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 个圆以 (xi,yi) 为圆心。最初,所有圆的半径都是 0

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

你目前在 (xs,ys) 处,你的目标是到达 (xt,yt) 处而不触及任何圆的周长(包括到达 (xt,yt) 处的时刻)。您可以朝任何方向移动。不过,你的速度限制为每秒 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 个顶点组成。顶点的编号从 1n ,根顶点为 1 。我们还给出了一个排列 p

您需要回答 q 个查询。每个查询都会给你两个整数 x , y ;你需要交换 pxpy ,并确定 p1,p2,,pn 是否是给定树的有效 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 其子树 vi 是否都满足要求:[posvmin,posvmax+sizvmax1][posu,posu+sizu1]

即保证对于所有节点 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

给定一个整数数组 s1,s2,,sl 后,宇宙射线每秒钟都会同时删除 i=1sisi1 中的所有 si ,并将剩余部分串联起来,形成新的数组 s1,s2,,sl

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

给你一个由整数组成的数组,以 n 对的形式压缩,从左到右描述数组。每一对 (ai,bi) 代表 biai 份,即 bi,bi,,biai times

对于每个 i=1,2,,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];
    }
}