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

A、Alice and Bob

题目大意

两人博弈，每次一个人从一堆中拿$k$个，同时从另一堆拿$k*s(s\ge0)$个，问谁先不能拿
$10000$组数据，$N\le5000$

考察内容

博弈、SG优化

解题思路

暴力

设$sg[i][j]$表示第一堆是$i$且第二堆是$j$时的SG函数，直接模拟所有取石子转移。注意有一维枚举的是倍数，所以总复杂度是$𝑂(𝑁^3log𝑁)$

优化

我们考虑后手胜利的状态不会很多，当某堆石子数量为i时，另一堆石子最多只有一种数量满足后手胜，这里引用出题人给出的证明：
反证法：假设$(i,p)$和$(i,q)$都是后手必胜，且$q>p$。那么在状态$(i,q)$时，先手可以在第二堆选$q-p$个，第一堆选$0$个，转移到后手胜的$(i,p)$,说明$(i,q)$是先手胜，矛盾。
因此我们可以根据SG函数的定义，我们可以采用筛的方式，用SG为0的去筛SG为1的。复杂度是$𝑂(𝑁^2log𝑁)$，实际速度近似$𝑂(𝑁)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# include <bits/stdc++.h>
# define LL long long

bool f[5010][5010];
int n,m,T;

int main() {
    for (int i=0; i<=5000; ++i)
        for (int j=0; j<=5000; ++j) {
            if (f[i][j]) continue;
            for (int x=1; x+i<=5000; ++x)
                for (int y=0; y+j<=5000; y+=x)
                    f[x+i][y+j] = 1;
            for (int x=1; x+j<=5000; ++x)
                for (int y=0; y+i<=5000; y+=x)
                    f[y+i][x+j] = 1;
        }
    
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        if (f[n][m]) printf("Alice\n");
        else printf("Bob\n");
    }
}

B、Ball Dropping

题目大意

一个球卡在一个直角等腰梯形内部，求卡着的高度。

考察内容

简单平面几何。

解题思路

就是模拟计算就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# include <bits/stdc++.h>
# define LL long long
# define N 2010
using namespace std;
int r,a,b,h;
int main() {
    scanf("%d%d%d%d",&r,&a,&b,&h);
    if (b > 2*r) printf("Drop\n"),exit(0);
    printf("Stuck\n");
    double t = 1.0*b*h/(a-b);
    double ans = sqrt(t*t*1.0+b*b*1.0/4);
    ans = ans*2*r/b-t*1.0;
    printf("%.8lf",ans);
}

C、Cut the Tree

待补

D、Determine the Photo Position

题目大意

给出一个$nn$的01矩阵，要用一个$1m$的矩阵去覆盖一段$0$，问方案数。

考察内容

模拟

解题思路

签到

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include <bits/stdc++.h>
# define LL long long
# define N 2010
using namespace std;
int n,m,ans,p[N];
char s[2010];
 
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; ++i)
    {
        scanf("%s",s+1);
        p[n+1] = n+1;
        for (int j=n; j; --j) {
            if (s[j] == '0') p[j] = p[j+1];
            else p[j] = j;
        }
        for (int j=1; j<=n; ++j) if (p[j]-j >= m) ans++;
    }
    scanf("%s",s);
    printf("%d",ans);
}

E、Escape along Water Pipes

题目大意

给出一个$n*m$的水管图，要从$(1,1)$顶部走到$(n,m)$底部。每走一步前，可以选择一个管道集合旋转相同的角度。要求在$20nm$步前走到终点或者输出无解。

考察内容

模拟能力，BFS

解题思路

其实不同各自之间的状态是无关的，选取集合旋转没有意义，我们只需要每次走一步然后将下一个格子转到我们想要的角度就可以在接着走就可以，因此实际上所有的状态只会有$4nm$个，即$nm$个格子以及$4$个方向，每个状态会有转动格子和行走两个操作，因此最多只会有$8nm$个操作，我们只需要BFS这$4nm$个状态即可。注意细节：一个格子可能会被先后重复旋转，而第二次旋转之前的角度是第一次旋转之后的结果，不能每次旋转的时候都和刚开始时候比较选择角度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# include <bits/stdc++.h>
# define N 1010
using namespace std;

int T,n,m,to[4][4],a[N][N],dir[N][N][4],vis[N][N][4],ans;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

struct zx{
    int x,y,d;
}pre[N][N][4];

struct pp{
    int d,x,y;
}ansq[N*N*20];

void init() {
    to[0][3] = to[3][0] = 0;
    to[0][1] = to[1][0] = 1;
    to[1][2] = to[2][1] = 2;
    to[2][3] = to[3][2] = 3;
    to[1][3] = to[3][1] = 4;
    to[0][2] = to[2][0] = 5;
}

void dfs() {
    int nx=0,ny=1,nd=0;
    while (nx != n||ny != m||nd != 0) {
        zx t = pre[nx][ny][nd];
        int tx = t.x,ty = t.y;
        if (a[tx][ty] != dir[nx][ny][nd]) ansq[++ans]=(pp){(dir[nx][ny][nd]-a[tx][ty]+4)%4*90,tx,ty};
        a[tx][ty] = dir[nx][ny][nd];
        ansq[++ans] = (pp){0,tx,ty};
        nx = tx,ny = ty,nd = t.d;
    }
}

int main() {
    init();
    scanf("%d",&T);
    
    for (int tt=1; tt<=T; ++tt){
        scanf("%d%d",&n,&m);
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=m; ++j)
                scanf("%d",&a[i][j]);
        queue <zx> q;
        while (!q.empty()) q.pop();
        q.push((zx){n,m,0});
        vis[n][m][0] = tt;
        while (!q.empty()) {
            if (vis[0][1][0] == tt) break;
            zx t=q.front();
            q.pop();
            if (a[t.x][t.y] <= 3) {
                for (int i=3; i>=1; i-=2) {
                    int td = (t.d+i)%4;
                    int tx = t.x+dx[td],ty = t.y+dy[td];
                    if (vis[tx][ty][td] != tt) {
                        vis[tx][ty][td] = tt;
                        pre[tx][ty][td] = t;
                        dir[tx][ty][td] = to[(t.d+2)%4][td];
                        if (tx>=1 && tx<=n && ty>=1 && ty<=m) q.push((zx){tx,ty,td});
                    }
                }
            }
            else {
                int td = t.d;
                int tx = t.x+dx[td],ty = t.y+dy[td];
                if (vis[tx][ty][td] != tt) {
                    vis[tx][ty][td] = tt;
                    pre[tx][ty][td] = t;
                    dir[tx][ty][td] = to[(t.d+2)%4][td];
                    if (tx>=1 && tx<=n && ty>=1 && ty<=m) q.push((zx){tx,ty,td});
                }
            }
        }
        if (vis[0][1][0] == tt) {
            ans = 0;
            dfs();
            printf("YES\n%d\n",ans);
            for (int i=1; i<=ans; ++i) {
                if (ansq[i].d) printf("1 %d %d %d\n",ansq[i].d,ansq[i].x,ansq[i].y);
                else printf("0 %d %d\n",ansq[i].x,ansq[i].y);
            }
        } else printf("NO\n");
    }
}

F、Find 3-friendly Numbers

题目大意

定义一个自然数是3-friendly的，如果它存在一个子串（允许前导$0$）是$3$的倍数。多组数据，求L~R中3-friendly的数的个数。

考察内容

数位DP（假），暴力

解题思路

$n\ge100$时必然合法，引用出题人的证明：根据鸽笼原理，只要位数不少于$3$位，必然出现一组前缀和模$3$相同的位置，所以他们这段区间必然模$3$为$0$。不允许前导$0$也能得出一样的结论。因为只要出现$0$，单个的$0$就直接合法了。这样我们只要对$<100$的$n$暴力即可。
###

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# include <bits/stdc++.h>
# define LL long long
# define N 2010
using namespace std;
int T;
LL l,r;

int main() {
    scanf("%d",&T);
    while (T--) {
        scanf("%lld%lld",&l,&r);
        if (l >= 100LL) printf("%lld\n",r-l+1);
        else
        {
            LL tot = 0;
            for (LL i=l; i<=min(r,99LL); ++i) {
                if (i >= 10) {
                    if (i%3LL == 0 || i/10%3LL == 0 || i%10%3LL == 0);
                    else tot++;
                }
                else {
                    if (i%3LL) tot++;
                }
            }
            printf("%lld\n",r-l+1-tot);
        }
    }
}

G、Game of Swapping Numbers

题目大意

给定序列 A,B，需要交换恰好$k$次A中两个不同的数，使得 A,B 每个位置的绝对差值和最大。$N\le100000$

考察内容

贪心 结论

解题思路

当我们考虑删去绝对值符号，问题就等价于给这些数字中的$n$个数赋正号，其余的为负号。
考虑如果没有$k$的限制的话，实质上就相当于我们在这$2n$个数字中选出$n$个最大的数字当作正号，其他的数字当成负数。
我们可以想到一个事实，当$n$大于$2$时，交换$k$次等价于交换不超过$k$次，余出的交换我们可以认为是找找两个符号相同的数字进行交换，这样不影响结果。
加上$k$，的限制之后，我们考虑将最开始时的数字按照正负号分成两组，分别是A和B，如果A的最小值$x$小于B的最大值$y$，那么我们如果将$x$和$y$的符号交换显然可以得到更大的收益，结果会增加$2*(y-x)$，而这就是一次交换，我们发现这样的做法满足贪心的性质，因此我们贪心地选择前k次交换就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# include <bits/stdc++.h>
# define LL long long
# define N 500010
using namespace std;

int n,k,a[N],b[N];
LL ans;

int main() {
    scanf("%d%d",&n,&k);
    for (int i=1; i<=n; ++i) scanf("%d",&a[i]);
    for (int i=1; i<=n; ++i) {
        scanf("%d",&b[i]);
        if (a[i] > b[i]) a[i]^=b[i]^=a[i]^=b[i];
        ans += b[i]-a[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    for (int i=1; i<=k&&i<=n; ++i) ans += max(0LL,2LL*a[n-i+1]-2LL*b[i]);
    printf("%lld",ans);
}

H、Hash Function

题目大意

给定$n$个互不相同的数，找一个最小的模域，使得它们在这个模域下互不相同$n\le500000$。

考察内容

简单数论 卷积

解题思路

暴力乱杀。
考虑两个数$a$和$b$模$m$余数相同的时候，当且仅当$\left|a-b\right|$可以被$m$整除，因此问题转化成了找到最小的$m$使得$m$不是任意一个$\left|a_i-a_j\right|$的约数，由于差值的范围为$1\le\left|a_i-a_j\right|\le500000$，因此如果我们知道了任意一个差值是否存在，我们可以通过美剧倍数的形式在$O(nlogn)$的时间内找到最优解，现在问题为如何快速求得每一个差值是否存在。
我们考虑用$A_i$和$B_{500000-i}$表示i出现的次数，那么我们可以将$A$和$B$卷积，判断对应位置是否大于$0$来判断对应差值是否存在，这个过程可以用FFT或者NTT加速这一过程即可，复杂度为$O(nlogn)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# include <bits/stdc++.h>
# define N 1048576
# define M 500005
# define LL long long
# define g 3
# define mod 998244353

using namespace std;

int A[N],B[N],w[2][N],n,rev[N],x;

int adda(int a,int b) {
    a += b;
    a >= mod? a -= mod:0;
    return a;
}

int powe(int x,int y) {
    int ret = 1;
    while (y) {
        if (y&1) ret = 1LL*ret*x%mod;
        x = 1LL*x*x%mod;
        y >>= 1;
    }
    return ret;
}

void NTT(int *A,int f) {
    for (int i=0; i<N; ++i) if (i<rev[i]) swap(A[i],A[rev[i]]);
    for (int i=1; i<N; i<<=1)
        for (int j=0,t=N/(i<<1); j<N; j+=(i<<1))
            for (int k=0,l=0; k<i; ++k,l+=t) {
                int x=A[j+k],y=1LL*A[j+k+i]*w[f][l]%mod;
                A[j+k] = adda(x,y); A[j+k+i] = adda(mod,adda(x,-y));
            }
    if (f) {
        int invn = powe(N,mod-2);
        for (int i=0; i<N; ++i) A[i] = 1LL*A[i]*invn%mod;
    }
}

void work(int *A,int *B) {
    w[0][0] = 1;w[0][1] = powe(g,(mod-1)/N);
    for (int i=2; i<N; ++i) w[0][i] = 1LL*w[0][i-1]*w[0][1]%mod;
    for (int i=0; i<N; ++i) w[1][i] = powe(w[0][i],mod-2);
    for (int i=0; i<N; ++i) 
        for (int j=1,k=i; j<N; j<<=1,k>>=1)
            (rev[i]<<=1) |= (k&1);
    
    NTT(A,0); NTT(B,0);
    for (int i=0; i<N; ++i) A[i] = 1LL*A[i]*B[i]%mod;
    NTT(A,1);
}

int main() {
    scanf("%d",&n);
    for (int i=1; i<=n; ++i) {
        scanf("%d",&x);
        A[x]++; B[M-x]++;
    }
    work(A,B);
    for (int i=1; i<M; ++i) {
        int flag = 1;
        for (int j=i; j<M && flag; j+=i)
            if (A[j+M]) flag = 0;
        if (flag) printf("%d",i),exit(0);
    }
}

I、Increasing Subsequence

题目大意

给出排列$P$，两个人轮流取数，每次取的数需要在之前该人取数的右边，且比当前取出来所有的数都要大。所有当前可选的数都将等概率随机的被当前决策人选中。问两个人期望取数的轮数。$N\le5000$

考察内容

动态规划

解题思路

不得不吐槽一句，官方题解太晦涩了。
设$f_{i,j}$表示当前最后一个选择的人选数字$j$,上一个人选择的数字为$i$之后的剩余轮数的期望,$P_i$表示$i$这个数字出现的位置下标,转移方程如下：$$f_{i,j} =1+\frac{\sum_{k>j,P_k>P_i}f_{j,k}}{cnt}$$
$cnt$为满足条件的$k$的个数，$cnt$和$\sum_{k>j,P_k>P_i}f_{j,k}$可以预处理出来。
最后答案即为$$ans=\frac{\sum_{i=1}^{n}f_{0,i}}{n}$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# include <bits/stdc++.h>
# define mod 998244353
# define N 5005
# define LL long long
using namespace std;

void add(int &x,int y) {x += y; x >= mod? x -= mod:0;}
int adda(int x,int y) {x += y; x >= mod? x -= mod:0; return x;}
int powe(int x,int y) {
    int ret = 1;
    while (y) {
        if (y&1) ret = 1ll*ret*x%mod;
        x = 1ll*x*x%mod;
        y >>= 1;
    }
    return ret;
}

int a[N],p[N],f[N][N],c[N],sum[N],n,ans,inv[N];

int main() {
    scanf("%d",&n);
    for (int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
        p[a[i]] = i;
    }

    for (int i=1; i<=n; ++i) inv[i] = powe(i,mod-2);

    for (int j=n; j; --j) {
        memset(c,0,sizeof(c));
        memset(sum,0,sizeof(sum));
        for (int i=j+1; i<=n; ++i) c[p[i]] = 1,sum[p[i]] = f[j][i];
        for (int i=n; i>=0; --i) c[i] += c[i+1], add(sum[i],sum[i+1]);
        for (int i=0; i<=j-1; ++i) if (c[p[i]+1]) add(f[i][j],adda(1ll*inv[c[p[i]+1]]*sum[p[i]+1]%mod,1));
    }

    for (int i=1; i<=n; ++i) add(ans,f[0][i]);
    printf("%d",adda(1ll*inv[n]*ans%mod,1));
    return 0;
}

J、Journey of Railway Stations

题目大意

一段路上有$N$个点，每个点有一个合法时间段$[u_i, v_i]$，相邻两个点有一个长度。每次问，在$u_i$的时间从$i$出发后，能否依次经过$i+1$到$j$的所有点，使得到达时间满足每个点的合法区间（如果提前到可以等待，迟到了失败了）。同时还可能修改一段路的长度，或者修改一个点的合法时间段。$N,Q\le1000000$

考察内容

数据结构

解题思路

数据结构好题，一如既往，官方题解写得十分晦涩。
我们用线段树维护一段区间$[l,r]$是否可以从$l$走到$r$,线段树的每个区间$[l,r]$维护$res$:当前区间是否可以从$l$走到$r$，$u$:从当前区间走到下一个点的最早时间点,$v$：到达当前区间的最晚时间点。 这样的区间是有可合并性的。
考虑合并$res$时，首先左右两个子区间$res$一定需要为$1$。其次如果$u_l>v_r$那么$res$为$1$，否则为$0$。
合并$u$时,我们考虑如果在左区间内有任意一个时刻有等待行为，那么最终他到达右区间的时间点一定是唯一的，这个很显然，因此$u=max(u_l+sum_r,u_r)$前者表示在右边区间行走时没有任何的等待行为，一路畅通无阻的情况，后者即为有等待情况，二者需要去较大值。
类似的合并$v$时也考虑这两种情况，$v=min(v_l,v_r-sum_l)$。
修改就是常规的线段树修改即可，查询就查询对应区间的$res$是否为$1$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# include <bits/stdc++.h>
# define LL long long
# define LS o<<1
# define RS LS|1
# define N 1000010

using namespace std;

int n,m,T,opt,l,r,p,u[N],v[N],a[N];

struct zx {
    LL sum,u,v;
    bool res;
    zx() {
        sum = u = 0;
        v = 0x7fffffffffffffff;
        res = 1;
    }
}t[N*5];

zx operator + (zx a,zx b) {
    zx ret;
    ret.res = a.res&b.res;
    if (a.u > b.v) ret.res = 0;
    ret.sum = a.sum + b.sum;
    ret.u = max(a.u+b.sum,b.u);
    ret.v = min(a.v,b.v-a.sum);
    return ret;
}

void build(int o,int l,int r) {
    if (l == r) {
        t[o].sum = a[l];
        t[o].u = u[l]+a[l];
        t[o].v = v[l];
        t[o].res = 1;
        return;
    }
    int mid = l+r>>1;
    build(LS,l,mid);
    build(RS,mid+1,r);
    t[o] = t[LS]+t[RS];
}

void modify(int o,int l,int r,int p) {
    if (l == r) {
        t[o].sum = a[l];
        t[o].u = u[l]+a[l];
        t[o].v = v[l];
        t[o].res = 1;
        return;
    }

    int mid = l+r>>1;
    if (p <= mid) modify(LS,l,mid,p);
    else modify(RS,mid+1,r,p);
    t[o] = t[LS]+t[RS];
}

zx qury(int o,int l,int r,int x,int y) {
    if (x <= l&&r <= y) return t[o];
    int mid = l+r>>1;
    zx ret;
    if (x <= mid) ret = ret+qury(LS,l,mid,x,y);
    if (y > mid) ret = ret+qury(RS,mid+1,r,x,y);
    return ret;
}

int main() {
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1; i<=n; ++i) scanf("%d",&u[i]);
        for (int i=1; i<=n; ++i) scanf("%d",&v[i]);
        for (int i=1; i<n; ++i) scanf("%d",&a[i]);
        build(1,1,n);
        scanf("%d",&m);
        while (m--) {
            scanf("%d",&opt);
            if (opt == 0) {
                scanf("%d%d",&l,&r);
                zx now = qury(1,1,n,l,r);
                if (now.res) printf("Yes\n");
                else printf("No\n");
            } else if (opt == 1) {
                scanf("%d%d",&l,&r);
                a[l] = r;
                modify(1,1,n,l);
            } else {
                scanf("%d%d%d",&p,&l,&r);
                u[p] = l;v[p] = r;
                modify(1,1,n,p);
            }
        }
    }
}

K、Knowledge Test about Match

贪心乱搞题，不想补了。