CSP-S 提高组高频题型与代码模板

📌系列推文第2篇｜真题解析专栏

前言

CSP-S提高组的题型更加综合，近3年考试高频出现的算法类型相对固定。

本文梳理4大高频题型，并附上可直接背记的代码模板。

一、动态规划——高频王者

典型题型

• 背包问题（01背包、完全背包）
• 最长上升子序列LIS
• 最长公共子序列LCS
• 区间DP、树形DP

01背包标准模板

题意：n个物品，背包容量V，每个物品有体积vi和价值wi，求最大价值。

#include<iostream> #include<algorithm> using namespace std; const int MAXN=1005;int f[MAXN]; int main(){int n,V;cin>>n>>V; for(int i=1;i<=n;i++){int v,w;cin>>v>>w; for(int j=V;j>=v;j--)f[j]=max(f[j],f[j-v]+w);} cout<

完全背包模板

for(int i=1;i<=n;i++){int v,w;cin>>v>>w; for(int j=v;j<=V;j++)f[j]=max(f[j],f[j-v]+w);}

🔑口诀：01背包倒序走，完全背包正序走。

二、贪心+排序

活动选择模板

策略：按结束时间排序，能选就选。

#include<iostream> #include<algorithm> using namespace std; struct Activity{int s,e;}a[100005]; bool cmp(Activity x,Activity y){return x.e>n; for(int i=1;i<=n;i++)cin>>a[i].s>>a[i].e; sort(a+1,a+n+1,cmp); int ans=0,last=0; for(int i=1;i<=n;i++)if(a[i].s>=last){ans++;last=a[i].e;} cout<

三、二分查找

二分答案通用模板

bool check(int mid){/*判断mid是否可行*/} int binarySearch(){   int lo=1,hi=1000000000,ans=0;   while(lo<=hi){int mid=(lo+hi)/2;     if(check(mid)){ans=mid;lo=mid+1;}else{hi=mid-1;}}   return ans; }

⚠️边界陷阱：mid溢出用lo+(hi-lo)/2。

四、DFS深度优先搜索

全排列模板

int a[15],n;bool used[15]; void dfs(int step){   if(step==n+1){for(int i=1;i<=n;i++)cout<>n;dfs(1);return 0;}

题型速查表

下一篇预告：高频考点系统梳理，一张表搞定复习计划！

作者：CSP信奥资料共享｜转载请注明出处