9.16 近期比赛总结

2026年9月16日 ooliver OI

26 CSP 七连测 day3 | 正睿 OI

题目 #3642 | 正睿 OI

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

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

代码：

C++

#include
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

`#include
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;in;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$ 。

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

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

统计答案有：

$a n s = \sum_{i = 1}^{m i n (n - 1, m)} m - 1 [PARSE ERROR: Undefined("Command(\"choose\")")] i - 1 \sum_{j = 1}^{\frac{i}{2} + 1} i - j [PARSE ERROR: Undefined("Command(\"choose\")")] n - i - j d p_{i, j}$

代码：

C++

#include
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>>m;
    cm[0]=1,dp[1][1]=1;
    init();
    for(int i=1;i

`#include
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;in;i++) for(int j=0;ji;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;imin(n-1,m);i++){
        cm[i]=cm[i-1]*(m-i)%mod*qpow(i,mod-2)%mod;
        int sum=0;
        for(int j=1;ji/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;
    }
    coutans;
    return 0;
}`

26 NOIP 十连测 day2 | 正睿 OI

题目 #3646 | 正睿 OI

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

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

代码：

C++

#include
using namespace std;

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

bool dfs(int u,int f,int fu){
    vector 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>n>>m;
    ans.clear();
    for(int i=1;i>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>T;
    while(T--) solve();
    return 0;
}

`#include
using namespace std;

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

bool dfs(int u,int f,int fu){
    vectorint> 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;ie.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;in;i++) vis[i]=0,g[i].clear();
    for(int i=1;im;i++) tag[i]=0;
    for(int i=1,u,v;im;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) coutx" "y"\n";
}

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

题目 #3647 | 正睿 OI

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

$E = 1 + \frac{1}{| C (l, r) |} \sum_{i \in C (l, r)} [PARSE ERROR: Undefined("Command(\"Big\")")] (E (l, a_{i} - 1) + E (a_{i} + 1, r) [PARSE ERROR: Undefined("Command(\"Big\")")])$

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

代码：

C++

#include
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>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=l){
                int ai=ra[r];
                int t=(l

`#include
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;im;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;in;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;rm;r++){
                cnt[r]++;
                int t=(ai+1r?dp[ai+1][r]:0);
                h[r]=(h[r]+t)%mod;
            }
        }
        int sum=0;
        for(int r=l;rm;r++){
            if(rl[r]>=l){
                int ai=ra[r];
                int t=(lai-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;
        }
    }
    coutdp[1][m]"\n";
    return 0;
}`

题目 #3648 | 正睿 OI

神了。

不难发现 $10^{18} 考虑 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$ 步内直接收尾的边界情况。第一种是 $l e n = 1$ ，此时只剩第 $l$ 位未知，答案仅可能为 $a n s$ 或 $a n s + 2^{l}$ 。直接询问 $a n s + 2^{l}$ ，若返回余数为 $0$ 或商为 $1$ 说明为 $a n s + 2^{l}$ ，否则为 $a n s$ 。

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

代码：

C++

#include"guess.h"
#include
#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;lenlen){
            f[l][r]=1;
            continue;
        }
        for(int k=l+1;k

`#include"guess.h"
#include
#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;len60;len++) for(int l=0;l+len60;l++){
        int r=60-len-l;
        if(len==1||l>len){
            f[l][r]=1;
            continue;
        }
        for(int k=l+1;k60-r;k++){
            int v=max(f[k][r],f[l][60-k])+1;
            if(vf[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+(1lll));
            if(op=='%') return y==0?ans+(1lll):ans;
            return y==1?ans+(1lll):ans;
        }
        if(lenl){
            int val=(1lll)-1;
            auto [op,y]=query(val);
            if(op=='%') return ans+=(y-ans%val+val)%vall;
            else return y*val+((ans&val)-y*val%(1lll)+(1lll))%(1lll);
        }
        int k=g[l][r];
        auto [op,y]=query(1llk);
        if(op=='/'){
            ans|=(yk);
            r=60-k;
        }
        else{
            ans|=y;
            l=k;
        }
    }
}`