20zr联赛集训day15

Author： RainAir
发布时间：November 3, 2020
877views
No comments
540 words
Categories：题解

A

打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。

具体证明：考虑如果 $n$ 是奇数的话，先手第一步取中间的那一块，序列变成了互相独立的两部分，之后先手只需要在没有被后手操作的块里模拟后手动作即可。

如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。

$k=1$ 等价于每次只能取一个，所以 $n$ 是偶数的话后手能赢。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

int main(){
    int n,k;scanf("%d%d",&n,&k);
    puts(k==1&&(!(n&1)) ? "yrrebxaw":"qjd");
    return 0;
}

B

求出每个边的存活时间，线段树分治即可，写个支持撤销的并查集。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

int f[MAXN],sz[MAXN],inv[MAXN],now = 1;

inline int find(int x){
    return x == f[x] ? x : find(f[x]);
}

struct Node{
    int x,y,z;
    Node(int x=0,int y=0,int z=0) : x(x),y(y),z(z) {}
};

std::vector<Node> opt;

inline void merge(int x,int y){
    x = find(x);y = find(y);
    if(x == y) return;
    if(sz[x] > sz[y]) std::swap(x,y);
    now = 1ll*now*inv[sz[x]]%ha;
    now = 1ll*now*inv[sz[y]]%ha;
    opt.pb(Node(x,y,sz[x]));
    sz[y] += sz[x];f[x] = y;
    now = 1ll*now*sz[y]%ha;
}

inline void undo(){
    Node v = opt.back();opt.pop_back();
    now = 1ll*now*inv[sz[v.y]]%ha;
    f[v.x] = v.x;sz[v.x] = v.z;sz[v.y] -= v.z;
    now = 1ll*now*sz[v.x]%ha;
    now = 1ll*now*sz[v.y]%ha;
}

std::vector<P> G[MAXN<<2];
#define lc ((x)<<1)
#define rc ((x)<<1|1)

inline void modify(int x,int l,int r,int L,int R,P d){
    if(l == L && r == R){
        G[x].pb(d);
        return;
    }
    int mid = (l + r) >> 1;
    if(R <= mid) modify(lc,l,mid,L,R,d);
    else if(L > mid) modify(rc,mid+1,r,L,R,d);
    else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
}

int ans[MAXN];

inline void dfs(int x,int l,int r){
    int t = opt.size();
    for(auto v:G[x]) merge(v.fi,v.se);
    if(l == r){
        ans[l] = now;
        while(t != opt.size()) undo();
        return;
    }
    int mid = (l + r) >> 1;
    dfs(lc,l,mid);dfs(rc,mid+1,r);
    while(t != opt.size()) undo();
}

int n,m;
int s[MAXN],e[MAXN];

int main(){
  //  freopen("B.in","r",stdin);
    //freopen("B.out","w",stdout);
    inv[1] = 1;
    FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha;
    scanf("%d%d",&n,&m);
    FOR(i,1,n) f[i] = i,sz[i] = 1;
    std::map<P,int> S;
    FOR(i,1,m){
        int o,u,v;scanf("%d%d%d",&o,&u,&v);
        if(u > v) std::swap(u,v);
        if(o == 1){
            S[MP(u,v)] = i;
        }
        else{
            modify(1,1,m,S[MP(u,v)],i-1,MP(u,v));
            S.erase(MP(u,v));
        }
    }
    for(auto x:S) modify(1,1,m,x.se,m,x.fi);
    dfs(1,1,m);
    FOR(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

C

主要是普及一下排列如何 $O(n \log n)$ 求三维偏序：

给定三个排列 $a_i,b_i,c_i$，我们要求

$$ \sum_{i,j} [a_i < a_j][b_i < b_j][c_i < c_j] $$

由于是排列，不难发现有

$$ \sum_{i,j} [a_i < a_j][b_i < b_j][c_i < c_j] = \sum_{i,j}[a_i > a_j][b_i > b_j][c_i > c_j] $$

并且排列中不会有相等关系，所以 $[a \leq b] = [a < b],[a \geq b] = [a > b]$，考虑将上述求的东西容斥，需要算的就只有若干个二维偏序和一维偏序问题了。

对于这个题我们考虑硬算期望：首先对于两个都不是 $-1$ 的位置，就是一个三维偏序。

然后对于两个都是 $-1$ 的位置，如果满足 $i<j,p_i < p_j$，就有 $\frac{1}{2}$ 的概率是 $q_i<q_j$，所以这个就是个二维数点，答案乘上 $\frac{1}{2}$。

对于一个是 $-1$ 一个不是的位置，可以预处理没有用过的数中有多少个比某个数 $x$ 大/小的，然后写下式子也是二维数点问题。

题解的做法是直接对上述容斥式子套期望线性性，就比较简单。。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(register int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

int n,p[MAXN],q[MAXN];
const int ha = 998244353;
int inv[MAXN];

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXN],ts[MAXN],now;

    inline void reset(){++now;}

    inline void add(int pos,int x){
        while(pos < MAXN){
            if(ts[pos] != now) ts[pos] = now,tree[pos] = 0;
            ::add(tree[pos],x);
            pos += lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos){
            if(ts[pos] != now) ts[pos] = now,tree[pos] = 0;
            ::add(res,tree[pos]);
            pos -= lowbit(pos);
        }
        return res;
    }
}bit;

int ans = 0;
struct Node{
    int x,y,z;
    Node(int x=0,int y=0,int z=0) : x(x),y(y),z(z) {}

    inline bool operator < (const Node &t) const {
        return x < t.x;
    }
}a[MAXN];

inline int work2(int n){
    bit.reset();
//    std::sort(a+1,a+n+1);
    int res = 0;
    FOR(i,1,n){
        add(res,bit.query(a[i].y));
        bit.add(a[i].y,1);
    }
    return res;
}

inline void work(int n){// 单 log 三维偏序
    ans = 1ll*n*(n-1)%ha;
    add(ans,ha-3ll*n%ha*(n-1)%ha*inv[2]%ha);
    std::sort(a+1,a+n+1);
    add(ans,work2(n));// (x,y,z)
    FOR(i,1,n) std::swap(a[i].x,a[i].z);
    std::sort(a+1,a+n+1);
    add(ans,work2(n));// (z,y,x)
    FOR(i,1,n) std::swap(a[i].y,a[i].z);
    add(ans,work2(n));// (z,x,y)
    ans = 1ll*ans*inv[2]%ha;
//    int t = 0;
//    FOR(i,1,n) FOR(j,1,n) if(i != j && a[i].x < a[j].x && a[i].y < a[j].y && a[i].z < a[j].z) ++t;
//    DEBUG(t);
}

int nxt[MAXN],pre[MAXN];

int main(){
 //   freopen("C.in","r",stdin);
   // freopen("C.out","w",stdout);
    read(n);FOR(i,1,n) read(p[i]);FOR(i,1,n) read(q[i]);
    inv[1] = 1;FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha;
    int m = 0;
    // part 1
    FOR(i,1,n) if(q[i] != -1) a[++m] = Node(i,p[i],q[i]);
    work(m);
    // part 2
    m = n-m;
    bit.reset();
    FOR(i,1,n){
        if(q[i] != -1) continue;
        add(ans,1ll*bit.query(p[i])*inv[2]%ha);
        bit.add(p[i],1);
    }
    // part 3
    FOR(i,1,n) if(q[i] != -1) nxt[q[i]] = 1;
    FOR(i,1,n) nxt[i] ^= 1,pre[i] = nxt[i];
    ROF(i,n,1) nxt[i] += nxt[i+1];
    FOR(i,1,n) pre[i] += pre[i-1];
    bit.reset();
    FOR(i,1,n){
        if(q[i] == -1){
            add(ans,bit.query(p[i]));
        }
        else{
            bit.add(p[i],1ll*nxt[q[i]]*inv[m]%ha);
        }
    }
    bit.reset();
    FOR(i,1,n){
        if(q[i] == -1){
            bit.add(p[i],1);
        }
        else{
            add(ans,1ll*bit.query(p[i])*pre[q[i]]%ha*inv[m]%ha);
        }
    }
    printf("%d\n",ans);
    return 0;
}

D

先考虑策略是什么，考试的时候我没有注意到这个事实：后手可以等先手钻进某个角落自闭的时候慢慢把所有道路清掉，就以为策略之间很麻烦。。

那么我们考虑以 $t$ 为根，那么这个策略大概是先手往上爬，爬到某个位置后钻进子树内，然后就自闭了，这时后手把路上的边都删掉，然后让先手精确地到达 $t$。

我们设 $f_v$ 表示从 $v$ 点钻进去的代价，那么如果先手考虑从 $v$ 点钻进去，后手肯定会先 ban 掉最大的 $f_x$，其中 $x \in son_v$。

我们考虑二分答案，每次暴力从 $s$ 到 $t$ 往上条，到每个点判断一下是否从某个儿子钻进去之后代价会 $>mid$，如果会的话就一定要删掉，这里代价计算的时候有点细节。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
std::vector<int> G[MAXN];
int n,s,t;
int f[MAXN],fa[MAXN],sm[MAXN];

inline void dfs(int v,int fa=0){
    int mx = 0,cmx = 0,deg = (int)G[v].size()-(fa!=0);::fa[v] = fa;
    for(auto x:G[v]){
        if(x == fa) continue;
        sm[x] = sm[v]+(v==t?0:deg-1);
        dfs(x,v);
        if(f[x] > mx){
            cmx = mx;mx = f[x];
        }
        else if(f[x] > cmx){
            cmx = f[x];
        }
    }
    if(!deg) f[v] = 0;
    else if(deg == 1) f[v] = 1;
    else f[v] = cmx+deg;
}

inline bool chk(int lim){// 花费不超过 lim 到根
    int v = s,las = -1,now = 0,r = 1;
    while(v != t){ // 枚举在哪个点钻进去
        int cnt = 0;
        for(auto x:G[v]){
            if(x == fa[v] || x == las) continue;
            cnt += (now+f[x]+1+sm[x]-(v!=s) > lim);
        }
        now += cnt;
        if(now > r || now > lim) return 0;
        v = fa[las=v];++r;
    }
    return 1;
}

int main(){
    scanf("%d%d%d",&n,&t,&s);
    if(s == t) return puts("0"),0;
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    dfs(t);
    int l = 0,r = 2*n,ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid)) ans = mid,r = mid-1;
        else l = mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

Last modification：July 11th, 2022 at 06:09 pm

如果觉得我的文章对你有用，请随意赞赏

20zr联赛集训day15

RainAir • 2020 年 11 月 03 日

A

打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。

如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。

$k=1$ 等价于每次只能取一个，所以 $n$ 是偶数的话后手能赢。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

int main(){
    int n,k;scanf("%d%d",&n,&k);
    puts(k==1&&(!(n&1)) ? "yrrebxaw":"qjd");
    return 0;
}

B

求出每个边的存活时间，线段树分治即可，写个支持撤销的并查集。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int ha = 1e9 + 7;

int f[MAXN],sz[MAXN],inv[MAXN],now = 1;

inline int find(int x){
    return x == f[x] ? x : find(f[x]);
}

struct Node{
    int x,y,z;
    Node(int x=0,int y=0,int z=0) : x(x),y(y),z(z) {}
};

std::vector<Node> opt;

inline void merge(int x,int y){
    x = find(x);y = find(y);
    if(x == y) return;
    if(sz[x] > sz[y]) std::swap(x,y);
    now = 1ll*now*inv[sz[x]]%ha;
    now = 1ll*now*inv[sz[y]]%ha;
    opt.pb(Node(x,y,sz[x]));
    sz[y] += sz[x];f[x] = y;
    now = 1ll*now*sz[y]%ha;
}

inline void undo(){
    Node v = opt.back();opt.pop_back();
    now = 1ll*now*inv[sz[v.y]]%ha;
    f[v.x] = v.x;sz[v.x] = v.z;sz[v.y] -= v.z;
    now = 1ll*now*sz[v.x]%ha;
    now = 1ll*now*sz[v.y]%ha;
}

std::vector<P> G[MAXN<<2];
#define lc ((x)<<1)
#define rc ((x)<<1|1)

inline void modify(int x,int l,int r,int L,int R,P d){
    if(l == L && r == R){
        G[x].pb(d);
        return;
    }
    int mid = (l + r) >> 1;
    if(R <= mid) modify(lc,l,mid,L,R,d);
    else if(L > mid) modify(rc,mid+1,r,L,R,d);
    else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d);
}

int ans[MAXN];

inline void dfs(int x,int l,int r){
    int t = opt.size();
    for(auto v:G[x]) merge(v.fi,v.se);
    if(l == r){
        ans[l] = now;
        while(t != opt.size()) undo();
        return;
    }
    int mid = (l + r) >> 1;
    dfs(lc,l,mid);dfs(rc,mid+1,r);
    while(t != opt.size()) undo();
}

int n,m;
int s[MAXN],e[MAXN];

int main(){
  //  freopen("B.in","r",stdin);
    //freopen("B.out","w",stdout);
    inv[1] = 1;
    FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha;
    scanf("%d%d",&n,&m);
    FOR(i,1,n) f[i] = i,sz[i] = 1;
    std::map<P,int> S;
    FOR(i,1,m){
        int o,u,v;scanf("%d%d%d",&o,&u,&v);
        if(u > v) std::swap(u,v);
        if(o == 1){
            S[MP(u,v)] = i;
        }
        else{
            modify(1,1,m,S[MP(u,v)],i-1,MP(u,v));
            S.erase(MP(u,v));
        }
    }
    for(auto x:S) modify(1,1,m,x.se,m,x.fi);
    dfs(1,1,m);
    FOR(i,1,m) printf("%d\n",ans[i]);
    return 0;
}

C

主要是普及一下排列如何 $O(n \log n)$ 求三维偏序：

给定三个排列 $a_i,b_i,c_i$，我们要求

$$ \sum_{i,j} [a_i < a_j][b_i < b_j][c_i < c_j] $$

由于是排列，不难发现有

$$ \sum_{i,j} [a_i < a_j][b_i < b_j][c_i < c_j] = \sum_{i,j}[a_i > a_j][b_i > b_j][c_i > c_j] $$

并且排列中不会有相等关系，所以 $[a \leq b] = [a < b],[a \geq b] = [a > b]$，考虑将上述求的东西容斥，需要算的就只有若干个二维偏序和一维偏序问题了。

对于这个题我们考虑硬算期望：首先对于两个都不是 $-1$ 的位置，就是一个三维偏序。

然后对于两个都是 $-1$ 的位置，如果满足 $i<j,p_i < p_j$，就有 $\frac{1}{2}$ 的概率是 $q_i<q_j$，所以这个就是个二维数点，答案乘上 $\frac{1}{2}$。

对于一个是 $-1$ 一个不是的位置，可以预处理没有用过的数中有多少个比某个数 $x$ 大/小的，然后写下式子也是二维数点问题。

题解的做法是直接对上述容斥式子套期望线性性，就比较简单。。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(register int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

int n,p[MAXN],q[MAXN];
const int ha = 998244353;
int inv[MAXN];

inline void add(int &x,int y){
    x += y-ha;x += x>>31&ha;
}

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXN],ts[MAXN],now;

    inline void reset(){++now;}

    inline void add(int pos,int x){
        while(pos < MAXN){
            if(ts[pos] != now) ts[pos] = now,tree[pos] = 0;
            ::add(tree[pos],x);
            pos += lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos){
            if(ts[pos] != now) ts[pos] = now,tree[pos] = 0;
            ::add(res,tree[pos]);
            pos -= lowbit(pos);
        }
        return res;
    }
}bit;

int ans = 0;
struct Node{
    int x,y,z;
    Node(int x=0,int y=0,int z=0) : x(x),y(y),z(z) {}

    inline bool operator < (const Node &t) const {
        return x < t.x;
    }
}a[MAXN];

inline int work2(int n){
    bit.reset();
//    std::sort(a+1,a+n+1);
    int res = 0;
    FOR(i,1,n){
        add(res,bit.query(a[i].y));
        bit.add(a[i].y,1);
    }
    return res;
}

inline void work(int n){// 单 log 三维偏序
    ans = 1ll*n*(n-1)%ha;
    add(ans,ha-3ll*n%ha*(n-1)%ha*inv[2]%ha);
    std::sort(a+1,a+n+1);
    add(ans,work2(n));// (x,y,z)
    FOR(i,1,n) std::swap(a[i].x,a[i].z);
    std::sort(a+1,a+n+1);
    add(ans,work2(n));// (z,y,x)
    FOR(i,1,n) std::swap(a[i].y,a[i].z);
    add(ans,work2(n));// (z,x,y)
    ans = 1ll*ans*inv[2]%ha;
//    int t = 0;
//    FOR(i,1,n) FOR(j,1,n) if(i != j && a[i].x < a[j].x && a[i].y < a[j].y && a[i].z < a[j].z) ++t;
//    DEBUG(t);
}

int nxt[MAXN],pre[MAXN];

int main(){
 //   freopen("C.in","r",stdin);
   // freopen("C.out","w",stdout);
    read(n);FOR(i,1,n) read(p[i]);FOR(i,1,n) read(q[i]);
    inv[1] = 1;FOR(i,2,MAXN-1) inv[i] = 1ll*(ha-ha/i)*inv[ha%i]%ha;
    int m = 0;
    // part 1
    FOR(i,1,n) if(q[i] != -1) a[++m] = Node(i,p[i],q[i]);
    work(m);
    // part 2
    m = n-m;
    bit.reset();
    FOR(i,1,n){
        if(q[i] != -1) continue;
        add(ans,1ll*bit.query(p[i])*inv[2]%ha);
        bit.add(p[i],1);
    }
    // part 3
    FOR(i,1,n) if(q[i] != -1) nxt[q[i]] = 1;
    FOR(i,1,n) nxt[i] ^= 1,pre[i] = nxt[i];
    ROF(i,n,1) nxt[i] += nxt[i+1];
    FOR(i,1,n) pre[i] += pre[i-1];
    bit.reset();
    FOR(i,1,n){
        if(q[i] == -1){
            add(ans,bit.query(p[i]));
        }
        else{
            bit.add(p[i],1ll*nxt[q[i]]*inv[m]%ha);
        }
    }
    bit.reset();
    FOR(i,1,n){
        if(q[i] == -1){
            bit.add(p[i],1);
        }
        else{
            add(ans,1ll*bit.query(p[i])*pre[q[i]]%ha*inv[m]%ha);
        }
    }
    printf("%d\n",ans);
    return 0;
}

D

先考虑策略是什么，考试的时候我没有注意到这个事实：后手可以等先手钻进某个角落自闭的时候慢慢把所有道路清掉，就以为策略之间很麻烦。。

我们设 $f_v$ 表示从 $v$ 点钻进去的代价，那么如果先手考虑从 $v$ 点钻进去，后手肯定会先 ban 掉最大的 $f_x$，其中 $x \in son_v$。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
std::vector<int> G[MAXN];
int n,s,t;
int f[MAXN],fa[MAXN],sm[MAXN];

inline void dfs(int v,int fa=0){
    int mx = 0,cmx = 0,deg = (int)G[v].size()-(fa!=0);::fa[v] = fa;
    for(auto x:G[v]){
        if(x == fa) continue;
        sm[x] = sm[v]+(v==t?0:deg-1);
        dfs(x,v);
        if(f[x] > mx){
            cmx = mx;mx = f[x];
        }
        else if(f[x] > cmx){
            cmx = f[x];
        }
    }
    if(!deg) f[v] = 0;
    else if(deg == 1) f[v] = 1;
    else f[v] = cmx+deg;
}

inline bool chk(int lim){// 花费不超过 lim 到根
    int v = s,las = -1,now = 0,r = 1;
    while(v != t){ // 枚举在哪个点钻进去
        int cnt = 0;
        for(auto x:G[v]){
            if(x == fa[v] || x == las) continue;
            cnt += (now+f[x]+1+sm[x]-(v!=s) > lim);
        }
        now += cnt;
        if(now > r || now > lim) return 0;
        v = fa[las=v];++r;
    }
    return 1;
}

int main(){
    scanf("%d%d%d",&n,&t,&s);
    if(s == t) return puts("0"),0;
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);
        G[u].pb(v);G[v].pb(u);
    }
    dfs(t);
    int l = 0,r = 2*n,ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid)) ans = mid,r = mid-1;
        else l = mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

20zr联赛集训day15

A

B

C

D

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「NOIP2016」换教室

最小树形图 / 朱刘算法

主席树学习笔记

CF 1086 题解

「Luogu P3603」雪辉

20zr联赛集训day15

A

B

C

D