contest5 题解

Author： RainAir
发布时间：October 22, 2020
1099views
One comment
1548 words
Categories：题解

A. 星际穿越

感觉也很神。。

先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。

考虑 $r$ 往左走的最短路径是怎么走的：

引理一：往右走之前一定不会往左走

反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。

引理二：不会存在连续的两次往右走

反证法。如果存在两次连续的往右走，那么之后一定有一次往左走，并且跨越起点的，我们可以一开始就走到这个点，答案不会变劣。

所以我们的路径只有可能是先往右最多走一次，再往左走。

我们观察一下一个点 $v$ 到达左边的点 $x$ 的最短距离的分布是怎么样的：

如果 $dis(v,x)=1$，那么有 $l_v \leq x$。

如果 $dis(v,x) \leq 2$，那么我们就会先走一步，用这个点中转，也就是问在区间 $[l_v,n]$ 内是否存在点 $y$，使得 $dis(x,y) \leq 1$。注意这里这个区间包含了一些根本不跨过 $v$ 的点，但这是显然不影响答案的。

归纳可以得到：如果 $dis(v,x) \leq k$，当且仅当存在一个点 $y \in [l_v,n]$，满足 $dis(x,y) \leq k-1$。

所以一个暴力的想法是每次先特判了距离为 $1$ 的点，然后每次求出最往左的距离为 $2$ 的点跳过去，以此类推。。

对于跳这种东西，我们肯定想到要用倍增优化。我们想找到 $\leq k$ 的最往左的点，就要找到 $dis(x,y) \leq k-1$ 的最往左的点。。。所以我们定义在找 $dis(v,x) \leq k$ 的一次跳跃是从 $x$ 点找到最小的一个点 $z$，满足 $\exists y \in [l_v,n],dis(z,y) \leq k-1$，所以设 $f_{i,j}$ 表示从 $i$ 号点，跳了 $2^j$ 次（也就是处理了距离为 $[1,2^j+1]$ 的点），为了统计答案，设 $g_{i,j}$ 表示从 $i$ 号点跳了 $2^j$ 的所有答案，初始化 $f_{i,0} = \min_{j \geq i}\{l_j\}$，$f_{1,0} = 0,g_{i,0} = i-f_{i,0}$。转移大概写一下：

$$ \begin{aligned} f_{i,j} &= f_{f_{i,j-1},j-1}\\ g_{i,j} &= g_{i,j-1}+g_{f_{i,j-1},j-1}+2^{j-1}(f_{i,j-1}-f_{i,j}) \end{aligned} $$

查询的时候跳一下，记一下已经跳了多少长度即可。最后有一些零散的边界要判掉。

#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 = 3e5 + 5;
const int MAXM = 18;

int n,l[MAXN];
// 处理[i,n]跳2^j步的最远位置 和这一块的答案
int f[MAXN][MAXM+1];
LL g[MAXN][MAXM+1];
int pw[MAXM+1];

inline LL calc(int l,int p){
    if(l > p) return 0;
    if(l >= ::l[p]) return p-l;
    LL res = p-::l[p],now = 1;p = ::l[p];
    ROF(i,MAXM,0){
        if(f[p][i] < l) continue;
        res += g[p][i] + now*(p-f[p][i]);
        now += (1<<i);
        p = f[p][i];
    }
    if(l <= p) res += (now+1)*(p-l);
    return res;
}

inline LL gcd(LL x,LL y){
    return !y ? x : gcd(y,x%y);
}

int main(){
    pw[0] = 1;FOR(i,1,MAXM) pw[i] = pw[i-1]<<1;
    scanf("%d",&n);
    FOR(i,2,n) scanf("%d",l+i),f[i][0] = l[i];
    ROF(i,n-1,2) f[i][0] = std::min(f[i][0],f[i+1][0]),g[i][0] = i-f[i][0];
    f[1][0] = 0;
    FOR(j,1,MAXM){
        FOR(i,1,n){
            f[i][j] = f[f[i][j-1]][j-1];
            g[i][j] = g[i][j-1]+g[f[i][j-1]][j-1]+(f[i][j-1]-f[i][j])*pw[j-1];
        }
    }
    int q;scanf("%d",&q);
    // DEBUG(calc(3,6));
    // exit(0);
    while(q--){
        int l,r,x;scanf("%d%d%d",&l,&r,&x);
        LL res = calc(l,x)-calc(r+1,x);
        LL g = gcd(r-l+1,res);
        printf("%lld/%lld\n",res/g,(r-l+1)/g);
    }
    return 0;
}

B. Minimax

设 $f_{v,i}$ 表示 $v$ 号点权值为 $i$ 的概率，考虑如何合并两个子树 $x,y$：

$$ f_{v,i} = f_{x,i}(p_v\sum_{j < i} f_{y,j}+(1-p_v)\sum_{j > i} f_{y,j}) + f_{y,i}(p_v\sum_{j < i} f_{x,j}+(1-p_v)\sum_{j > i} f_{x,j}) $$

这种 dp 维护可以搞个线段树合并，每次在区间 $[l,r]$ 的时候考虑同时维护一个对 $x,y$ 分别应该打什么标记，类似cdq分治那样处理左边对右边的贡献，和右边对左边的贡献即可。

#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 = 3e5 + 5;
const int ha = 998244353;
const int inv = 796898467;

int n;
std::vector<int> G[MAXN];
int a[MAXN];

int rt[MAXN],sm[MAXN*25],tag[MAXN*25],lc[MAXN*25],rc[MAXN*25],tot;

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

inline void cover(int x,int d){
    // add(tag[x],d);
    tag[x] = 1ll*tag[x]*d%ha;
    sm[x] = 1ll*sm[x]*d%ha;
}

inline void pushdown(int x){
    if(tag[x] != 1){    
        if(lc[x]) cover(lc[x],tag[x]);
        if(rc[x]) cover(rc[x],tag[x]);
        tag[x] = 1;
    }
}

int p,M;

inline void update(int &x,int l,int r,int p){
    x = ++tot;sm[x] = tag[x] = 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(p <= mid) update(lc[x],l,mid,p);
    else update(rc[x],mid+1,r,p);
}

inline int merge(int x,int y,int dx,int dy){
    if(!x && !y) return 0;
    if(!x || !y){
        cover(x|y,x?dx:dy);
        return x|y;
    }
    pushdown(x);pushdown(y);
    int lsx = sm[lc[x]],rsx = sm[rc[x]],lsy = sm[lc[y]],rsy = sm[rc[y]];
    lc[x] = merge(lc[x],lc[y],(dx+1ll*(1+ha-p)%ha*rsy%ha)%ha,(dy+1ll*(1+ha-p)%ha*rsx%ha)%ha);
    rc[x] = merge(rc[x],rc[y],(dx+1ll*p*lsy%ha)%ha,(dy+1ll*p*lsx%ha)%ha);
    sm[x] = (sm[lc[x]]+sm[rc[x]])%ha;
    return x;
}

inline int query(int x,int l,int r,int p){
    if(l == r) return sm[x];
    int mid = (l + r) >> 1;pushdown(x);
    if(p <= mid) return query(lc[x],l,mid,p);
    return query(rc[x],mid+1,r,p);
}

inline void dfs(int v){
    if(G[v].empty()){
        update(rt[v],1,M,a[v]);
        return;
    }
    for(auto x:G[v]) dfs(x);
    if(G[v].size() == 1){
        rt[v] = rt[G[v][0]];
        return;
    }
    p = a[v];
    rt[v] = merge(rt[G[v][0]],rt[G[v][1]],0,0);
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        int f;scanf("%d",&f);
        if(f) G[f].pb(i);
    }
    std::vector<int> S;
    FOR(i,1,n){
        scanf("%d",a+i);
        if(G[i].empty()) S.pb(a[i]);
        else a[i] = 1ll*a[i]*inv%ha;
    }
    std::sort(all(S));M = S.size();
    FOR(i,1,n) if(G[i].empty()) a[i] = std::lower_bound(all(S),a[i])-S.begin()+1;
    dfs(1);
    int ans = 0;
    FOR(i,1,M){
        int t = query(1,1,M,i);
        // DEBUG(t);
        add(ans,1ll*i*S[i-1]%ha*t%ha*t%ha);
    }
    printf("%d\n",ans);
    return 0;
}

C. 随机算法

考虑给定最终选出的一个独立集序列 $p_1,p_2,\ldots,p_m$，如何求有多大的概率生成的排列能得到这个序列。

首先第一个数一定是 $p_1$，接下来和 $p_1$ 相连的点就可以乱放了，在剩下的点中第一个要放的一定是 $p_2$，然后和 $p_2$ 相连，还没有被放完的点也可以乱放了。所以我们处理出 $sz_S$ 表示集合 $S$ 放完之后，有多少个点可以乱放（包含集合 $S$ 内的点），并且这个只对独立集有定义。

所以概率就是：

$$ \prod_{i=1}^m \frac{1}{n-sz_{\cup_{j=1}^{i-1}\{p_j\}}} $$

我们考虑对这个dp：设 $f_S$ 表示最终独立集序列为 $S$ ，所有 $|S|!$ 种方案的概率的和，答案显然就是每个最大独立集的 $f_S$。转移只需要枚举一个点，如果可以加入这个独立集就把对应的概率乘上就行了。

#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 = 20;
const int ha = 998244353;
#define lowbit(x) ((x)&(-(x)))

int n,m,e[MAXN];
int ee[(1<<MAXN)+3],sz[(1<<MAXN)+3];// 选了独立集 S 后 位置可以自由选择的位置的数量
int f[(1<<MAXN)+3];// S 内 任意顺序排列概率的和
bool vis[(1<<MAXN)+3];
int inv[MAXN+1];

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

int main(){
    inv[1] = 1;FOR(i,2,MAXN) inv[i] = (ha-1ll*(ha/i)*inv[ha%i]%ha)%ha;
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        int u,v;scanf("%d%d",&u,&v);--u;--v;
        e[u] |= (1<<v);e[v] |= (1<<u);
    }
    FOR(i,0,n-1) ee[1<<i] = e[i];
    FOR(S,1,(1<<n)-1) ee[S] = ee[S-lowbit(S)]|ee[lowbit(S)];
    int mx = 0;
    FOR(S,0,(1<<n)-1) if(!(ee[S]&S)) vis[S] = 1,mx = std::max(mx,(int)__builtin_popcount(S));
    FOR(S,0,(1<<n)-1) sz[S] = __builtin_popcount(ee[S]|S);
    f[0] = 1;
    FOR(S,0,(1<<n)-1){
        if(!f[S]) continue;
        if(!vis[S]) continue;
        FOR(i,0,n-1){
            if((S>>i)&1) continue;
            if(!vis[S|(1<<i)]) continue;
            add(f[S|(1<<i)],1ll*f[S]*inv[n-sz[S]]%ha);
        }
    }
    int ans = 0;
    FOR(S,0,(1<<n)-1) if(vis[S] && __builtin_popcount(S) == mx) add(ans,f[S]);
    printf("%d\n",ans);
    return 0;
}

Last modification：October 22nd, 2020 at 10:13 pm

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

One comment

Qingyu
October 24th, 2020 at 11:51 am

膜拜队长！

Reply

contest5 题解

RainAir • 2020 年 10 月 22 日

A. 星际穿越

感觉也很神。。

先将询问拆成前缀和的形式，我们要对于一组询问 $(l,r)$ 求出 $[l,r]$ 内所有点到 $r$ 的最短距离的和。

考虑 $r$ 往左走的最短路径是怎么走的：

引理一：往右走之前一定不会往左走

反证法。如果先往左走在往右走，那么这个右边的点一定能 cover 到起点，所以可以第一步就先往右走，答案不会变劣。

引理二：不会存在连续的两次往右走

反证法。如果存在两次连续的往右走，那么之后一定有一次往左走，并且跨越起点的，我们可以一开始就走到这个点，答案不会变劣。

所以我们的路径只有可能是先往右最多走一次，再往左走。

我们观察一下一个点 $v$ 到达左边的点 $x$ 的最短距离的分布是怎么样的：

如果 $dis(v,x)=1$，那么有 $l_v \leq x$。

归纳可以得到：如果 $dis(v,x) \leq k$，当且仅当存在一个点 $y \in [l_v,n]$，满足 $dis(x,y) \leq k-1$。

所以一个暴力的想法是每次先特判了距离为 $1$ 的点，然后每次求出最往左的距离为 $2$ 的点跳过去，以此类推。。

$$ \begin{aligned} f_{i,j} &= f_{f_{i,j-1},j-1}\\ g_{i,j} &= g_{i,j-1}+g_{f_{i,j-1},j-1}+2^{j-1}(f_{i,j-1}-f_{i,j}) \end{aligned} $$

查询的时候跳一下，记一下已经跳了多少长度即可。最后有一些零散的边界要判掉。

#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 = 3e5 + 5;
const int MAXM = 18;

int n,l[MAXN];
// 处理[i,n]跳2^j步的最远位置 和这一块的答案
int f[MAXN][MAXM+1];
LL g[MAXN][MAXM+1];
int pw[MAXM+1];

inline LL calc(int l,int p){
    if(l > p) return 0;
    if(l >= ::l[p]) return p-l;
    LL res = p-::l[p],now = 1;p = ::l[p];
    ROF(i,MAXM,0){
        if(f[p][i] < l) continue;
        res += g[p][i] + now*(p-f[p][i]);
        now += (1<<i);
        p = f[p][i];
    }
    if(l <= p) res += (now+1)*(p-l);
    return res;
}

inline LL gcd(LL x,LL y){
    return !y ? x : gcd(y,x%y);
}

int main(){
    pw[0] = 1;FOR(i,1,MAXM) pw[i] = pw[i-1]<<1;
    scanf("%d",&n);
    FOR(i,2,n) scanf("%d",l+i),f[i][0] = l[i];
    ROF(i,n-1,2) f[i][0] = std::min(f[i][0],f[i+1][0]),g[i][0] = i-f[i][0];
    f[1][0] = 0;
    FOR(j,1,MAXM){
        FOR(i,1,n){
            f[i][j] = f[f[i][j-1]][j-1];
            g[i][j] = g[i][j-1]+g[f[i][j-1]][j-1]+(f[i][j-1]-f[i][j])*pw[j-1];
        }
    }
    int q;scanf("%d",&q);
    // DEBUG(calc(3,6));
    // exit(0);
    while(q--){
        int l,r,x;scanf("%d%d%d",&l,&r,&x);
        LL res = calc(l,x)-calc(r+1,x);
        LL g = gcd(r-l+1,res);
        printf("%lld/%lld\n",res/g,(r-l+1)/g);
    }
    return 0;
}

B. Minimax

设 $f_{v,i}$ 表示 $v$ 号点权值为 $i$ 的概率，考虑如何合并两个子树 $x,y$：

$$ f_{v,i} = f_{x,i}(p_v\sum_{j < i} f_{y,j}+(1-p_v)\sum_{j > i} f_{y,j}) + f_{y,i}(p_v\sum_{j < i} f_{x,j}+(1-p_v)\sum_{j > i} f_{x,j}) $$

#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 = 3e5 + 5;
const int ha = 998244353;
const int inv = 796898467;

int n;
std::vector<int> G[MAXN];
int a[MAXN];

int rt[MAXN],sm[MAXN*25],tag[MAXN*25],lc[MAXN*25],rc[MAXN*25],tot;

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

inline void cover(int x,int d){
    // add(tag[x],d);
    tag[x] = 1ll*tag[x]*d%ha;
    sm[x] = 1ll*sm[x]*d%ha;
}

inline void pushdown(int x){
    if(tag[x] != 1){    
        if(lc[x]) cover(lc[x],tag[x]);
        if(rc[x]) cover(rc[x],tag[x]);
        tag[x] = 1;
    }
}

int p,M;

inline void update(int &x,int l,int r,int p){
    x = ++tot;sm[x] = tag[x] = 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(p <= mid) update(lc[x],l,mid,p);
    else update(rc[x],mid+1,r,p);
}

inline int merge(int x,int y,int dx,int dy){
    if(!x && !y) return 0;
    if(!x || !y){
        cover(x|y,x?dx:dy);
        return x|y;
    }
    pushdown(x);pushdown(y);
    int lsx = sm[lc[x]],rsx = sm[rc[x]],lsy = sm[lc[y]],rsy = sm[rc[y]];
    lc[x] = merge(lc[x],lc[y],(dx+1ll*(1+ha-p)%ha*rsy%ha)%ha,(dy+1ll*(1+ha-p)%ha*rsx%ha)%ha);
    rc[x] = merge(rc[x],rc[y],(dx+1ll*p*lsy%ha)%ha,(dy+1ll*p*lsx%ha)%ha);
    sm[x] = (sm[lc[x]]+sm[rc[x]])%ha;
    return x;
}

inline int query(int x,int l,int r,int p){
    if(l == r) return sm[x];
    int mid = (l + r) >> 1;pushdown(x);
    if(p <= mid) return query(lc[x],l,mid,p);
    return query(rc[x],mid+1,r,p);
}

inline void dfs(int v){
    if(G[v].empty()){
        update(rt[v],1,M,a[v]);
        return;
    }
    for(auto x:G[v]) dfs(x);
    if(G[v].size() == 1){
        rt[v] = rt[G[v][0]];
        return;
    }
    p = a[v];
    rt[v] = merge(rt[G[v][0]],rt[G[v][1]],0,0);
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        int f;scanf("%d",&f);
        if(f) G[f].pb(i);
    }
    std::vector<int> S;
    FOR(i,1,n){
        scanf("%d",a+i);
        if(G[i].empty()) S.pb(a[i]);
        else a[i] = 1ll*a[i]*inv%ha;
    }
    std::sort(all(S));M = S.size();
    FOR(i,1,n) if(G[i].empty()) a[i] = std::lower_bound(all(S),a[i])-S.begin()+1;
    dfs(1);
    int ans = 0;
    FOR(i,1,M){
        int t = query(1,1,M,i);
        // DEBUG(t);
        add(ans,1ll*i*S[i-1]%ha*t%ha*t%ha);
    }
    printf("%d\n",ans);
    return 0;
}

C. 随机算法

考虑给定最终选出的一个独立集序列 $p_1,p_2,\ldots,p_m$，如何求有多大的概率生成的排列能得到这个序列。

所以概率就是：

$$ \prod_{i=1}^m \frac{1}{n-sz_{\cup_{j=1}^{i-1}\{p_j\}}} $$

#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 = 20;
const int ha = 998244353;
#define lowbit(x) ((x)&(-(x)))

int n,m,e[MAXN];
int ee[(1<<MAXN)+3],sz[(1<<MAXN)+3];// 选了独立集 S 后 位置可以自由选择的位置的数量
int f[(1<<MAXN)+3];// S 内 任意顺序排列概率的和
bool vis[(1<<MAXN)+3];
int inv[MAXN+1];

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

int main(){
    inv[1] = 1;FOR(i,2,MAXN) inv[i] = (ha-1ll*(ha/i)*inv[ha%i]%ha)%ha;
    scanf("%d%d",&n,&m);
    FOR(i,1,m){
        int u,v;scanf("%d%d",&u,&v);--u;--v;
        e[u] |= (1<<v);e[v] |= (1<<u);
    }
    FOR(i,0,n-1) ee[1<<i] = e[i];
    FOR(S,1,(1<<n)-1) ee[S] = ee[S-lowbit(S)]|ee[lowbit(S)];
    int mx = 0;
    FOR(S,0,(1<<n)-1) if(!(ee[S]&S)) vis[S] = 1,mx = std::max(mx,(int)__builtin_popcount(S));
    FOR(S,0,(1<<n)-1) sz[S] = __builtin_popcount(ee[S]|S);
    f[0] = 1;
    FOR(S,0,(1<<n)-1){
        if(!f[S]) continue;
        if(!vis[S]) continue;
        FOR(i,0,n-1){
            if((S>>i)&1) continue;
            if(!vis[S|(1<<i)]) continue;
            add(f[S|(1<<i)],1ll*f[S]*inv[n-sz[S]]%ha);
        }
    }
    int ans = 0;
    FOR(S,0,(1<<n)-1) if(vis[S] && __builtin_popcount(S) == mx) add(ans,f[S]);
    printf("%d\n",ans);
    return 0;
}

contest5 题解

A. 星际穿越

B. Minimax

C. 随机算法

One comment

Leave a Comment Cancel reply

NOI2021 退役记

I'm back

SDOI2020 退役记

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

CSP2019 游记

概率期望入门

「优化」内存池

CF 666 题解

CF461D Appleman and Complicated Task

KD-Tree 学习笔记

contest5 题解

A. 星际穿越

B. Minimax

C. 随机算法