link

知识点回顾

基础

  • 快读
1
2
ios::sync_with_stdio(false);
cin.tie(0);
  • 语法相关
    • 时空复杂度， TLE
      • 时间 < 10810^8
        • 典型
          -n=100n=100 O(n3) O(n4)O(n^3) ~ O(n^4)
          -n=1000n=1000 O(n2)O(n^2)
          -n=105n=10^5 O(nlog⁡n)O(n\log n)
          -n=106n=10^6 O(n)O(n)
          -n=20000n=20000 O(nn)O(n\sqrt{n})
      • 空间 2∗1072*10^7 个 int 左右 →\to 128MB MLE
    • 数据类型
      • int 2^32-1 →\to 2e9 %d
      • long long, 2^64-1→\to 1e19 %lld
        • unsigned 无符号，可将负数部分用于存储更多的正数
      • double →\to 2e9 %lf
      • long double →\to 1e19 %Lf
      • char
        • gets 整行
        • cin scanf(“%s”, s+1)
    • 数据类型读取方式
      • printf(“%.2lf”)
      • while(cin>>a) while(scanf(“%d”, &a)!=EOF)
    • 字符串函数 (注：字符串操作时间复杂度是O(n)O(n)的，故不要放在循环条件上)
1
2
3
4
int len = strlen(s)
for(int i=1;i<=len;i++) O(n)
  
for(int i=1;i<=strlen(s);i++)  O(n^2)
1
2
3
* strlen 
    * strcpy 
    * strcmp
  • STL函数库
    • set O(nlog⁡n)O(n\log n)
    • mapO(nlog⁡n)O(n\log n)
    • unordered_map O(n)O(n)

简单算法

数据结构

图论

动态规划

树论

字符串

数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void init(){
	mu[1]=1;
	phi[1]=1;
	int cnt=0;
	for(int i=2;i<maxn;i++){
		if(!vis[i]){
			prime[cnt++]=i;
			mu[i]=-1;
			phi[i]=i-1;
		}
		for(int j=0;j<cnt&&i*prime[j]<maxn;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]){
			    mu[i*prime[j]]=-mu[i];
			    phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
			else {
				mu[i*prime[j]]=0;
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
		}
	}
}
1
2
3
* 杜教塞
        + [<font style="color:#DF2A3F;">P4213 【模板】杜教筛</font>](https://www.luogu.com.cn/problem/P4213)
    * min25筛

计算几何

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来参与讨论吧~