9.16 近期比赛总结

ooliver 发布于 23 天前 1000 次阅读 OI

AI 摘要

本期正睿四题：环形DP概率、计数峰、树边配对、交互猜数。最惊艳是60位猜数——DP预处理最优策略，两类边界一步收尾，最坏仅4步！思路与代码全奉上，快来一读。

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

不难发现，对于当前处理的二元组 $(a_i,b_i)$，$S$ 中这一段区间必须是空的。虑转换一下思考方式，对于一段空区间 $[l,r]$，我们计算期望新增的二元对数量，设 $C(l,r)$ 表示被区间完全包围的二元对数量，有：

$$ \mathbb{E} = 1 + \frac{1}{|C(l, r)|} \sum_{i \in C(l, r)} \Big( E(l, a_i - 1) + E(a_i + 1, r) \Big) $$

按照遍历顺序优化一下即可。

代码：

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

#define int long long
const int N=6005,mod=998244353;
int n,m;
int inv[N],dp[N][N],lr[N],la[N],rl[N],ra[N],cnt[N],h[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    m=2*n;
    inv[1]=1;
    for(int i=2;i<=m;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        int l=min(u,v),r=max(u,v);
        lr[l]=r,la[l]=u,rl[r]=l,ra[r]=u;
    }
    for(int l=m;l>=1;l--){
        int id=lr[l];
        if(id){
            int ai=la[l];
            for(int r=id;r<=m;r++){
                cnt[r]++;
                int t=(ai+1<=r?dp[ai+1][r]:0);
                h[r]=(h[r]+t)%mod;
            }
        }
        int sum=0;
        for(int r=l;r<=m;r++){
            if(rl[r]>=l){
                int ai=ra[r];
                int t=(l<=ai-1?dp[l][ai-1]:0);
                sum=(sum+t)%mod;
            }
            if(!cnt[r]) dp[l][r]=0;
            else dp[l][r]=(1+(sum+h[r])%mod*inv[cnt[r]])%mod;
        }
    }
    cout<<dp[1][m]<<"\n";
    return 0;
}

题目 #3648 | 正睿 OI

神了。

不难发现 $10^{18} < 2^{60}$，考虑将待猜的数 $x$ 看作一个 $60$ 位的二进制数。在交互过程中，我们维护当前已知 $x$ 的最低 $l$ 位和最高 $r$ 位，中间未知位数为 $len = 60 - l - r$，所有已知位统一保存在 $ans$ 中。

考虑 DP 预处理最优策略。设 $f[l][r]$ 表示最坏情况下猜出答案的最少询问次数，$g[l][r]$ 记录最优决策。枚举分界点 $k \in (l, 60 - r)$ 询问 $2^k$：若返回商则确定最高 $60 - k$ 位，转移到 $(l, 60 - k)$；若返回余数则确定最低 $k$ 位，转移到 $(k, r)$。有转移 $f[l][r] = \min_k { \max(f[k][r], f[l][60 - k]) + 1 }$。

考虑两种可以在 $1$ 步内直接收尾的边界情况。第一种是 $len = 1$，此时只剩第 $l$ 位未知，答案仅可能为 $ans$ 或 $ans + 2^l$。直接询问 $ans + 2^l$，若返回余数为 $0$ 或商为 $1$ 说明为 $ans + 2^l$，否则为 $ans$。

第二种是 $len < l$。设中间未知的数值为 $M$，显然有 $M < 2^{len} \le 2^{l-1} < 2^l - 1$。考虑询问 $val = 2^l - 1$：注意到 $2^l \equiv 1 \pmod{val}$，若返回余数 $y$，有 $y \equiv ans + M \pmod{val}$，因 $M < val$ 可唯一还原出 $M = (y - ans \bmod val + val) \bmod val$；若返回商 $y$，由除法等式 $x = y \cdot val + R$ 模 $2^l$ 展开，余数可直接由 $R = (ans - y \cdot val) \bmod 2^l$ 算出，进而还原出 $x = y \cdot val + R$。无论何种返回均可 $1$ 步得出结果。

因此在 init() 中按长度 $len$ 从小到大预处理，满足上述边界时置 $f[l][r] = 1$，其余情况枚举 $k$ 转移，最坏只需 $4$ 步；在 solve() 中若命中两类边界则一步收尾，否则查表询问 $2^k$ 迭代状态即可。

代码：

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

int f[110][110],g[110][110];

int init(){
    memset(f,0x3f,sizeof f);
    for(int len=1;len<=60;len++) for(int l=0;l+len<=60;l++){
        int r=60-len-l;
        if(len==1||l>len){
            f[l][r]=1;
            continue;
        }
        for(int k=l+1;k<60-r;k++){
            int v=max(f[k][r],f[l][60-k])+1;
            if(v<f[l][r]) f[l][r]=v,g[l][r]=k;
        }
    }
    return 1e18;
}

int solve(){
    int l=0,r=0;
    int ans=0;
    while(1){
        int len=60-l-r;
        if(len==1){
            auto [op,y]=query(ans+(1ll<<l));
            if(op=='%') return y==0?ans+(1ll<<l):ans;
            return y==1?ans+(1ll<<l):ans;
        }
        if(len<l){
            int val=(1ll<<l)-1;
            auto [op,y]=query(val);
            if(op=='%') return ans+=(y-ans%val+val)%val<<l;
            else return y*val+((ans&val)-y*val%(1ll<<l)+(1ll<<l))%(1ll<<l);
        }
        int k=g[l][r];
        auto [op,y]=query(1ll<<k);
        if(op=='/'){
            ans|=(y<<k);
            r=60-k;
        }
        else{
            ans|=y;
            l=k;
        }
    }
}