contest4 题解

Author： RainAir
发布时间：October 20, 2020
942views
No comments
883 words
Categories：题解

A. Slay the Spire

考虑最优的操作是什么：由于强化牌都 $>1$，所以我们肯定是先尽量用强化牌，最后一次用攻击牌。

将两种牌分别从大到小排序，可以分别 dp：设 $f_{i,j,0/1}$ 表示考虑前 $i$ 张牌强化牌，选了 $j$ 张，是否选择第 $i$ 张的所有方案的和（每种方案的权值是乘积），$g_{i,j,0/1}$ 考虑攻击牌，这里方案的权值就是和了。

转移比较显然，我们考虑最后如何计算答案：

枚举选了 $i$ 个强化牌，那么就选了 $m-i$ 个攻击牌，要使用 $k-i$ 个，如果 $i \leq k-1$，说明所有强化牌都要用，枚举两种牌使用牌的最小值，答案是：

$$ \sum_{x=1}^n f_{x,i,1}\sum_{y=1}^n g_{y,k-i,1}\binom{n-y}{m-k} $$

如果 $i > k-1$，说明只能使用 $k-1$ 个强化牌，使用 $1$ 个攻击牌，也是枚举：

$$ \sum_{x=1}^n f_{x,k-1,1}\binom{n-x}{i-k+1}\sum_{y=1}^n g_{y,1,1}\binom{n-y}{m-i-1} $$

需要卡常。

#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(register int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;
const int ha = 998244353;
int n,m,k,w1[MAXN],w2[MAXN];
int binom[MAXN][MAXN];

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

inline void prework(){
    binom[0][0] = 1;
    FOR(i,1,MAXN-1){
        binom[i][0] = 1;
        FOR(j,1,i){
            binom[i][j] = add(binom[i-1][j],binom[i-1][j-1]);
        }
    }
}

inline int C(int n,int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return binom[n][m];
}

int f[MAXN][MAXN][2],g[MAXN][MAXN][2];
int F[MAXN][MAXN],G[MAXN][MAXN];

inline void Solve(){
    scanf("%d%d%d",&n,&m,&k);
    FOR(i,1,n) scanf("%d",&w1[i]);
    FOR(i,1,n) scanf("%d",&w2[i]);
    std::sort(w1+1,w1+n+1);std::sort(w2+1,w2+n+1);
    std::reverse(w1+1,w1+n+1);std::reverse(w2+1,w2+n+1);
    // FOR(i,0,n){
        // FOR(j,0,i){
            // f[i][j][0] = f[i][j][1] = g[i][j][0] = g[i][j][1] = F[i][j] = G[i][j] = 0;
        // }
    // }
    f[0][0][0] = 1;
    FOR(i,1,n){
        FOR(j,0,i){
            f[i][j][0] = add(f[i-1][j][0],f[i-1][j][1]);
            if(j) f[i][j][1] = 1ll*add(f[i-1][j-1][0],f[i-1][j-1][1])*w1[i]%ha;
            g[i][j][0] = add(g[i-1][j][0],g[i-1][j][1]);
            if(j) g[i][j][1] = add(add(g[i-1][j-1][0],g[i-1][j-1][1]),1ll*w2[i]*C(i-1,j-1)%ha);
            F[i][j] = f[i][j][1];
            G[i][j] = g[i][j][1];
        }
    }
    F[0][0] = G[0][0] = 1;
    int ans = 0;
    FOR(i,0,std::min(m,k-1)){
        int gx1 = 0,gx2 = 0;
        FOR(x,i,n) gx1 = add(gx1,F[x][i]);
        FOR(y,k-i,n) gx2 = add(gx2,1ll*G[y][k-i]*C(n-y,m-k)%ha);
        ans = add(ans,1ll*gx1*gx2%ha);
    }
    FOR(i,k,m){
        int gx1 = 0,gx2 = 0;
        FOR(x,k-1,n) gx1 = add(gx1,1ll*F[x][k-1]*C(n-x,i-k+1)%ha);
        FOR(y,1,n) gx2 = add(gx2,1ll*G[y][1]*C(n-y,m-i-1)%ha);
        ans = add(ans,1ll*gx1*gx2%ha);
    }
    printf("%d\n",ans);
}
/*
设 F[i][j]: 强制选择第i个牌 选了j个强化牌
G[i][j]: 攻击牌
枚举选了几个强化牌 i 可以得到剩下的牌 m-i
如果 i <= k-1 那么会有 k-i 张攻击牌可以使用m-k剩下的攻击牌 在后面选一下
F[x][i]*G[y][j]*C(n-y,m-k)
如果 i > k-1 那么必须使用 k-1 张强化牌 剩下的使用 1 个攻击牌
F[x][k-1]*C(n-x,i-k+1)*G[y][1]*C(n-y,m-i-1)
*/

int main(){
    prework();
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

B. 最大前缀和

计数题一定要分析性质！！

分析一下最大前缀和的性质，设最大前缀和的位置是 $p$：

$p$ 前缀的每一个真后缀和都 $> 0$ 否则可以替换
$p$ 后缀的每一个前缀都 $\leq 0$ 否则替换更优

不难发现这样把每一个序列在最前面的最大前缀和枚举了，所以我们考虑分开dp：

设 $f_{S}$ 表示 $S$ 内元素排列满足第一种性质的方案数，$g_S$ 表示第二种的。

考虑第二种：我们考虑每次往后加一个数，只需要判断当前状态是否还是 $\leq 0$ 就行了，设子集和为 $sm_S$，也就是 $g_S += \sum_{i \in S} g_{S-i}$。

第一种我们考虑往前加：由于是真后缀，所以要判断当前状态是否满足条件，然后向所有状态转移，$f_{S+i} += f_S(i \not \in S)$。

最后统计答案枚举断点，$\sum_{S} sm_S f_Sg_{U-S}$。

这里注意一下 $f$ 的初始值是 $f_{2^i} = 1$，因为大小为 $1$ 的串没有真后缀。。

前缀和后缀相关 dp 就要按着顺序加才是对的。。

这也告诉我们 dp 真前缀的时候应该考虑从哪里转移的那个状态是否合法而不是当前状态。。。

#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;
LL sm[(1<<MAXN)+3];
int f[(1<<MAXN)+3],g[(1<<MAXN)+3];
// f[S]: S内元素真后缀>0的方案数
// g[S]: S内元素最大前缀和<=0的方案数

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

int main(){
    scanf("%d",&n);
    FOR(i,0,n-1) scanf("%lld",&sm[1<<i]);
    FOR(S,1,(1<<n)-1) sm[S] = sm[S-lowbit(S)]+sm[lowbit(S)];
    FOR(i,0,n-1) f[1<<i] = 1;
    g[0] = 1;
    FOR(S,1,(1<<n)-1){
        if(sm[S] <= 0){
            FOR(i,0,n-1) if((S>>i)&1) add(g[S],g[S^(1<<i)]);
        }
        else{
            FOR(i,0,n-1) if(!((S>>i)&1)) add(f[S^(1<<i)],f[S]);
        }
    }
    // DEBUG(f[(1<<5)|(1<<10)]);
    int ans = 0;
    FOR(S,1,(1<<n)-1) add(ans,(1ll*sm[S]%ha*f[S]%ha*g[S^((1<<n)-1)]%ha+ha)%ha);
    printf("%d\n",ans);
    return 0;
}

C. 氪金手游

首先这个数不一定是外向树。。不过我们可以先思考一下外向树怎么做

首先一个经典的结论：给树上每个点随机一个数，每个点成为子树中最小值的概率是独立的。

所以我们考虑这个题，如果知道了每个点的 $w$ 的取值，设子树内 $w$ 的和为 $sm_i$，那么这个点成为最小值的概率就是 $\frac{w_i}{sm_i}$。不难发现概率只和子树内的和有关，所以可以搞一个dp：设 $f_{v,i}$ $v$ 子树内，$w$ 的和为 $i$ ，满足条件的概率，转移直接树上背包合并，由于 $i \leq 3sz_v$，复杂度是 $O(n^2)$ 的。

现在的问题是会有一些反向边，然而反向边我们可以看成反向的限制，于是可以容斥成无限制和正向的限制，每有一个正向的限制容斥系数就要 $\times (-1)$。所以我们直接带着容斥系数dp，每次遇到反向边枚举一下是断开还是变成正向边就行了。注意如果断开的话那个子树内的 $\sum w$ 是不能累加到 dp 数组内的，而只是作为两个独立的事件，乘到所有状态上就行。

#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 = 1000+5;
const int ha = 998244353;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

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

int f[MAXN][MAXN*3];
int n,p[MAXN][4];

struct Edge{
    int to,w,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void adde(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
}

int t[MAXN*3],sz[MAXN];

inline void merge(int x,int y,int w){
    FOR(i,1,sz[x]*3) t[i] = f[x][i],f[x][i] = 0;
    FOR(i,1,sz[x]*3){
        FOR(j,1,sz[y]*3){
            if(w) add(f[x][i+j],1ll*t[i]*f[y][j]%ha);
            else{
                add(f[x][i+j],ha-1ll*t[i]*f[y][j]%ha);
                add(f[x][i],1ll*t[i]*f[y][j]%ha);
            }
        }
    }
}

inline void dfs(int v,int fa=0){
    FOR(i,1,3) f[v][i] = 1ll*p[v][i]*i%ha;
    sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs(e[i].to,v);
        merge(v,e[i].to,e[i].w);
        sz[v] += sz[e[i].to];
    }
    FOR(i,1,sz[v]*3) f[v][i] = 1ll*f[v][i]*qpow(i)%ha;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        int sm = 0;
        FOR(j,1,3) scanf("%d",&p[i][j]),add(sm,p[i][j]);
        sm = qpow(sm);
        FOR(j,1,3) p[i][j] = 1ll*p[i][j]*sm%ha;
    }
    FOR(i,1,n-1){
        int u,v;scanf("%d%d",&u,&v);adde(u,v,1);adde(v,u,0);
    }
    dfs(1);
    int ans = 0;
    FOR(i,1,n*3) add(ans,f[1][i]);
    printf("%d\n",ans);
    return 0;
}

Last modification：October 22nd, 2020 at 08:32 pm

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

contest4 题解

RainAir • 2020 年 10 月 20 日

A. Slay the Spire

考虑最优的操作是什么：由于强化牌都 $>1$，所以我们肯定是先尽量用强化牌，最后一次用攻击牌。

转移比较显然，我们考虑最后如何计算答案：

枚举选了 $i$ 个强化牌，那么就选了 $m-i$ 个攻击牌，要使用 $k-i$ 个，如果 $i \leq k-1$，说明所有强化牌都要用，枚举两种牌使用牌的最小值，答案是：

$$ \sum_{x=1}^n f_{x,i,1}\sum_{y=1}^n g_{y,k-i,1}\binom{n-y}{m-k} $$

如果 $i > k-1$，说明只能使用 $k-1$ 个强化牌，使用 $1$ 个攻击牌，也是枚举：

$$ \sum_{x=1}^n f_{x,k-1,1}\binom{n-x}{i-k+1}\sum_{y=1}^n g_{y,1,1}\binom{n-y}{m-i-1} $$

需要卡常。

#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(register int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5000+5;
const int ha = 998244353;
int n,m,k,w1[MAXN],w2[MAXN];
int binom[MAXN][MAXN];

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

inline void prework(){
    binom[0][0] = 1;
    FOR(i,1,MAXN-1){
        binom[i][0] = 1;
        FOR(j,1,i){
            binom[i][j] = add(binom[i-1][j],binom[i-1][j-1]);
        }
    }
}

inline int C(int n,int m){
    if(n < 0 || m < 0 || n < m) return 0;
    return binom[n][m];
}

int f[MAXN][MAXN][2],g[MAXN][MAXN][2];
int F[MAXN][MAXN],G[MAXN][MAXN];

inline void Solve(){
    scanf("%d%d%d",&n,&m,&k);
    FOR(i,1,n) scanf("%d",&w1[i]);
    FOR(i,1,n) scanf("%d",&w2[i]);
    std::sort(w1+1,w1+n+1);std::sort(w2+1,w2+n+1);
    std::reverse(w1+1,w1+n+1);std::reverse(w2+1,w2+n+1);
    // FOR(i,0,n){
        // FOR(j,0,i){
            // f[i][j][0] = f[i][j][1] = g[i][j][0] = g[i][j][1] = F[i][j] = G[i][j] = 0;
        // }
    // }
    f[0][0][0] = 1;
    FOR(i,1,n){
        FOR(j,0,i){
            f[i][j][0] = add(f[i-1][j][0],f[i-1][j][1]);
            if(j) f[i][j][1] = 1ll*add(f[i-1][j-1][0],f[i-1][j-1][1])*w1[i]%ha;
            g[i][j][0] = add(g[i-1][j][0],g[i-1][j][1]);
            if(j) g[i][j][1] = add(add(g[i-1][j-1][0],g[i-1][j-1][1]),1ll*w2[i]*C(i-1,j-1)%ha);
            F[i][j] = f[i][j][1];
            G[i][j] = g[i][j][1];
        }
    }
    F[0][0] = G[0][0] = 1;
    int ans = 0;
    FOR(i,0,std::min(m,k-1)){
        int gx1 = 0,gx2 = 0;
        FOR(x,i,n) gx1 = add(gx1,F[x][i]);
        FOR(y,k-i,n) gx2 = add(gx2,1ll*G[y][k-i]*C(n-y,m-k)%ha);
        ans = add(ans,1ll*gx1*gx2%ha);
    }
    FOR(i,k,m){
        int gx1 = 0,gx2 = 0;
        FOR(x,k-1,n) gx1 = add(gx1,1ll*F[x][k-1]*C(n-x,i-k+1)%ha);
        FOR(y,1,n) gx2 = add(gx2,1ll*G[y][1]*C(n-y,m-i-1)%ha);
        ans = add(ans,1ll*gx1*gx2%ha);
    }
    printf("%d\n",ans);
}
/*
设 F[i][j]: 强制选择第i个牌 选了j个强化牌
G[i][j]: 攻击牌
枚举选了几个强化牌 i 可以得到剩下的牌 m-i
如果 i <= k-1 那么会有 k-i 张攻击牌可以使用m-k剩下的攻击牌 在后面选一下
F[x][i]*G[y][j]*C(n-y,m-k)
如果 i > k-1 那么必须使用 k-1 张强化牌 剩下的使用 1 个攻击牌
F[x][k-1]*C(n-x,i-k+1)*G[y][1]*C(n-y,m-i-1)
*/

int main(){
    prework();
    int T;scanf("%d",&T);
    while(T--) Solve();
    return 0;
}

B. 最大前缀和

计数题一定要分析性质！！

分析一下最大前缀和的性质，设最大前缀和的位置是 $p$：

$p$ 前缀的每一个真后缀和都 $> 0$ 否则可以替换
$p$ 后缀的每一个前缀都 $\leq 0$ 否则替换更优

不难发现这样把每一个序列在最前面的最大前缀和枚举了，所以我们考虑分开dp：

设 $f_{S}$ 表示 $S$ 内元素排列满足第一种性质的方案数，$g_S$ 表示第二种的。

考虑第二种：我们考虑每次往后加一个数，只需要判断当前状态是否还是 $\leq 0$ 就行了，设子集和为 $sm_S$，也就是 $g_S += \sum_{i \in S} g_{S-i}$。

第一种我们考虑往前加：由于是真后缀，所以要判断当前状态是否满足条件，然后向所有状态转移，$f_{S+i} += f_S(i \not \in S)$。

最后统计答案枚举断点，$\sum_{S} sm_S f_Sg_{U-S}$。

这里注意一下 $f$ 的初始值是 $f_{2^i} = 1$，因为大小为 $1$ 的串没有真后缀。。

前缀和后缀相关 dp 就要按着顺序加才是对的。。

这也告诉我们 dp 真前缀的时候应该考虑从哪里转移的那个状态是否合法而不是当前状态。。。

#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;
LL sm[(1<<MAXN)+3];
int f[(1<<MAXN)+3],g[(1<<MAXN)+3];
// f[S]: S内元素真后缀>0的方案数
// g[S]: S内元素最大前缀和<=0的方案数

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

int main(){
    scanf("%d",&n);
    FOR(i,0,n-1) scanf("%lld",&sm[1<<i]);
    FOR(S,1,(1<<n)-1) sm[S] = sm[S-lowbit(S)]+sm[lowbit(S)];
    FOR(i,0,n-1) f[1<<i] = 1;
    g[0] = 1;
    FOR(S,1,(1<<n)-1){
        if(sm[S] <= 0){
            FOR(i,0,n-1) if((S>>i)&1) add(g[S],g[S^(1<<i)]);
        }
        else{
            FOR(i,0,n-1) if(!((S>>i)&1)) add(f[S^(1<<i)],f[S]);
        }
    }
    // DEBUG(f[(1<<5)|(1<<10)]);
    int ans = 0;
    FOR(S,1,(1<<n)-1) add(ans,(1ll*sm[S]%ha*f[S]%ha*g[S^((1<<n)-1)]%ha+ha)%ha);
    printf("%d\n",ans);
    return 0;
}

C. 氪金手游

首先这个数不一定是外向树。。不过我们可以先思考一下外向树怎么做

首先一个经典的结论：给树上每个点随机一个数，每个点成为子树中最小值的概率是独立的。

#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 = 1000+5;
const int ha = 998244353;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

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

int f[MAXN][MAXN*3];
int n,p[MAXN][4];

struct Edge{
    int to,w,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void adde(int u,int v,int w){
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
}

int t[MAXN*3],sz[MAXN];

inline void merge(int x,int y,int w){
    FOR(i,1,sz[x]*3) t[i] = f[x][i],f[x][i] = 0;
    FOR(i,1,sz[x]*3){
        FOR(j,1,sz[y]*3){
            if(w) add(f[x][i+j],1ll*t[i]*f[y][j]%ha);
            else{
                add(f[x][i+j],ha-1ll*t[i]*f[y][j]%ha);
                add(f[x][i],1ll*t[i]*f[y][j]%ha);
            }
        }
    }
}

inline void dfs(int v,int fa=0){
    FOR(i,1,3) f[v][i] = 1ll*p[v][i]*i%ha;
    sz[v] = 1;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs(e[i].to,v);
        merge(v,e[i].to,e[i].w);
        sz[v] += sz[e[i].to];
    }
    FOR(i,1,sz[v]*3) f[v][i] = 1ll*f[v][i]*qpow(i)%ha;
}

int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        int sm = 0;
        FOR(j,1,3) scanf("%d",&p[i][j]),add(sm,p[i][j]);
        sm = qpow(sm);
        FOR(j,1,3) p[i][j] = 1ll*p[i][j]*sm%ha;
    }
    FOR(i,1,n-1){
        int u,v;scanf("%d%d",&u,&v);adde(u,v,1);adde(v,u,0);
    }
    dfs(1);
    int ans = 0;
    FOR(i,1,n*3) add(ans,f[1][i]);
    printf("%d\n",ans);
    return 0;
}

contest4 题解

A. Slay the Spire

B. 最大前缀和

C. 氪金手游

Leave a Comment Cancel reply

I'm back

NOI2021 退役记

SDOI2020 退役记

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

CSP2019 游记

qbxt 10 月 Day6 讲课(施工中)

「NOI2017」游戏

最小树形图 / 朱刘算法

CF1525F Goblins And Gnomes

后缀数组学习笔记

contest4 题解

A. Slay the Spire

B. 最大前缀和

C. 氪金手游