CCF-CSP考试的时候总是会犯一些错误，并且自己思路太单调想不到好方法，这里简单总结一下相关的方法和技巧。

1、201912-2回收站选址

（1）自己最开始的思路就是单纯的模拟，后来发现有负数，不了了之。

（2）一个技巧是建立结构体数组，这样坐标就可以为负数。另外遍历的时候不是遍历所有的地址，而实只遍历含有垃圾的地方，这样会大大降低时间复杂度。

（3）有一些其他的技巧用到了STL中的Map和set。

2、201909-2小明种苹果

这道题用数组就可以模拟，难点在于如何统计相邻连续三棵树发生苹果掉落的组数。

（1）这道题应该是考试的时候第二题拿分最高的一道了，拿了50分，课后做了90分，当时不知道分是怎么丢的，现在想来是在E的理解上与题目有偏差。认为只有三棵树时，连续三棵树有苹果掉落的组数最大应该为1，其它2种情况应该是重复的。而题目意思实际上应该是3。

（2）高超的模拟是设立flag数组，这样发生掉落的苹果树数和连续三组发生掉落的苹果树数都好计算。同时苹果总数本身就好计算，不多说。

3、201903-2二十四点

（1）这道题考试的时候真的是没思路，只能强硬模拟。最后竟然也拿了分。【后续发现其实就是简化版的中缀表达式求值】

（2）用队列或栈的特性实现四则运算。

顺序遍历表达式，如果遇到的是数字，压入数字栈，如果遇到的是符号，压入符号栈。由于x、/的优先级较高，所以当遇到乘法和除法时，直接计算结果，并把结果压入数字栈。还由于，减法的结合性是从左向右的，所以我们做一个简单地转换，将所有的减法变为加法。最后数字栈中的数就是结果了。【都是加法就可以从右往左算了，真的精妙】”

<code>

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

int n;

char str[10];

stack<int> num;

stack<char> sign;

int main(){

scanf("%d",&n);

getchar(); //读取留在缓冲区的换行符

for(int i=0;i<n;i++){

gets(str);

while(!num.empty()) num.pop(); //清空栈

while(!sign.empty()) sign.pop();

int j=0;

while(j<strlen(str)){

if(str[j]>'0' && str[j]<='9'){

num.push(str[j]-'0');

}

else{

if(str[j]=='+'){

sign.push('+');

}

else if(str[j]=='-'){ //将减法转换成加法

num.push((str[j+1]-'0')*(-1));

sign.push('+');

j++;

}

else if(str[j]=='x'){ //直接计算乘法

int lhs=num.top();

num.pop();

num.push(lhs*(str[j+1]-'0'));

j++;

}

else if(str[j]=='/'){ //直接计算除法

int lhs=num.top();

num.pop();

num.push(lhs/(str[j+1]-'0'));

j++;

}

}

j++;

}

while(!sign.empty()){ //计算剩余的加法

int rhs=num.top();

num.pop();

int lhs=num.top();

num.pop();

sign.pop();

num.push(lhs+rhs);

}

int ans=num.top();

if(ans==24) printf("Yes\n");

else printf("No\n");

}

return 0;

}

</code>

此外，本道题还可以构造表达式树。

4、201812-2小明放学

（1）这道题自己的思路只有10分，也是强硬模拟，不过至今不知道是那里出问题，只能强硬参考别人的思路了。

（2）一些人利用取余运算和数组运算实现循环变换，这些自己当时没有想到，毕竟靠的有些生硬。

5、201809-2买菜

（1）这道题自己也是分类讨论，但是分不高。

（2）有些人利用给每个时间段建立数组，每当该时间段有人时就加一，最后计算有2个人的时间段有哪些，这种方法真的精妙。

（3）有些人不利用分类讨论，利用数学公式遍历所有时间段min(a,b) -max(c,d)。

6、201803-2碰撞的小球

（1）自己最开始模拟的时候没想清楚序号和位置的关系，思路很混乱，不知道应该怎么实现。

（2）有些人不考虑序号问题（因为最终小球的顺序一定是按放入的顺序排的），直接用pos[i]记录每个小球的位置，step[i]记录每个小球运动的方向。遇到墙改变方向。每次移动完之后判断小球直接有没有发生碰撞，改变方向的情况。

（3）有些人利用结构体数组存储每个小球的序号，位置和移动方向。模拟的时候比较简单，按位置排序后，移动每一个小球。最后输出的时候按序排好序号输出每一个小球。

7、201712-2 游戏 

（1）做的时候只拿了40分，利用循环来模拟。

（2）一些人利用队列模拟，很精妙。“起始时将所有人的编号压入队列，设置一个代表当前报的数字的变量，每次从队列弹出一个编号作为当前报数的人，查看其报的数字是否应该被淘汰，如果没有被淘汰将这个人编号重新压入队列中。当队列中只剩余一个人的编号时，这个人即为胜利者，输出即可。”

<code>

#include<bits/stdc++.h>

using namespace std;

int main(){

    int N,K;

    scanf("%d%d",&N,&K);

    queue<int>q;

    for(int i=1;i<=N;++i)//将所有人编号压入队列 

        q.push(i);

    int num=1;//当前的报数 

    while(q.size()>1){

        int t=q.front();//获取当前报数的人的编号 

        q.pop();

        if(!(num%K==0||num%10==K))//如果既不是K的倍数，末位也不为K 

            q.push(t);//将这个人编号加入队列中 ，表示没有被淘汰 

        ++num;//递增当前报数

    }

    printf("%d",q.front());//输出最后获胜的人的编号 

} 

</code>

8、201709-2 公共钥匙盒

（1）做的时候暴力模拟40分。

（2）定义一个Key类，包含钥匙编号、当前时间、是还钥匙还是取钥匙。为了使用优先级队列，还需重载<运算符，注意，优先级队列默认队首元素为最大的元素，所以在定义<运算符时要与题目要求的情况相反，才能保证满足题目要求的元素位于队首。之后的操作就是在读取数据时将相应的Key类对象压入队列，之后一一弹出，并对记录挂钩上钥匙编号的数组进行相关操作就可以了。

<code>

#include<bits/stdc++.h>

using namespace std;

struct Key{//定义Key类

int num;//钥匙编号

int time;//当前时间

bool borrow;//表示是取钥匙还是还钥匙 ，true表示取，false表示还

Key(int n,int t,bool b):num(n),time(t),borrow(b){}//构造函数

bool operator<(const Key&k)const{//重载<运算符 ，注意优先级队列默认以最大元素为队首元素

if(this->time!=k.time)//以时间最早的位于队首

return this->time>k.time;

else if(this->borrow!=k.borrow)//先还钥匙再取钥匙

return this->borrow&&!k.borrow;

else//以钥匙编号最小的位于队首

return this->num>k.num;

}

};

priority_queue<Key>pq;//优先级队列

int main(){

int N,K;

scanf("%d%d",&N,&K);

int a[N+1];//表示当前挂钩上钥匙顺序的数组

for(int i=0;i<N+1;++i)

a[i]=i;

for(int i=0;i<K;++i){//读取数据

int a,b,c;

scanf("%d%d%d",&a,&b,&c);

pq.push(Key(a,b,true));

pq.push(Key(a,b+c,false));

}

while(!pq.empty()){//队列不空，继续循环

Key k=pq.top();

pq.pop();

if(k.borrow){//如果是取钥匙

int i=1;

while(a[i]!=k.num)//查找取的钥匙编号在数组中的位置

++i;

a[i]=-1;//令该位置处钥匙编号为-1，表示该挂钩没有挂钥匙

}else{//如果是还钥匙

int i=1;

while(a[i]!=-1)//查找数组中第一个没挂钥匙的挂钩

++i;

a[i]=k.num;//令该位置处钥匙编号为还的钥匙编号

}

}

for(int i=1;i<N+1;++i)//输出

printf("%d ",a[i]);

}

</code>

9、20170302-学生排队

（1）暴力模拟

（2）在移动过程中，不可避免地要涉及到元素在中间位置的插入和删除，所以用stl中的list容器是最好的。可利用暴力搜索的方法遍历整个链表找到要移动的元素的位置，并将该元素删除；利用迭代器的递增递减运算找到要移动之后的位置，将该元素插入。注意，list的迭代器不支持+、- 运算符，但支持++、-- 运算符。

<code>

#include<bits/stdc++.h>

using namespace std;

int main(){

int N,M;

scanf("%d%d",&N,&M);

list<int>l;//存储学号的链表

for(int i=0;i<N;++i)//将所有学号加入链表中

l.push_back(i+1);

while(M--){

int a,b;

scanf("%d%d",&a,&b);//读取移动的学号，和移动的长度

list<int>::iterator i=l.begin();

while(*i!=a)//遍历链表查找要移动的学号在链表中的位置

++i;

i=l.erase(i);//删除该元素

while(b<0){//找到移动后的位置

--i;

++b;

}

while(b>0){

++i;

--b;

}

l.insert(i,a);//插入该元素

}

for(list<int>::iterator i=l.begin();i!=l.end();++i)//遍历输出

printf("%d ",*i);

return 0;

}

</code>