1.申请数组
如果数组大小较大（大概10^6）则需要定义在main函数外，否则会使程序异常退出（因为函数内部申请的局部变量来自系统栈，即允许申请的空间较小；而函数外部申请的全局变量来自【静态存储区】，即允许申请的空间较大）。
2.scanf的%c和%s
scanf的%c格式时可以读入空格和换行\n的；%d的输入则是以空白符（即空格、换行等）作为结束判断标志。
字符数组使用%s格式读入时的结束标志：空格、换行符。
#include <stdio.h> int main(){ int a; char c,str[10]; scanf("%d%c%s",&a,&c,str); printf("a=%d,c=%c,str=%s",a,c,str); system("pause"); }
输入的结果是：1 a bcd
输出的结果是：a=1,c= ,str=a
int型变量a遇到空格时停止读入（a不包含空格）；而char型字符变量c（注意不是字符串变量）实际是一个空格——%c可以读入空格；str字符串变量为a（a后面即空格——结束）。
3.double
double型变量的输出格式为%d，而scanf输入的格式时%ld。
对于浮点型，不要使用float（因为精度只有6~7位），即只要是浮点型就使用double型最保险。
4.无穷大数
const int INF=(1<<30)-1; const int INF=0x3fffffff；
上面两种写法都是可以的；注意1<<30必须加括号（因算术运算符的优先级高于位运算符）。
如果是定义long long型的最大值则是long long inf=(1 long long <<63)-1;
注意：const用来定义常量，如const double pi=3.14；
另一种定义符号常量的方式是：【宏定义】#define pi 3.14
5.memset赋值
（1）添加头文件#include <string.h>
（2）用memset给数组赋值全部为0或-1（因为memset是按字节赋值，即组成int型的4个字节都会被赋成相同值——0的二进制补码为全0,-1的二进制补码为全1）
——memset(数组名，值，sizeof(数组名))。
（3）若对数组赋值其他数字（如1）则使用fill函数。
6.字符数组2种初始化
（1）和普通数组一样逐个赋值：char str[15]={'g','m','s'};
（2）直接通过字符串初始化（只有初始化可以，其他地方不能这样直接赋值整个字符串）：
char str[15]="guomiansheng"
打印则用for循环逐个；printf("%c",str[i])
7.用while接收输入
// 使⽤while接收输⼊的两种⽅式 while(scanf("%d", n) != EOF) { } // 等价于下⾯这种： //因为EOF⼀般为-1，所以~按位取反-1正好是0，就可以退出循环了 //所以也写成下⾯这种情况 while(~scanf("%d", &n)) { }
如果在自己的编译器运行后的命令行这样做会得不到输出结果（因为计算机一直在等你的输入结束，你需要在黑框中手动输入后，用<Ctrl+Z>组合键后按<Enter>键来高速系统已经到达了EOF即到达了所谓的“文件末尾”——这样系统才会结束while），但是OJ却能AC，因为OJ会自己判断输入文件有没有已经读取完。
8.说反话
实现的效果是【输入】Hello World Here I Come；【输出】Come I Here World Hello。
——相当于结合了第二条笔记和第七条笔记，用while循环接收输入，一直输入直到文件末尾：
#include<cstdio> int main(){ int num=0;//单词的个数 char ans[90][90]; while(scanf("%s",ans[num]!=EOF)){//一直输入直到文件末尾 num++;//单词个数加1 } for(int i=num-1;i>=0;i==){//倒着输出单词 printf("%s",ans[i]); if(i>0) printf(" "); } system("pause"); }
9.sort排序
（1）sort默认是从小到大排序，可以使用cmp改变排序规则；
（2）注意排序cmp写法，如下面栗子：如果a和b身高不同则按从大到小的身高排序，如果a和b的身高相同则按名字降序排序。
（3）记忆方法：return的“大于”就是按从大到小排列。
struct node{ string name; int height; }; int cmp(struct node a,struct node b){ return a.height != b.height ?a.height>b.height:a.name<b.name; } sort(v.begin(),v,end(),cmp);
10.字符串hash（进制转换）
若要一个字符串S哈希映射为一个整数（唯一），26个大写字母对应到二十六进制中，即将二十六进制转为十进制，但若字符串包含小写字母则是将五十二进制转换为十进制（若字符串包含数字，就将进制数增大为62）：
int hashFunc(char S[],int len){//hash函数，将字符串S转为整数 int id=0; for(int i=0;i<len;i++){//如果len未知，可以用strlen(S) if(S[i]>='A'&&S[i]<='Z'){ id=id*52+(S[i]-'A'); }else if(S[i]>='a'&&S[i]<='z'){ id=id*52+(S[i]-'a')+26; } } return id; }
11.判断素数
1. bool isprime(int n){ 2. for(int i=2;i*i<=n;i++) 3. if(n%i==0) return false; 4. return true; 5. }
12.sort进阶
sort排序默认是从小到大，如果要从大到小排序：(注意functional的头文件)：
#include<algorithm> #include<functional> int a[100000]; sort(a,a+n,greater<int>()); //或者 int cmp(int a,int b){return a>b;} sort(a,a+n,cmp);
符号重载的node结构体作为set的元素自动排序（按频率cnt降序，如cnt同则编号升序）
注意运算符重载在结构体中的写法：
struct node{ int value,cnt; bool operator<(const node &a)const{ return (cnt!=a.cnt)?cnt>a.cnt:value<a.value; //第一优先级:频率降次 第二优先级:编号 } };
13.
PAT刷题tips
3.倒置输出vector内容
#include <iostream> #include <vector> using namespace std; int main(){ vector<int> vec; for (int i = 0; i < 5; ++i) vec.push_back(i); vector<int>::reverse_iterator it; for (it = vec.begin(); it != vec.end(); it++) cout<<*it<<" "; cout<<endl; }
5.优先级(简)：！> 算术运算符 > 关系运算符 > && > || > 赋值运算符
【口诀】：算关与或赋值(盘算关羽或者这对父子)
7.cin读入字符串是以空格为分隔符，要读入以一整行(包括空格)用getline
#include<string> string s; getline(cin,s); cout<<s.length();//输出字符串长度
8.段错误~访存越界等
解决方法(在pat系统上)
while(1)大法 【原理】pat在段错误及时跳出错误，若到了while(1)则显示超时错误
9.二级指针
struct node{ int data;//数据域 node *left,*right;//指针域 }; void insert(node* &root,int data){ ....}
main函数内调用
int main(){ ... node* root=NULL; insert(root,data); ... return 0; }
10.递归~return~【A1135】
12.map<string,int>的int初始值为0
13.vector< int > ivec( ia, ia+6 ) //指将ia数组的6个元素复制到vector中
14.参考“日沉浮起”dalao的github的代码模板
https://github.com/richenyunqi/Common-code-templates-for-ACM-PAT-CSP-OJ-topics
15.一定要注意多个for循环的循环变量i不能写混乱，可以为i、ii、iii
16.printf("%04d",a);//注意默认是左对齐,如：-1占4格的最左边
17.有重复功能模块的地方不能单纯复制，一定要看清楚哪些需要改动！！如i和j
18.万能头文件 #include<bits/stdc++.h>
20.a&=b等价于a=a&b
21.已知先序&后序构造二叉树:
1.前序的首结点=后序的末结点=根结点，用一刀砍成左&右子树
2.前序的第二个结点即左子树的根结点，同时要找到这个结点在后序的位置，那么从后序开头到这个位置之间就是左子树，这个位置到后序的末尾就是右子树。(如下图)
22.一位小数num四舍五入：(int)(a+0.5);
把double/float转为int时不会四舍五入，而是取整数部分。
24.不是旅行商环路：(以下条件为或的关系)
（1）存在两个连续的点不可达
（2）初末结点不是同一个
（3）路径未访问all结点
若是旅行商环路~根据是否访问过n+1个结点(源点访问2次)判断是否simple
25.
26.二维的向量定义
创建一个10行5列的int类型的二维向量(即一个向量中元素为向量的向量)
1. vector< vector<int> > b(10, vector<int>(5)); 2. //创建一个10*5的int型二维向量
27.大写转小写两种方法
#include<iostream> #include<cctype> int main(){ char c='A'; char t=tolower(c);//如果c本身是小写字母也没有关系 char y=c+32; cout<<t<<endl<<y; return 0; }
28.输出每个学校的总分和排名：pres表示前一个学校的加权总分，如果pres和当前学校的加权总分不同说明rank等于数组下标+1，否则rank不变。
struct node{ string school; int tws,ns;//加权总分 参赛人数 };
sort(ans.begin(),ans.end(),cmp); int rank=0,pres=-1; //pres表示前一个学校的加权总分 //如果pres和当前学校的加权总分不同，说明rank等于数组下标+1,否则rank不变 printf("%d\n",(int)ans.size()); for(int i=0;i<ans.size();i++){ if(pres!=ans[i].tws) rank=i+1; pres=ans[i].tws; printf("%d ",rank); cout<<ans[i].school; printf(" %d %d\n",ans[i].tws,ans[i].ns);//加权总分，参赛人数 }
29.输出string类的字符串s某个字符s[i]的printf的格式为%c
30.找坏键A1112~用散列。注意只要某字符有一次重复出现的个数≠K的倍数,此键算好键。
//字符在计算机中以ASCII码的形式存储，当字符作为数组下标时，其表示的下标值为该字符的ASCII码的十进制值。
附：ASCII码对照表 (使用字符作为下标时，容易发生溢出问题，注意！！)
string input,output=""; int K; cin>>K>>input; //==========处理hashTable=========== int hashTable[128]={0};//表示是不是坏键 //下标为字符，元素为1表示该字符是坏键,为-1表示该字符好键，0表示该字符还没遇到过 for(int i=0;i<input.size();){ int j=i+1; while(j<input.size()&&input[j]==input[i]) ++j;//找到i位置后第一个不等于input[i]的字符位置 if(hashTable[input[i]]>=0)//当前的input[i]是坏键 hashTable[input[i]]=(j-i)%K==0?1:-1; //通过连续出现的input[i]的个数是否是K的倍数给hashTable赋值1、-1 i=j; }
31.n&(n-1)的运用
题目：输出某数的二进制中1的个数，其中负数用补码表示。
public int NumberOf1(int n) { int count = 0; while (n!=0) { count++; n = n & (n - 1); } return count; }
（1）n为奇数(n的二进制表示的末位为1)：
n: xxxxxxxx1
n-1: xxxxxxxx0
n&(n-1): xxxxxxxx0
相当于去掉最右边的一个1。
（2）n为偶数且不等于0(n的二进制表示的末位为0)：
n: xxxxx1000
n-1: xxxxx0111
n&(n-1): xxxxx0000
也是相当于去掉最右边的一个1。
32.
经验
（1）上交大佬的总结https://zhuanlan.zhihu.com/p/60841044
（2）CSP题型（5道题）
第一题：水题（稍微有些编程经验就可以写）
第二题：小模拟（处理比较简单的问题，掌握C++STL很有帮助）
第三题：大模拟（处理复杂的问题，一般涉及文本处理，需要熟练掌握C++STL并且细心）
第四题：算法题（难度一般，重点考图论算法和动态规划）
第五题：算法题（难度很高，涉及算法面很多，而且数据量很大，需要对算法极致优化，很难满分）
mark一个b站博主的CSP经验分享（https://www.bilibili.com/video/BV1oK411W7st）
