2022 年牛客多校第一场补题记录

A Villages: Landlines

题意：有一个电站位于 $x_{s}x\_s$，需要在 $[x_s-r_s,x_s+r_s][x\_s-r\_s,x\_s+r\_s]$ 的范围内设置至少一个电塔将电引出。$n-1n-1$ 个用电处位于 $x_{i}x\_i$，需要在其范围 $[x_i-r_i,x_i+r_i][x\_i-r\_i,x\_i+r\_i]$ 有一电塔才能保证供电。你可以任意设置电塔（与电站、用电所重合也可），但是这些电塔需要用线连接起来。问最少需要多长电线。$n\le 2\times 10^{5}n\; \backslash leq\; 2\backslash times\; 10^5$，$-1\times 10^9\le x_s,x_i\le 1\times 10^9-1\backslash times\; 10^9\; \backslash leq\; x\_s,x\_i\backslash leq\; 1\backslash times\; 10^9$，$0\le r_i,r_s\le 1\times 10^{9}0\; \backslash leq\; r\_i,r\_s\; \backslash leq\; 1\backslash times\; 10^9$。

解法：题意等效于 $nn$ 个区间：$[x_s-r_s,x_s+r_s][x\_s-r\_s,x\_s+r\_s]$，$[x_i-r_i,x_i+r_i][x\_i-r\_i,x\_i+r\_i]$，然后用电线填补区间中间的空白，问空白长度。对所有区间按左端点排序，求出最长可以连续延申到的右端点，将有交集的区间合并。然后将这些合并后的区间直接填补中间的空白即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    long long x, y;
    scanf("%d%lld%lld", &n, &x, &y);
    vector<pair<long long, long long>> que;
    que.emplace_back(x - y, x + y);
    for (int i = 1; i < n;i++)
    {
        scanf("%lld%lld", &x, &y);
        que.emplace_back(x - y, x + y);
    }
    sort(que.begin(), que.end());
    long long ans = 0;
    long long maxr = que[0].second;
    vector<pair<long long, long long>> now;
    for (int i = 0; i < n;)
    {
        int j = i;
        long long maxr = que[i].second;
        while (j < n && que[j].first <= maxr)
        {
            maxr = max(maxr, que[j].second);
            j++;
        }
        now.emplace_back(que[i].first, maxr);
        i = j;
    }
    for (int i = 0; i + 1 < now.size();i++)
        ans += now[i + 1].first - now[i].second;
    printf("%lld", ans);
    return 0;
}

B Spirit Circle Observation

题意：给定纯数字序列 $SS$，问存在多少对区间 $[l_1,r_1],[l_2,r_2][l\_1,r\_1],[l\_2,r\_2]$ 满足 $r_1-l_1=r_2-l_{2}r\_1-l\_1=r\_2-l\_2$ 且 $\overline{s_{l_1}{s}_{l_1+1}\cdots s_{r_1}}+1=\overline{s_{l_2}{s}_{l_2+1}\cdots s_{r_2}}\backslash overline\{s\_\{l\_1\}s\_\{l\_1+1\}\; \backslash cdots\; s\_\{r\_1\}\}+1=\backslash overline\{s\_\{l\_2\}s\_\{l\_2+1\}\; \backslash cdots\; s\_\{r\_2\}\}$。$\mathrm{\mid }S\mathrm{\mid }\le 4\times 10^5|S|\; \backslash leq\; 4\backslash times\; 10^5$。

解法：合法的区间一定满足 $[l_1,r_1]=Ap99\cdots 9[l\_1,r\_1]=Ap99\backslash cdots\; 9$，$[l_2,r_2]=A(p+1)00\cdots 0[l\_2,r\_2]=A(p+1)00\backslash cdots\; 0$，其中 $AA$ 表示一段连续且完全相同的子串。

考虑一个看似暴力实则正确的做法：建立 SAM，暴力枚举每个节点（即枚举 $AA$），对于每个节点枚举 $pp$，从当前节点开始一个沿着 $p99\cdots 9p99\backslash cdots\; 9$ 走下去，另一个沿着 $(p+1)00\cdots 0(p+1)00\; \backslash cdots\; 0$ 走下去，两边取次数的 $\min \backslash min$，答案即为当前节点所覆盖长度乘以次数，再乘以上每次枚举 $pp$ 的方案之和。

为什么可以每次都暴力走下去？由于 SAM 的性质保证了其状态数最简，因而每个 $0,90,9$ 字符出边只会作为 $pp$ 被访问一次，然后作为 $pp$ 的延申段被访问一次——它不可能同时被多个状态的相同字符出边所直接指向。对于其他字符出边只会作为 $pp$ 被访问一次。总时间复杂度 $\mathcal{O}(n)\backslash mathcal\; O(n)$。

#include <bits/stdc++.h>
using namespace std;
class SAM
{
    const int shift = 48, sigma = 10;
    struct node
    {
        int ch[10];
        int len;
        int father;
        long long cnt;
        node()
        {
            memset(ch, 0, sizeof(ch));
            len = father = cnt = 0;
        }
    } NIL;
    vector<node> t;
    vector<vector<int>> graph;
    int last, ind;
    void insert(int c)
    {
        int p = last;
        int np = last = ++ind;
        t.push_back(NIL);
        t[np].len = t[p].len + 1;
        t[np].cnt = 1;
        for (; p && !t[p].ch[c]; p = t[p].father)
            t[p].ch[c] = np;
        if(!p)
            t[np].father = 1;
        else
        {
            int q = t[p].ch[c];
            if (t[p].len + 1 == t[q].len)
                t[np].father = q;
            else
            {
                int nq = ++ind;
                t.push_back(t[q]);
                t[nq].cnt = 0;
                t[nq].len = t[p].len + 1;
                t[q].father = t[np].father = nq;
                for (; p && t[p].ch[c] == q; p = t[p].father)
                    t[p].ch[c] = nq;
            }
        }
    }
 
public:
    SAM(string s)
    {
        last = ind = 1;
        t.push_back(NIL);
        t.push_back(NIL);
        for (auto i : s)
            insert(i - shift);
        graph.resize(t.size());
        for (int i = 2; i <= ind;i++)
            graph[t[i].father].push_back(i);
        function<void(int)> dfs = [&](int place)
        {
            for (auto i : graph[place])
            {
                dfs(i);
                t[place].cnt += t[i].cnt;
            }
        };
        dfs(1);
    }
    long long query()
    {
        long long ans = 0;
        function<void(int, int)> dfs = [&](int place, int father)
        {
            long long pre = t[place].len - t[t[place].father].len;
            for (int i = 0; i < 9;i++)
            {
                int x = t[place].ch[i], y = t[place].ch[i + 1];
                while (x && y)
                {
                    ans += t[x].cnt * t[y].cnt * pre;
                    x = t[x].ch[9];
                    y = t[y].ch[0];
                }
            }
            for (auto i : graph[place])
                dfs(i, place);
        };
        t[0].len = -1;
        dfs(1, 0);
        return ans;
    }
};
int main()
{
    int n;
    string s;
    cin >> n >> s;
    SAM solve(s);
    printf("%lld", solve.query());
    return 0;
}

C Grab the Seat!

题意：$(0,1)(0,1)$ 至 $(0,m)(0,m)$ 有一个长度为 $mm$ 的荧幕，在 $[1,n]:[1,m][1,n]:[1,m]$ 的范围内已经坐了 $kk$ 个人。$qq$ 次询问，每次会永久性更新一个人的座位，问更改晚座位后，有多少个座位能够完整的看到荧幕而不会被任何已经坐着的 $kk$ 个人挡住。$n,m,k\le 2\times 10^{5}n,m,k\; \backslash leq\; 2\backslash times\; 10^5$，$q\le 200q\; \backslash leq\; 200$。

解法：$qq$ 非常小因而考虑 $O(mq)O(mq)$ 或者 $O(kq)O(kq)$ 的做法。考虑一个人 $(x,y)(x,y)$ 能够挡住的范围，一定是沿着直线 $(0,1)\to (x,y)(0,1)\; \backslash to\; (x,y)$ 和直线 $(0,m)\to (x,y)(0,m)\; \backslash to\; (x,y)$ 所围成的一个类似三角形区域（因为有边界）。

统计答案的时候可以根据每一行能坐多少个座位，因而可以考虑维护出每一行最右（$xx$ 最大）能坐到哪里。对于荧幕的一个边缘 $(0,1)(0,1)$，从下到上的枚举每一行已经坐了人的最左侧位置，并不断更新这个人和 $(0,1)(0,1)$ 的斜率 $kk$：若当前这个人和 $(0,1)(0,1)$ 的斜率不足 $kk$，则表示这个人看 $(0,1)(0,1)$ 都会被之前某个人影响，因而这个人存在与否是不重要的；如果超过 $kk$，证明从这里开始，$(0,1)\to (x,y)(0,1)\; \backslash to\; (x,y)$ 这一射线的右上三角部分都会受这个人的影响，但是坐在下面的（$yy$ 更小的座位）看 $(0,1)(0,1)$ 不会受到这个人的影响，因而更新 $kk$。本行最右侧能看到 $(0,1)(0,1)$ 的位置由 $\lceil {\displaystyle \frac{i-1}{k}}-1\rceil \backslash left\; \backslash lceil\; \backslash dfrac\{i-1\}\{k\}-1\backslash right\; \backslash rceil$ 给定。对于荧幕的最上侧 $(0,m)(0,m)$ 同理，只是从上到下的去枚举即可。时间复杂度 $\mathcal{O}(mq)\backslash mathcal\; O(mq)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 200000, M = 200;
long long x[N + 5], y[N + 5];

int main()
{
    int n, m, k, q, id;
    long long nowx, nowy;
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for (int i = 1; i <= k;i++)
        scanf("%lld%lld", &x[i], &y[i]);
    while(q--)
    {
        scanf("%d%lld%lld", &id, &nowx, &nowy);
        x[id] = nowx;
        y[id] = nowy;
        vector<long long> minimum(m + 1, n + 1);
        for (int i = 1; i <= k;i++)
            minimum[y[i]] = min(minimum[y[i]], x[i]);
        double k = 0;
        vector<int> lim1(m + 1), lim2(m + 1);
        for (int i = 1; i <= m; i++)
        {
            k = max(k, double(i - 1) / minimum[i]);
            if (k == 0)
                lim1[i] = minimum[i] - 1;
            else
                lim1[i] = floor((double)(i - 1) / k - 1e-9);
        }
        k = 0;
        for (int i = m; i >= 1;i--)
        {
            k = min(k, (double)(i - m) / minimum[i]);
            if (k == 0)
                lim2[i] = minimum[i] - 1;
            else
                lim2[i] = floor((double)(i - m) / k - 1e-9);
        }
        long long ans = 0;
        for (int i = 1; i <= m;i++)
            ans += min({n, lim1[i], lim2[i]});
        printf("%lld\n", ans);
    }
    return 0;
}

D Mocha and Railgun

题意：给定一个半径为 $rr$ 的圆，和一个圆内定点 $QQ$，有一中心钉在 $QQ$，可以绕着 $QQ$ 任意旋转的长度为 $2l2l$ 的线段 $ABAB$，问 $ABAB$ 所对应的弧长最长有多少，距离对应规则如下。保证 $QQ$ 离圆弧距离超过 $ll$。

解法：可以证明当 $AB\perp OQAB\; \backslash perp\; OQ$ 时答案最大（利用画图软件观察得到）。剩下的利用三角函数计算即可。

E LTCS

题意：定义最大公共子树为，树上节点的值相同，且树上祖孙、兄弟关系完全相同。给定两个均以 $11$ 为根的有根树，大小为 $n,mn,m$，并给定树上点的值 $\{a_i\},\{b_i\}\backslash \{a\_i\backslash \},\backslash \{b\_i\backslash \}$，问最大公共子树。$n,m\le 500n,m\; \backslash leq\; 500$。

解法：考虑最朴素的 dp：$f_{i,j,0\mathrm{/}1}f\_\{i,j,0/1\}$ 表示在第一个树上走到节点 $ii$，第二个树上走到节点 $jj$，$00$ 表示 $i,ji,j$ 节点不一定匹配，$11$ 表示一定匹配，的最大公共子树。

对于 $f_{i,j,1}f\_\{i,j,1\}$，首先满足 $a_i=b_{j}a\_i=b\_j$。此外，两个子树需要匹配，考虑对 $ii$ 和 $jj$ 的儿子进行匹配——对 $ii$ 的儿子 $u_{i}u\_i$ 和 $v_{j}v\_j$ 儿子匹配的边权为 $f_{u_i,v_j,0}f\_\{u\_i,v\_j,0\}$。那么就是进行一次二分图的带权最大匹配，记这一最大匹配为 $ww$，则 $f_{i,j,1}\leftarrow w+1f\_\{i,j,1\}\; \backslash leftarrow\; w+1$；对于 $f_{i,j,0}f\_\{i,j,0\}$，可以从 $f_{u_i,v_j,0},f_{i,j,1}f\_\{u\_i,v\_j,0\},f\_\{i,j,1\}$ 转移。

可以证明这样做的复杂度为 $\mathcal{O}(n^3)\backslash mathcal\; O(n^3)$，足以通过本题。

G Lexicographical Maximum

题意：给定 $nn$，问 $[1,n][1,n]$ 数字按字典序排序，最大值为多少。$n\le 10^{100000}n\; \backslash leq\; 10^\{100000\}$。

解法：当 $n\in [10^k-10,10^k]n\; \backslash in\; [10^\{k\}-10,10^k]$ 时直接输出 $nn$，否则输出 $k-1k-1$ 个 $99$。

H Fly

题意：给定长度为 $nn$ 的序列 $\{a_i\}\backslash \{a\_i\backslash \}$，和 $mm$ 条制限：$(b_i,c_i)(b\_i,c\_i)$ 表示第 $b_{i}b\_i$ 个数字 $x_{b_i}x\_\{b\_i\}$ 的二进制表示中 $c_{i}c\_i$ 位必须为 $00$，问满足 $\sum a_i{x}_i\le m\backslash sum\; a\_ix\_i\; \backslash leq\; m$ 的长度为 $nn$ 的合法有序数列 $(x_1,x_2,\cdots ,x_n)(x\_1,x\_2,\backslash cdots,x\_n)$ 的个数。$n,\sum a_i\le 4\times 10^{4}n,\backslash sum\; a\_i\; \backslash leq\; 4\backslash times\; 10^4$，$m\le 1\times 10^{18}m\; \backslash leq\; 1\backslash times\; 10^\{18\}$。

解法：原题即为把 $x_{i}x\_i$ 拆分成 $6060$ 个价值为 $a_i{2}^j,j\in [0,59]a\_i2^j,j\; \backslash in\; [0,59]$ 的物品，每个物品至多只能选一次，求价值小于等于 $mm$ 的方案数。对于此类价值为 $2^{k}2^k$ 形式的，一律使用二进制拆分：即依照 $2^{k}2^k$ 从高到底的顺序考察物品。对于 $2^{k}2^k$ 这一档，总价值可以缩水到 $\lfloor {\displaystyle \frac{m}{2^k}}\rfloor \backslash left\; \backslash lfloor\backslash dfrac\{m\}\{2^k\}\; \backslash right\; \backslash rfloor$——因为多余部分不可能利用 $2^{k}2^k$ 填满，因而只能被迫扔掉。同时由于 $\sum a_i\backslash sum\; a\_i$ 的保证，总价值必然不会超过 $2\sum a_{i}2\backslash sum\; a\_i$——${\displaystyle \sum _{i=0}^k\frac{a_i}{2^{k-i}}\le 2\sum a_i}\backslash displaystyle\; \backslash sum\_\{i=0\}^k\; \backslash dfrac\{a\_i\}\{2^\{k-i\}\}\; \backslash leq\; 2\backslash sum\; a\_i$。对于 $2^{k}2^k$ 向 $2^{k-1}2^\{k-1\}$ 转移时，只需要将当前占据的体积扩大一倍，同时对 $2\sum a_{i}2\backslash sum\; a\_i$ 取 $\min \backslash min$ 即可。

此外，由于此题 $nn$ 较大，物品数达到了 $2.4\times 10^{6}2.4\backslash times\; 10^6$，因而朴素的 01 背包无法满足，需要使用生成函数来优化 01 背包计算——$\prod (1+x^{a_i})\backslash prod\; (1+x^\{a\_i\})$ 可以利用递归树做到 $\mathcal{O}(n{}^{2}n)\backslash mathcal\; O(n\; \backslash log^2n)$ 的复杂度。

因而总的复杂度为 $\mathcal{O}(120\sum a_i{}^{2}n)\backslash mathcal\; O(120\backslash sum\; a\_i\; \backslash log^2n)$。

I Chiitoitsu

题意：给定起始 $1313$ 张麻将牌，然后一个人随机摸牌 $123123$ 巡，问期望多少次能自摸七对子。保证起始手牌没有刻子和暗杠。

解法：显然如果手上有对子，摸到第三张也会直接打掉；若没有这一张，也不会留着——换张对推进手牌没有任何意义，因而只有当手上有这张牌才会留着。

考虑 $f_{i,j}f\_\{i,j\}$ 表示已经有 $ii$ 个对子，摸到第 $jj$ 巡，还要期望摸多少巡能自摸。对于当前情况，山里还有 $3(13-2i)3(13-2i)$ 张可能的上张牌——只要不成对的，剩余的三张全在牌山里，因而向听数前进的概率 $p={\displaystyle \frac{3(13-2i)}{123-j}}p=\backslash dfrac\{3(13-2i)\}\{123-j\}$。因而倒推：$f_{i,j}\leftarrow f_{i,j+1}(1-p)+f_{i+1,j+1}p+1f\_\{i,j\}\; \backslash leftarrow\; f\_\{i,j+1\}(1-p)+f\_\{i+1,j+1\}p\; +\; 1$，边界情况 $f_{7,i}=0f\_\{7,i\}=0$。

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long power(long long a, long long x)
{
    long long ans = 1;
    while(x)
    {
        if (x & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
long long inv(long long a)
{
    return power(a, mod - 2);
}
long long f[8][200];
int main()
{
    for (int i = 6; i >= 0;i--)
        for (int j = 3 * (13 - 2 * i); j <= 136 - 13;j++)
        {
            long long p = 3 * (13 - 2 * i) % mod * inv(j) % mod;
            f[i][j] = (f[i + 1][j - 1] * p % mod + f[i][j - 1] * (mod + 1 - p) % mod + 1) % mod;
        }
    int t;
    scanf("%d", &t);
    for (int o = 1; o <= t;o++)
    {
        string s;
        cin >> s;
        int cnt = 0;
        map<string, int> vis;
        for (int i = 0; i < 13;i++)
            vis[s.substr(i * 2, 2)]++;
        for (auto i : vis)
            if(i.second == 2)
                cnt++;
        printf("Case #%d: %lld\n", o, f[cnt][123]);
    }
    return 0;
}

J Serval and Essay

题意：有 $nn$ 个命题，每个命题可以被证明为正确当且仅当其前提条件均被证明为正确。若一个命题没有前置条件，且未被设定为公理，则被认为是错误的。现在可以选定任一个命题认为是公理，问最多可以证明多少个命题是正确的。$n,m\le 2\times 10^{5}n,m\; \backslash leq\; 2\backslash times\; 10^5$。

解法：记 $S_{i}S\_i$ 表示设定命题 $ii$ 为公理时，所能推断出来的正确集合。则 $S_j\subseteq S_{i}S\_j\; \backslash sube\; S\_i$ 当且仅当命题 $jj$ 的所有前置条件均在 $S_{i}S\_i$ 中。如果把每个前置条件关系看作一条有向边，$S_{i}S\_i$ 集合所有的出边全部合并入 $ii$ 的出边，则 $S_j\subseteq S_{i}S\_j\; \backslash sube\; S\_i$ 当且仅当 $jj$ 仅有一条入边 $i\to ji\; \backslash to\; j$。

基于以上的想法，可以考虑启发式合并：首先 $\mathrm{\forall }i\in [1,n]\backslash forall\; i\; \backslash in\; [1,n]$，$S_i=\{i\}S\_i=\backslash \{i\backslash \}$。然后类似拓扑排序：若一个点 $uu$的入边个数仅为 $11$——$vv$，则将 $uu$ 合并进入 $vv$，且将 $uu$ 的所有出边全部归入 $vv$ 中。为了保证复杂度，需要将出边少的点合并进入出边多的点，使用 set维护每个点的出边信息和 $S_{i}S\_i$ 大小。总复杂度 $\mathcal{O}(n{}^{2}n)\backslash mathcal\; O(n\; \backslash log^2n)$。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    for (int o = 1; o <= t;o++)
    {
        scanf("%d", &n);
        vector<set<int>> reach(n + 1);
        vector<set<int>> graph(n + 1);
        vector<int> deg(n + 1, 0), siz(n + 1, 1), father(n + 1);
        function<int(int)> getfather = [&](int x)
        {
            return father[x] == x ? x : father[x] = getfather(father[x]);
        };
        queue<pair<int, int>> q;
        auto merge = [&](int u, int v)
        {
            if (u == v)
                return;
            if (graph[u].size() < graph[v].size())
                swap(u, v);
            father[v] = u;
            siz[u] += siz[v];
            for (auto i : graph[v])
            {
                if (graph[u].count(i))
                {
                    deg[i]--;
                    if (deg[i] == 1)
                        q.emplace(u, i);
                }
                else
                    graph[u].insert(i);
            }
            graph[v].clear();
        };
        for (int i = 1, x; i <= n;i++)
        {
            father[i] = i;
            scanf("%d", &deg[i]);
            for (int j = 1; j <= deg[i];j++)
            {
                scanf("%d", &x);
                graph[x].insert(i);
            }
            if (deg[i] == 1)
                q.emplace(i, x);
        }
        while(!q.empty())
        {
            auto tp = q.front();
            q.pop();
            merge(getfather(tp.first), getfather(tp.second));
        }
        int ans = 0;
        for (int i = 1; i <= n;i++)
            ans = max(ans, siz[getfather(i)]);
        printf("Case #%d: %d\n", o, ans);
    }
    return 0;
}