9.16 近期比赛总结

ooliver 发布于 21 小时前 110 次阅读 OI

AI 摘要

我的近期正睿 OI 比赛复盘：环上 DP 如何减去连成环的贡献？计数题的峰为何必长为 2？树与返祖边又怎样配对？#3642/#3643/#3646/#3647 核心思路与代码，一次看全。

26 CSP 七连测 day3 | 正睿 OI

题目 #3642 | 正睿 OI

这题用的是 DP，感觉更好想一点。。。

先考虑不是一个环，设 $dp_{i,1/0}$ 表示当前这个位置是点亮还是熄灭，$dp$ 到最后时在用概率把链连成环需要的贡献减去即可。这个贡献的计算考虑每次遇到不确定状态的位置时，我们都会新增一条分支，需要减去的贡献也会乘以 $2$，最后还需要根据头和尾的状态进行分类讨论。

代码：

C++
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e6+5;
const int mod=998244353;
int T,n;
string s;
ll dp[N][2],p2;

ll qpow(ll x,int y){
    ll res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

void solve(){
    int sum0=0;
    scanf("%d",&n);
    cin>>s;
    dp[0][0]=0,dp[0][1]=(s[0]!='0');
    sum0+=(s[0]=='0');
    ll p=1+(s[0]=='?');
    for(int i=1;i<n;i++){
        sum0+=(s[i]=='0');
        dp[i][0]=dp[i][1]=0;
        if(s[i]!='1') (dp[i][0]+=dp[i-1][0]+dp[i-1][1])%=mod;
        if(s[i]!='0'){
            (dp[i][1]+=dp[i-1][0]+dp[i-1][1])%=mod;
            if(s[i-1]=='?') (dp[i][1]+=(p*p2%mod))%=mod;
            if(s[i-1]=='0') (dp[i][1]+=p)%=mod;
        }
        if(s[i]=='?') (p*=2)%=mod;
    }
    if(s[n-1]=='?'){
        if(s[0]=='?') (dp[n-1][1]+=mod-((p*p2)%mod*p2%mod))%=mod;
        if(s[0]=='1') (dp[n-1][1]+=mod-(p*p2%mod))%=mod;
        dp[n-1][1]=(dp[n-1][1]%mod+mod)%mod;
    }
    if(s[n-1]=='1'){
        if(s[0]=='?') (dp[n-1][1]+=mod-(p*p2%mod))%=mod;
        if(s[0]=='1') (dp[n-1][1]+=mod-p)%=mod;
        dp[n-1][1]=(dp[n-1][1]%mod+mod)%mod;
    }
    printf("%d\n",(dp[n-1][0]+dp[n-1][1]+!sum0)%mod);
}

signed main(){
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    scanf("%d",&T);
    p2=qpow(2,mod-2);
    while(T--) solve();
    return 0;
}

题目 #3643 | 正睿 OI

计数题。

我们考虑最后剩下的颜色一共有 $i$ 种，我们考虑最终得到的颜色序列（将一个长度为 $2$ 的块合并成一个块）一定是一个序列，会发现一个性质，那就是这个序列（在左右两边补两个 $0$）的一个峰一定长度为 $2$，因为作为峰，它一定涂色得比相邻的两个晚，则不可能长度为 $1$。

设 $dp_{i,j}$ 表示满足有 $i$ 个数和 $j$ 个峰的排列的个数，有：

$$ dp_{i,j}=2j\cdot dp_{i,j-1}+(n-2j+2)\cdot dp_{i-1,j-1} $$

统计答案有：

$$ ans=\sum_{i=1}^{min(n-1,m)} {m-1 \choose i-1} \sum_{j=1}^{\frac{i}{2}+1}{i-j \choose n-i-j} dp_{i,j} $$

代码：

C++
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=4005;
const int mod=998244353;
int n,m,ans;
int cm[N],c[N][N],dp[N][N];

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) (res*=x)%=mod;
        (x*=x)%=mod,y>>=1;
    }
    return res;
}

void init(){
    c[0][0]=1;
    for(int i=1;i<=n;i++) for(int j=0;j<=i;j++){
        c[i][j]=c[i-1][j];
        if(j) (c[i][j]+=c[i-1][j-1])%=mod;
    }
}

signed main(){
    cin>>n>>m;
    cm[0]=1,dp[1][1]=1;
    init();
    for(int i=1;i<=min(n-1,m);i++){
        cm[i]=cm[i-1]*(m-i)%mod*qpow(i,mod-2)%mod;
        int sum=0;
        for(int j=1;j<=i/2+1;j++){
            if(i!=1) dp[i][j]=((2*j*dp[i-1][j])%mod+((i-2*j+2)*dp[i-1][j-1]%mod))%mod;
            sum=(sum+dp[i][j]*c[i-j][n-i-j]%mod)%mod;
        }
        ans=(ans+sum*cm[i-1]%mod)%mod;
    }
    cout<<ans;
    return 0;
}

26 NOIP 十连测 day2 | 正睿 OI

题目 #3646 | 正睿 OI

考虑原图是一颗树，我们按照从叶子到根节点的顺序操作，如果当前点连接它所有儿子的边的数量为偶数，那就一一配对，如果为奇数，那就把连接当前点和它父亲的点的那一条边也放进来计算即可。

如果不是一棵树，我们考虑把返祖边也放入边集即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int T,n,m;
int tag[N],vis[N];
vector<pair<int,int>> ans,g[N];

bool dfs(int u,int f,int fu){
    vector<int> e;
    for(auto[v,w]:g[u]){
        if(tag[w]||v==f) continue;
        if(vis[v]) e.push_back(w);
        else{
            vis[v]=1;
            int res=dfs(v,u,w);
            if(res) e.push_back(w);
        }
    }
    for(int i=1;i<e.size();i+=2) ans.push_back({e[i-1],e[i]}),tag[e[i-1]]=tag[e[i]]=1;
    if(e.size()&1) return ans.push_back({e.back(),fu}),tag[e.back()]=tag[fu]=1,0;
    return 1;
}

void solve(){
    cin>>n>>m;
    ans.clear();
    for(int i=1;i<=n;i++) vis[i]=0,g[i].clear();
    for(int i=1;i<=m;i++) tag[i]=0;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        g[u].push_back({v,i});
        g[v].push_back({u,i});
    }
    vis[1]=1;
    dfs(1,0,0);
    for(auto[x,y]:ans) cout<<x<<" "<<y<<"\n";
}

signed main(){
    cin>>T;
    while(T--) solve();
    return 0;
}

题目 #3647 | 正睿 OI

考虑转换一下思考方式，