牛客多校第六场题解

C Delete Edges

题意：给定一个由 $n$ 个点组成的完全图，每次可以选择三个点 $x,y,z$ ，如果边 $(x,y),(y,z),(z,x)$ 均存在，则删去这三条边。求一种构造可以不断的进行这样的操作使得最后剩下来的边数不超过 $n$ 。

解法：我们需要删掉的边总数至少为 $\displaystyle \frac{n(n-1)}{2}-n$ 。一开始我们可以有一个朴素的想法：找一个点出来，剩下的点两两配对，这样构成三点，这样我们删去边的次数为 $\displaystyle \frac{n-1}{2}$ 次。如果这个能重复 $n$ 次我们的目标就达到了。因而，我们可以考虑重复这个过程，即每一个点都拎出来，和剩下的点两两配对。如果能做到不重复的构造就行了。

基于这个思想，我们可以考虑利用数字关系。对于第 $i$ 号点，我们为其找的配对点对满足条件 $j+k=n-i$ 或者 $j+k=2n-i$ 。这样一来不容易构成重复，二来容易构造。

但是这样的三元组足够多吗？考察方程 $x+y+z \equiv 0 \mod n$ ，解的个数为 $\displaystyle \sum_{i=1}^{n} \lfloor \frac{n-i}{2} \rfloor=\frac{n^2-3n+2}{6},n=3k$ 或 $\displaystyle \frac{n^2-3n+6}{2},n \neq 3k$ 。带入发现这样的数目是绝对足够的。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct triple
{
    int a;
    int b;
    int c;
};
vector<triple> ans;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
        for (int j = i + 1; j <= n;j++)
        {
            int k = n - i - j;
            if(k<=0)
                k += n;
            if(k<=j || k==i)
                continue;
            ans.push_back((triple){i, j, k});
        }
    printf("%d\n", ans.size());
    for(auto i:ans)
        printf("%d %d %d\n", i.a, i.b, i.c);
    return 0;
}

D Gambling Monster

题意：有一个随机数发生器，以 $p_i$ 的概率生成一个数 $i$ ， $0 \leq i \leq n-1$ 。初始的数为 $0$ ，记上一轮的数为 $x$ ，若本轮产生的随机数 $y$ 满足 $x \oplus y>x$ ，则 $x$ 赋值为 $x \oplus y$ ，否则不动。问变成 $n-1$ 的期望轮数，满足 $n=2^k$ ， $n \leq 2^{16}$ 。

解法：首先考虑朴素 DP。记 $E(i)$ 为当前数值为 $i$ ，变到 $n-1$ 所需的期望步数，则 $E(n-1)=0$ ，待求 $E(0)$ 。考虑其转移： $\displaystyle E(x)=[E(x)+1][1-S(x)]+\sum_{x<z,x \oplus y=z} (E(z)+1) p(y)$ ，其中 $S(x)$ 为当前数为 $x$ ，随机选取了一个数 $y$ ，使其变大（ $x \oplus y>x$ ）的概率。整个式子含义为，若当前的数值为 $x$ ，那么可能摇到了一个无法让它变大的数，那么停留在 $x$ ，期望步数增加 $1$ ——对应 $[E(x)+1][1-S(x)]$ 。否则，摇到了 $y$ ，轮数增加， $x$ 对应变大到 $x \oplus y=z$ ，其概率为 $p(y)$ 。

考虑 $S(x)$ 的求法。显然，只有在 $x$ 对应二进制位下为 $0$ 的位置， $y$ 为 $1$ ，才会使 $x \oplus y$ 变大。考虑从高到低的枚举 $x$ 的每一个二进制位，如果第 $i$ 位为 $0$ ，则把**最高位为第 $i$ 位并且此位为 $1$ 的值**累加到 $S(x)$ 中。因为如果在第 $i$ 位这里变大了，后面的位其实可以不用管。

显然这样朴素转移的时间复杂度是 $O(n^2)$ ，无法接受。考虑此处转移的一个特殊性：只会由 $z>x$ 处转移到 $x$ ，因而可以考虑使用 cdq（陈丹琦）分治。cdq 分治原本是针对于序列上的操作，将全部修改询问操作离线化后利用时间的单调性，将操作序列按时间先后分成两个部分，先处理左侧的操作序列，再统计左侧操作对右侧的影响，再考虑右侧。此处可以类比这个操作——因为 DP 修改与赋值是单向的，只会由后侧的数对前面的数值产生影响，因而可以考虑使用 cdq 分治。

此外，注意到这个求和的条件—— $x \oplus y=z$ ，移项得到 $x =z \oplus y$ 。类比于多项式卷积的条件 $i+j=k$ ，此处是位运算的卷积，可以使用 FWT（快速沃尔什变换）在 $O(n \log n)$ 复杂度下处理异或卷积。推荐学习本文算法笔记｜快速沃尔什变换 FWT（或卷积、与卷积、异或卷积）。

整体复杂度 $O(n \log n)$ 。

代码中有两处细节需要说明：

一是在 cdq 函数中对 FWT 数组进行预处理时。由于这里的 $n=2^k$ ，因而每一个二分出来的区间，其区间端点一定都是 $2$ 的幂次的倍数，如 $4,12$ 等等。其特殊性在于，其区间中点 $mid$ 一定是最高变化位上的一个分界。例如，在区间 $[8,11]$ 中，其区间中点为 $10$ 。 $8$ 与 $9$ 的二进制为 $1000,1001$ ， $10$ 与 $11$ 的二进制为 $1010,1011$ 。容易发现，这一中点将区间恰好分成两个部分——第二位上为 $0$ 与为 $1$ 的部分，而第二位是这个区间中最高变化位。因而，可以考虑将 $mid$ 作为转移的分界点——在 $mid$ 以前，其概率均为 $0$ ，认为不可以从这些数转移；比 $mid$ 大的则可以转移。
在 cdq 函数的边界情况的考虑。注意到我们 cdq 函数最后的操作——直接将 $E(x)$ 累加上了 $\displaystyle \sum_{x<z,x \oplus y=z} (E(z)+1) p(y)$ 。因而现在 $E(x)$ 中存的不是 $E(x)$ 了而是方程中的后半项，即 $\displaystyle \sum_{x<z,x \oplus y=z} (E(z)+1) p(y)$ ，因而需要通过方程的求解解出 $E(x)$ 。解得 $\displaystyle E(x)=\frac{1+\sum_{x<z,x \oplus y=z} (E(z)+1) p(y)}{S(x)}-1$ ，这与代码中的表述相吻合。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const long long mod = 1000000007ll;
long long power(long long a,long long x)
{
    long long ans = 1;
    while(x)
    {
        if(x&1)
            ans = a * ans % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
long long inv(long long a)
{
    return power(a, mod - 2);
}
long long S[200005], sum[200005], E[200005], p[200005];
long long A[200005], B[200005];
void FWT(int n,long long *A,bool flag)
//flag为0表示正向变换，1表示反向变换（即反演）
{
    long long inv2 = (mod + 1) >> 1;
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1)
        for (int j = 0; j < n; j += l)
            for (int i = 0; i < m; i++)
            {
                long long x = A[i + j], y = A[i + j + m];
                if (!flag)
                {
                    A[i + j] = (x + y) % mod;
                    A[i + j + m] = (x - y + mod) % mod;
                }
                else
                {
                    A[i + j] = (x + y) * inv2 % mod;
                    A[i + j + m] = (x - y + mod) * inv2 % mod;
                }
            }
}

void cdq(int left,int right)
{
    if(left==right)
    {
        E[left] = ((E[left] + 1) * inv(S[left]) % mod + mod - 1) % mod;
        return;
    }
    int mid = (left + right) >> 1;
    cdq(mid + 1, right);//此处是后侧对前侧的影响。因而先处理后侧，然后是后侧对前侧的影响（见下），即是异或卷积部分
    int len = right - left + 1;
    for (int i = left; i <= mid;i++)
        A[i - left] = 0;
    for (int i = mid + 1; i <= right;i++)
        A[i - left] = E[i] + 1;
    for (int i = 0; i < len;i++)
        B[i] = p[i];
    FWT(len, A, 0);
    FWT(len, B, 0);
    for (int i = 0; i < len; i++)
        A[i] = (A[i] * B[i]) % mod;
    FWT(len, A, 1);
    for (int i = left; i <= mid;i++)
        E[i] = (E[i] + A[i - left]) % mod;
    cdq(left, mid);
    //最后处理左侧区间
}
int main()
{
    int n, t, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        m = log2(n);
        long long tot = 0;
        for (int i = 0; i < n;i++)
            E[i] = S[i] = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &p[i]);
            tot = (tot + p[i]) % mod;
        }
        tot = inv(tot);
        for (int i = 0; i < n;i++)
        {
            p[i] = p[i] * tot % mod;
            if (i)
                sum[i] = (sum[i - 1] + p[i]) % mod;
            else
                sum[i] = p[i];
        }
        for (int i = 0; i < n;i++)
            for (int j = m - 1; j >= 0;j--)
                if(!(i&(1<<j)))
                    S[i] = (S[i] + (sum[(1 << (j + 1)) - 1] - sum[(1 << j) - 1]) % mod + mod) % mod;
        cdq(0, n - 1);
        printf("%lld\n", E[0] + 1);
    }
    return 0;
}

H Hopping Rabbit

题意：在 $xOy$ 平面上有 $n$ 个矩形，问是否存在一点 $(x,y)$ ，使得从这一点任意的向 $x$ 轴正、负向， $y$ 轴正、负向跳 $d$ 步（允许多次）都不会落入任何一个矩形中。 $n, d\leq 1\times 10^5$ 。

解法：从一个点 $(x,y)$ 跳出去可以到达的点为 $(x+k_1d,y+k_2d),k_1,k_2 \in Z$ 。因而不妨取模，将所有的点与矩形全部集中在 $S=[0,d-1] \times [0,d-1]$ 中。

考虑如何将矩形放入 $S$ 中。如果其长大于 $d$ ，则映射到 $S$ 中则是一个横向覆盖了 $[0,d-1]$ 的长条；如果宽大于 $d$ 则同理，是一个纵向覆盖了 $[0,d-1]$ 的竖条。

如果长或者宽不超过 $d$ ，则一定没有完全覆盖 $[0,d-1]$ ，宽同理。下面以长举例：考虑对左右边界 $x_1,x_2$ 取模。如果 $x_1 \leq x_2$ ，则是分在一个 $d \times d$ 的块中，映射到 $S$ 就是直接的 $x_1,x2$ ；否则，在原图上则是覆盖了两个 $d \times d$ 的块，因而此时需要拆分成左侧的 $[1,x_2]$ 与右侧的 $[x_1,d]$ 。 $y$ 方向上同理。

覆盖完成之后，只需要像扫描线那样，一排排的处理，不断的覆盖、删去矩形即可。可以维护一个区间最小值，如果最小值为 $0$ ，则证明这一排有未覆盖的部分，可以直接枚举找到即可。当然也可以求出所有矩形在 $S$ 上的覆盖面积。二者都可以使用扫描线快速的求出。

注意到此题 $d$ 不是很大，因而不需要离散化处理。整体复杂度 $O(n \log n)$ 。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int inf = 0x3f3f3f3f;
struct node
{
    int minimum;
    int tag;
};
struct node t[400005];
void change(int place, int left, int right, int start, int end,int x);
void pushdown(int place,int left,int right)
{
    if(t[place].tag)
    {
        int mid = (left + right) >> 1;
        change(place << 1, left, mid, left, mid, t[place].tag);
        change(place << 1 | 1, mid + 1, right, mid + 1, right, t[place].tag);
        t[place].tag = 0;
    }
    return;
}
void change(int place,int left,int right,int start,int end,int x)
{
    if(start<=left && right<=end)
    {
        t[place].minimum += x;
        t[place].tag += x;
        return;
    }
    pushdown(place, left, right);
    int mid = (left + right) >> 1;
    if(start<=mid)
        change(place << 1, left, mid, start, end, x);
    if(end>mid)
        change(place << 1 | 1, mid + 1, right, start, end, x);
    t[place].minimum = min(t[place << 1].minimum, t[place << 1 | 1].minimum);
}
int query(int place,int left,int right,int start,int end)
{
    if(start<=left && right<=end)
        return t[place].minimum;
    pushdown(place, left, right);
    int mid = (left + right) >> 1;
    int ans = inf;
    if(start<=mid)
        ans = min(ans, query(place << 1, left, mid, start, end));
    if(end>mid)
        ans = min(ans, query(place << 1 | 1, mid + 1, right, start, end));
    return ans;
}
struct line
{
    int left;
    int right;
    int flag;
};
vector<line> op[100005];
int main()
{
    int n, d;
    int x1, y1, x2, y2;
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n;i++)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        //由于它是跳在格子正中，因而真正在覆盖的时候x2与y2都需要减一
        int left, right, up, down;
        if (x2 - x1 >= d)//先判定长度是否大于 d，不要贸然取模
        {
            left = 1;
            right = d;
        }
        else
        {
            left = (x1 % d + d) % d + 1;
            right = ((x2 - 1) % d + d) % d + 1;
        }
        if (y2 - y1 >= d)
        {
            down = 1;
            up = d;
        }
        else
        {
            down = (y1 % d + d) % d + 1;
            up = ((y2 - 1) % d + d) % d + 1;
        }
        if (left<=right)//分横向是否被分成两块
        {
            if (down<=up)//分纵向是否被分成两块
            {
                op[down].push_back((line){left, right, 1});
                op[up + 1].push_back((line){left, right, -1});
            }
            else
            {
                op[1].push_back((line){left, right, 1});
                op[up + 1].push_back((line){left, right, -1});
                op[down].push_back((line){left, right, 1});
                op[d + 1].push_back((line){left, right, -1});
            }
        }
        else
        {
            if (down<=up)
            {
                op[down].push_back((line){1, right, 1});
                op[down].push_back((line){left, d, 1});
                op[up + 1].push_back((line){1, right, -1});
                op[up + 1].push_back((line){left, d, -1});
            }
            else
            {
                op[1].push_back((line){1, right, 1});
                op[1].push_back((line){left, d, 1});
                op[up + 1].push_back((line){1, right, -1});
                //纵向上采用了差分的思想：只在要改变的时候再修改。因而上边界都要加1
                op[up + 1].push_back((line){left, d, -1});
                op[down].push_back((line){1, right, 1});
                op[down].push_back((line){left, d, 1});
                op[d + 1].push_back((line){1, right, -1});
                op[d + 1].push_back((line){left, d, -1});
            }
        }
    }
    for (int i = 1; i <= d;i++)
    {
        for (auto j : op[i])//要将一行处理完再下定论
            change(1, 1, d, j.left, j.right, j.flag);
        if (query(1, 1, d, 1, d) == 0)
        {
            for (int j = 1; j <= d;j++)
                if (query(1, 1, d, j, j) == 0)
                {
                    printf("YES\n%d %d\n", j - 1 + d, i - 1 + d);
                    break;
                }
            return 0;
        }
    }
    printf("NO");
    return 0;
}

J Defend Your Country

题意：给定一张无向连通图，每个点有点权 $a_i$ 。现在可以从原图上删除一些边，将图分成若干个连通块。每一个连通块 $S$ 的总权值等于 $\displaystyle (-1)^n\sum_{i \in S} a_i$ ，其中 $n$ 为连通块 $S$ 的点数。问所有连通块总的权值和最大为多少。 $n \leq 1\times 10^6$ 。

解法：显然，如果全部点数（即原式连通块大小）为偶数，那么根本不用切分。因而接下来的情况均是考虑奇数个点的连通块情况。

考虑一个奇数个点的连通块。如果当前这个连通块内点的最小权值 $a_i$ 对应的点 $i$ 不是这个连通块的割点，即去掉后原连通块不会变成若干个子连通块，那么显然切除它是最优选择；或者，去掉它之后，整个连通块变成了它和若干个偶数大小的子连通块，那么也是切除它。

并且，最后不会留有一个奇数大小的连通块——因为切到最后，最坏不过全切成单点，这样都不会变坏；而且切到只剩三个点的时候，一定有一个非割点的存在，那么至少可以保全一个偶数大小（为 $2$ ）的连通块，这样答案更优。

那么现在的情况就是最小权值刚好为割点的情况。显然，不会切除偶数个割点——否则整个初始连通块大小为奇数，切完之后大于 $1$ 的连通块点数之和还为奇数，矛盾。因而现在切有奇数个割点。

考虑这些割点的排布。如果将原图放在圆方树上，割点也放入，则它们构成了一棵树。如果一个图上割去了大于 $1$ 个割点，则必然存在一个割点，它与多个节点相邻，而割点都应该是叶子节点，矛盾。因而只割去一个割点。

因此只需要枚举一个点，如果是割点，则看它的权值是否满足全部的子连通块均为偶数；反之直接统计权值。对于那些切分下来存在奇数大小连通块的，不予考虑。

整体复杂度 $O(n)$ 。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
struct line
{
    int from;
    int to;
    int next;
};
struct line que[2 * N + 5];
int cnt, headers[N + 5];
int dfn[N + 5], low[N + 5], ind, siz[N + 5];
bool cut[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;
}
long long minimum = inf;
long long a[N + 5];
void tarjan(int u,int father)
{
    dfn[u] = low[u] = ++ind;
    siz[u] = 1;
    int child = 0;
    bool ok = 1;
    for (int i = headers[u]; i; i = que[i].next)
        if(!dfn[que[i].to])
        {
            tarjan(que[i].to, father);
            low[u] = min(low[u], low[que[i].to]);
            siz[u] += siz[que[i].to];
            if(low[que[i].to]>=dfn[u])
            {
                if(u!=father)
                    cut[u] = 1;
                else
                    child++;
                if(siz[que[i].to]%2==1)
                    ok = 0;
            }
        }
        else
            low[u] = min(low[u], dfn[que[i].to]);
    if(child>=2)
        cut[u] = 1;
    if(!cut[u])
        minimum = min(minimum, a[u]);
    if(cut[u] && ok)
        minimum = min(minimum, a[u]);
}
int main()
{
    int n, m, t, u, v;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        cnt = ind = 0;
        for (int i = 1; i <= n;i++)
            headers[i] = dfn[i] = low[i] = siz[i] = cut[i] = 0;
        minimum = inf;
        long long sum = 0;
        for (int i = 1; i <= n;i++)
        {
            scanf("%lld", &a[i]);
            sum += a[i];
        }
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
        }
        if(n%2==0)
        {
            printf("%lld\n", sum);
            continue;
        }
        tarjan(1, 1);
        printf("%lld\n", sum - 2*minimum);
    }
    return 0;
}

牛客多校第六场 题解

C Delete Edges

D Gambling Monster

H Hopping Rabbit

J Defend Your Country

牛客多校第六场题解