2021-08-11 12:27 北京大学 C++

关注

牛客多校第一场题解

G Game of Swapping Numbers

题意：给定两个序列 $\{a_n\},\{b_n\}$ ，可以对 $\{a_n\}$ 进行恰好 $k$ 次交换，最大化 $\displaystyle \sum_{i=1}^{n} |a_i-b_i|$ 。

解法：先简化该问题，若不计交换次数，即允许任意排列 $a_i$ ，最大答案为多少？

考虑每一位上对答案的贡献。若 $a_i>b_i$ ，则 $|a_i-b_i|=a_i-b_i$ ，反之等于 $-a_i+b_i$ 。可以注意到在这个操作中， $a_i$ 与 $b_i$ 各添加了一个正负号。那么进而拓展到整个序列，那么对于答案来说，一定是等于将 $a_i$ 与 $b_i$ 合并起来加上 $n$ 个正号 $n$ 个负号之后加起来的答案。那么为了最大化这个答案，我一定是将最大的 $n$ 个数给正号，其余给负号，这样的答案一定最大。

关于其正确性：显然，正号负号一样多，如果存在两个负号放在一起，即此时的 $a_i$ 与 $b_i$ 同为最小的 $n$ 个数。那么必然有两个正号放在一起。如果此时交换这两对数，一定可以使答案变得更大，因而恢复到每一对数都有一正一负的情况，刚好符合绝对值的定义。

此题第二个难点：恰好 $k$ 次。注意到除了 $n=2$ ，其余的都有“至多 $k$ 次一定等于恰好 $k$ 次”。原因很简单：当 $n\geq 3$ 时，一定存在多于两对数的 $a_i$ 正负性相同，此时交换这两对数不会对答案造成影响，因而一定可以凑足 $k$ 次。

考虑此时加回 $k$ 的限制。根据以上的分析，我们显然不会对一正一负的情况进行交换，而只交换一对由两正和两负构成的数对。不妨设两正的数对为 $(a_i,b_i)$ 与 $(a_j,b_j)$ ，其中 $a_i>b_i$ ， $a_j>b_j$ 。原有答案为 $a_i-b_i+a_j-b_j$ ，交换后形成两对一正一负，答案变为 $a_i+b_i-a_j-b_j$ ，答案的变化量为 $2(b_i-a_j)$ 。更加一般化的，每次操作的变化量为 $2(\min\{a_i,b_i\}-\max\{a_j,b_j\})$ 。

那么出于一个贪心的考量，当 $n\geq 3$ 时，一定是选取最大的 $k$ 个 $\min\{a_i,b_i\}$ 与最小的 $k$ 个 $\max\{a_i,b_i\}$ ，这样答案最优。注意交换一次之后如果答案变小了，则可以终止了。

#include <cstdio>
#include <algorithm>
using namespace std;
long long a[500005], b[500005];
long long maximum[500005], minimum[500005];
int main()
{
    int n;
    long long k;
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n;i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n;i++)
        scanf("%lld", &b[i]);
    if (n == 2)
    //n=2需要特判
    {
        if (k % 2 == 1)
            swap(a[1], a[2]);
        printf("%lld", abs(a[1] - b[1]) + abs(a[2] - b[2]));
        return 0;
    }
    long long ans = 0;
    for (int i = 1; i <= n;i++)
        ans += abs(a[i] - b[i]);
        //统计基本盘
    for (int i = 1; i <= n;i++)
    {
        maximum[i] = max(a[i], b[i]);
        minimum[i] = min(a[i], b[i]);
    }
    sort(maximum + 1, maximum + n + 1);
    sort(minimum + 1, minimum + n + 1);
    for (int i = 1; i <= min((long long)n, k);i++)
    //此处为增量部分
        ans += 2ll * max(minimum[n - i + 1] - maximum[i], 0ll);//找最大的k个min值与最小的k个max值。注意要让ans越来越大。
    printf("%lld", ans);
    return 0;
}

H Hash Function

题意：给定一组数 $\{ a_n \}$ ，求出最小模数，使得任意两个数在该模数意义下互不同余。数的个数 $n \leq 5\times 10^5$ ，数的范围 $a_i \in [0,5\times 10^5]$ 。

解法：很明显，要想互不同余，那么它们之间的差的任何因子不能作为模数，因而问题转化为求解这些差值，之后枚举因数即可。

如果一个差值存在，那么一定存在一种构造方法，因而问题可以继续转变——求解一个差值到底有多少种方式构成。

而统计方案数，通常考虑构造母函数。记 $max$ 为最大的 $a_i$ ，令 $\displaystyle f(x)=\sum_{i=1}^{max}b_ix^i$ ， $\displaystyle g(x)=\sum_{i=1}^{max}b_ix^{-i}$ 。其中：
$ $b_i=\left\{ \begin{array}{c} 1 ,a_{b_i}\in \{a_n\}\\ 0,otherwise \end{array} \right.$ $

将二者相乘，得到 $h(x)=f(x)g(x)$ ，可以被表示为 $\displaystyle h(x)=\sum_{i=-n}^{n}c_ix^i$ ， $c_i$ 表示了有多少种方式可以构成这个差值 $i$ 。因而此题使用 FFT 即可解决。

但是我们注意到 FFT 通常不能处理负数次方，因而改写 $\displaystyle g(x)=x^{-max} \sum_{i=1}^{max}b_ix^{max-i}$ ，即可保证在乘积过程中每项次方数为正。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi = acos(-1);
struct complex
{
    double x;
    double y;
};
struct complex f[4000005], g[4000005];
int r[4000005];
complex operator +(complex a,complex b)
{
    return (complex){a.x + b.x, a.y + b.y};
}
complex operator -(complex a,complex b)
{
    return (complex){a.x - b.x, a.y - b.y};
}
complex operator *(complex a,complex b)
{
    return (complex){a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x};
}
void FFT(complex *J,int times,int flag)
{
    for (int i = 1; i < times;i++)
        if(i<r[i])
            swap(J[i], J[r[i]]);

    for (int i = 1; i < times; i <<= 1)
    {
        complex unit = (complex){cos(flag * pi / i), sin(flag * pi / i)};
        for (int j = 0; j < times; j += i * 2)
        {
            complex w = (complex){1, 0};
            for (int k = 0; k < i; k++, w = w * unit)
            {
                complex x = J[j + k], y = w * J[j + i + k];
                J[j + k] = x + y;
                J[j + k + i] = x - y;
            }
        }
    }
}
int a[500005];
bool vis[500005];
int main()
{
    int n, times = 1, left = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        f[a[i]].x = g[500000 - a[i]].x = 1;
        //此处即为修改后g的定义。显然，我们不需要那个前面的负数次方，因为并不影响计算，因而直接叠上去。
    }
    while (times <= 1000000)
    {
        times <<= 1;
        left++;
    }
    for (int i = 0; i < times; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (left - 1));
    FFT(f, times, 1);
    FFT(g, times, 1);
    for (int i = 0; i <= times; i++)
        f[i] = f[i] * g[i];
    FFT(f, times, -1);
    for (int i = 500001; i <= 1000000; i++)
    {
        int temp = (int)(f[i].x / times + 0.5);//注意 FFT 的局限性，有精度误差，因而建议使用 NTT
        if (temp)
            vis[i - 500000] = 1;
    }  
    // O(nlogn) 方法检测因数是否存在
    for (int i = n; i <= 500001;i++)
    {
        bool flag = 0;
        for (int j = i; j <= 500000; j += i)
            if(vis[j])
            {
                flag = 1;
                break;
            }
        if(!flag)
        {
            printf("%d", i);
            return 0;
        }
    }
    return 0;
}

I Increasing Subsequence

题意：给定一个 $1$ 到 $n$ 的排列，Alice 与 Bob 二人从这个排列中随机选取数字。要求如下：

每一个人取出的数字都要比另一个人上一轮取出的数字大。
每一个人都要比自己上一轮取出的数字更靠右。
如果存在多个合法数字，则从中等概率选取。

问期望游戏轮数。

解法：首先将问题进行转化。考虑排列为 $\{p_n\}$ ，令新的序列为 $q_{p_i}=i$ ，即 $i$ 位于 $p$ 中的位置为 $q_i$ ，则原问题转化为在 $q$ 序列上，Alice 和 Bob 两人从前向后取数字，同时满足自己比上一轮取得数字更大。

首先，这个问题的边界条件一定是某一个人取到了最后一位。如果刚一开始就取到了这个值，那么答案为 $1$ 。还有一种终止情况：如果某一个人选取完第 $i$ 位的数字后， $[i+1,n]$ 的范围内没有数字比 $q_i$ 大，那么对手一定有选取方法——显然现在还有比 $i$ 更靠后的位置可以选，同时他没有受到这个人在数值上的限制，因而可选。同时对手取完后游戏结束，因而这种情况下答案为 $2$ 。

显然我们知道最后的结局，因而考虑倒推这个 DP，即起始状态为最后终止状态。设计 DP 状态： $f[i][j]$ 表示当前选取的位置为 $i$ ，上一轮在 $j$ 处选取时的期望轮数。

接下来是转移。如果 $j$ 之后大于 $q_i$ 的数字有 $k$ 个，所在位置分别记为 $\{p_k\}$ ，那么可以从这 $k$ 个状态中等概率转移至此，即 $\displaystyle f[i][j]=1+ \frac{\sum^{k}_{l=1}f[j][p_l]}{k}$ 。

接下来形式化边界条件。如果 $k=0$ ，且 $i \neq n$ ，则 $f[i][j]=2$ 。如果 $i=n$ ，则游戏立刻结束， $f[i][j]=1$ 。

考虑其实现。从后到前枚举 $i$ ，开启一个新计数器 $cnt$ ，从后向前推进 $j$ ，如果当前枚举发现 $q_j>q_i$ ，即证明这里可以成为潜在的转移对象，计数器增加 $1$ 。同时使用树状数组统计 $\displaystyle \sum^{cnt}_{l=1}f[j][p_l]$ 。统计完毕后将 $f[i][j]$ 插入到以 $i$ 为键值的树状数组中。

但是我们很容易发现一个问题：树状数组里存储的数在位置上连续而非值域上连续。即，树状数组里我们需要累加的和并非是在空间上连续的，这样是无法使用树状数组的。因而我们需要让值域连续排布，这样就可以使用树状数组了。即，每次插入 $f[i][j]$ ，我们统计第 $j$ 棵树状数组中 $[q[i],n]$ 的和，然后插入到第 $i$ 棵树状数组的 $q[j]$ 位置。

总体时间复杂度 $O(n^2 \log n)$ 。

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
const int N=5005;
const int p=998244353;
int n,P[N],q[N];

inline int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=1ll*ans*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return ans;
}

int dp[N][N];
inline void dpadd(int x,int k,int opt){for(int i=x;i<=n+1;i+=lowbit(i)) {dp[opt][i]=dp[opt][i]+k;if(dp[opt][i]>p) dp[opt][i]-=p;}}
inline int dpsum(int x,int opt){int ans=0;for(int i=x;i;i-=lowbit(i)) {ans=ans+dp[opt][i];if(ans>p) ans-=p;}return ans;}

int tmp[N];

int c[N];
inline void add(int x,int k){for(int i=x;i<=n;i+=lowbit(i)) c[i]+=k;}
inline int sum(int x){int ans=0;for(int i=x;i;i-=lowbit(i)) ans+=c[i];return ans;}
int cnt[N][N];
int icnt[N][N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",P+i);
    for(int i=1;i<=n;i++) q[P[i]]=i;
    for(int i=0;i<=5000;i++) tmp[i]=qpow(i,p-2);
    //注：此处可使用递推，复杂度可以降低一个log。具体方法见下。
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<n;j++)
        {
            cnt[i][j]=sum(n-j+1),icnt[i][j]=tmp[cnt[i][j]];
            if(cnt[i][j]==0) break;
        }
        add(n-q[i]+1,1);
    }

    dpadd(1,1,n);
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            int ans=dpsum(n+1-q[i]+1,j);
            if(cnt[j][q[i]]) ans=1ll*ans*icnt[j][q[i]]%p;
            else ans=1;
            ans=ans+1;
            if(ans>p) ans-=p;
            dpadd(n+1-q[j]+1,ans,i);
        }
    }

    int ans=0;
    for(int i=1;i<n;i++) ans=(ans+1ll*dpsum(n+1,i)*tmp[n-i]%p*tmp[n]%p)%p;
    ans=(ans+1ll*dpsum(n+1,n)*qpow(n,p-2)%p)%p;
    printf("%d\n",ans);

    return 0;
}

此题还有另外一种解法：还是做最初的那个变换，使用前缀和优化 DP。令 $f[i][j]$ 为当前选取第 $i$ 位，上一位选取的数字大于等于 $j$ 的期望轮数。因而转移方程得到简化： $\displaystyle f[i][j]=1+ \frac{f[j][q_i+1]}{k}$ ，最后只需要 $O(n)$ 的复杂度完成一次前追求和即可。依旧还是倒着完成 DP，但是此法不需要使用树状数组维护，因而总体时间复杂度为 $O(n^2)$ 。

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
const int N=5005;
const int p=998244353;
int n,P[N],q[N];

int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=1ll*ans*a%p;
        a=1ll*a*a%p;
        b>>=1;
    }
    return ans;
}

int dp[N][N];

int tmp[N];
int cnt[N][N];
int icnt[N][N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",P+i);
    for(int i=1;i<=n;i++) q[P[i]]=i;
    for(int i=0;i<=5000;i++) tmp[i]=qpow(i,p-2);
    for(int i=n-1;i>=1;i--)
    {
        for(int j=n;j>=1;j--)
        {
            cnt[i][j]=cnt[i+1][j]+(q[i+1]>j);
            icnt[i][j]=tmp[cnt[i][j]];
        }
    }

    for(int i=1;i<=n+1;i++) dp[n][i]=1;
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(cnt[j][q[i]]) dp[i][q[j]]=(1+1ll*dp[j][q[i]+1]*icnt[j][q[i]]%p)%p;
            else dp[i][q[j]]=2;
            //和上文一样，如果没有cnt则直接强制赋2
        }
        for(int j=n;j>=1;j--) dp[i][j]=(dp[i][j]+dp[i][j+1])%p;
        //求前缀和
    }

    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+1ll*dp[i][1]*tmp[n-i]%p*tmp[n]%p)%p;
    ans=(ans+1ll*dp[n][1]*tmp[n]%p)%p;
    printf("%d\n",ans);

    return 0;
}

J Journey among Railway Stations

题意：每个站有一个开站时间 $[u_i,v_i]$ ，仅能在开站时间内到着、停靠、发车，站间有间距 $dis_i$ ，现有如下三种操作：

询问火车能否从 $i$ 站到 $j$ 。
修改站 $i$ 到 $i+1$ 站的距离。
修改站 $i$ 的开站时间。

解法：考虑线段树维护一个函数：自变量为发车时间，因变量为到着下一站的时间。显然这个函数通常情况是一个分段函数——由一段平段和一个斜率为 $1$ 的上斜段构成。其中，平段是由于下一站开站时间过晚，以至于前一站发车后到着下一站但无法停靠。斜段则是正常的到着，此后函数无定义。

这种函数的一个好处是容易合并：两个这样的函数依旧可以合成一个这样的函数。因而考虑使用线段树，仅需执行两种单点修改、区间查询。合并的操作见函数 pushup。

详细说明在代码的注释中。

#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
    long long earliest;
    //当前站（区间最左站）为了到区间最右站最早开车时间
    long long latest;
    //当前站（区间最左站）为了到区间最右站最晚开车时间
    long long last_time;
    //上一个区间最右站到当前站（区间最左站）最早到着时间。即函数图像中平段的函数值
    long long dis;
    //区间最右站到下一个区间最左站所用时间
    bool ans;
};
struct node t[4000005];
node pushup(node left,node right)
{
    node u;
    u.ans = left.ans & right.ans;
    if(!u.ans)
        return u;
    //t-left.last_time-left.dis是为了到下一个站时间为t所需时间差
    if(left.last_time+left.dis<right.earliest)
    //到的太早了，最早到着时尚未开站，与其在到着站等着开站不如在原站等到不能等或者合适的时候再开车，到着的时候直接开站
    {
        u.earliest = min(left.earliest + right.earliest - left.last_time - left.dis, left.latest);
        u.latest = min(left.earliest + right.latest - left.last_time - left.dis, left.latest);
        //由于当前需要等待，因而总区间平段函数值等于右端平段函数值
        u.last_time = right.last_time;
    }
    else if(left.last_time+left.dis<=right.latest)
    //最早开车下一站也开站了，因而只用考虑能不能在下个站关站前到着
    {
        u.earliest = min(left.earliest, left.latest);
        u.latest = min(left.earliest + right.latest - left.last_time - left.dis, left.latest);
        //去即开站，没有平段，因而只记录最快到着时间
        u.last_time = left.last_time + left.dis + (right.last_time - right.earliest);
    }
    else//错过
        u.ans = 0;
    u.dis = right.dis;
    return u;
}
long long earliest[1000005], latest[1000005], dis[1000005];
//下面为正常的线段树
void build(int place,int left,int right)
{
    if(left==right)
    {
        t[place].earliest = t[place].last_time = earliest[left];
        t[place].latest = latest[left];
        t[place].dis = dis[left];
        t[place].ans = 1;
        return;
    }
    int mid = (left + right) >> 1;
    build(place << 1, left, mid);
    build(place << 1 | 1, mid + 1, right);
    t[place] = pushup(t[place << 1], t[place << 1 | 1]);
}
void update1(int place,int left,int right,int start,long long earliest,long long latest)
{
    if(left==right)
    {
        t[place].earliest = t[place].last_time = earliest;
        t[place].latest = latest;
        return;
    }
    int mid = (left + right) >> 1;
    if(start<=mid)
        update1(place << 1, left, mid, start, earliest, latest);
    else
        update1(place << 1 | 1, mid + 1, right, start, earliest, latest);
    t[place] = pushup(t[place << 1], t[place << 1 | 1]);
}
void update2(int place,int left,int right,int start,long long dis)
{
    if(left==right)
    {
        t[place].dis = dis;
        return;
    }
    int mid = (left + right) >> 1;
    if(start<=mid)
        update2(place << 1, left, mid, start, dis);
    else
        update2(place << 1 | 1, mid + 1, right, start, dis);
    t[place] = pushup(t[place << 1], t[place << 1 | 1]);
}
node query(int place,int left,int right,int start,int end)
{
    if(start<=left && right<=end)
        return t[place];
    int mid = (left + right) >> 1;
    if(end<=mid)
        return query(place << 1, left, mid, start, end);
    if(start>mid)
        return query(place << 1 | 1, mid + 1, right, start, end);
    return pushup(query(place << 1, left, mid, start, end), query(place << 1 | 1, mid + 1, right, start, end));
}
int main()
{
    int n, m, t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n;i++)
            scanf("%lld", &earliest[i]);
        for (int i = 1; i <= n;i++)
            scanf("%lld", &latest[i]);
        for (int i = 1; i < n;i++)
            scanf("%lld", &dis[i]);
        dis[n] = 0;
        build(1, 1, n);
        scanf("%d", &m);
        while(m--)
        {
            int op;
            scanf("%d", &op);
            switch(op)
            {
                case 0:
                {
                    int left, right;
                    scanf("%d%d", &left, &right);
                    node ans = query(1, 1, n, left, right);
                    if(ans.ans)
                        printf("Yes\n");
                    else
                        printf("No\n");
                    break;
                }
                case 1:
                {
                    int place;
                    long long w;
                    scanf("%d%lld", &place, &w);
                    update2(1, 1, n, place, w);
                    break;
                }
                case 2:
                {
                    int place;
                    long long u, v;
                    scanf("%d%lld%lld", &place, &u, &v);
                    update1(1, 1, n, place, u, v);
                    break;
                }
            }
        }
    }
    return 0;
}

K Knowledge Test about Match

题意：给定一个序列 $\{a_n\}$ ，保证 $a_i \in [0,n-1]$ ， $n\leq 1\times 10^3$ 。现在希望调整这个序列中元素的顺序，使得 $\displaystyle \sum_{i=0}^{n-1}\sqrt{|a_i-i|}$ 最小。但是允许存在 $4\%$ 的相对误差。

解法：此题属于应用类题——允许误差存在，但是数据范围相对较大。正解为 KM 算法：考虑 $a_i$ 对 $[0,n-1]$ 中每个元素建立一条权值为 $\sqrt{|a_i-i|}$ 的边，然后解为最小权匹配。但是这个算法的复杂度为 $O(n^3)$ ，无法承受，又允许一定误差，因而可以使用贪心或者近似算法。

两种方法：考虑 $f(x)=\sqrt{x}$ 的性质：越靠近 $0$ ，其导数越大，因而在靠近 $0$ 的时候权重越大。因而优先保障差值较小的值，可以使用暴力匹配的方式。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
int a[1005], ans[1005];
bool vis[1005];
int main()
{
    int n, t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        map<int, int> num;
        for (int i = 1; i <= n;i++)
            vis[i] = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 0; i < n;i++)
            num[i] = 1;
        for (int i = 0; i < n;i++)
        //枚举差值
        {
            for (int j = 1; j <= n;j++)
                if(!vis[j])
                {
                    if(num[a[j]-i]==1)
                    //[0,n-1] 中存在这样的值，便匹配
                    {
                        num[a[j] - i] = 0;
                        vis[j] = 1;
                        ans[a[j] - i] = a[j];
                    }
                    else if(num[a[j]+i]==1)
                    {
                        vis[j] = 1;
                        num[a[j] + i] = 0;
                        ans[a[j] + i] = a[j];
                    }
                }
        }
        for (int i = 0; i < n; i++)
            printf("%d ", ans[i]);
        printf("\n");
    }
    return 0;
}

还可以使用局部调整的想法，类似于冒泡排序：如果两个数交换后权值更低，则交换。

double f(int x,int y)
{
    return sqrt(abs(x-y));
}
void cal(int n)
{
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(cal(a[i],i-1)+cal(a[j],j-1)>cal(a[i],j-1)+cal(a[j],i-1))
                swap(a[i],a[j]);
}