牛客多校第六场签到题题解

B Eezie and Pie

题意：给定一个 $nn$ 个点的树，第 $ii$ 个节点可以到达其第 $j,j\in [1,d_i]j,j\; \backslash in\; [1,d\_i]$ 级祖先。问每个点能被几个点到达。$n\le 2\times 10^{6}n\; \backslash leq\; 2\backslash times\; 10^6$。

解法：树上差分。对于每个点，其贡献在于从它往上 $d_{i}d\_i$ 个节点的一条链。倒过来从儿子往父亲差分，那么只需要给当前节点打上 $+1+1$ 标记，$d_i+1d\_i+1$ 级祖先打上 $-1-1$ 标记即可。总时间复杂度 $\mathcal{O}(n)\backslash mathcal\; O(n)$。

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)

using namespace std;
const int N = 2e6 + 5;
using ll = int64_t;
int n, d[N], sz[N], dep[N], fa[N][21];
vector<int> G[N];
int get(int u, int k) {
    for (int i = 20; ~i; --i)
        if (k >= dep[u] - dep[fa[u][i]])
            k -= dep[u] - dep[fa[u][i]], u = fa[u][i];
    return u;
}
void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u][0] = p, sz[u] = 1;
    fp(i, 1, 20) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    --sz[get(u, d[u] + 1)];
    for (auto v : G[u])
        if (v != p)
            dfs(v, u), sz[u] += sz[v];
}
void Solve() {
    scanf("%d", &n);
    for (int u, v, i = 1; i < n; ++i)
        scanf("%d%d", &u, &v),
        G[u].push_back(v), G[v].push_back(u);
    fp(i, 1, n) scanf("%d", d + i);
    dfs(1, 0);
    fp(i, 1, n) printf("%d ", sz[i]);
}
int main() {
    int t = 1;
    while (t--) Solve();
    return 0;
}

G Icon Design

题意：画出给定缩放尺寸的 NFLS 字符画。

解法：找出定位点，暴力模拟。

#include <bits/stdc++.h>
using namespace std;
char a[30][1001];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= 4 * n + 5;i++)
        for (int j = 1; j <= 13 * n + 19;j++)
            a[i][j] = '.';
    for (int i = 1; i <= 13 * n + 19; i++)
        a[1][i] = a[4 * n + 5][i] = '*';
    for (int i = 1; i <= 4 * n + 5;i++)
        a[i][1] = a[i][13 * n + 19] = '*';
    for (int x = n + 2, y = n + 3, i = 1; i <= 2 * n + 3;i++, x++, y++)
        a[x][y] = a[x][n + 3] = a[x][3 * n + 5] = '@';
    for (int y = 4 * n + 7, i = 1; i <= 2 * n + 3;i++, y++)
        a[n + 2][y] = a[2 * n + 3][y] = '@';
    for (int i = 1, x = n + 2; i <= 2 * n + 3;i++, x++)
        a[x][4 * n + 7] = '@';
    for (int i = 1, x = n + 2; i <= 2 * n + 3;i++, x++)
        a[x][7 * n + 11] = '@';
    for (int i = 1, y = 7 * n + 11; i <= 2 * n + 3;i++, y++)
        a[3 * n + 4][y] = '@';
    for (int i = 1, x = 10 * n + 15; i <= 2 * n + 3;i++, x++)
        a[n + 2][x] = a[2 * n + 3][x] = a[3 * n + 4][x] = '@';
    for (int i = 1, y = n + 2; i <= n + 1;y++, i++)
        a[y][10 * n + 15] = '@';
    for (int i = 1, y = 2 * n + 3; i <= n + 1; i++, y++)
        a[y][12 * n + 17] = '@';
    for (int i = 1; i <= 4 * n + 5; i++)
        printf("%s\n", a[i] + 1);
    return 0;
}

J Number Game

题意：给定三个数字 $A,B,CA,B,C$，一次操作可以令 $B\leftarrow A-BB\; \backslash leftarrow\; A-B$ 或 $C\leftarrow B-CC\; \backslash leftarrow\; B-C$。问 $CC$ 能否变成 $xx$。$A,B,C,x\in [-1\times 10^{18},1\times 10^{18}]A,B,C,x\; \backslash in\; [-1\backslash times\; 10^\{18\},1\backslash times\; 10^\{18\}]$，$TT$ 组测试，$T\le 1\times 10^{5}T\; \backslash leq\; 1\backslash times\; 10^5$。

题意：显然不会连续进行两次 $B\leftarrow A-BB\; \backslash leftarrow\; A-B$，否则等于没有操作，因而一定是两个操作交替进行的。设初始值为 $A_0,B_0,C_{0}A\_0,B\_0,C\_0$：

1. $B\leftarrow A-BB\; \backslash leftarrow\; A-B$：$A_0,A_0-B_0,C_{0}A\_0,A\_0-B\_0,C\_0$；
2. $C\leftarrow B-CC\; \backslash leftarrow\; B-C$：$A_0,A_0-B_0,A_0-B_0-C_{0}A\_0,A\_0-B\_0,A\_0-B\_0-C\_0$；
3. $B\leftarrow A-BB\; \backslash leftarrow\; A-B$：$A_0,B_0,A_0-B_0-C_{0}A\_0,B\_0,A\_0-B\_0-C\_0$；
4. $C\leftarrow B-CC\; \backslash leftarrow\; B-C$：$A_0,B_0,2B_0-A_0+C_{0}A\_0,B\_0,2B\_0-A\_0+C\_0$；
5. …

可以注意到最终的 $CC$ 会与 $C_{0}C\_0$ 差一个 $A_0-2B_{0}A\_0-2B\_0$ 的倍数，具体倍数的正负与先进行第一个操作与第二个操作有关。因而最终只需要判断 $x-C_{0}x-C\_0$ 与 $A_0-2B_{0}A\_0-2B\_0$ 的整除关系即可。当然 $C_{0}C\_0$ 也可以先进行一次操作变成 $B_0-C_{0}B\_0-C\_0$，因而再判断一次即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d", &t);
    long long A, B, C, x;
    while(t--)
    {
        scanf("%lld%lld%lld%lld", &A, &B, &C, &x);
        if (A == 2 * B)
        {
            if (x == C || x == B - C)
                printf("Yes\n");
            else
                printf("No\n");
            continue;
        }
        bool flag = 0;
        if ((x - (B - C)) % (A - 2 * B) == 0)
            flag = 1;
        if ((x - C) % (A - 2 * B) == 0)
            flag = 1;
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

M Z-Game on grid

题意：给定一个 $n\times mn\backslash times\; m$ 的棋盘，上面有 A,B,. 三种字符。有一个棋子从 $(1,1)(1,1)$ 出发，如果走到 A 的格子则 先手获胜，走到 B 的格子则后手获胜，走到 $(n,m)(n,m)$ 且为 . 则为平局。若一个棋子在 $(i,j)(i,j)$ 可以走到 $(i+1,j)(i+1,j)$ 或者 $(i,j+1)(i,j+1)$，在不走出棋盘的情况下。二人轮流操作，不允许不操作。问先手是否有必胜、平、败策略。$n,m\le 500n,m\; \backslash leq\; 500$。

解法：设 $f_{i,j}f\_\{i,j\}$ 为走到 $(i,j)(i,j)$ 的先手情况。先手必胜即是只有走到 A 才有 $f_{i,j}=1f\_\{i,j\}=1$，必败是走到 B 才算 $f_{i,j}=1f\_\{i,j\}=1$，平局则不能碰到任何一个非 . 的格子，只有 $f_{n,m}=1f\_\{n,m\}=1$。利用 $i+ji+j$ 的奇偶性判断先后手，先手取 $\max \backslash max$ 转移，后手取 $\min \backslash min$ 转移。注意清空数组。

#include <bits/stdc++.h>
using namespace std;
const int N = 500;
int f[N + 5][N + 5];
char a[N + 5][N + 5];
int main()
{
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n;i++)
            scanf("%s", a[i] + 1);
        memset(f, 0, sizeof(f));
        for (int i = n; i >= 1;i--)
            for (int j = m; j >= 1;j--)
            {
                if (a[i][j] == 'A')
                    f[i][j] = 1;
                else if (a[i][j] == 'B' || (i == n && j == m))
                    continue;
                else if (i == n)
                    f[i][j] = f[i][j + 1];
                else if (j == m)
                    f[i][j] = f[i + 1][j];
                else
                {
                    if ((i + j) % 2 == 0)
                        f[i][j] = max(f[i + 1][j], f[i][j + 1]);
                    else
                        f[i][j] = min(f[i + 1][j], f[i][j + 1]);
                }
            }
        if(f[1][1])
            printf("yes ");
        else
            printf("no ");
        memset(f, 0, sizeof(f));
        for (int i = n; i >= 1;i--)
            for (int j = m; j >= 1;j--)
            {
                if (a[i][j] != '.')
                    f[i][j] = 1;
                else if (i == n && j == m)
                    f[i][j] = 0;
                else if (i == n)
                    f[i][j] = f[i][j + 1];
                else if (j == m)
                    f[i][j] = f[i + 1][j];
                else
                {
                    if ((i + j) % 2 == 0)
                        f[i][j] = min(f[i + 1][j], f[i][j + 1]);
                    else
                        f[i][j] = max(f[i + 1][j], f[i][j + 1]);
                }
            }
        if(!f[1][1])
            printf("yes ");
        else
            printf("no ");
        memset(f, 0, sizeof(f));
        for (int i = n; i >= 1;i--)
            for (int j = m; j >= 1;j--)
            {
                if (a[i][j] == 'B')
                    f[i][j] = 1;
                else if (a[i][j] == 'A' || (i == n && j == m))
                    continue;
                else if (i == n)
                    f[i][j] = f[i][j + 1];
                else if (j == m)
                    f[i][j] = f[i + 1][j];
                else
                {
                    if ((i + j) % 2 == 0)
                        f[i][j] = max(f[i + 1][j], f[i][j + 1]);
                    else
                        f[i][j] = min(f[i + 1][j], f[i][j + 1]);
                }
            }
        if(f[1][1])
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}