题解：P11528 [THUPC 2025 初赛] 乒乓球赛

· · 题解

来一篇记忆化搜索的题解。
注：下文中加赛指的是有一个人分数超过 11 分的情况。

题目传送门

首先先判断不合法的情况。

对于总局数，如果还没打到 11 局或加赛之后总局数为奇数，则不合法。
对于比赛过程，比如得分与局数不符，分数倒退，已经获胜但比赛仍然进行，这些情况也不合法。

~这些信息有点离谱了。~

接下来，分讨两类。

n \le 20

直接记搜，为了方便，可以将最终的分数减一统计，不用判边界条件。

n > 20

参考样例提示的方法，我们先暴力记搜出两人十平的情况，接下来的对局因为必定是一分一分涨，套一个快速幂即可。

记搜时不要忘记判断不合法情况。

Code

#include <bits/stdc++.h>
using namespace std;
#define W return cout <<"0\n",void()
using ll=long long;
const int N=1e5+10,mod=998244353;
int n,T;
int a[N],b[N];
int f[20][20];
inline int ksm(int p,int q){
    int res=1;
    while(q){
        if(q&1) res=1ll*res*p%mod;
        q>>=1;p=1ll*p*p%mod;
    }
    return res;
}
inline bool J(int x,int y,int r){
    if((x==a[r]&&y==b[r])||(x==b[r]&&y==a[r])) return 0;
    return 1;
}
int dfs(int x,int y){
    if(!x&&!y) return 1;
    if(f[x][y]!=-1) return f[x][y];
    if(a[x+y]!=-1) if(J(x,y,x+y)) return f[x][y]=0;
    int res=0;
    if(x) res+=dfs(x-1,y);
    if(y) res+=dfs(x,y-1);
    return f[x][y]=res%mod;
}
inline void solve(){
    if(n<11||n>20&&(n&1)) W;
    for(int i=1,la=0,lb=0;i<n;i++){
        if(a[i]==-1) continue;
        if(max(a[i],b[i])<la||max(a[i],b[i])<lb||a[i]+b[i]!=i||(max(a[i],b[i])>=11&&abs(a[i]-b[i])>=2)) W;
        la=a[i],lb=b[i];
    }
    memset(f,-1,sizeof(f));
    if(n<=20){
        if(a[n]!=-1) if(J(11,n-11,n)) W;
        return cout <<(dfs(10,n-11)+dfs(n-11,10))%mod<<'\n',void();
    }
    else{
        if(a[n]!=-1) if(J((n>>1)+1,(n>>1)-1,n)) W;
        return cout <<1ll*dfs(10,10)*ksm(2,n-20>>1)%mod<<'\n',void();
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
        solve();
    }   
    return 0;
}