牛客多校第一场补题记录

题意：有一个电站位于 x s x_s xs​，需要在 [ x s − r s , x s + r s ] [x_s-r_s,x_s+r_s] [xs​−rs​,xs​+rs​] 的范围内设置至少一个电塔将电引出。 n − 1 n-1 n−1 个用电处位于 x i x_i xi​，需要在其范围 [ x i − r i , x i + r i ] [x_i-r_i,x_i+r_i] [xi​−ri​,xi​+ri​] 有一电塔才能保证供电。你可以任意设置电塔（与电站、用电所重合也可），但是这些电塔需要用线连接起来。问最少需要多长电线。 n ≤ 2 × 1 0 5 n leq 2times 10^5 n≤2×105， − 1 × 1 0 9 ≤ x s , x i ≤ 1 × 1 0 9 -1times 10^9 leq x_s,x_ileq 1times 10^9 −1×109≤xs​,xi​≤1×109， 0 ≤ r i , r s ≤ 1 × 1 0 9 0 leq r_i,r_s leq 1times 10^9 0≤ri​,rs​≤1×109。

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

#include 
using namespace std;
int main()
{
    int n;
    long long x, y;
    scanf("%d%lld%lld", &n, &x, &y);
    vector> 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> 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;
}

题意：给定纯数字序列 S S S，问存在多少对区间 [ l 1 , r 1 ] , [ l 2 , r 2 ] [l_1,r_1],[l_2,r_2] [l1​,r1​],[l2​,r2​] 满足 r 1 − l 1 = r 2 − l 2 r_1-l_1=r_2-l_2 r1​−l1​=r2​−l2​ 且 s l 1 s l 1 + 1 ⋯ s r 1 ‾ + 1 = s l 2 s l 2 + 1 ⋯ s r 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}} sl1​​sl1​+1​⋯sr1​​​+1=sl2​​sl2​+1​⋯sr2​​​。 ∣ S ∣ ≤ 4 × 1 0 5 |S| leq 4times 10^5 ∣S∣≤4×105。

解法：合法的区间一定满足 [ l 1 , r 1 ] = A p 99 ⋯ 9 [l_1,r_1]=Ap99cdots 9 [l1​,r1​]=Ap99⋯9， [ l 2 , r 2 ] = A ( p + 1 ) 00 ⋯ 0 [l_2,r_2]=A(p+1)00cdots 0 [l2​,r2​]=A(p+1)00⋯0，其中 A A A 表示一段连续且完全相同的子串。

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

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

#include 
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 t;
    vector> 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 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 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;
}

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

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

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

#include 
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 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 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("%lldn", ans);
    }
    return 0;
}

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

解法：可以证明当 A B ⊥ O Q AB perp OQ AB⊥OQ 时答案最大（利用画图软件观察得到）。剩下的利用三角函数计算即可。

题意：定义最大公共子树为，树上节点的值相同，且树上祖孙、兄弟关系完全相同。给定两个均以 1 1 1 为根的有根树，大小为 n , m n,m n,m，并给定树上点的值 { a i } , { b i } {a_i},{b_i} {ai​},{bi​}，问最大公共子树。 n , m ≤ 500 n,m leq 500 n,m≤500。

解法：考虑最朴素的 dp： f i , j , 0 / 1 f_{i,j,0/1} fi,j,0/1​ 表示在第一个树上走到节点 i i i，第二个树上走到节点 j j j， 0 0 0 表示 i , j i,j i,j 节点不一定匹配， 1 1 1 表示一定匹配，的最大公共子树。

对于 f i , j , 1 f_{i,j,1} fi,j,1​，首先满足 a i = b j a_i=b_j ai​=bj​。此外，两个子树需要匹配，考虑对 i i i 和 j j j 的儿子进行匹配——对 i i i 的儿子 u i u_i ui​ 和 v j v_j vj​ 儿子匹配的边权为 f u i , v j , 0 f_{u_i,v_j,0} fui​,vj​,0​。那么就是进行一次二分图的带权最大匹配，记这一最大匹配为 w w w，则 f i , j , 1 ← w + 1 f_{i,j,1} leftarrow w+1 fi,j,1​←w+1；对于 f i , j , 0 f_{i,j,0} fi,j,0​，可以从 f u i , v j , 0 , f i , j , 1 f_{u_i,v_j,0},f_{i,j,1} fui​,vj​,0​,fi,j,1​ 转移。

可以证明这样做的复杂度为 O ( n 3 ) mathcal O(n^3) O(n3)，足以通过本题。

题意：给定 n n n，问 [ 1 , n ] [1,n] [1,n] 数字按字典序排序，最大值为多少。 n ≤ 1 0 100000 n leq 10^{100000} n≤10100000。

解法：当 n ∈ [ 1 0 k − 10 , 1 0 k ] n in [10^{k}-10,10^k] n∈[10k−10,10k] 时直接输出 n n n，否则输出 k − 1 k-1 k−1 个 9 9 9。

题意：给定长度为 n n n 的序列 { a i } {a_i} {ai​}，和 m m m 条制限： ( b i , c i ) (b_i,c_i) (bi​,ci​) 表示第 b i b_i bi​ 个数字 x b i x_{b_i} xbi​​ 的二进制表示中 c i c_i ci​ 位必须为 0 0 0，问满足 ∑ a i x i ≤ m sum a_ix_i leq m ∑ai​xi​≤m 的长度为 n n n 的合法有序数列 ( x 1 , x 2 , ⋯   , x n ) (x_1,x_2,cdots,x_n) (x1​,x2​,⋯,xn​) 的个数。 n , ∑ a i ≤ 4 × 1 0 4 n,sum a_i leq 4times 10^4 n,∑ai​≤4×104， m ≤ 1 × 1 0 18 m leq 1times 10^{18} m≤1×1018。

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

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

因而总的复杂度为 O ( 120 ∑ a i log ⁡ 2 n ) mathcal O(120sum a_i log^2n) O(120∑ai​log2n)。

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

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

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

#include 
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 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: %lldn", o, f[cnt][123]);
    }
    return 0;
}

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

解法：记 S i S_i Si​ 表示设定命题 i i i 为公理时，所能推断出来的正确集合。则 S j ⊆ S i S_j sube S_i Sj​⊆Si​ 当且仅当命题 j j j 的所有前置条件均在 S i S_i Si​ 中。如果把每个前置条件关系看作一条有向边， S i S_i Si​ 集合所有的出边全部合并入 i i i 的出边，则 S j ⊆ S i S_j sube S_i Sj​⊆Si​ 当且仅当 j j j 仅有一条入边 i → j i to j i→j。

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

#include 
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    for (int o = 1; o <= t;o++)
    {
        scanf("%d", &n);
        vector> reach(n + 1);
        vector> graph(n + 1);
        vector deg(n + 1, 0), siz(n + 1, 1), father(n + 1);
        function getfather = [&](int x)
        {
            return father[x] == x ? x : father[x] = getfather(father[x]);
        };
        queue> 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", °[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: %dn", o, ans);
    }
    return 0;
}