2022 年牛客多校加赛场签到题题解

E Everyone is bot

题意：$nn$ 个人打算复读。一次复读的过程如下，每一轮，$nn$ 个人按照编号从小到大依次执行以下操作：如果这个人在前几轮已经进行过复读，他不会再次复读，否则他可以选择复读。如果某一轮没有人进行复读，那么复读的过程结束。 结束后选择复读的倒数第 $pp$ 个人会扣分，而其他的人会得分（第 $ii$ 个人若为第 $jj$ 个复读的，则会获得 $a_{i,j}>0a\_\{i,j\}>0$ 的分数）。每个人最大化得分，问最终每个人的分数。$1\le p\le n\le 1\times 10^{3}1\; \backslash leq\; p\; \backslash leq\; n\; \backslash leq\; 1\backslash times\; 10^3$。

解法：只有 $n\mathrm{m}\mathrm{o}\mathrm{d}pn\; \backslash bmod\; p$ 个人会得分。

若最后只有 $pp$ 个人还没复读，剩下的人都已经复读了，那么最后的 $pp$ 个人谁都不会说话：若某个人选择复读，则后面每个人都因为不会被扣分而选择复读，那么谁开启了最后 $pp$ 个人的复读谁就会扣分，而让别人加分，因而没人会当冤大头。

那么对于 $n-2p+1n-2p+1$ 到第 $n-pn-p$ 个选择复读的人，他们同样会陷入这个困境：因为一旦最后的 $pp$ 个人因为上面的逻辑没人去复读为第一个开启这一段复读的人埋单（使得他不会成为倒数第 $pp$ 个），那么这一段也会因为同样的逻辑每个人都选择不复读，以保证自己不会被扣分。同理最后的每 $pp$ 个人都会因为同样的逻辑都不复读，哪怕 $a_{i,j}a\_\{i,j\}$ 非常的大。因而最后只有 $n\mathrm{m}\mathrm{o}\mathrm{d}pn\; \backslash bmod\; p$ 个人会复读。这些人因为是一定会复读的（没有人可以使得他们成为倒数第 $pp$ 个），所以排在前面的一定会先下手为强。所以前 $n\mathrm{m}\mathrm{o}\mathrm{d}p+1n\; \backslash bmod\; p+1$ 个人按顺序复读。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int a[N + 5][N + 5];
int main()
{
    int n, p;
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= n;j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n % p; i++)
        printf("%d ", a[i][i]);
    for (int i = 1; i <= n - n % p; i++)
        printf("0 ");
    return 0;
}

H Here is an Easy Problem of Zero-chan

题意：给定一个 $nn$ 个节点以 $11$ 为根的树，$qq$ 次询问，每次给定 $xx$，问 ${\displaystyle \prod _{i=1}^n\mathrm{l}\mathrm{c}\mathrm{a}(x,i)}\backslash displaystyle\; \backslash prod\_\{i=1\}^n\; \{\backslash rm\; lca\}(x,i)$ 的后缀有多少个 $00$。$n,q\le 1\times 10^{5}n,q\; \backslash leq\; 1\backslash times\; 10^5$。

解法：可以通过换根计算出每个点的后缀 $00$ 个数。显然 $x=1x=1$ 时答案为 $00$。考虑从 $uu$ 节点走到它的一个儿子 $vv$，那么 $\mathrm{l}\mathrm{c}\mathrm{a}(x,i)\{\backslash rm\; lca\}(x,i)$ 中 $vv$ 出现次数增加 ${\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_v\{\backslash rm\; size\}\_v$ 次，而 $uu$ 的出现次数减少 ${\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}_v\{\backslash rm\; size\}\_v$ 次。因而可以通过维护 $22$ 和 $55$ 因子个数 $O(1)O(1)$ 的统计答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
struct line
{
    int from;
    int to;
    int next;
};
struct line que[2 * N + 5];
int cnt, headers[N + 5], siz[N + 5];
void add(int from, int to)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
int ans[N + 5];
int cnt2[N + 5], cnt5[N + 5];
void dfs1(int place, int father)
{
    siz[place] = 1;
    for (int i = headers[place]; i; i = que[i].next)
        if (que[i].to != father)
        {
            dfs1(que[i].to, place);
            siz[place] += siz[que[i].to];
        }
}
void dfs2(int place, int father, int two, int five)
{
    ans[place] = min(two, five);
    for (int i = headers[place]; i; i = que[i].next)
        if(que[i].to != father)
            dfs2(que[i].to, place, two - siz[que[i].to] * (cnt2[place] - cnt2[que[i].to]), five - siz[que[i].to] * (cnt5[place] - cnt5[que[i].to]));
}
int main()
{
    for (int i = 1; i <= N;i++)
    {
        int x = i;
        while (x % 2 == 0)
        {
            x >>= 1;
            cnt2[i]++;
        }
        x = i;
        while (x % 5 == 0)
        {
            x /= 5;
            cnt5[i]++;
        }
    }
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1, u, v; i < n;i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs1(1, 1);
    dfs2(1, 1, 0, 0);
    for (int i = 1, x; i <= q;i++)
    {
        scanf("%d", &x);
        printf("%d\n", ans[x]);
    }
    return 0;
}