牛客 Round 1 解题记录

比赛链接: https://ac.nowcoder.com/acm/contest/11166

还在补题，但是好多，补不完了qwq。

已完成：A (B) D F I J

A - Alice and Bob

题意简介

两堆石子，分别是 $n$ 和 $m$ 个，Alice 先取，Bob 后取。每次，可以从其中一堆中取走 $k$ ( $k>0$ ) 个，然后从另一堆中取走 $s\times k$ ( $s\geq 0$ ) 。轮到某个人时石子都没了，那个人就会输掉。现在给你 10000 组询问， $1\leq n,m\leq 5\times 10^3$ ，要你输出每组询问谁会赢。

思路分析

想不出正解，但是先暴力算一遍再说。记 $f(i,j)$ 表示第一堆石子剩下 $i$ ，第二堆石子剩下 $j$ 的情况下先手方的状态， $1$ 表示必胜，有： $f(i,j) = \max{(1-f(i-k,j-ks))}$

因为发现必败态只有 2719 种，于是存下来，每次询问直接二分查找。

上面是比赛时用的打表思路。

经过后续的听讲，我们知道这道题可以利用每个 i 只唯一对应一个必败态来搞事，而且据出题人说可以跑得飞快，于是我就自己敲了一个。

思路就是用 $Q_i$ 存下对于每个 $i$ ，与之唯一对应的必败态 $j$ （当然也可能不存在，记为 $-1$ ）。

然后再根据这些必败态，枚举倍数来排除必胜态，找到下一个必败态。

理论复杂度是 $O(n^2 \log n)$ 的，但因为减了不少枝，所以跑得飞快，500 来毫秒左右。

但是我并没有理解出题人说的 $n = 10000$ 也可以跑出来需要怎么做，因为我无法省去这个二维数组，求大佬教教我qwq。

解题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5005;
int n, m, Q[N]; bool vis[N][N];
int main() {
    memset(Q, -1, sizeof(Q));
    Q[0] = 0;
    for(int i=0; i<=5000; i++) {
        if(Q[i] != -1) {
            for(int j=Q[i]+1; j<=5000; j++) {
                for(int k=i; k<=5000; k+=j-Q[i]) vis[k][j] = 1;
            }
            continue;
        }
        for(int j=i-1; j>=0; j--) {
            if(Q[j] == -1) continue;
            for(int k=Q[j]; k<=5000; k+=i-j) vis[i][k] = 1;
        }
        for(int j=i+1; j<=5000; j++) {
            if(!vis[i][j]) {
                Q[i] = j, Q[j] = i;
                break;
            }
        }
        if(Q[i] != -1) {
            for(int j=Q[i]+1; j<=5000; j++) {
                for(int k=i+j-Q[i]; k<=5000; k+=j-Q[i]) vis[k][j] = 1;
            }
        }
    }
    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        if(Q[n] != -1 && Q[n] == m) puts("Bob");
        else puts("Alice");
    }
    return 0;
}

B - Ball Dropping

题意简介

如上图，给你 $a,b,r,h$ ，问你球是否会从漏斗里掉出去。如果不会，求图上红边的长度。

数据保证 $2r \neq b$ , $2r<a$ , $2r<h$ 。

思路分析

队友切的。几何题一生之敌qwq。

TODO

通过代码见：提交记录

C - Cut the Tree

题意简介

TODO

思路分析

TODO

D - Determine the Photo Position

题意简介

给你一个只含 0 和 1 的 $n\times n$ 的矩阵，表示相片上有的地方站了学生有的地方没站。现在告诉你有 $m$ 个老师站成一排，要求你把这一排老师完整地、不能拆分或旋转地，插入到相片地空白处。问你有多少种插入方式。

思路分析

签到。求出所有的连续的 0 段的 0 的数目 c，每个连续 0 段对答案的贡献是 $\max{(c-m+1, 0)}$ 。

解题代码

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=2005;
int n,m; char s[N][N],s2[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf(" %s",s[i]+1);
    scanf(" %s",s2+1);
    int ans=0;
    for(int i=1;i<=n;i++){
        int c0=0;
        for(int j=1;j<=n+1;j++){
            if(s[i][j]!=s[i][j-1]){
                if(s[i][j]!='0'){
                    ans+=max(0,c0-m+1);
                    c0=0;
                }else{
                    c0=1;
                }
            }else if(s[i][j]=='0') c0++;
        }
    }
    printf("%d",ans);
    return 0;
}

E - Escape along Water Pipe

题意简介

TODO

思路分析

TODO

F - Find 3-friendly Integers

题意简介

一个整数被称为 3友好整数 ，当且仅当可以从它的十进制表示中找到一个连续子串，这个连续子串的表示的数字是 3 的倍数。

给你 10000 组询问，问你 $L$ 到 $R$ 里有多少个整数满足上述要求。( $1\leq L\leq R \leq 10^{18}$ )

思路分析

我们知道，一个数是三的倍数，那么它的各位数之和也是三的倍数。

想要方便直观地各位数之和，那么我们可以给每一位数都模个 3 。

我们知道，想要一个数想要不满足题意，它的各个数字模 3 后首先不能是 0 。

所以，我们试着用数字 1 和 2 来构造不满足题意的数，不难发现，根本无法构造出 4 位数以上的数字。

所以，对于位数少的，我们直接预处理出那些数字满足题意，对于位数大的部分，它一定是满足题意的，直接 $R-L+1$ 就完事了。

解题代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e6;
int vis[N];
inline void calc(int x){
    static int dig[1000];
    int cn=0;
    int ux=x;
    while(x){
        dig[++cn]=x%10;
        x/=10;
    }
    for(int i=1;i<=cn;i++) dig[i]+=dig[i-1];
    for(int i=1;i<=cn;i++) for(int j=i;j<=cn;j++){
        if((dig[j]-dig[i-1])%3==0){
            vis[ux] = 1; return;
        }
    }
    return;
}
int main(){
    int t; scanf("%d",&t);
    vis[0]=1;
    for(int i=1;i<=N;i++) {
        calc(i);
        vis[i]+=vis[i-1];
    }
    while(t--){
        ll L,R; scanf("%lld%lld",&L,&R);
        ll ans=0;
        if(R<=N) ans=vis[R]-vis[L-1];
        else if(L<=N) ans=R-N+vis[N]-vis[L-1];
        else ans=R-L+1;
        printf("%lld\n",ans);
    }
    return 0;
}

G - Game of Swapping Numbers

题意简介

TODO

思路分析

TODO

H - Hash Function

题意简介

给你一个大小为 $n$ 的没有重复数字的集合 $\{a_i\}$ ，问你使集合内所有数对 $x$ 取模的答案两两不同的最小 $x$ 。 $0\leq a_i\leq 500000$ ， $1\leq n \leq 500000$ 。

思路分析

比赛时开桶暴力瞎搞的。数据加强了之后烂了。不会多项式，下一个。

TODO

I - Increasing Subsequence

题意简介

Alice 和 Bob 轮流对一个排列进行取数。每次取都要比上一个被取的数字更大。同时，对于同一个人，他取数时除了要满足比上一个数大外，还要求新取的数要在自己上一次取的数的右边。如果这一轮里一个人可以取的数不止一个，他会随机等概率拿一个出来。求游戏进行的轮次的期望值。

思路分析

比赛时有一个 O(n^3) 的思路，但是没时间了，细节也没搞清楚，于是没搞出来，赛后重新复盘了一下。

我们记 $p(i, j)$ 为 Alice 选了 $i$ 次，Bob 选了 $j$ 次的概率。

显然的， $A_i > A_j$ 时，当前这个状态最后一次取的人是 Alice（因为每次取数要比上一次取数更大），所以这个状态必然是由 $p(k, j)$ 转移过来的。且根据题意，我们可以知道，这个状态必须满足 $A_k < A_j$ ，和 $k < i$ 。

而从 $(k ,j)$ 转移到 $(i, j)$ ，意味着 Alice 在 $k$ 往后的位置中所有能选的位置里，恰好挑中了 $i$ 。

于是，我们有转移： $p(i, j) = \sum p(k, j) \times \frac{1}{c}$ ，其中 $c$ 表示 $k$ 往后的位置中能选的位置的数量，且 $k$ 必须满足上面分析的条件（搞进公式里太复杂了，自已意会一下好了qwq）。

同理，对于 $A_j > A_i$ ，我们有转移： $p(i, j) = \sum p(i, k) \times \frac{1}{c}$

有了这个东西之后，轮次期望的转移就变得非常明显了。

我们记 $f(i, j)$ 为 Alice 选了 $i$ 次，Bob 选了 $j$ 次的轮次期望。

于是，对于 $A_i > A_j$ 有： $f(i, j) = \sum f(k, j) \times \frac{1}{c} + 1 \times p(k, j) \times \frac{1}{c}$ 。

小于的情况类似。

接下来考虑如何实现。

首先，题目 $n \leq 5000$ ，因此我们只能是 $O(n^2)$ ，甚至不能带 $\log n$ 。发现需要求逆元的 $c$ 小于 $n$ ，所以我们先预处理出 $1$ 到 $n$ 的所有逆元。

对于 $c$ 的快速求解，我们可以开个二维数组，用 $cnt(i, j)$ ，表示从下标 $i$ 开始的后缀里，值小于等于 $j$ 的数量（相当于对每个后缀开了一个桶）。

接下来，仔细观察转移的式子，我们可以发现，大于的状态必然从小于的状态转移过来，而且转移过程与 $i$ （ $j$ ）无关，所以我们可以维护类似前缀和的东西。

具体实现见代码。

解题代码

代码中的注释部分为 $O(n^3)$ 的写法。

#include <cstdio>
typedef long long ll;
const ll mod = 998244353, N = 5005;
int n; ll A[N], P[N], f[N][N], cnt[N][N], p[N][N], sp1[N], sf1[N], sp2[N][N], sf2[N][N], inv[N];
inline char getc() {
    static char buf[1<<14], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<14, stdin), p1 == p2) ? EOF : *p1++;
}
inline ll scan() {
    ll x = 0; char ch = 0;
    while(ch < 48) ch = getc();
    while(ch >= 48) x = x * 10 + ch - 48, ch = getc();
    return x;
}
inline ll _pow(ll x, ll p) {
    ll ans = 1;
    while(p) {
        if(p&1) ans = ans * x %mod;
        x = x * x % mod; p >>= 1;
    }
    return ans;
}
inline ll _inv(ll x) {
    return _pow(x, mod - 2);
}
inline ll add(ll a, ll b) {
    return a + b >= mod ? a + b - mod : a + b;
}
int main() {
    n = scan();
    for(int i=1; i<=n; i++) {
        A[i] = scan();
        P[A[i]] = i;
        inv[i] = _inv(i);
    }
    for(int i=1; i<=n; i++) {
        for(int j=i; j<=n; j++) {
            cnt[i][A[j]]++;
        }
        for(int j=1; j<=n; j++) {
            cnt[i][j] += cnt[i][j-1];
        }
    }
    p[0][0] = 1;
    for(int i=1; i<=n; i++) {
        p[i][0] = f[i][0] = inv[n];
        int _c = cnt[1][n] - cnt[1][A[i]]; 
        sp2[i][0] = p[i][0] * inv[_c] % mod;
        sf2[i][0] = (f[i][0] + 1 * p[i][0]) * inv[_c] % mod;
        for(int j=1; j<=n; j++) {
            // 计算 f[i][j] 和 p[i][j]
            if(A[i] > A[j]) {
                /*for(int k=1; k<i; k++) {
                    if(A[k] < A[j]) {
                        int c = cnt[k+1][n] - cnt[k+1][A[j]];
                        p[i][j] += p[k][j] * _inv(c) % mod;
                        p[i][j] %= mod;
                        f[i][j] += (f[k][j] + 1 * p[k][j]) * _inv(c) % mod;
                        f[i][j] %= mod;
                    }
                }*/
                p[i][j] = add(p[i][j], sp1[j]);
                f[i][j] = add(f[i][j], sf1[j]);
                // 维护 sp2 和 sf2
                int c = cnt[j+1][n] - cnt[j+1][A[i]];
                sp2[i][j] = (sp2[i][j] + p[i][j] * inv[c]) % mod;
                sf2[i][j] = (sf2[i][j] + (f[i][j] + p[i][j]) * inv[c]) % mod;
            }
            if(A[i] < A[j]) {
                /*for(int k=0; k<j; k++) {
                    if(A[k] < A[i]) {
                        int c = cnt[k+1][n] - cnt[k+1][A[i]];
                        p[i][j] += p[i][k] * _inv(c) % mod;
                        p[i][j] %= mod;
                        f[i][j] += (f[i][k] + 1 * p[i][k]) * _inv(c) % mod;
                        f[i][j] %= mod;
                    }
                }*/
                p[i][j] = add(p[i][j], sp2[i][j-1]);
                f[i][j] = add(f[i][j], sf2[i][j-1]);
            }
            sp2[i][j] = add(sp2[i][j], sp2[i][j-1]);
            sf2[i][j] = add(sf2[i][j], sf2[i][j-1]);
        }
        // 维护前缀和
        for(int j=0; j<=n; j++) {
            if(A[i] < A[j]) {
                int c = cnt[i+1][n] - cnt[i+1][A[j]];
                sp1[j] = (sp1[j] + p[i][j] * inv[c]) % mod;
                sf1[j] = (sf1[j] + (f[i][j] + p[i][j]) * inv[c]) % mod;
            }
        }
    }
    ll res = 0;
    for(int i=1; i<=n; i++) for(int j=0; j<=n; j++) {
        if(A[i] > A[j]) {
            int c = cnt[j+1][n] - cnt[j+1][A[i]];
            if(c == 0) res = add(res, f[i][j]);
        }
        if(A[j] > A[i]) {
            int c = cnt[i+1][n] - cnt[i+1][A[j]];
            if(c == 0) res = add(res, f[i][j]);
        }
    }
    printf("%lld", res);
    return 0;
}

J - Journey among Railway Stations

题意简介

$n$ 个车站，每个车站有一个开启时间和一个关闭时间。如果提早到了，需要等到开启时间才能走，如果晚到了，就再也过不去了。

相邻车站有一条从左到右的单向道路，表示需要走多少时间才能从一个车站到另一个车站。

现在有两种操作，一种询问：

修改车站的起始时间。
修改车站间路的长度。
询问能否从第 $l$ 个车站移动到第 $r$ 个车站并通过。

思路分析

看一眼数据范围： $n \leq 10^6$ 。还有修改和查询。是数据结构哒！

~~然后我就溜了。~~

补题的时候听了下讲解。这道题是个很巧妙的线段树题。

我们可以观察到，不管是多长的区间，我们画出进入区间的时间与离开区间的最早时间的函数，你总能发现这样的三部分：

早来了，在移动过程中需要经过等待，最终出区间的时间一样。
中间不需要任何等待，出区间的时间随入区间的时间单调递增，且斜率为 1。
来晚了，过不去了。

不难发现，我们只要维护三个值，就可以推出完整的函数图像：

wait: 在这个时间之前来，一定需要等待
late: 在这个时间之后来，一定过不去
time: 从 wait 这个时间前来，会在什么时候离开（也就是可能的最早离开时间）。

具体的维护和初始化，画画图，仔细想想、分类讨论一下可以搞出来（语文能力差，表达不出来）。可以参考代码的 merge 函数，可能写得有点丑qwq。

因为都是单点修改，所以每次改完后递归到底，往上一路 maintain 就完事了。

解题代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
#define ls (u<<1)
#define rs ((u<<1)+1)
struct Node {
    ll wait, late, time;
    Node(): wait(0), late(0), time(0) {}
}Tr[N<<2];
int s[N], e[N], cost[N], n, q;
inline void debug(Node x) {
    printf("Wait: %lld, late: %lld, time: %lld\n", x.wait, x.late, x.time);
}
inline void output(int u, int l, int r) {
    if(l > r) return;
    printf("For [%d, %d]: ", l, r); 
    debug(Tr[u]);
    if(l == r) return;
    int mid = (l + r) >> 1;
    output(ls, l, mid); 
    output(rs, mid + 1, r);
}
inline Node merge(Node A, Node B, ll w) {
    Node C = Node();
    if(A.time == -1 || B.time == -1) return C.time = -1, C;
    ll ti = A.time + w;
    if(ti > B.late) return C.time = -1, C;
    if(ti >= B.wait) C.wait = A.wait;
    else {
        C.wait = A.wait + (B.wait - ti);
        ti = B.wait;
    }
    C.time = B.time + (ti - B.wait);
    C.late = min(A.late, C.wait + (B.late - ti));
    return C;
}
inline void maintain(int u, int l, int r) {
    int mid = (l + r) >> 1;
    Tr[u] = merge(Tr[ls], Tr[rs], cost[mid]);
}
void build(int u, int l, int r) {
    if(l == r) {
        Tr[u].wait = s[l]; 
        Tr[u].late = e[l];
        Tr[u].time = s[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    return maintain(u, l, r);
}
Node query(int u, int l, int r, int ql, int qr) {
    if(l > qr || r < ql) return Node();
    if(ql <= l && r <= qr) return Tr[u];
    int mid = (l + r) >> 1;
    if(l > qr || mid < ql) return query(rs, mid + 1, r, ql, qr);
    if(mid + 1 > qr || r < ql) return query(ls, l, mid, ql, qr);
    return merge(query(ls, l, mid, ql, qr), query(rs, mid + 1, r, ql, qr), cost[mid]);
}
void update(int u, int l, int r, int x) {
    if(l > x || r < x) return;
    if(l == r) {
        Tr[u].wait = s[l];
        Tr[u].late = e[l];
        Tr[u].time = s[l];
        return;
    }
    int mid = (l + r) >> 1;
    update(ls, l, mid, x); update(rs, mid + 1, r, x);
    return maintain(u, l, r);
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", s+i);
        for(int i=1; i<=n; i++) scanf("%d", e+i);
        for(int i=1; i<n; i++) scanf("%d", cost+i); 
        build(1, 1, n);
        // puts("=======================");
        // output(1, 1, n);
        // puts("=======================");
        scanf("%d", &q);
        while(q--) {
            int opt; scanf("%d", &opt);
            if(opt == 0) {
                int l, r; scanf("%d%d", &l, &r);
                Node ans = query(1, 1, n, l, r);
                puts(ans.time == -1 ? "No" : "Yes");
            }
            if(opt == 1) {
                int i, w; scanf("%d%d", &i, &w);
                cost[i] = w;
                update(1, 1, n, i);
            }
            if(opt == 2) {
                int i, _s, _e;
                scanf("%d%d%d", &i, &_s, &_e);
                s[i] = _s, e[i] = _e;
                update(1, 1, n, i);
            }
            /* if(opt) {
                 puts("=======================");
                output(1, 1, n);
                puts("=======================");
            } */
        }
    }
    return 0;
}

牛客 Round 1 解题记录

A - Alice and Bob

题意简介

思路分析

解题代码

B - Ball Dropping

题意简介

思路分析

C - Cut the Tree

题意简介

思路分析

D - Determine the Photo Position

题意简介

思路分析

解题代码

E - Escape along Water Pipe

题意简介

思路分析

F - Find 3-friendly Integers

题意简介

思路分析

解题代码

G - Game of Swapping Numbers

题意简介

思路分析

H - Hash Function

题意简介

思路分析

I - Increasing Subsequence

题意简介

思路分析

解题代码

J - Journey among Railway Stations

题意简介

思路分析

解题代码

K - Knowledge Test about Match

题意简介

思路分析