# 非官方题解 |『RetOI』#2题解

CuSn

2026-02-21 20:07:30

发布于：浙江

8阅读

0回复

0点赞

前言：

虽然我没AK哈，but我还是很努力的写代码了哈，喷轻点。

哈哈，废话不多说，直接开干。

正文：

T1:签到题

这道题个人评分：红，签到题题目不多讲，直接写：

namespace CuSn{
    void solve(){
        string s;
        cin>>s;
        vector<int> res(1,1);
        for(char c:s){
            int num=c,carry=0;
            for(int i=0;i<res.size()||carry;i++){
                if(i==res.size())res.push_back(0);
                long long tmp=1ll*res[i]*num+carry;
                res[i]=tmp%10;
                carry=tmp/10;
            }
        }
        reverse(res.begin(),res.end());
        for(int i:res)cout<<i;
        cout<<'\n';
    }
}

T2:闰年：

这题纯粹水体，普通的一遍过。

namespace CuSn{
    typedef long long ll;
    void solve(){
        ll l,r;
        cin>>l>>r;
        l--;
        ll ans=r/4-l/4;
        ans-=r/100-l/100;
        ans+=r/400-l/400;
        cout<<ans;
    }
}

T3:玉米树

可恶，赛事由于我太着急只能将就写一个组合偏分代码骗了20分，QAQ

Code:

namespace CuSn{
    int T,n,v[105],f[105][105];
    string s;
    bool isL(char c){
        return c=='P'||c=='i'||c=='p'||c=='l'||c=='o'||c=='n'||c=='g';
    }
    void solve(){
        cin>>T;
        while(T--){
            cin>>s;
            n=s.size();
            for(int i=0;i<n;i++)
                v[i+1]=isL(s[i]);
            s=" "+s;
            memset(f,0,sizeof f);
            for(int i=0;i<=n;i++)
                f[i+1][i]=0;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n-i+1;j++){
                    int k=j+i-1;
                    if(i==1){
                        f[j][k]=1;
                        continue;
                    }
                    if(s[j]==s[k])
                        f[j][k]=1-f[j+1][k-1];
                    else if(v[j]&&!v[k])
                        f[j][k]=1-f[j+1][k];
                    else if(!v[j]&&v[k])
                        f[j][k]=1-f[j][k-1];
                    else if(!v[j]&&!v[k])
                        f[j][k]=max(1-f[j+1][k],1-f[j][k-1]);
                    else 
                        f[j][k]=max(1-f[j+2][k],1-f[j][k-2]);
                }
            }
            if(f[1][n])
                cout<<"lz will win.\n";
            else 
                cout<<"pzh will win.\n";
        }
    }
}

T4:踩方格

有入说我写题解不讲题？

呃，刑。

思路解析

这是一个经典的网格路径覆盖问题。

网格大小为 $n \times m$ ，起点为 $(x, y)$ ，每次可以上下左右移动，要求不重复地走遍所有格子。
结论：
- 如果 $n$ 或 $m$ 是偶数，一定可以遍历所有格子 ✅
- 如果 $n$ $n$ 和 $m$ $m$ 都是奇数，那么能否遍历取决于起点的颜色（棋盘染色）：
  - 将格子按 $(i+j) \% 2$ 染色，起点为黑色
  - 黑色格子总数比白色多 $1$
  - 只有起点是黑色才能遍历所有格子（即 $x + y$ 为偶数）
- 特殊情况：只有一行或一列时，起点必须在端点才能遍历

代码实现

namespace CuSn{
    long long T,n,m,x,y;
    void solve(){
        cin>>T;
        while(T--){
            cin>>n>>m>>x>>y;
            if(n==1||m==1){
                if(n==1&&y!=m&&y!=1||m==1&&x!=n&&x!=1)
                    cout<<"No\n";
                else     
                    cout<<"Yes\n";
            }
            else if(n%2==0||m%2==0)
                cout<<"Yes\n";
            else if((x+y)%2==0)
                cout<<"Yes\n";
            else 
                cout<<"No\n";
        }
    }
}

T5：路径

思路解析

给定 $n \times m$ 网格，从 $(1,1)$ 到 $(n,m)$ 只能向右或向下，求所有路径中经过的格子 $(i,j)$ 满足 $i+j$ 为质数的总次数。

每条路径长度为 $n+m-2$ 步，经过 $n+m-1$ 个格子。
对于每个格子 $(i,j)$ ，经过它的路径数为 $\binom{i+j-2}{i-1} \times \binom{n+m-i-j}{n-i}$ 。
若 $i+j$ 为质数，则累加该路径数到答案。
质数最大为 $n+m \le 2\times 10^6$ ，可以预处理。

代码实现

namespace CuSn{
    const int N=2e6+5;
    const int mod=1e9+7;
    int n,m;
    bool np[N];
    long long fac[N],inv[N],ans;
    long long qpow(long long a,long long b){
        long long r=1;
        while(b){
            if(b&1)r=r*a%mod;
            a=a*a%mod;
            b>>=1;
        }
        return r;
    }
    void init(){
        fac[0]=1;
        for(int i=1;i<=n+m;i++)fac[i]=fac[i-1]*i%mod;
        inv[n+m]=qpow(fac[n+m],mod-2);
        for(int i=n+m-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
        for(int i=2;i<=n+m;i++){
            if(!np[i]){
                for(int j=i+i;j<=n+m;j+=i)np[j]=1;
            }
        }
    }
    long long C(int a,int b){
        if(a<b||b<0)return 0;
        return fac[a]*inv[b]%mod*inv[a-b]%mod;
    }
    void solve(){
        cin>>n>>m;
        init();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!np[i+j]){
                    ans=(ans+C(i+j-2,i-1)*C(n+m-i-j,n-i))%mod;
                }
            }
        }
        cout<<ans<<'\n';
    }
}