知识点:
1、基本输入输出语法:
(1)如cin速度比scanf慢 两者遇到空格回车会停止读入
(2)若想读整行需要cin.getline()或gets函数
(3)读到文件尾用scanf()!=EOF等等
(4)占位符‘%’相关格式,如对齐方式,补0等。
2、C/C++库函数以及stl模板
(1)algorithm: sort next_permutation lower_bound/upper_bound
(2)queue(priority_queue) stack vector set map基本操作等
3、数据结构
(1)结构体:注意结构体用sort排序,可自定义cmp函数,也可在结构体内重载“<”运算符。
(2)字符串:string类的使用、字典树(用于求解前缀和后缀问题)。
(3)栈、队列:前缀、后缀表达式计算等。
(4)图:两种表示方法,邻接表和邻接矩阵,当n较大时只能采用邻接表。
(5)树:树是一种特殊的图。如按层输出节点等
(6)线段树:基本的单点修改、区间修改、区间查询等。
4、算法
(1)暴力:蓝桥杯又称暴力杯,n<=1e3(1000),O(n2)的代码大概率能解,如果1e4<=n<=1e6,则要考虑O(n*logn)的算法,不过蓝桥按测试点得分,实在不会,可用O(n2)骗分,骗到了就是赚到了。
(2)思维:不涉及算法,不涉及复杂数据结构,往往几行代码就可以解决,考验思维能力,多训练此类题目即可。
(3)模拟:模拟指根据题目描述,按部就班的写代码就可以AC,通常思路容易看出但是代码量较大,考验细节与心态。
①大数加减法
②进制转换
(4)数学问题:
①质数相关:埃式筛、欧拉筛、唯一分解定理等。
②求最大公因数:要自己会写gcd函数(欧几里得算法)
③快速幂模板,矩阵快速幂模板
④慢速乘模板(防止相乘的时候数太大爆掉long long)
(5)贪心
(6)动态规划:
①最长公共子序列
②最长上升/不下降子序列
③背包问题(01背包、多重背包、完全背包等)
④前缀和问题(一维/二维前缀和)
(7)搜索:搜索基本是必考的点,包括DFS/BFS,可分别用栈和队列模拟。记忆化搜索也是常考的点,用于避免重复搜索。
(8)图论:
①最短路:最基本要掌握两种求法,floyd算法和dijkstra算法。前者O(n^3),适用于n不大于500的情况。后者dijkstra用的较多,数据结构实现有两种,邻接矩阵与邻接表,建议用邻接表(具体实现啊哈算法上有)。
②最小生成树:kruscal算法和prim算法
③拓扑排序
(9)字符串:回文、kmp算法(字符串匹配算法)
(10)其他:并查集、二分/三分算法等
头文件
万能头文件 #include
实数函数及运算符
求幂次
pow(x,y);数据类型下x,y应为double型
移位运算符
x< x>>y == x/(2^y) void sort(first,last); void sort(first,last,comp); 复杂度为O(nlogn),排序的范围为[first,last),包括first不包括last。 string s=“bca”; sort(s.begin(),s.end());//字符串内部排序,得到最小的排列"abc" do{ cout< }while(next_permutation(s.begin(),s.end())); //s.end()指向最后一个字符的下一个位置 例如:memset(a,0,sizeof(a)) find()函数:查找 substr()函数:查子串 采用倍增的原理 幂运算的结果往往很大,一般题目会要求先取模再输出。根据取模的性质有:an mod m=(a mod m)n mod m。 题目-纯质数 九进制转十进制,111=199+19+11=; 题目-统计子矩阵!!! 计数类型的递推或者递归: 整数拼接:dp优化 填空题STL排序sort函数
STL全排列函数next_permutation()
初始化函数memset()
GCD(最大公约数)和LCM(最小公倍数)
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{return a/gcb(a,b)*b;
}
C++字符串函数
按字典序反序排序
bool cmp(string a,string b){ return a+b>b+a;
}
素数判断
bool is_prime(long long n){ If(n<=1) return false;
For(long long i=2;i<=sqrt(n);i++)
{If(n%i==0) return false;
}
Return true;
}
快速幂
int fastpow(int a,int b)//计算a的n次方
{ Int ans=1;
while(n){ If(n&1) ans*=a;
a*=a;
n>>=1;//n右移一位,把刚处理过的n的最后一位去掉
}
return ans;
}
Ll fastpow(ll a,ll b)
{ Ll ans=1;
A%=mod;
while(n){If(n&1) ans=(ans*a)%mod;
A=a*a%modl
N>>=1;
}
Return ans;
}
整数二分
Int L=1,R=N;
//第一种写法
While(L
前缀和
For(int i=1;i
素数:
bool isPrime(int a){// 判断是否为质数
if(a == 2){return true;
}
if(a < 2 || a % 2 == 0){return false;
}
for(int i = 3;i * i <= a;i += 2){if(a % i == 0){return false;
}
}
return true;
}
bool isRealPrime(int a){// 判断是否为纯质数
if(!isPrime(a)){return false;
}
do{if(!isPrime(a % 10)){return false;
}
a /= 10;
}while(a != 0);
return true;
}
日期闰年:
if((i%4==0&&i%100!=0)||(i%400==0)){//闰年2月29天}
进制转换:
前缀和:
#include
状态dp:
#include
Bitset用法:明码
#include
分治思想的快速排序
#include