『RetOI』Round 2 官方题解

Zhang

2026-02-24 12:22:47

发布于：浙江

13阅读

0回复

0点赞

『RetOI』Round 2 全题解

T1 签到题 Sign

题目大意

给定一个长不超过 $10^3$ 的字符串，求这个字符串每一位的 ASCII 码值的乘积。

题目分析

根据题意，对于 $100 \%$ 的数据而言， $|s| \le 10^3$ ，显然用 int128 也只能得到 $50$ 分，所以这时候就需要使用高精度乘法，先定义三个数组 $a,b,c$ ，初始时将 $a$ 设为 $1$ ，接下来枚举字符串每一位上的字符，将其的 ASCII 码加入数组 $b$ ，用高精度将结果记录在 $c$ 中，最后将 $c$ 中的值复制回 $a$ ，以此类推，最终输出 $a$ 数组中的数。
对于高精度乘法这里不在过多讲解，可自行参考 P1601。

Code

#include <bits/stdc++.h>
using namespace std;
string s;
int a[100001],b[100001],c[200001],n;//定义变量 
int main() {
	cin>>s;
	a[0]=1;a[1]=1;//初始化a 
	for(int i=0; i<s.length(); i++) {
		int ascii=(int)s[i];//用ascii记录每个字符的ascii码 
		b[0]=0;//初始化b 
		memset(c,0,sizeof c);//多次不清空，亲人两行泪 
		while(ascii) {
			b[++b[0]]=ascii%10;
			ascii/=10;
		}//将ascii值加入b中 
		for(int i=1; i<=a[0]; i++) {
			for(int j=1; j<=b[0]; j++) {
				c[i+j-1]+=a[i]*b[j];
				c[i+j]+=c[i+j-1]/10;
				c[i+j-1]%=10;
			}
		}//高精度乘法核心，详见P1601 
		c[0]=a[0]+b[0]-1;
		if(c[c[0]+1]>0)c[0]++;
		if(i==s.length()-1)
			for(int i=c[0]; i>=1; i--)
				cout<<c[i];//输出答案 
		for(int i=0; i<=c[0]; i++)a[i]=c[i];//将每次的答案重新放回a中 
	}
	return 0;
}

T2 闰年 Leap

题目分析

已知闰年的定义有以下几点：

能被 $4$ 整除，而不能被 $100$ 整除。
能直接被 $400$ 整除。

这样问题就可以转换成：在 $[l,r]$ 这个区间内有多少个正整数满足能被 $4$ 整除而不能被 $100$ 整除或者能直接被 $400$ 整除。

已知 $[1,n]$ 内有 $\lfloor\frac{n}{4} \rfloor$ 个数可以被 $4$ 整除。同理， $[1,n]$ 内有 $\lfloor\frac{n}{100} \rfloor$ 个数可以被 $100$ 整除； $[1,n]$ 内有 $\lfloor\frac{n}{400} \rfloor$ 个数可以被 $400$ 整除。我们可以使用容斥原理，在 $\lfloor\frac{n}{4}\rfloor$ 中减去能被 $100$ 整除的数的数量 $\lfloor\frac{n}{100}\rfloor$ ，再加上之前被错减掉的能被 $400$
整除的数的个数 $\lfloor\frac{n}{400}\rfloor$ ，这样我们可以得出在 $[1,n]$ 之间的闰年个数为 $\lfloor\frac{n}{4}\rfloor-\lfloor\frac{n}{100}\rfloor+\lfloor\frac{n}{400}\rfloor$ 。

但是题目中要求求出 $[l,r]$ 内闰年的数量。我们可以设 $f(n)=\lfloor\frac{n}{4}\rfloor-\lfloor\frac{n}{100}\rfloor+\lfloor\frac{n}{400}\rfloor$ ，则 $[l,r]$ 区间内闰年数量就是 $[1,r]$ 内闰年数量减去 $[1,l-1]$ 内闰年的数量，即 $f(r)-f(l-1)$ 。

Code

#include<bits/stdc++.h>
#define int long long
int l,r;
using namespace std;
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>l>>r;
	cout<<(r/4-(l-1)/4)-(r/100-(l-1)/100)+(r/400-(l-1)/400);//将题目中所描述的 f(r)-f(l-1) 展开后就是该公式
	return 0;
}

T3 玉米树 TreeC

题目大意

给定一个字符串，两个入依次进行博弈（删字符），谁先删完谁赢。

题目分析

本场比赛的定位就是很多水题，然后又考虑到博弈论这个知识点本来就很冷门，于是决定放一个很板的题普及一下，顺便安利一下我同学的博客 Link。

如果您认真看了上述文章，那么这道题想必非常简单。
让我们先回顾一下博弈论的基本概念，对于当前的局势，所有通过一次操作可以变成的新的局势，我们称这几种状态为当前状态的后继，同样的，当前状态为这几种状态的先驱。
如果存在一个状态的后继满足先手必败，那么当前状态为先手必胜，否则为先手必败。这个也很好理解，如果我可以通过一个操作让对手接下来“必败”，那么我一定是“必胜”的，如果我不可以，也就是每个操作都会让对手接下来“必胜”，那么我就一定是“必败”的。

细心的读者已经发现，这个和 DP 的状态转移非常相似，如果能想到这里，那么 DP 的状态也呼之欲出了。我们不妨设 $f_{l,r}$ 表示在 $[l,r]$ 的区间内的状态， $0$ 表示先手必败， $1$ 表示先手必胜。

那么接下来我们只需要完善一个简单的区间 DP 即可，具体细节请见代码（建议先从主函数开始理解，最后看 updata 函数）。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 101;
const string ans[] = {"pzh will win.\n", "lz will win.\n"};//个人习惯
unordered_map<char, bool> islucky;
int T;
bool f[maxn][maxn];
string s;
void init() {
	islucky['P'] = 1, islucky['p'] = 1;
	islucky['i'] = 1, islucky['l'] = 1;
	islucky['o'] = 1, islucky['n'] = 1;
	islucky['g'] = 1;
}//预处理幸运字符
bool updata(int l, int r) {
	if (s[l] == s[r]) return !(l + 1 <= r - 1 ? f[l + 1][r - 1] : 0);//如果两个字符一样直接全部删掉，取反是因为当后继为必胜态，则当前状态是必败态，所以要取反
	if (!islucky[s[l]] && !islucky[s[r]]) {
		bool p1 = !(l + 1 <= r ? f[l + 1][r] : 0),
		     p2 = !(l <= r - 1 ? f[l][r - 1] : 0);//同上
		return p1 || p2;//如果两个后继中有一个是必败态，则当前状态就是必胜态
	}//都不为幸运字符
	if (islucky[s[l]] && islucky[s[r]]) {
		bool p1 = !(l + 2 <= r ? f[l + 2][r] : 0),
		     p2 = !(l <= r - 2 ? f[l][r - 2] : 0);
		return p1 || p2;//同上
	}//都为幸运字符
	if (islucky[s[l]]) return !(l + 1 <= r ? f[l + 1][r] : 0);//如果s[l]是幸运字符
	return !(l <= r - 1 ? f[l][r - 1] : 0);//s[r]是幸运字符
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	init();//处理幸运字符
	cin >> T;
	while (T--) {//多测
		cin >> s;
		int n = s.size();
		for (int len = 1; len <= n; len++) {
			for (int l = 0; l + len - 1 < n; l++) {
				int r = l + len - 1;//区间 DP 板子，先枚举区间长度
				if (len == 1) {
					f[l][r] = 1;//如果只有一个字符显然直接删掉即可，故为先手必胜态
					continue;
				}
				f[l][r] = updata(l, r);//更新
			}
		}
		cout << ans[f[0][n - 1]];//输出答案
	}
	return 0;
}

T4 踩方格 Grid

题目大意

能否在一个 $N \times M$ 的方格图上，从 $(x,y)$ 点开始不重复的遍历全图。

题目分析

~~这显然是一道找规律的题目。~~
对于每一个方格图，我们可以对他进行染色，这里举一个例子：

1
3 3 2 1

上述的样例可以用下图表示：

可见 zc 从 $(2,1)$ 出发，应遍历 $k$ 个蓝色格子和 $k + 1$ 个灰色格子，而图中除去出发点还有 $3$ 个蓝格和 $5$ 个灰格，显然不符合要求。
综上，观察可得，当且仅当 $N,M,x+y$ 都为奇数时，不能满足要求。
注意，当 $N$ 或 $M$ 为 $1$ 时，应当单独讨论。

Code

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        // 处理特殊情况
        if (n == 1 && m == 1) {
            cout << "Yes\n";
            continue;
        }
        if (n == 1) {
            // 只有一行，起点必须是端点
            if (y == 1 || y == m) cout << "Yes\n";
            else cout << "No\n";
            continue;
        }
        if (m == 1) {
            // 只有一列，起点必须是端点
            if (x == 1 || x == n) cout << "Yes\n";
            else cout << "No\n";
            continue;
        }
        // 处理正常情况
        if (n % 2 == 1 && m % 2 == 1 && (x + y) % 2 == 1) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
        }
    }
    return 0;
}

T5 路径 Road

题目大意

给定方格图，求从左上角走到右下角所有路径所经过的格子横纵和为质数的数量。

题目分析

方案一：DFS

经典的暴力算法，简单粗暴，复杂度 $O(C(n+m−2,n−1)×(n+m))$ 。

方案二：遍历

我们要求解从 $(1,1)$ 到 $(n,m)$ 的所有路径中，经过的"质数格子"( $i+j$ 为质数)的总次数。
数学表达为：

$\sum_{所有路径} \sum_{(i,j)在路径中且i+j为质数} 1$

可转化为：

$\sum_{所有满足i+j为质数的(i,j)} 经过(i,j)的路径数$

此时用 $dp$ 预处理一遍每个点到 $(1,1)$ 和 $(n,m)$ 的路径数，再遍历全图，复杂度 $O(n \times m)$ ，可得 $60$ 分。
对于每个点，经过此点的路径数另外一种方法如下：
对于任意格子 $(i,j)$ ，从 $(1,1)$ 到 $(i,j)$ 的路径数为：

$P_{1}(i,j) = C(i+j-2, i-1)$

从 $(i,j)$ 到 $(n,m)$ 的路径数为：

$P_{2}(i,j) = C(n-i+m-j, n-i)$

因此，经过 $(i,j)$ 的总路径数为：

$P(i,j) = P_{1}(i,j) \times P_{2}(i,j) = C(i+j-2, i-1) \times C(n-i+m-j, n-i)$

此方法需要预处理一遍阶乘取模，时间复杂度 $O(n \times m)$ 。

方案三：数学

令 $p = i + j$ ，其中 $p$ 为质数。对于固定的质数 $p$ ，其对答案的贡献：

$\sum_{质数p} \sum_{i=max(1,p-m)}^{min(n,p-1)} C(p-2, i-1) \times C(n+m-p, n-i)$

令 $k = i - 1$ 。
$k$ 的范围：从 $max(0, p-m-1)$ 到 $min(n-1, p-2)$ 。
上式变为：

$\sum_{k} C(p-2, k) \times C(n+m-p, n-1-k)$

上述式子中， $1 \le i \le n$ ， $1 \le j \le m$ 。
根据范德蒙德卷积恒等式：

$\sum_{k} C(a, k) \times C(b, c-k) = C(a+b, c)$

在我们的情况下， $a = p - 2$ ， $b = n + m - p$ ， $c = n - 1$ 。
式子转化为：

$C(n+m-2, n-1)$

对于每个质数p，我们有：

$\sum_{i} C(p-2, i-1) \times C(n+m-p, n-i) = C(n+m-2, n-1)$

这意味着：对于每个质数 $p$ ，所有满足 $i + j = p$ 的格子被经过的总路径数恰好等于总路径数。
因此答案等于：

$\sum_{质数p} C(n+m-2, n-1)$

转化为：

$质数p的个数 \times C(n+m-2, n-1)$

其中， $2 \le p \le n+m$ 。
因此可以先预处理一遍阶乘取模并计算 $C(n+m-2,n-1)$ ，再用欧拉筛质数计算出 $[2,n + m]$ 间质数的个数，最后将两者相乘取模即可。
时间复杂度 $O(n + m)$ 。

说明：本题解中部分数学推导由 deepseek 辅助完成。

Code

#include<bits/stdc++.h>
#define int long long
#define N 2001000
#define P 1000000007
using namespace std;
vector<int> primes;
bool isprime[N];
int fa[N], ifa[N];
void ls(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isprime[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > n) break;
            isprime[i * p] = true;
            if (i % p == 0) break;
        }
    }
}
int ppow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
void icb(int n) {
    fa[0] = 1;
    for (int i = 1; i <= n; i++) {
        fa[i] = fa[i - 1] * i % P;
    }
    ifa[n] = ppow(fa[n], P - 2);
    for (int i = n - 1; i >= 0; i--) {
        ifa[i] = ifa[i + 1] * (i + 1) % P;
    }
}
int cb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fa[n] * ifa[k] % P * ifa[n - k] % P;
}
signed main() {
    int n, m;
    cin >> n >> m;
    int ns = n + m;
    ls(ns);
    icb(ns);
    int tot = cb(n + m - 2, n - 1);
    int cnt = 0;
    for (int p : primes) {
        if (p >= 2 && p <= n + m) {
            cnt++;
        }
    }
    int ans = tot * cnt % P;
    cout << ans << endl;
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 3

Zzzzzzsr（不处）
对于 T4，“当 $N,M=0$ 应单独讨论”。显然这里应该是 $=1$ 。有锅快改

5天前来自广东
0
- Zhang
  回复
  Zzzzzzsr（不处）
  okok改了
  
  5天前来自浙江
  0
- 不会C++的noah
  回复
  Zhang
  其实T5有个比较简单的解释方法
  
  5天前来自泰国
  0
Zzzzzzsr（不处）
qp

5天前来自广东
0
Zhang
@Grapher

5天前来自浙江
0