2025~2026赛季 正赛部分题解
chenzefan
·
·
科技·工程
:::::success[\text{CSP-J 2025}]
温馨提醒：由于 T1 和 T2 过于简单，暂不提供部分分解法。
::::info[T1]
把字符串 $S$ 内属于 `0`$\sim$`9` 的字符加入大根堆（或其他 $\text{STL}$ 容器），自动降序后输出。瓶颈在 $\text{STL}$ 容器内部排序处。
$O(n)$ 做法：
直接开一个大小为 $10$ 的数组 $a$，$a_i$ 表示字符串 $S$ 中字符 `i+'0'` 出现的次数。故可以不排序，枚举 $i=9\sim0$ 输出 $a_i$ 个对应数字即可。
:::info[T1 [$\text{AC}$](https://www.luogu.com.cn/record/244739740) 代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
priority_queue <char> q;
signed main(){
cin>>s;
for(int i=0;i<s.size();i++)
if(s[i]>='0'&&s[i]<='9') q.push(s[i]);
while(!q.empty()) cout<<q.top(),q.pop();
return 0;
}
```
:::
::::
::::info[[T2](https://www.luogu.com.cn/problem/P14358)]
#### 线性找排名：找出 $a_1$ 的排名。
$O((nm)\log(nm))$ 做法：
对序列 $a$ 排序，由于有 $1\le n,m \le 10$，则 $1\le nm \le 100$ 轻松通过。
$O(nm)$ 做法：
输入时直接判断 $a_i$ 是否大于 $a_1$，满足条件则计数，即表示为 $a_1$ 后移一位。
#### 蛇形找位：得出答案。
$O(nm)$ 做法：
由于 $1\le nm \le 100$，直接模拟即可通过，即枚举次数同时朝对应方向移动，到达边界则判断。
$O(1)$ 做法：
推式子。我们发现每 $2n$ 个会形成周期，则可以将排名对 $2n$ 取模进行判断。
注意输出的是“第几列第几行”。
:::info[T2 [$\text{AC}$](https://www.luogu.com.cn/record/244739765) 代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,a[N],cnt;
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n*m;i++){
scanf("%d",a+i);
if(a[i]>a[1]) cnt++;
}
int x=1,y=1,d=1;
while(cnt--){
x+=d;
if(x>n) x=n,y++,d=-1;
if(x<1) x=1,y++,d=1;
}printf("%d %d",y,x);
return 0;
}
```
:::
::::
::::info[[T3](https://www.luogu.com.cn/problem/P14359)]
不提供特殊性质做法。
$O(n^3)$ 做法：
直接 $\text{dp}$，定义 $dp_i$ 表示前 $i$ 个所能分割出的最多区间。则不难有 $dp_i=\displaystyle\max_{j=1}^i[\displaystyle\bigoplus_{l=j}^i a_l=k]\times(dp_{j-1}+1)$。其中 $[]$ 内判断若满足则为 $1$，否则为 $0$。则枚举 $i$ 为 $O(n)$，枚举 $j$ 为 $O(n)$，枚举 $l$ 为 $O(n)$，总时间复杂度为 $O(n^3)$。
期望得分：$40$ 分。
$O(n^2)$ 做法：
优化算法一的时间复杂度。注意到异或和有如下性质：
$$
a \oplus a =0
$$
即相同两数异或为 $0$。则可以对 $l$ 的循环优化为 $O(1)$。预处理出前缀异或和 $xor_i=xor_{i-1} \oplus a_i$。则有 $\displaystyle\bigoplus_{i=l}^r a_i=xor_r \oplus xor_{l-1}$。
所以之间复杂度优化成了 $O(n^2)$。
期望得分：$60$ 分。
$O(n) /O(n \log n)$ 做法：
考虑贪心。要使分割序列越长，每段肯定越短越好。则我们要对每个 $r$ 找到最近的 $l$ 使得 $xor_r \oplus xor_{l-1}=k$。
记变量 $last$ 表示区间 $[1,last]$ 已经不能再分割了。
若上式满足 $l>last$，则显然可以分割，贪心的考虑移动： $last=r$。即 $r$ 以及之前的都不能再使用了。
考虑如何 $O(1)$ 求 $l$。显然对于 $xor_r \oplus xor_{l-1}=k$ 可以移项 $xor_r \oplus k=xor_{l-1}$。由于左式可以 $O(1)$ 算，只要知道满足条件的 $xor_{l-1}$ 在此之前是否存在过就可以了。用 $\text{map}$ 记录是 $O(n \log n)$ 的，而改用数组则为 $O(n)$。
期望得分：$100$ 分。
:::info[T3 [$\text{AC}$](https://www.luogu.com.cn/record/244824991) 代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int M=3e6+5;
int n,k,a[N],sum_xor[N],ans,last,id[M];
signed main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",a+i),sum_xor[i]=sum_xor[i-1]^a[i];
memset(id,-0x3f,sizeof(id));id[0]=0;
for(int r=1;r<=n;r++){
int x=sum_xor[r]^k;
if(id[x]>=last) ans++,last=r;
id[sum_xor[r]]=r;
}
printf("%d",ans);
return 0;
}
```
:::
::::
::::info[[T4](https://www.luogu.com.cn/problem/P14360)]
$O(2^n)$ 做法：
枚举木棒子序列，同时维护和 $\operatorname{sum}$ 以及最大值 $\max$，再用 $O(1)$ 判断能否成功即可。直接暴力 $\text{dfs}$。
期望得分：$40$ 分。
当 $\displaystyle\max_{i=1}^n a_i \le 1$ 时：
通过上述暴力程序可以得出下表（满足 $\forall i \in [1,n] a_i=1$）：
| $n$ | $ans$ |
|:-:|:-:|
| $3$ | $1$ |
| $4$ | $5$ |
| $5$ | $16$ |
| $6$ | $42$ |
| $7$ | $99$ |
| $\cdots$ | $\cdots$ |
有如下结论：$ans=\displaystyle\sum_{i=3}^n \text{C}_n^i$。
有根据公式 $\text{C}_n^m=\frac{n!}{m!(n-m)!}$。
所以预处理出 $i!(i \in [1,n])$，然后费马小定理求逆元即可。
时间复杂度为 $O(n \log n)$，求线性逆元可以做到 $O(n)$。
期望得分：$24$ 分。
$O(n^2)$ 做法：
我们发现题目要求的是子序列而非字串。所以 $a_i$ 之间顺序无影响。考虑对 $a$ 升序排序。
所以因为 $\forall i\in[1,n) a_i<a_{i+1}$，则有 $\forall i\in[1,m) l_i<l_{i+1}$，这样就可以将题目给的式子 $\displaystyle\sum_{i=1}^m l_i>2 \times \displaystyle\max_{i=1}^m l_i$ 转化成了 $\displaystyle\sum_{i=1}^{m-1} l_i>l_m$。
枚举 $a_k=\displaystyle\max_{i=1}^k a_i(k\in [3,n])$，我们可以将题目的限制转化为：
> 从 $a$ 的 $[1,k−1]$ 中选木棍，使其长度和 $>a_k$ 的方案数。
联想到了 $\text{dp}$。设计状态 $dp_{i,j}$ 表示考虑前 $i$ 个木棍，长度和 $>j$ 的方案数。
然后发现这样搞很难。于是换一下：
> 设计状态 $dp_{i,j}$ 表示考虑前 $i$ 个木棍，长度和 $=j$ 的方案数。
然后容斥原理搞一搞就完事了。
状态转移：$dp_{i,j}=
\begin{cases}
dp_{i-1,j} &j<a_i\\
dp_{i-1,j}+dp_{i-1,j-a_i} &j \ge a_i
\end{cases}
然后容易得多了。初始化：dp_{i,0}=1(i \in [1,n])。
最后用总方案数减去算出来不满足条件的方案数即可。
期望得分：100 分。
:::info[T4 \text{AC} 代码]
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5005;
const int mod=998244353;
int n,a[N],dp[N],sum[N],ans;
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod,b>>=1;
}return ans;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",a+i);
sort(a+1,a+n+1);
dp[0]=dp[a[1]]=1;
for(int i=2;i<=n;i++){
for(int j=N-5;j>=a[i];j--) dp[j]=(dp[j]+dp[j-a[i]])%mod;
for(int j=0;j<=a[i+1];j++) sum[i]=(sum[i]+dp[j])%mod;
}
for(int i=3;i<=n;i++) ans=(ans+(qpow(2,i-1)-sum[i-1]+mod)%mod)%mod;
printf("%lld",ans);
return 0;
}
:::
::::
:::::
:::::success[\text{CSP-S 2025}]
温馨提醒：由于 T3 和 T4 过于困难，暂不提供解法。
::::info[T1]
并没有想到部分分做法。
首先看到题目就是一眼**贪心**。观察第 $3$ 个样例，思路很明显了，我们需要先把每个人好感度最大值相加，找到最优方案（不应顶满足条件），然后我们开始**反悔**。
本题要求每个社团人数不超过 $\frac{n}{2}$，又因为 $n$ 为偶数。所以不满足条件的社团只有一个。所以单一考虑即可。
分类讨论此时哪个社团人数超过了 $\frac{n}{2}$，我们要考虑将其中一部分人**转移**到另一个社团去。又因为我们想要好感度和最大，那么转移的差就要最小，不妨用 $\text{STL}$ 容器排序即可。
期望得分：$100$ 分。
:::info[T1 [$\text{AC}$](https://www.luogu.com.cn/record/249044047) 代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,cnt1,cnt2,cnt3,ans,id[N];
struct node{int x,y,z;}a[N];
vector <int> vec;
signed main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);ans=cnt1=cnt2=cnt3=0;
int m=n/2;vec.clear();
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
int maxx=max({a[i].x,a[i].y,a[i].z});ans+=maxx;
if(maxx==a[i].x) cnt1++,id[i]=1;
else if(maxx==a[i].y) cnt2++,id[i]=2;
else cnt3++,id[i]=3;
}
if(cnt1<=m&&cnt2<=m&&cnt3<=m){printf("%d\n",ans);continue;}
for(int i=1;i<=n;i++){
if(cnt1>m&&id[i]==1) vec.push_back(a[i].x-max(a[i].y,a[i].z));
if(cnt2>m&&id[i]==2) vec.push_back(a[i].y-max(a[i].x,a[i].z));
if(cnt3>m&&id[i]==3) vec.push_back(a[i].z-max(a[i].x,a[i].y));
}sort(vec.begin(),vec.end());
int i=0,cnt=max({cnt1,cnt2,cnt3});
while(cnt>m) ans-=vec[i++],cnt--;
printf("%d\n",ans);
}
return 0;
}
```
:::
::::
::::info[[T2](https://www.luogu.com.cn/problem/P14362)]
$O(2^k(kn^2+(kn^2+m)\log(kn^2+m)))$ 做法：
对于 $2^k$ 种乡村选择全部枚举一边，对于每个乡村与原城市的边权进行建边，即设加入了乡村 $i$，则建 $(j,k,a_{i,j}+a_{i,k})$ 共 $n^2$ 条边。再跑最小生成树 $\text{kruskal}$ 算法即可。
期望得分：$16$ 分（即 $k=0$ 的数据）。
$O(2^k(kn+(kn+m)\log(kn+m)))$ 做法：
在上一个算法中加入乡村虚点，则建边就是 $kn$ 的，同样跑 $\text{kruskal}$。
期望得分：$32$ 分。
$O(2^k(kn+(kn)\log(kn))+m\log m)$ 做法：
我们发现原城市的 $m$ 条边每次都参与了排序，很耗时间，考虑只做一次。则提前预处理排序，做 $\text{kruskal}$ 在新边和旧边中找边权小的即可。
期望得分：$80$ 分。
$O(2^k(kn+m)+(kn+m)\log(kn+m))$ 做法：
因为所有边一开始已经确定，不妨将所有边一并存下来排好序，同时新增一个 $id$ 变量，表示是从哪个乡村来拿出来的边。这样在跑 $\text{kruskal}$ 时看看这条边对应的乡村有没有选即可。
期望得分: $100$ 分。
拓展：$O(2^k(kn+n)+(kn+n)\log(kn+n)+m\log m)$ 做法：
由于 $1\le m \le 10^6$，赛场上不确定上个做法会不会错。因为一开始的 $m$ 条边中只有 $n-1$ 条边有用，即原图最小生成树上的边，则我们可以将前 $m$ 条边线做 $\text{kruskal}$ 变成 $n-1$ 条边，即从 $10^6$ 级瞬间变成了 $10^4$ 级。即可优化原算法。
期望得分：$100$ 分。
时间对比。[$13.02 \text s$](https://www.luogu.com.cn/record/249048123) 和 [$8.27 \text s$](https://www.luogu.com.cn/record/249048972)。
:::info[T2 [$\text{AC}$](https://www.luogu.com.cn/record/249048972) 代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e4+5;
const int M=1e6+5;
const int K=15;
int n,m,k,fa[N+K],c[K],a[K][N],cnt,ans,ans1=LLONG_MAX;
struct node{int u,v,w,id;}e1[M],e[M+N*K];
bool cmp(node x,node y){return x.w<y.w;}
bool vis[K];
int find(int x){
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
void unionn(int x,int y,int w){
x=find(x),y=find(y);
if(x!=y) fa[y]=x,cnt++,ans+=w;
}
void kruskal(int t){
cnt=0;
for(int i=1;i<=n+k;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w,id=e[i].id;
if(!vis[id]&&id) continue;
unionn(u,v,w);
if(cnt==n+t-1) break;
}
}
void work(){
int tot=0;
for(int i=1;i<=k;i++) tot+=(vis[i]!=0);
kruskal(tot);ans1=min(ans1,ans);
}
void dfs(int i,int sum){
if(i==k+1){
ans=sum;work();
return ;
}
vis[i]=1;dfs(i+1,sum+c[i]);
vis[i]=0;dfs(i+1,sum);
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1,u,v,w;i<=m;i++) scanf("%lld%lld%lld",&u,&v,&w),e1[i]={u,v,w,0};
for(int i=1;i<=n;i++) fa[i]=i;sort(e1+1,e1+m+1,cmp);
for(int i=1;i<=m;i++){
int u=e1[i].u,v=e1[i].v,w=e1[i].w,last=cnt;
unionn(u,v,w);
if(last==cnt-1) e[cnt]={u,v,w,0};
if(cnt==n-1) break;
}m=n-1;
for(int i=1;i<=k;i++){
scanf("%lld",c+i);
for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]),e[++m]={n+i,j,a[i][j],i};
}
sort(e+1,e+m+1,cmp);
if(k==0) return printf("%lld",ans),0;
dfs(1,0);printf("%lld",ans1);
return 0;
}
```
:::
::::
:::::
:::::success[$\text{NOIP 2025}$]
**温馨提醒：暂时只有 T1 做法。**
::::info[[T1](https://www.luogu.com.cn/problem/P14635)]
~~感觉部分分就是**背包**，但由于过于简单，我们直接说正解。~~
$O(n \log n + n \log m)$ 做法：
我们发现题目购买的方案似乎和奇偶性有关。考虑分类讨论：
对于当前第 $i$ 种糖果：
- 若购买奇数个：价格为 $k \times (x_i+y_i)+x_i$。$k$ 为非负整数，易得，此时购买了第 $i$ 种糖果 $2k+1$ 个。
- 若购买偶数个（包括**不买**）：价格为 $k \times (x_i+y_i)$。$k$ 为非负整数，易得，此时购买了第 $i$ 种糖果 $2k$ 个。
则我们知道，对于每种糖果 $i$，$x_i+y_i$ 可以无限的买，而 $x_i$ 只能买最多一个（因为再多就归到前面一类去了）。
我们令 $X_i=x_i+y_i,Y_i=x_i$。表示两种购买方式。
易得贪心策略，若要买 $k$ 组 $X$ 类型，则一定买 $k$ 组 $(x_i+y_i)_{\min}$。若要买 $Y$ 类型，则选择 $x_i$ 最小且未被选择的。
所以贡献仅有 $(x_i+y_i)_{\min}$ 和 $x_i$ 产生。
故考虑将 $X_i$ 和 $Y_i$ 排序。那么答案为若干组 $X_1$ 和 $Y$ 的任意前缀和构成。
则定义 $sum_i$ 表示 $Y$ 的前缀和。
因为此时花钱越多买的越多，则不妨对购买总数二分答案，对于当前的 $mid$，计算可能的 $k$。
$k$ 是有范围限制的，因为此时购买 $k$ 组 $X$ 和 $mid-2k$ 个 $Y$ 的最小钱数：
$$
now=kX_1+sum_{mid-2k}
$$
显然 $0 \le mid-2k \le n$，可以解得 $\frac{mid-n}{2}\le k\le \frac{mid}{2}$。注意我们枚举得时候，左边界要向上取整，因为再往下一点我们是取不到的。右边界无碍。中途计算会爆 long long，注意开 __int128。这样即可做到 $O(n \log n + n \log m)$。
期望得分：$100$ 分。
$O(n \log n)$ 做法：
尝试不用二分，我们发现切入口可以不是 $X$ 而是 $Y$，排完序后枚举 $Y$ 得购买数量，然后去尽可能地买 $X$，计算最大能买数量，这样排序后时间复杂度从 $O(n \log m)$ 降到了 $O(n)$。总复杂度瓶颈在排序地 $O(n \log n)$。
期望得分：$100$ 分。
:::info[T1 [$\text{AC}$](https://www.luogu.com.cn/record/251540918) 代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,x[N],y[N],sum[N],ans;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld%lld",x+i,y+i),y[i]+=x[i];
sort(x+1,x+n+1);sort(y+1,y+n+1);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i];
for(int i=0;i<=n;i++){
if(m<sum[i]) break;
ans=max(ans,i+(m-sum[i])/y[1]*2);
}
printf("%lld",ans);
return 0;
}
```
:::
::::
:::::
:::::success[$\text{WC 2026}$]
温馨提示：由于太难了，暂时没有解法。
:::::
:::::success[联合省选 $2026$]
温馨提示：由于太难了，暂时没有解法。
:::::
:::::success[$\text{APIO 2026}$]
温馨提示：由于太难了，暂时没有解法。
:::::