题解 | 2025浙江工商大学新生赛（上） – 逢絮聆风—

也算是本蒟蒻第一次参加线下的正式赛，结果不尽人意。但不重要了，写一篇题解复盘一下没过的题。

本题解按照题目难度梯度和校内赛时ac情况进行讲解，分上下集。上集难度总体可以接受，下集对新生略难，且大多为DP题。（其实是下集的题目我都没看过）

0x00 钝评

赛后听完讲评，其实题解上篇的题目难度都不大，更多考察的是一些基础思维。但是放到线下赛场限时独立完成，也确实给选手们上了一些压力。还是多加模拟赛场环境进行练习，至少这六道题是可以a掉的。

0x01 F：不要空格

题面：

作为大一新生的大杨，刚学习到C语言的字符串输入和输出。
一天，他的好友鹿鹿想考考他，给了他一串很长的含有空格的字符串，然后请他把里面的空格删除后再输出。由于大杨刚上手C语言，他不知道怎么删除字符串里的空格，所以请你帮帮他解决这个问题。

签到题，但是其实也不是很签到，事实上也吓了大家一下。由于C/C++的输入输出按照空格等特殊字符进行分割，单纯的cin输入字符串并不能完全读入字符串，所以我们采用getline方法。

（话说能用py切，何乐而不为？本人考试的时候还真就py切了走人）

0x02 I：魔法镜

题面：

在ACM王国的古老传说中，有一面神奇的魔法镜，只有能够念出"镜像咒语"的勇者，才能通过它的试炼，获得参加新生赛的资格。作为新生的大杨，也来到了这面魔法镜前……
魔法镜显示的咒语是一个由大写字母和小写字母组成的字符串 $s$ s。一个字符串能够通过魔法镜的试炼，当且仅当它满足镜像对称。镜像对称的规则如下：
1. 字符串被看作写在一条水平线上。
2. 字符串的图像必须关于某一条纵向垂直的对称轴对称。
镜像字符对的定义如下：
- 自身就是镜像（大写）： $A、H、I、M、O、T、U、V、W、X、Y$ A、H、I、M、O、T、U、V、W、X、Y。
- 相互镜像： $b$ b和 $d$ d、 $p$ p和 $q$ q。
- 自身就是镜像（小写）： $i、l、o、v、w、x$ i、l、o、v、w、x。

签到题，根据题目意思，最简单粗暴就是判断是不是对称字符。用左右指针从两端向中间靠拢判断字符是否满足题意即可。注意如果字符串长度为奇数，中间的字符必须自身对称。

第一个遗憾的点，第一次交的时候把一个等号替换成了感叹号，白吃了一个罚时。

以下是个人的暴力美学（虾jb写）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
bool is_pri(string a)
{
	int l=0,r=a.size()-1;
	if(a.size()%2==0) 
	{
		while(l<r)
		{
			if(a[l]==a[r])
			{
				if(a[l]=='A'||a[l]=='H'||a[l]=='I'||a[l]=='M'||a[l]=='O'||a[l]=='T'||a[l]=='U'||a[l]=='V'||a[l]=='W'||a[l]=='X'||a[l]=='Y'||a[l]=='i'||a[l]=='l'||a[l]=='o'||a[l]=='v'||a[l]=='v'||a[l]=='w'||a[l]=='x') ;
				else return false;
			}
			else {
				if((a[l]=='p'&&a[r]=='q')||(a[l]=='q'&&a[r]=='p')||(a[l]=='b'&&a[r]=='d')||(a[l]=='d'&&a[r]=='b')) ;
				else return false;
			}
			l++;
			r=a.size()-1-l;
		}
		return true;
	}
	else
	{
		while(l<r)
		{
			if(a[l]==a[r])
			{
				if(a[l]=='A'||a[l]=='H'||a[l]=='I'||a[l]=='M'||a[l]=='O'||a[l]=='T'||a[l]=='U'||a[l]=='V'||a[l]=='W'||a[l]=='X'||a[l]=='Y'||a[l]=='i'||a[l]=='l'||a[l]=='o'||a[l]=='v'||a[l]=='v'||a[l]=='w'||a[l]=='x') ;
				else return false;
			}
			else {
				if((a[l]=='p'&&a[r]=='q')||(a[l]=='q'&&a[r]=='p')||(a[l]=='b'&&a[r]=='d')||(a[l]=='d'&&a[r]=='b')) ;
				else return false;
			}
			l++;
			r=a.size()-1-l;
		}
		if(a[l]=='A'||a[l]=='H'||a[l]=='I'||a[l]=='M'||a[l]=='O'||a[l]=='T'||a[l]=='U'||a[l]=='V'||a[l]=='W'||a[l]=='X'||a[l]=='Y'||a[l]=='i'||a[l]=='l'||a[l]=='o'||a[l]=='v'||a[l]=='v'||a[l]=='w'||a[l]=='x') return true;
		else return false;
	}

}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	string s;
	cin>>s;
	if(s.size()==1)
	{
		if(s=="A"||s=="H"||s=="I"||s=="M"||s=="O"||s=="T"||s=="U"||s=="V"||s=="W"||s=="X"||s=="Y"||s=="i"||s=="l"||s=="o"||s=="v"||s=="w"||s=="x")
		{
			cout<<"YES";
			return 0;
		}
		else 
		{
			cout<<"NO";
			return 0;
		}
	}
	if(is_pri(s)) cout<<"YES";
	else cout<<"NO";
	return 0;
}

0x03 A：A.很简单的数学题

题面：

完美的你拥有好多好多个完美的数字，对于一个正整数 $X$ ，其所有的正因子为 $a_1, a_2, ..., a_k$ ，若其满足 $a_1 + a_2 + ... + a_k = 2 \cdot X$ ，则称 $X$ 为一个完美的数字。例如， $6$ 就是一个完美的数字。
对于给定的整数 $n$ ，请求第 $n$ 小的完美数字的正因子倒数之和 $\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_k}$ 。

第二个遗憾的点吧，自己没有转过弯。其实最直观的反应是这样的数字应该不多，所以果断写个小程序尝试暴力打表。不难发现10000以内只有四个数。接下来考虑，由于打表到十万运行速度已经堪忧了，所以从样例入手。尝试按照给定的样例模拟计算，不难发现：

对，既然因子之和是2X，那么通分之后分母必然为X，分子是2X，消掉为常数2，直接输出即可。看上去有着“要在草稿纸上大干一番”的架势，其实就是这么简单。

0x04 B：不再日落

题面：

大杨为了让他家乡小镇的居民复活，他十分需要鸣式宝石的能量来构建巡游天国，为了完成这个愿望，力量虚弱的他选择和漂泊者合作。但是邪恶的漂泊者并不相信他，告诉他必须要完成以下任务才能和他合作，不然邪恶的漂泊者就要使用湮灭力量捅他个透心凉。帮帮大杨吧！
构建一个长度为 $n$ 的排列 $p$ ，使得在 $1 \leq i \leq n-1$ 范围内，排列中的任意两个元素 $p_i + p_{i+1}$ 是一个合数。若无法构造则输出 $-1$ 。

排列：长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，且这些整数是从 $1$ 到 $n$ 以任意顺序排序。比如 $[2,3,1,5,4]$ 是一个排列, 但 $[1,2,2]$ 不是一个排列，因为 $2$ 在数组中出现了两次, 以及 $[1,3,4]$ 也不是一个排列，因为 $n=3$ 但是 $4$ 出现在了数组里。

合数：如果一个整数 $x$ 除了 $1$ 和它本身外还有别的因数，那么它就是一个合数。比如 $4$ 是一个合数，因为除了 $1$ 和它本身外还有 $2$ 这个因数。

考场上主要卡在了构造上，那么我们讲讲构造问题。

首先，拿到题目的第一反应必然是从较小数字开始尝试，发现在n<=4范围必然无解。

接下来开始思考怎么构造n>=5的情况。如果你对质数判断有过练习，应该很快就能想到，所有除了2之外的偶数都必然为合数，至少有一个因子为2。所以构造思路的核心就是让相邻数字之和为偶数。根据一些小学数学我们知道：奇数+奇数=偶数，偶数+偶数=偶数。所以核心就是奇偶数各自分组，最后考虑两组拼到一起。

拼起来的时候注意一下，由于偶数+奇数=奇数，我们需要对连接部分进行挑选。赛后补题想到最直观的方法就是双指针遍历奇数数组和偶数数组，对每一个组合进行质数判断，一旦发现有两个数字之和为合数就把它们移到各自数组的一头一尾，最后输出就好了（顺带一提，找到两个数字了就记得break。不然TLE）。

0x05 D：银河铁道之夜

题面：

有一天，大杨看见鹿鹿总宅在房间里，于是拉他出门种树，顺便考考了他一个问题。
大杨带了 $3$ 株初始高度均为 $0$ 的不同树苗（分别记为树苗 $1$ 、树苗 $2$ 、树苗 $3$ ），以及 $3$ 种数量不同的肥料（分别记为肥料 $1$ 、肥料 $2$ 、肥料 $3$ ，数量依次为 $a$ 、 $b$ 、 $c$ ）。
肥料有个神奇效果，它能让树苗立刻长高，且 $1$ 单位肥料恰好能让树苗长高 $1$ 1米。不过，肥料和树苗的搭配有明确限制：

肥料 $1$ 只能给树苗 $1$ 、树苗 $2$ 施肥；

肥料 $2$ 只能给树苗 $2$ 、树苗 $3$ 施肥；

肥料 $3$ 只能给树苗 $1$ 、树苗 $3$ 施肥。

为了防止一只黑猫爬上树，你需要让 $3$ 株树苗中最矮的那株，长得尽可能高。
你能算出最矮树苗能达到的最高高度吗?

很简单的一个思维题，但是考场上脑抽，想了两种办法，就是没把他们拼在一起。

对于一颗树，我们假定它是三棵树中最矮的。有两种肥料可以对它的高度做出贡献。所以我们只要看这棵树最高情况能到多高。

同时，我们考虑总肥料对生长高度的限制。三棵树高度之和最大为三种肥料数之和。我们考虑尽可能平均主义，那么三棵树的高度有：

所以，答案被束缚在上面四个值中最小的，即：

0x06 C：大杨的难题

题面：

大杨对 $01$ 字符串比较着迷。一天，鹿鹿决定给大杨出一道关于 $01$ 字符串的题目：给定一个长度为 $n$ 且只包含 $1$ 和 $0$ 的字符串 $S$ ，大杨最多可以进行 $k$ 次以下操作（可能为 $0$ 次）：
- 选择两个整数 $l,r(1 \leq l \leq r \leq n)$ ，对 $S$ （下标从 $1$ 开始）的第 $l,l+1,...,r-1,r$ 位的值取反，即 $0$ 变 $1$ 1， $1$ 变 $0$ 。
在进行最多 $k$ 次操作后，鹿鹿问大杨， $S$ 中连续 $1$ 的个数的最大值是多少？大杨没法回答这个问题，你能帮帮他吗？

由于整个串只由0和1构成，我们在串中挑选出 k+1 个 1 连续串，要使连续 1 的长度最大，本质上是通过翻转某些 0 段，将多个 1 段连接起来。一次操作可以翻转一个连续的 0 段（也可以翻转包含 1 的区间，但最优策略通常只翻转 0 段）。因此，最多翻转 k 个 0 段，从而最多连接 k+1 个 1 段。问题转化为：在字符串中选取一段连续的区域，包含不超过 k 个 0 段，并考虑该区域左右紧邻的 1 段（因为翻转后这些 1 段也会被连接进来），使得总长度最大。接下来，用滑动窗口维护整个字符串S，通过对窗口内的 1 和 0 个数进行统计，用max维护答案。