A、Ares, Toilet Ares

说题目意思前先吐槽一下这题，这题面完完全全不清不楚，纯靠猜，果然厕所战神还是太强大了。

虽然出题人表示只想要出个简答题+讲个故事，最终导致了赛中每队基本人均一 $wa$ ，战况惨烈。

题目大意

你原本的得分是 $a$ ，你可以去 $k$ 次厕所，每次去厕所有 $\frac{z_i-y_i}{z_i}$ 的概率拿到可以让你的得分加一的卡片的一小部分，这一小部分表示为 $x_i$ ，保证 $\sum\limits_{i=1}^k x_i=l$ ， $l$ 就是完整卡片的长度，你只有在拿到全部长度的时候才能让你的得分加一，问你得分的期望是多？

Solution

我们不管 $x_i=0$ 的卡片长度，其余的求一次乘法逆元就行了。

ll n, m, k, a, l;

int solve() {
    n = read(), m = read(), k = read(), a = read(), l = read();
    int b = 1;
    for (int i = 1; i <= k; ++i) {
        int x = read(), y = read(), z = read();
        if(x == 0)    continue;
        b = (b * (z - y) * qpow(z, MOD - 2, MOD) % MOD) % MOD;
    }
    print((a + b) % MOD);

    return 1;
}

D、OR

题目大意

你原本有个长度为 $n(2\le n\le10^5)$ 的序列 $a_i$ ，现在我只告诉你两个长度为 $n-1$ 的序列 $b_i,c_i$ ，问合理的 $a_i$ 序列有多少种？

我们定义 $b_i=a_{i-1}\ \mathbf{or}\ a_i,c_i=a_{i-1}+a_i$ 。

Solution

由于给出的 $b,c$ 数组都是位运算得来的，我们就可以按位拆分，枚举 $b,c$ 的每一位，再去枚举不同的数。

我们首先看最低位，注意下面的 $b_j$ 代表着当前枚举的这一位二进制是 $0$ 还是 $1$ ， $c_j$ 同理，映射到题目就是 $b_j=b_j>>0\&1$ ：

如果在最低位的情况下， $b_j=1,c_j=1$ 这样的 $j$ 一共有 $n-1$ 个说明我们这一位存在两种构建方法，即 $010101$ 或者 $101010$ 这样交替进行。

我们把不足 $n-1$ 位我们可以分成下面的情况。

如果在最低位的某一个 $b_j=1,c_j=0$ ，说明它一定产生了进位，那么我们就把这次产生的进位消除，当我们每次都消除进位的时候就可以一直当作最低位处理了，例如 $c_i=1000,b_i=0111$ ，在我们消除最低位的 $1$ 带来的影响后 $c_i=0111$ 它的第二位第三位都可以看作新的最低位处理了。

如果在最低位的某一个 $b_j=0,c_j=1$ 这一定是非法的，因为最低位不可能有来自进位的 $1$ 。

如果在最低位的某一个 $b_j=0,c_j=0$ ，我们就看它进位是不是来自 $j-1$ 如果是刚刚前两个 $a_i$ 的话说明当前的这个 $b_j$ 不可能是 $0$ ，一定会存在一个 $1$ 让它进位。那么其余合法的时候例如 $b_j=1,c_j=1$ 后面跟一个 $b_{j+1}=0,c_{j+1}=0$ 这是合法的，但是出现了这样的进位说明当前这一位我们也只有一种构造 $a_i$ 序列的方法。

const int N = 1e5 + 7;
ll n, m;
int b[N], c[N];

int solve() {
    n = read();
    for (int i = 1; i < n; ++i)    b[i] = read();
    for (int i = 1; i < n; ++i)    c[i] = read();

    for (int i = 1; i < n; ++i) {
        if (b[i] > c[i]) {
            return print(0), 1;
        }
    }

    ll res = 1;
    for (int i = 0; i < 34; ++i) {
        int cnt = 0, pos = -100;
        for (int j = 1; j < n; ++j) {
            int bit1 = b[j] >> i & 1, bit2 = c[j] >> i & 1;
            if (bit1 == 1 && bit2 == 1)    ++cnt;
            else if (bit1 == 1 && bit2 == 0) {
                c[j] -= (1ll << i);
                pos = j;
            }
            else if (bit1 == 0 && bit2 == 1) {
                return print(0), 0;
            }
            else if (bit1 == 0 && bit2 == 0) {
                if (pos == j - 1) {
                    return print(0), 0;
                }
            }
        }
        if (cnt == n - 1)    res *= 2;
    }
    print(res);


    return 1;
}

E、Rise of Shadows

题目大意

给你一个年份，你要判断它是不是一个素数并且是一个闰年。

闰年定义为要么被 $400$ 整除，要么被 $4$ 整除并且不能被 $100$ 整除。

Solution

任何一个闰年都不能是素数，直接输出 $no$ 就行了。

F、Robots

题目大意

你有一个二维的地图，在地图上用 $1$ 代表无法跨过的障碍物，现在你有三种机器人，一种机器人是只能向下走，第二种是只能往右走，第三种是能往下走也可以往右走，询问共有 $Q$ 次，每次给出机器人的起点和终点以及是第几种机器人，如果可以到终点输出 $\mathbf{yes}$ 如果不能输出 $\mathbf{no}$ 。

Solution

由于地图不会改变，我们考虑离线的做法。

我们对每一列开一个 $bitset$ ，大小为地图的大小，里面存储能往下以及往右走的机器人在这个点出发能去到的全部点。

这样我们倒序的从最后一行最后一列往前推就可以知道每个点它可以去到的全部点都有那些。

接下来到了某个地方是机器人的起点，那就看终点是不是它能到的点就行了。

时间复杂度 $O(\frac{n^2m^2}{W})$ ，时限给了 $5s$ 不过这个 $bitset$ 只跑了到 $800ms$ 应该是没给到极限把并不认为牛客的机子 $1s$ 可以跑 $2·10^9$ 。

const int N = 500 + 7;
char s[N][N];
bitset<N* N> b[N];

const int M = 5e5 + 7;
bool ans[M];

struct Node {
    int op, id, x, y;
};

vector<Node> q[N][N];

int solve() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s[i] + 1);
    }
    int Q = read();
    for (int i = 1; i <= Q; ++i) {
        int op = read(), X1 = read(), Y1 = read(), X2 = read(), Y2 = read();
        q[X1][Y1].push_back({ op,i,X2,Y2 });
    }

    for (int i = n; i >= 1; --i) {
        for (int j = m; j >= 1; --j) {
            if (s[i][j] == '0') {
                b[j].set((i - 1) * m + j);
                if (s[i][j + 1] == '0')
                    b[j] |= b[j + 1];
            }
            else {
                b[j].reset();
            }
            for (auto& [op, id, x, y] : q[i][j]) {
                if (op == 1) {
                    ans[id] = (j == y && b[j][(x - 1) * m + y]);
                }
                else if (op == 2) {
                    ans[id] = (i == x && b[j][(x - 1) * m + y]);
                }
                else {
                    ans[id] = b[j][(x - 1) * m + y];
                }
            }
        }
    }

    for (int i = 1; i <= Q; ++i) {
        if (ans[i])    puts("yes");
        else puts("no");
    }

    return 1;
}

J、Tree

题目大意

$A,B$ 二人现在站在一棵树上的不同点，现在有成员得分等于这个人走过的路径长度，并且在这棵树上行走有一个特殊的性质，就是从 $u\to v$ 之后 $u$ 点将会被删除，并且与 $u$ 相连的全部边都会被删除。现在他们双方都想让自己的得分减掉对方得分最大化， $A$ 起始站在 $s$ 点， $B$ 起始站在 $t$ 点，问游戏结束 $A$ 的得分减掉 $B$ 的得分结果是多少？

Solution

考点： $ST$ 表+对抗搜索

第一我们知道对于 $u\to v$ 之间的最短路径来说，如果有任何一个玩家脱离了这条路径上，那么这时候两名玩家就变成完全独立的两个部分分别走最大值了。

第二就是我们用同一个式子来表示双方都想最大化得分差值的式子。如果我们用 $S_A$ 代表 $A$ 的得分， $S_B$ 代表 $B$ 的得分，所以也就是 $A$ 想要 $S_A-S_B$ 最大， $B$ 想要 $S_B-S_A$ 最大，等价于 $B$ 想要 $S_A-S_B$ 最小。

对于具体的方案来说，我们用一次 $dfs$ 求出从 $s\to t$ 路径上全部的点。

对着这些路径上的点走非 $s\to t$ 的路径可以走的最远距离记为 $Path[i]$ 。

接下来我们用 $Path1[i]$ 代表 $A$ 从 $i$ 点离开可以走的最大距离，这个会等于 $Path[i]+i-1$ 也就是从 $s$ 走到 $i$ 然后再往下走。

同理我们也用 $Path2[i]$ 代表 $B$ 从 $i$ 点离开可以走的最大距离，这个会等于 $Path[i]+len-i$ 也就是从 $t$ 走到 $i$ 接着走。

然后我们就去 $s\to t$ 的链上跑对抗搜索，对于任意一个人来说，它可以现在就在这个点离开也可以接着走，直到两人相遇的话就不能越过了，这里我们假设现在是 $A$ 走，那么我们假设 $A$ 在 $i$ 点离开，那么 $B$ 可以选择的最大值应该是 $[i+1,r]$ 里面的最大值，这里静态的查询我们用 $ST$ 表可以高效的维护。

剩下的就是两人依次取 $\max$ 和 $\min$ 的操作了。

时间复杂度 $O(n\log n)$ ，多出来的 $\log$ 是 $ST$ 表预处理的时间复杂度，对于每次 $dfs$ 我们保证每个点一定不会被遍历一次。

const int N = 5e5 + 7;
int Log[N], st1[21][N], st2[21][N];

int n, s, t;

vector<int> G[N];

bool vis[N], tag[N];
int path[N], path1[N], path2[N], len;

bool dfs1(int u, int dep) {
    vis[u] = 1;
    if (u == t) {
        len = dep;
        path[dep] = u;
        tag[u] = 1;
        return true;
    }
    for (auto& v : G[u]) {
        if (vis[v])    continue;
        if (dfs1(v, dep + 1)) {
            path[dep] = u;
            tag[u] = 1;
            return true;
        }
    }
    return false;
}

int dfs2(int u, int dep) {
    vis[u] = 1;
    int maxi = dep;
    for (auto& v : G[u]) {
        if (vis[v] || tag[v])    continue;
        maxi = max(maxi, dfs2(v, dep + 1));
    }
    return maxi;
}

int query1(int l, int r) {
    int x = Log[r - l + 1];
    return max(st1[x][l], st1[x][r - (1 << x) + 1]);
}

int query2(int l, int r) {
    int x = Log[r - l + 1];
    return max(st2[x][l], st2[x][r - (1 << x) + 1]);
}

int dfs3(int l, int r, int mode) {
    if (mode == 0) {
        int now = path1[l] - query2(l + 1, r);
        if (l + 1 < r)    now = max(now, dfs3(l + 1, r, 1));;
        return now;
    }
    else {
        int now = query1(l, r - 1) - path2[r];
        if (l + 1 < r)    now = min(now, dfs3(l, r - 1, 0));
        return now;
    }
}

int solve() {
    n = read(), s = read(), t = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(s, 1);
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= len; ++i) {
        path[i] = dfs2(path[i], 0); // 不沿着 s->t 链还能走多远
    }

    for (int i = 1; i <= len; ++i) {
        path1[i] = path[i] + i - 1;
        path2[i] = path[i] + len - i;
    }

    Log[1] = 0;
    for (int i = 2; i < N; ++i)    Log[i] = Log[i >> 1] + 1;
    for (int i = 1; i <= len; ++i) {
        st1[0][i] = path1[i];
        st2[0][i] = path2[i];
    }
    for (int i = 1; i <= Log[len]; ++i) {
        for (int j = 1; j + (1 << i) - 1 <= len; ++j) {
            st1[i][j] = max(st1[i - 1][j], st1[i - 1][j + (1 << i - 1)]);
            st2[i][j] = max(st2[i - 1][j], st2[i - 1][j + (1 << i - 1)]);
        }
    }

    print(dfs3(1, len, 0));

    return 1;
}

K、Yet Another Problem About Pi

题目大意

二维矩阵的宽和高分别 $w,d$ 。你现在要用一个长度为 $\pi$ 的直线穿过尽可能多的区域，一个区域的贡献只会被计算一次。求穿过的最大区域数。

Solution

考点：思维

这题只要求穿过，也就是我们可以选择无穷小的长度也算穿过了，我们选择一个矩阵的右下点，也就是我们可以用无穷小的代价拿到的贡献为 $4$ 。接下啦我们就只有两种选择路线。

沿着短的边走直线，走过一个宽度的时候新增加的贡献为 $2$ 。
沿着对角线走，走过一个对角线的时候新增加贡献为 $3$ 。

上面做法的正确性很容易理解，任何时候走多余的弯路一定不是更优解。接下来只需要考虑全走直线，全走对角，走对角最后一次到不了完整的对角时会看能不能完整的走一次直线。三种情况取一次 $\max$ 即可。

const double PI = acos(-1);

int solve() {
    double w, d;

    scanf("%lf %lf", &w, &d);

    double mini = min(w, d);
    double duijiao = sqrt(w * w + d * d);

    int res = 4;
    for (int i = 0; i <= 2; ++i) {
        if (i * mini <= PI) {
            res = max<int>(res, (4 + i * 2 + floor((PI - i * mini) / duijiao) * 3));
        }
        if (i * duijiao <= PI) {
            res = max<int>(res, (4 + i * 3 + floor((PI - i * duijiao) / mini) * 2));
        }
    }
    print(res);

    return 1;
}

2021牛客暑期多校训练营8

A、Ares, Toilet Ares

题目大意

Solution

D、OR

题目大意

Solution

E、Rise of Shadows

题目大意

Solution

F、Robots

题目大意

Solution

J、Tree

题目大意

Solution

K、Yet Another Problem About Pi

题目大意

Solution