CSP-J 模板复习
2026-08-28 17:57:26
发布于：浙江
5阅读
0回复
0点赞
T1 前缀和
题目大意
给定一个长度为 n 的数组，有 m 次询问。
每次询问：
l r
求区间：
a[l] + a[l+1] + ... + a[r]
如果每次都遍历区间，最坏复杂度是 O(nm)。
可以提前预处理前缀和。
核心思路
定义：
s[i]
表示：
前
i个数的总和。
所以：
s[r] = a1+a2+...+a[l-1]+a[l]+...+a[r]
s[l-1] = a1+a2+...+a[l-1]
相减：
a[l]+...+a[r] = s[r]-s[l-1]
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,x;
long long s[100002];//s[i]表示前i个元素的总和
int l,r;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x;
s[i]=s[i-1]+x;
}
while(m--){
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
// s[r] = a1+a2+...+a[l-1]+a[l]+...+a[r]
// s[l-1] = a1+a2+...+a[l-1]
}
return 0;
}
复杂度：
预处理 O(n)
每次询问 O(1)
总复杂度 O(n+m)
T2 异或前缀和
题目大意
给一个数组，多次询问区间：
[l,r]
所有元素的异或值。
核心思路
普通前缀和使用减法：
s[r]-s[l-1]
异或有一个重要性质：
x ^ x = 0
x ^ 0 = x
定义：
s[i]=a[1]^a[2]^...^a[i];
那么：
s[r]^s[l-1]
前面的数字出现两次，会全部抵消。
所以：
区间异或 = s[r]^s[l-1]
代码
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m;
int a[N],s[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]^a[i];
}
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
cout<<(s[r]^s[l-1])<<endl;
}
return 0;
}
复杂度：
O(n+m)
T3 奖学金
题目大意
每个学生有：
语文成绩
数学成绩
英语成绩
排序规则：
- 总分高的在前；
- 总分相同，语文高的在前；
- 语文也相同，编号小的在前。
最后输出前 5 名。
核心思路
这是典型的：
结构体 + 自定义排序。
把每个学生的信息放进结构体。
比较函数直接按照题目要求写。
代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int chi,math,eng;
int sum,id;
}a[310];
bool cmp(node a,node b){
if(a.sum!=b.sum)return a.sum>b.sum;
if(a.chi!=b.chi)return a.chi>b.chi;
return a.id<b.id;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].chi>>a[i].math>>a[i].eng;
a[i].sum=a[i].chi+a[i].math+a[i].eng;
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=5;i++){
cout<<a[i].id<<" "<<a[i].sum<<endl;
}
return 0;
}
复杂度：
O(nlogn)
T4 第一个大于 x 的数
题目大意
给定一个升序数组。
找到：
第一个严格大于
x的元素位置。
也就是找最小的 i：
a[i] > x
核心思路
二分答案。
如果：
a[mid]>x
说明 mid 有可能是答案，但是左边可能还有更早的位置：
ans=mid;
r=mid-1;
否则：
l=mid+1;
代码
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,x;
int a[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>x;
int l=1,r=n;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]>x){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
复杂度：
O(logn)
T5 第一个大于等于 x 的数
与上一题只有一个区别。
这一题找：
a[i] >= x
代码
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,x;
int a[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>x;
int l=1,r=n;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]>=x){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
两道二分一定要区分
T4：a[mid] > x
T5：a[mid] >= x
T6 撤硕管理员
这题是典型的：
DFS 选或不选。
题目要求从 n 个同学中选择任意一些，使选择的费用总和是质数，求方案数量。([ACGO][1])
核心思路
枚举到第 id 个同学，有两种选择：
不选
选
所以：
dfs(id****um);
dfs(id****um+a[id]);
到最后判断：
sum是不是质数
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a[25];
int ans=0;
bool prime(int x){
if(x<=1)return false;
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
void dfs(int id,int sum){
if(id==n+1){
if(prime(sum))
ans++;
return;
}
// 不选第id个人
dfs(id****um);
// 选择第id个人
dfs(id****um+a[id]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
dfs(1,0);
cout<<ans;
return 0;
}
复杂度：
O(2^n × sqrt(sum))
核心模板：
DFS枚举每个元素：
选
不选
T7 全排列问题
题目大意
输出：
1~n
的所有全排列。
要求每个数字占 5 个字符宽度。([ACGO][2])
核心思路
定义：
a[x]
表示排列第 x 个位置放什么。
vis[i]：
1：数字i已经使用
0：还没有使用
每一层 DFS 枚举：
当前位置放1
当前位置放2
...
当前位置放n
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int a[15];
bool vis[15];
void dfs(int x){
if(x==n+1){
for(int i=1;i<=n;i++){
cout<<setw(5)<<a[i];
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(vis[i]==0){
vis[i]=1;
a[x]=i;
dfs(x+1);
vis[i]=0;//回溯
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
核心口诀：
枚举
标记
递归
撤销标记
复杂度：
O(n × n!)
T10 [CSP-J 2025] 多边形
题目条件是：
若选择的最大木棍为 mx，总长度为 sum，则必须满足：
sum > 2 × mx
题目保证 n<=5000，a[i]<=5000。([ACGO][4])
核心思路
先排序：
a[1] <= a[2] <= ... <= a[n]
假设：
a[i]
是当前方案中的最大边。
那么条件：
前面选中的木棍和 + a[i] > 2*a[i]
移项：
前面选中的木棍和 > a[i]
所以问题变成：
从前
i-1根木棍中选择若干根，统计子集和大于a[i]的方案数。
定义：
dp[j]
表示：
当前已经处理过的木棍中，选出的木棍长度和为
j的方案数。
因为最大 a[i] 只有 5000，所以所有：
>5000
的和统一存到：
dp[5001]
即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int n;
int a[5005];
long long dp[5005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
dp[0]=1;
long long ans=0;
for(int i=1;i<=n;i++){
// a[i]作为最大边
if(i>=3){
for(int j=a[i]+1;j<=5001;j++){
ans+=dp[j];
ans%=MOD;
}
}
// 加入a[i]
dp[5001]=dp[5001]*2%MOD;
for(int j=5000;j>=0;j--){
int to=min(5001,j+a[i]);
dp[to]+=dp[j];
dp[to]%=MOD;
}
}
cout<<ans;
return 0;
}
复杂度：
O(n × 5000)
T11 [CSP-J 2022] 上升点列
这题核心是：
LIS + 二维 DP。
将所有点按照：
x从小到大
x相同按照y从小到大
排序。
对于两个点：
(x1,y1)
(x2,y2)
如果：
x1<=x2
y1<=y2
就可以连接。
两个点的曼哈顿距离：
d=(x2-x1)+(y2-y1)
中间需要添加：
d-1
个点。([ACGO][5])
状态
dp[i][j]
表示：
以第
i个原有点作为结尾，已经使用了j个新增点时，最长点列长度。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=505;
struct node{
int x,y;
}a[N];
int n,k;
int dp[N][105];
bool cmp(node a,node b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
// 前面没有选其它原有点
dp[i][j]=j+1;
for(int h=1;h<i;h++){
if(a[h].x<=a[i].x&&a[h].y<=a[i].y){
int d=a[i].x-a[h].x+a[i].y-a[h].y;
// 中间要添加d-1个点
if(j>=d-1){
dp[i][j]=max(
dp[i][j],
dp[h][j-(d-1)]+d
);
}
}
}
// 剩余的点全部接在最后
ans=max(ans,dp[i][j]+k-j);
}
}
cout<<ans;
return 0;
}
复杂度：
O(n²k)
T12 [CSP-J 2019] 纪念品
这题是非常经典的：
每两天之间做一次完全背包。
每天可以买同一种纪念品无限次，因此属于完全背包。([ACGO][6])
核心思路
考虑第 i 天买，第 i+1 天卖。
第 j 个纪念品：
成本 = p[i][j]
收益：
p[i+1][j]-p[i][j]
当前拥有 m 枚金币：
背包容量 = m
于是做一次完全背包，求最大利润。
然后：
m += 最大利润
继续处理下一天。
代码
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int p[105][105];
int dp[10005];
int main(){
cin>>t>>n>>m;
for(int i=1;i<=t;i++){
for(int j=1;j<=n;j++){
cin>>p[i][j];
}
}
for(int i=1;i<t;i++){
memset(dp,0,sizeof dp);
for(int j=1;j<=n;j++){
int w=p[i][j];
int v=p[i+1][j]-p[i][j];
// 完全背包：容量正序
for(int k=w;k<=m;k++){
dp[k]=max(dp[k],dp[k-w]+v);
}
}
m+=dp[m];
}
cout<<m;
return 0;
}
复杂度：
O(T × N × M)
最关键：
01背包：容量倒序
完全背包：容量正序
T13 [CSP-J 2020] 方格取数
这题的移动规则决定了：
只能不断向右进入下一列，但是在同一列中可以向上或向下移动。
所以不能只写普通：
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
因为同一列可能：
从上往下走
也可能：
从下往上走
因此每一列需要做两遍 DP。该题是 CSP-J 2020 T4。([ACGO][7])
状态
f[i][j]
表示：
到达
(i,j)时能获得的最大价值。
对于每一列分别：
从上往下扫一次
从下往上扫一次
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const long long INF=-1e18;
int n,m;
long long a[N][N];
long long f[N];
long long up[N];
long long down[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
// 第一列只能从(1,1)一直往下
f[1]=a[1][1];
for(int i=2;i<=n;i++){
f[i]=f[i-1]+a[i][1];
}
// 从第2列开始
for(int j=2;j<=m;j++){
// 从上往下
up[1]=f[1]+a[1][j];
for(int i=2;i<=n;i++){
up[i]=max(
f[i],
up[i-1]
)+a[i][j];
}
// 从下往上
down[n]=f[n]+a[n][j];
for(int i=n-1;i>=1;i--){
down[i]=max(
f[i],
down[i+1]
)+a[i][j];
}
// 合并
for(int i=1;i<=n;i++){
f[i]=max(up[i],down[i]);
}
}
cout<<f[n];
return 0;
}
复杂度：
O(nm)
这里空空如也
有帮助，赞一个