AtCoder Beginner Contest 337-摩杜云开发者社区

A - Scoreboard (abc337 A)

题目大意

给定$n$场比赛高桥和青木的得分。

问最后是总分，是高桥高还是青木高，还是打平了。

解题思路

累计比较大小即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    LL a = 0, b = 0;
    while (n--) {
        int x, y;
        cin >> x >> y;
        a += x;
        b += y;
    }
    if (a > b)
        cout << "Takahashi" << '\n';
    else if (a < b)
        cout << "Aoki" << '\n';
    else
        cout << "Draw" << '\n';

    return 0;
}

B - Extended ABC (abc337 B)

题目大意

给定一个字符串，问是否形如AAAA..BBBB...CCCC。

解题思路

如果形如上述，那么通过unique函数去重后就是有序的，因此去重排序比较即可。

当然也可以朴素找出A B C的第一次出现和最后一次出现的下标，比较它们之间的下标是否有交集。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin >> s;
    s.erase(unique(s.begin(), s.end()), s.end());
    auto t = s;
    ranges::sort(t);
    if (s == t)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';

    return 0;
}

C - Lining Up 2 (abc337 C)

题目大意

$n$个人站成一排，给定每个人位于某人的右边，还原这个排列。

解题思路

对上述信息作一个映射$r[i]=j$，即第 $j$个人在第 $i$个人的右边。

然后找到最左边的人$l$，不断$l=r[l]$即可还原这个排列。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    map<int, int> pos;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pos[x] = i + 1;
    }
    int st = pos[-1];
    cout << st;
    for (int i = 0; i < n - 1; i++) {
        st = pos[st];
        cout << ' ' << st;
    }
    cout << '\n';

    return 0;
}

D - Cheating Gomoku Narabe (abc337 D)

题目大意

给定$h \times w$的二维网格，格子上有 xo.三种之一。

问最少进行的操作数，使得网格有连续$k$（水平或垂直）个格子都是 o。

操作为：将一个为.的格子改为o。

解题思路

$h\times w$只有 $2\times 10^5$，因此可以枚举这连续$k$个格子的左端点，然后往右的$k$个格子里，不能有 x，然后对.的数量取个最小值。事先预处理一下关于x和.数量的前缀和，即可$O(1)$判断和求答案。当然也可以滑动窗口直接维护这两字符的数量。

水平判一次后，将原图旋转 $90$度再判一次即可。时间复杂度是$O(hw)$。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w, k;
    cin >> h >> w >> k;
    vector<string> s(h);
    for (auto& i : s)
        cin >> i;
    vector<string> t(w);
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            t[i] += s[j][i];
        }
    }
    auto solve = [&](vector<string>& s) {
        int ans = inf;
        for (auto& i : s) {
            vector<int> preo(i.size(), 0), prex(i.size(), 0);
            preo[0] = i[0] == 'o';
            prex[0] = i[0] == 'x';
            for (int j = 1; j < i.size(); ++j) {
                preo[j] = preo[j - 1] + (i[j] == 'o');
                prex[j] = prex[j - 1] + (i[j] == 'x');
            }
            for (int j = 0; j + k - 1 < i.size(); ++j) {
                if (prex[j + k - 1] - (j ? prex[j - 1] : 0) == 0) {
                    ans =
                        min(ans, k - (preo[j + k - 1] - (j ? preo[j - 1] : 0)));
                }
            }
        }
        return ans;
    };
    int ans = min(solve(s), solve(t));
    if (ans == inf)
        ans = -1;
    cout << ans << '\n';

    return 0;
}

E - Bad Juice (abc337 E)

题目大意

交互题。

$n$个果汁，一个是坏的，喝了第二天会拉肚子。现在你要找出这个坏果汁是哪个。

你需要找最少数量的朋友，然后给他们一些果汁喝。一瓶果汁可以给多个朋友喝，一个朋友也可以喝多个果汁。

如果有朋友喝到坏的果汁，则第二天会告诉你他肚子疼。

你需要根据朋友第二天是否肚子疼的情况判断是哪个果汁坏了。

解题思路

一个经典的判断膺品的题。

考虑对果汁编号$0 \sim n - 1$，考虑其二进制。对于坏的果汁$x$，我们需要确定$x$的二进制下，哪些数位是 $1$。

对于第 $i$个朋友（编号从 $0$开始），它的作用就是判断$x$的第$i$位是否为$1$。即把 $0 \sim n - 1$中，所有二进制下第 $i$位为 $1$的都给第 $i$个朋友喝，如果它第二天肚子疼了，说明 $x$的第 $i$位为 $1$。

最终需要 $\lceil \log_2 n \rceil$个朋友。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int num = 0;
    while ((1 << num) < n)
        num++;
    cout << num << '\n';
    for (int i = 0; i < num; ++i) {
        vector<int> candi;
        for (int j = 0; j < n; ++j) {
            if ((j >> i) & 1)
                candi.push_back(j);
        }
        cout << candi.size() << ' ';
        for (auto x : candi)
            cout << x + 1 << ' ';
        cout << '\n';
    }
    cout.flush();
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '1')
            ans += (1 << i);
    }
    cout << ans + 1 << endl;

    return 0;
}

F - Usual Color Ball Problems (abc337 F)

题目大意

给定$n$个球的颜色$c_i$， $m$个盒子。

回答 $n$个询问。

第 $i$个(从$0$开始）询问，将前$i$个球放到最后。

然后依次考虑每个球$c_i$，

若有已经放了$c_i$个球的盒子，且数量不超过 $k$，则放入
否则，若有空盒子，则放入空盒子标号中，多个空盒子就放到标号最小的那个。
否则，吃了它。

问放入盒子的球的数量。

解题思路

先对第$0$个询问模拟求出答案。

注意到转移到下一个询问时，其实只有一个盒子的球会变动，然后感觉暴力模拟下就好了，~~但感觉写不明白~~一觉醒来感觉明白了。

首先整成$2n$个球，后面 $n$个球的颜色与前面相同，这样对于第$i$个询问，就考虑区间$[i,i+n]$的球。

然后预处理出$col[i]$表示颜色为 $i$的球的下标数组。注意到某个颜色被放入盒子的话，它始终是 $col[i]$的一个前缀（当然是从当前位置$i$开始）。因此我们再维护$l[i],r[i]$ 表示$col[i]$中下标在$[l[i], r[i])$的球被放入了盒子里。很显然答案$ans=\sum_{i=1}^{n} r[i] - l[i]$

考虑我们求得了第 $i - 1$个询问的答案，考虑如何求第 $i$个询问，即如何更新$l$数组和 $r$数组。

考虑此时的第一个球的颜色$color$，它将要放到最后面，这会带来什么影响。

首先，该球原来肯定放到了某个盒子里，因为它要被放到后面，所以这个盒子空了，首先$l[color] += 1. r[color] += 1$。
然后再减去该盒子对该颜色球的影响，此时放入盒子的颜色$color$的球会减少，思考减少多少。
假设该颜色球放入盒子数为$x$个，实际上会减少 $x % k + k \times [x % k == 0]$ ，即会减少$x % k$个，如果 $x % k == 0$则减少 $k$个，即该颜色球的最后一个盒子（数量最少）的数量。
考虑这个盒子将会被什么颜色球占领。很显然将会是取得$\min(col[i][r[i]])$对应的颜色，取对应数量的颜色球放入即可，因此还得开一个set维护$col[i][r[i]]$的最小值。

注意更新$l,r$数组时要同步更新 $ans和set。

按上述模拟，总时间复杂度是$O(n\log n)$，只是细节可能有亿点多。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> c(2 * n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
        c[i]--;
        c[i + n] = c[i];
    }
    vector<int> l(n, 0), r(n, 0);
    vector<vector<int>> col(n);
    set<int> minn;
    int ans = 0;
    for (int i = 0; i < 2 * n; ++i) {
        col[c[i]].push_back(i);
    }
    for (int i = 0; i < n; ++i) {
        if (!col[i].empty()) {
            minn.insert(col[i][r[i]]);
        }
    }
    auto modify_r = [&](int color, int R) {
        if (r[color] < col[color].size())
            minn.erase(col[color][r[color]]);
        ans -= r[color] - l[color];
        r[color] = R;
        ans += r[color] - l[color];
        if (r[color] < col[color].size())
            minn.insert(col[color][r[color]]);
    };

    auto push_box = [&](int pos, int R) {
        int color = c[pos];
        int r1 = min((int)col[color].size(), r[color] + k);
        int r2 = ranges::lower_bound(col[color], R) - col[color].begin();

        modify_r(color, min(r1, r2));
    };
    auto pop_box = [&](int pos, int L, int R) {
        int color = c[pos];
        int cnt = (r[color] - l[color]) % k;
        if (cnt == 0)
            cnt = k;

        l[color]++;
        ans--;
        modify_r(color, r[color] + 1);
        modify_r(color, r[color] - cnt);
    };
    auto not_in_box = [&](int pos) {
        int color = c[pos];
        return not(col[color][l[color]] <= pos and pos < col[color][r[color]]);
    };
    for (int i = 0; i < n; ++i) {
        if (not_in_box(i) && m) {
            push_box(i, n);
            --m;
        }
    }
    cout << ans << '\n';

    for (int i = 0; i < n - 1; ++i) {
        pop_box(i, i, i + n);
        if (!minn.empty()) {
            int pos = *minn.begin();
            push_box(pos, i + 1 + n);
        }

        cout << ans << '\n';
    }

    return 0;
}

G - Tree Inversion (abc337 G)

题目大意

给定一棵树，对每个点$u$，求 $f(u)$，表示为 $v$的数量，使得 $u \to v$的路径上有点 $w > v$。

解题思路

这里涉及到三个点$u,v,w$，依次考虑枚举哪个，发现枚举 $u,v$不会求，而枚举 $w$能求。

考虑枚举 $w$，其有 $x$个儿子和一个父亲。然后考虑 $v$在哪里：

若$v$在$w$的一个儿子$son$子树，里面点标号小于 $w$的都是 $v$，假设数量有 $y$个，那么 $w$的其他分支（包括 $w$）的所有点 $u$的 $f(u)+=y$。但这个其他分支的加法不太好做，我们可以维护全局加法$tot+=y$，然后这个儿子$son$子树的所有点$u$都$f(u)-=y$，这样就可以了。
若$v$在 $w$的父亲分支那部分，假设有 $y$个，那 $w$的所有儿子（包括 $w$）的所有点 $u$的 $f(u) += y$，这是一个子树的加法，直接加就好了。

当然这里的子树加法不是子树的每个点都$f(u)+=y$，注意到这里就多次修改，一次查询，因此树上差分就好了，或者说对要操作的子树的根打个标记，最后来一次$DFS$求答案时再传递标记即可。

剩下的问题就是如何求$y$，怎么求$w$的一个儿子$son$子树中，标号小于$w$的数量。

代码里写的比较复杂（不过板子是贴的），用的动态开点的权值线段树+线段树合并。求一个数在一堆区间的排名，一般可以转换成一个权值线段树的前缀和。由于在DFS时，每个点都要开一棵线段树，普通线段树会爆空间，但由于点权值是稀疏的，得用动态开点线段树。然后DFS合并两个儿子的权值线段树时，还得线段树合并。

$v$在 $w$父亲部分时求 $y$的数量，可以转换成求 $w$所有儿子中小于 $w$的数量$z$，这样$y = w - 1 - z$。就和第一种情况统一了。

如何求$y$，还有个更简单的办法，先对树求一个$DFS$序，与此同时还有一个初始为$0$的数组$val$。然后我们按照点编号从小到大依次考虑，假设当前考虑点$u$ ，让$val[time[u]]++$ ，即点$u$所在的 $DFS$序上的位置 $+1$。然后要求$u$的一个儿子 $son$的子树中标号小于 $u$的数量，则为这个子树对应的一个 $DFS$序的 $val$的区间和（因为 $1 \sim u$都加进来了）。

此处为单点修改和区间查询，用线段树或树状数组维护这个 $val$即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int maxn = 2e5 + 7;

int n;
int rt[maxn], ls[maxn * 20], rs[maxn * 20], num[maxn * 20], cnt;
inline void pushup(int x) { 
    num[x] = num[ls[x]] + num[rs[x]];
}
void update(int& x, int l, int r, int pos, int val = 1) {
    if (!x)
        x = ++cnt;
    if (l == r) {
        num[x] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(ls[x], l, mid, pos, val);
    else
        update(rs[x], mid + 1, r, pos, val);
    pushup(x);
}
int merge(int x1, int x2, int l, int r) {
    if ((!x1) || (!x2))
        return x1 + x2;
    if (l == r) {
        num[x1] += num[x2];
        return x1;
    }
    int mid = (l + r) >> 1;
    ls[x1] = merge(ls[x1], ls[x2], l, mid);
    rs[x1] = merge(rs[x1], rs[x2], mid + 1, r);
    pushup(x1);
    return x1;
}
int query(int x, int l, int r, int L, int R) {
    if (!x)
        return 0;
    if (L <= l && r <= R)
        return num[x];
    int mid = (l + r) >> 1, ans = 0;
    if (L <= mid)
        ans += query(ls[x], l, mid, L, R);
    if (R > mid)
        ans += query(rs[x], mid + 1, r, L, R);
    return ans;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    vector<vector<int>> edge(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    LL tot = 0;
    vector<LL> p(n, 0);
    auto DFS = [&](auto self, int u, int fa) -> void {
        for (auto& v : edge[u]) {
            if (v == fa)
                continue;
            self(self, v, u);
            LL tmp = query(rt[v], 1, n, 1, u + 1);
            tot += tmp;
            p[v] -= tmp;
            rt[u] = merge(rt[u], rt[v], 1, n);
        }
        update(rt[u], 1, n, u + 1);
        p[u] += u + 1 - query(rt[u], 1, n, 1, u + 1);
    };
    DFS(DFS, 0, 0);
    vector<LL> ans(n, 0);
    auto solve = [&](auto self, int u, int fa, LL pre) -> void {
        ans[u] += tot + p[u] + pre;
        for (auto& v : edge[u]) {
            if (v == fa)
                continue;
            self(self, v, u, pre + p[u]);
        }
    };
    solve(solve, 0, 0, 0);
    for (auto& i : ans)
        cout << i << ' ';
    cout << '\n';

    return 0;
}