备考CSP刷题经验总结

（目标300+）

经验

1.对题目中的数据范围进行枚举、试探，找到一个大致的范围

例题：ADPC01-正赛D质数区间
在这题中1<=l<=r<=1e18，乍一看好像区间太大。但是明确思路以后，发现素数集合是按照集合元素和的大小从小到大排序的，那么可以根据素数和进行枚举，记录下字符串长度。经过试探，素数和最大到2096，那么这个范围就找到了。

scanf("%lld%lld",&a,&b);
for(int i=2;i<100000&&cur<b;i++){ //试探过，i最大到2096，这个范围的素数也就300来个，所以记忆化
ll len=calc(0,i).second;
if(cur+len>=a) print(0,i);//进入区间，开始输出
else cur+=len;
}

例题：ADPC01-正赛K关于哥俩好的数字这件事
这道题的解决思路不难想到，从1开始枚举自然数，找到符合题目要求的集合。这道题首先一个问题就是我不知道要寻找大概的数据范围，枚举到哪一个自然数？在我的潜意识里就认为题目中的数位和太大，要找的自然数太大，无法确定范围。但其实仔细思考一下，一个6位整数的数位和，最大也是6*9=54，也就是说所有<=6位的整数的数位和都在【1，54】这个范围内，那么进一步可以算出枚举的最大自然数不会超过600000。我在做题时因为认为无法找到枚举的最大自然数（我压根就想不到要找），所以就认为找到的第一个满足n要求的集合就是答案，但其实之后满足n要求的集合也有可能是答案。所以正解应该是要保存最小值，并且继续枚举到最大范围。

2.递归求解的思想

同样是例题：ADPC01-正赛D质数区间
在试探以后得出素数和最大不超过2096，那么我们就可以从2开始到2096进行枚举，按照从小到大和字典序的顺序计算字符串长度，从l开始输出，一直到r。那么关键问题在于如何按照从小到大和字典序的顺序计算字符串长度？ 题解用到这样一个思想：用 ????_i,_???? 表示用 ≥ ????_???? 的质数凑出总和 ???? 的方案数，????_????,_????为对应的长度和。 有了这么一个思想以后，就可以用for循环从2开始到素数和为10000进行枚举，计算每一个素数和为i的长度和。而素数和为i会有很多种方案，比如素数和为10，可以是[2,3,5]组合，也可以是[3,7]组合，而区别在于从第几个质数开始。所以求素数和为i的长度可以进一步分为从第j个质数开始和从第j+1个质数开始，当递归到第j+1个质数时，又会继续递归第j+2个质数。递归函数的返回条件就要考虑从当前位置的质数开始求和无法匹配i以及刚好匹配i。另外可以用一个map来保存已经求出的g_i,_j。关键在于可以把一个大问题分解成许多个同样的小问题，或者可以把一个大区间分解成许多个小区间求解

inline P get(P p1,P p2,ll len){
return P(p1.first+p2.first,p1.second+p2.second+len*p1.first);
}
P calc(int x,int sum)//从第x个素数开始求总和为sum的方案数：first和长度：second
{
P p(x,sum);
if(sum<0) return P(0,0);//无法解决
if(M.count(p)) return M[p];//找到库存
if(sum==0) return M[p]=P(1,2); //长度2表示的是1种解决方案的两个中括号
if(primes[x]>sum) return P(0,0);//无法解决
return M[p]=get(calc(x+1,sum-primes[x]),calc(x+1,sum),getL(primes[x]));//求从第>=x个素数开始总和为sum的所有情况
}

例题：csp201709-3JSON查询
这道题对于对象的处理很明显是需要递归的，但是对于字符串的，我在同一个递归函数中进行处理，这样导致代码很乱，过程也很乱。字符串处理的题目，如果题目中明显告诉你“分为几种情况”、“有几个步骤”等，应当用不同的函数实现。另外在实现函数的时候，像字符串的处理，可以传参数的地址，以便返回后保存中间结果。
我自己写的80分代码（很乱）：

#include <bits/stdc++.h>
using namespace std;
map<string,pair<int,string>> mp[100];//int:0表示字符串;int:1表示对象
void Solute(string str,int id)
{
string key="";
string value="";
for(int i=0;i<str.length();i++)
{
int index=-1;
int quatation_num=0;
for(int j=i;j<str.length();j++)
{
if(str[j]=='"'&&(j==0||str[j-1]!='\')) quatation_num++;
else if(str[j]==':'&&(quatation_num%2==0))
{
index=j;
break;
}
}
if(index==-1) break;
else
{
bool flag=false;
for(int j=i;j<index;j++)
{
if(str[j]=='"'&&(j==0||str[j-1]!='\')) flag=!flag;
else if(flag)
{
if(str[j]=='\') j++;
key+=str[j];
}
}
bool is_obj=false;
flag=false;
for(int j=index+1;j<str.length();j++)
{
if(!flag&&str[j]=='{')
{
is_obj=true;
break;
}
else if(!is_obj&&str[j]=='"'&&str[j-1]!='\')
{
break;
}
}
if(is_obj)
{
int fr,ba;
int series_deep=0;
int quatation_num=0;
for(int j=index+1;j<str.length();j++)
{
if(str[j]=='"'&&str[j-1]!='\') quatation_num++;
else if(str[j]=='{'&&(quatation_num%2==0))
{
series_deep++;
if(series_deep==1) fr=j;
}
else if(str[j]=='}'&&(quatation_num%2==0))
{
series_deep--;
if(series_deep==0)
{
ba=j;
break;
}
}
}
Solute(str.substr(fr+1,ba-fr-1),id+1);
mp[id][key]=make_pair(1,to_string(id+1));
index=ba;
}
else
{
flag=false;
for(int j=index+1;j<str.length();j++)
{
if(!flag&&str[j]=='"'&&str[j-1]!='\') flag=true;
else if(flag&&str[j]=='"'&&str[j-1]!='\')
{
index=j;
break;
}
else if(flag)
{
if(str[j]=='\') j++;
value+=str[j];
}
}
mp[id][key]=make_pair(0,value);
}
key="";
value="";
int index1=-1;
for(int j=index+1;j<str.length();j++)
{
if(str[j]==',')
{
index1=j;
break;
}
}
if(index1==-1) break;
else i=index1;
}
}
}
int main()
{
int N,M;
cin>>N>>M;
string str;
getline(cin,str);
string t="";
for(int i=0;i<N;i++)
{
getline(cin,str);
t+=str;
}
int fr,ba;
for(int i=0;i<t.length();i++)
{
if(t[i]=='{')
{
fr=i;
break;
}
}
for(int i=t.length()-1;i>=0;i--)
{
if(t[i]=='}')
{
ba=i;
break;
}
}
Solute(t.substr(fr+1,ba-fr-1),0);
for(int i=0;i<M;i++)
{
cin>>str;
t="";
queue<string> qu;
for(int j=0;j<str.length();j++)
{
if(str[j]=='.')
{
qu.push(t);
t="";
}
else t+=str[j];
}
qu.push(t);
int id;
int next_id=0;
string key;
bool flag=false;
while(!qu.empty())
{
id=next_id;
string target=qu.front();
qu.pop();
if(mp[id].find(target)==mp[id].end()||(!qu.empty()&&mp[id][target].first==0))
{
cout<<"NOTEXIST"<<endl;
flag=true;
}
else
{
if(mp[id][target].first==1)
{
next_id=atoi(mp[id][target].second.c_str());
}
key=target;
}
}
if(!flag)
{
if(mp[id][key].first==0)
{
cout<<"STRING "<<mp[id][key].second<<endl;
}
else
{
cout<<"OBJECT"<<endl;
}
}
}
return 0;
}

大佬的满分代码，结构清晰：CCF CSP 201709-3 JSON查询

3.字符串处理类的模拟题，一定要有清晰的结构，可以采用一定的存储结构先存储再处理，不要想着在主函数中边输入边处理，那样反而会让过程更加复杂。清晰的数据结构是关键。

例题：ADPC01-正赛F但更爱字符串
这道题其实没有什么难度，按照题目的意思，先把输入的每一个词（包括空格、标点符号也当作一个词）压到容器中。这样的好处就是分好词。然后再从容器中依次取出每一个词进行处理，先判断是否好词，然后判断是否有连续好词，是否需要缩写。

例题：csp202006-3Markdown渲染器
题目要求的整个处理过程很复杂，一遍遍历完成很容易想乱掉，所以可以把处理过程分成两部分：（1）预处理过程：这个过程中，把输入分成三类：普通段落、项目列表项、项目列表嵌套项，这个过程同时把相同段落/列表项的多行输入拼接起来，打上类别标记后存入vector管理。（2）渲染过程：这个过程中，遍历vector中存储的内容，因为预处理时已经把内容都划分好了，所以思路很清晰。段落和列表间隔时插入空行、段内/列表项内按终端每行容量处理换行即可。

例题：csp202009-3点亮数字人生
这道题是一个模拟+图论的题，当时看到题目很复杂，有点懵，但其实主要想好主句结构，其实基本就解决了。
每一个逻辑门器件都抽象成图论中的节点，具体代码如下：

struct node
{
int type;
//节点种类对应着不同种类的器件 
int output;
//器件的输出状态值
int input_num;
//连接该器件的输入信号数量
int input[6];
//存储连接该器件的输入信号的序号
}Node[3005];

另外这道题也是提醒了我一个小的知识点：~符号和!符号并不相同，~是按二进制位取反，而!是对整体取反。

例题：csp202012-3带配额的文件系统
关键还是数据结构，考虑到题目的意思，这道题的数据结构必然是树。

struct node {
int father; //父节点
map<string, int>child; //孩子节点
int type; //1:文件
2:目录
long long ld, lr; //目录配额、后代配额
long long size; //如果是普通文件的话，代表普通文件大小
long long ld_r, lr_r; //实际孩子文件大小总和、
//实际后代文件大小总和
}Node[4000010];

然后就是对题目中的各种情况进行处理，其中有很多操作需要对父节点进行DFS，这应该是一道很复杂的模拟题了，细节很多。

4.感觉一道很简单的题做出来了却一直WA的时候，一定要多读几遍题目，想一想有没有别的没有考虑到的情况，这种情况往往是先入为主带来的对题意的误解。另外在读题目思考场景的时候不要想当然，一定要仔细分析一下各种可能性

例题：ADPC01-正赛J奇怪的小鸭子也增加了
这道题是一个签到题，但是我误解为小鸭子摆放的位置是整数，但其实是实数，也就是说每个小鸭子占的长度可以无限接近于自身的两倍。

例题：ADPC01-正赛K关于哥俩好的数字这件事
这道题的解决思路不难想到，从1开始枚举自然数，找到符合题目要求的集合。这道题首先一个问题就是我不知道要寻找大概的数据范围，枚举到哪一个自然数？在我的潜意识里就认为题目中的数位和太大，要找的自然数太大，无法确定范围。但其实仔细思考一下，一个6位整数的数位和，最大也是6*9=54，也就是说所有<=6位的整数的数位和都在【1，54】这个范围内，那么进一步可以算出枚举的最大自然数不会超过600000。我在做题时因为认为无法找到枚举的最大自然数（我压根就想不到要找），所以就认为找到的第一个满足n要求的集合就是答案，但其实之后满足n要求的集合也有可能是答案。所以正解应该是要保存最小值，并且继续枚举到最大范围。

5.时间复杂度优化技巧

有的题就是卡时间，往往题目不难，但是优化找不到技巧的话完全束手无策。
例题：ADPC01-热身C钻石
首先这道题不是贪心，因为每个袋子只能放一个钻石。那么很显然，解法就是按照钻石的价值从大到小塞进袋子里，但是无论是对每一颗钻石寻找一个合适的袋子，还是对每一个袋子寻找一颗合适的钻石，其时间复杂度都是O(mn)。哪怕先对钻石和袋子排序，再加一些限制技巧，只要是按照这个思路，其时间复杂度也是某O(mn*某小数），在这题的数据量中，仍然会超时。而根据题目的正解，做法是先将钻石和袋子排序，然后从小到大遍历袋子，按照钻石的体积从小到大遍历钻石，把钻石体积<=当前袋子容积的钻石价格压进一个优先队列中（大根堆），然后取队列的第一个钻石放进袋子。有限队列的排序复杂度是O(logN)，而将钻石放进队列以及从队列取钻石的复杂度是O(m+n)，那么总体复杂度就是O(NlogN)，满足时间限制。 对于这种优化后的算法，确实很难想到，只能是多练习，多思考，掌握一些规律，看临场发挥了。
C++ priority_queue（优先队列）简单介绍：
摘自：c++优先队列(priority_queue)用法详解
和队列基本操作相同:
: 访问队头元素
: empty 队列是否为空
: size 返回队列内元素个数
: push 插入元素到队尾 (并排序)
: emplace 原地构造一个元素并插入队列
: pop 弹出队头元素
: swap 交换内容

定义方式：

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

例题：csp202012-2期末预测之最佳阈值
这道题我考试的时候没做出来，最后3个测试点一直超时，我已经想了一些优化办法，但只要你的时间复杂度是O(m*m)级别的，就会超时。这题的解应该是用前缀和后缀和的思想，分别统计某一点之前预测为0的数量以及某一点之后（包括该点）预测为1的数量，之后寻找两者相加最大值所对应的最大阈值即可。
首先对阈值进行排序，按照阈值从小到大进行排序，可以很容易地想到，在选择的阈值之前的预测为0的是预测正确的，在阈值之后的预测为1的是预测正确的，因此提前生成两个数组，一个数组记录该点 之前预测为0的数量，另一个数组记录该点之后（包括该点）预测为1的数量，而对于该点，两个数组相加就是以该点数值为阈值的预测正确的数量。
还有一个问题，就是如果存在多个相同的安全指数，该怎么办呢，发现：相同的安全指数，预测为1的排在前面，预测为0的排在后面，就可以得到正确的答案。因此在利用sort快速排序的时候，先按照安全指数从小到大排序，再按照预测值从1到0排序即可。

6.有限状态机的思想

常见于模拟题和字符串处理类题目，根据题意，将处理过程分成几个状态，根据不同的状态和不同的输入进行处理。
例题：csp202006-3Markdown渲染器
这题中对输入的每一行字符串进行循环处理，对于每一个读进的字符，按照不同的状态处理（段落、项目、项目列表等）。

另外在KMP模式匹配串中也用到了有限状态机的思想，KMP算法中的状态转移数组其实是给模式串的每一个元素一个状态，然后根据当前是什么状态，下一个字符是什么，跳转到下一个状态。在构建状态转移数组的时候需要用到一个影子状态，也即当前状态如果匹配失败的情况下需要回溯到影子状态。

7.基本的数学知识和从题目中思考、发现技巧的能力，对题目中的数学关系进行分析和建模的能力

例题：csp202009-4星际旅行
这道题可以将距离和拆分成每两个点之间的距离，以简化问题。因此需要判断两点之间的连线是否与中心的黑洞圆有交点，如果没有交点，则两点之间最短的距离就是两点之间连线的距离；如果有交点，则说明两点之间最短距离肯定是要包含圆的一部分的。两点之间的直线距离通过距离公式即可直接求出，而中心圆的部分则需要相关数学几何的知识即可求出。但是如果没有考虑到以上这些，而是进入更复杂的分类讨论，那么很有可能会超时。 另外这题还有一个必须要考虑的点就是圆心到两点连线的距离小于半径，但是两点可以直连的情况，实际上两点和圆心构成的是一个钝角三角形。

例题：csp201903-3损坏的RAID5
很明显，对于要求输出的每一个全局块号，我们必须找到该块号对应的磁盘和该磁盘中对应的实际块号。如果不能很好地理清思路，会非常乱。

long long Find_index(int n,int s,long long block_num)
{
//n:磁盘数;block_num:块号;s:每个条带的块数;disc_num:所在磁盘号
long long strip_num;
long long strip_order=block_num/s;//全局条带编号=全局块号/每个条带的块数
strip_num=strip_order/(n-1);//该磁盘上的条带号=全局条带号/(n-1)
return strip_num*s+(block_num%s);//返回该磁盘上要找的全局块号对应的实际块号
}

8.AC自动机

AC自动机用于多个模式串和一个匹配串，需要在匹配串中查找模式串是否出现，或者出现了几次。
详解：AC自动机-详解AC自动机以及模板
例题：csp202009-5密信与计数
这道题显然是对词典中的单词进行枚举，将明文翻译为密文，然后需要判断密文中是否包含了词典中的单词。在判断密文中是否包含了词典中的单词这一步的时候，就需要用到AC自动机了。
详解参考：CSP202009-5 密信与计数

9.动态规划

动态规划介绍：动态规划套路详解
例题：csp202009-5密信与计数
这道题的解，状态和转移方程的确定我也看了很久才明白，确实很复杂，直接看原解可能会更清楚一点：CSP202009-5 密信与计数

10.树

详细介绍见：数据结构-树
例题：T160512 G - 森林

技巧

1.数字转16进制（转义字符表示）

void trans(string &s) {	//将r,g,b转换为十六进制
string result = "";
for (int i = 0; i < s.size(); i++)
result += "\x3" + s.substr(i, 1);
s = result;
}

摘自：CSP201909-3字符画

2.求素数的方式

isprime[1]=false;//isprime[x]==true表示x是素数
fill(isprime,isprime+maxn,true);
for(int i=2;i<maxn;i++){
if(isprime[i]){
primes.push_back(i);//将素数压栈
for(int j=i+i;j<maxn;j+=i) isprime[j]=false;//排除掉素数的倍数
}
}

3.拓扑排序判断是否存在环

例题：csp202009-3点亮数字人生
在这题中，需要判断电路中是否存在环，把每一个器件作为图中的一个节点，形成一个拓扑序列。拓扑排序判断是否有环的主要思想就是：根据建成的图结构，统计每一个节点的入度，将每一个入读为0的节点删去，重新调整其余节点的入度，一直循环下去，如果最后入读全为0，则说明该图形结构中没有环的出现；如果最后有入度不为0的节点，则说明图形结构中出现了环。参考：CSP202009-3 点亮数字人生
具体的代码如下：

int CheckCircle()
{
int i;
queue<int>qu;
bool ans = false;
for (i = 0; i < n; i++)
if (d[i] == 0) qu.push(i);
while (!qu.empty())
{
int v = qu.front();
qu.pop();
for (i = 0; i < Node[m + v].input_num; i++)
{
if (Node[m + v].input[i] >= m)
{
d[Node[m + v].input[i] - m]--;
if (d[Node[m + v].input[i] - m] == 0) qu.push(Node[m + v].input[i] - m);
}
}
}
for (i = 0; i < n; i++)
if (d[i] != 0) ans = true;
return ans;
}

4.C++大段IO时提高效率

ios::sync_with_stdio(false);

在main()函数中添加这一句，可以让C++高IO效率。至于原理，是因为C++为了兼容C，所以导致cin和cout变得异常缓慢，上述语句就是禁止兼容C语言，所以输入输出就变块了。
参考：CSP201903-3损坏的RAID5

5.C++16进制字符串（string类型）转数字

string str;
long long number=strtoll(str.c_str(),NULL,16);

6.C++输出16进制数字

cout<<setiosflags(ios::uppercase)<<hex<<result<<endl;

uppercase是设置字母大写，字母默认小写。

7.需要对数组中元素进行删除时，可以采用一个下标数组来保存顺序，类似于静态链表。

例题：csp201812-3CIDR合并
在这题中，需要合并两个IP前缀，也即删除后一个IP前缀，并且还需要前向合并，所以需要一个链向后一个元素的数组和链向前一个元素的数组。

int beg=0;//beg是第一个元素下标
for(int i=0;i<N-1;i++)
{
index[i]=i+1;//index数组保存的是后向链
}
index[N-1]=-1;//

ffront[beg]=-1;//第一个元素没有前一个元素，标记为-1
int fr=beg;//从第一个元素开始遍历，建立后向链
while(index[fr]!=-1)
{
ffront[index[fr]]=fr;//fr是当前元素，fr的下一个元素的前一个元素是fr
fr=index[fr];
}

8.十进制转二进制

string Change(string a)
{
int b=atoi(a.c_str());//string转int
stack<int> s;
while(b)
{
s.push(b%2);
b/=2;
}
string t="";
while(!s.empty())
{
t+=to_string(s.top());
s.pop();
}
//补齐8位
string tt="";
for(int i=0;i<8-t.length();i++)
{
tt+="0";
}
tt+=t;
return tt;
}

9.string类用法小结

1.转换方式
char数组转为string：

char a[10]={'a','b','c'};
string b(a);

int转为string：

int a=10;
string b=to_string(a);

string转int：

string a="879";
int b=atoi(a.c_str());//a.c_str()是先将string转为char数组

string转char数组：

string a="abcd";
char b[10];
strcpy(b,a.c_str());

2.查找字符/子串

string a="abcdefg";
int index=a.find('a');
int index=a.find('a',2);
int index=a.find("abc");

find()后可跟单个字符或者string类型的串，find()将会返回匹配到的字符/串的第一个元素的下标，find()函数中跟数字i表示从下标i往后查找。

3.获取strng串的长度（字符个数）

string a="abcdefg";
int b=a.length();

4.求子串

string a="abcdefg";
string b=a.substr(0,3);

substr(i,j)表示求该串从下标i开始的j个字符组成的新串。
5.C语言字符数组赋值
string类相互赋值可以通过=进行。

char a[100]={'a','b'};
char b[10];
strcpy(b,a);
string c="abcd";
strcpy(b,c.c_str());

10.尽量用vector，少用数组+下标变量的方式，很容易出错，并且涉及两个数组赋值的时候很容易运行错误

最后

以上就是美满翅膀为你收集整理的备考CSP刷题经验总结的全部内容，希望文章能够帮你解决备考CSP刷题经验总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。