ACM经验

2022-01-13

程序设计

N 人看过

优化

#pragma GCC optimize ("O1")
#pragma comment(linker, "/STACK:1024000000,1024000000")
//防止爆栈
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define r(i,a,b) for(int i=a,i<b;i++)
using ll = long long;
using namespace std;
const int N=100;
inline int read() {
    int s = 0, w = 1;//s是数值，w是符号
    char ch = getchar();
    while (ch < '0' || ch > '9') {//将空格、换行与符号滤去
        if (ch == '-') {//出现负号表示是负数
            w = -1;
            ch = getchar();//继续读入
        }
    }
    while (ch >= '0' && ch <= '9'){ //循环读取每一位的数字
        s = s * 10 + ch - '0';//将每一位的结果累加进s
        ch = getchar();
    }
    return s * w;//乘上符号
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}

编译器优化

-O0 表示无优化状态

-O1 表示对代码进行了优化

-O2 表示减小目标文件大小

-O3 表示减小代码段及栈空间的大小

#pragma GCC optimize (“O0”)

爆栈

#pragma comment(linker, “/STACK:1024000000,1024000000”)

全局变量自动初始化

ios::sync_with_stdio(false); // 关闭C++输入输出缓冲区同步
cin.tie(0); // 绑定缓冲区

关闭后cin不能与scanf,sscanf, getchar, fgets等混用,cout不能与printf,puts等混用

使用ios...和tie 130 ms
只使用ios... 676 ms
只使用tie 315 ms
无优化 885 ms

快读快出

scanf

scanf(“%控制格式”, &变量地址); 对于数组变量本身就是地址

格式	字符意义
d	十进制整数
o	八进制整数
x	十六进制整数
u	无符号十进制整数
f或e	实型数(用小数形式或指数形式)
c	单个字符
s	字符串
l/h	l表示长，h表示短，Eg：lf 读入doble
*	读入不赋值，EG：*d 读入int但不赋值
5（数字）	读入宽度
-/+	左/右对齐
#	需要时给出小数点和前缀o或 0x
空格	需要时显示正负号

没有精度控制 scanf(“%5.2f”,&a);是非法的

要求给出变量地址 scanf(“%d”,a);是非法的

在碰到空格，TAB，回车或非法数据时认为该数据结束

printf

printf(“%控制格式”, 变量本身);

%a(%A) 浮点数、十六进制数字和p-(P-)记数法(C99)
%c 字符
%d 有符号十进制整数
%f 浮点数(包括float和double)
%e(%E) 浮点数指数输出[e-(E-)记数法]
%g(%G) 浮点数不显无意义的零”0”
%i 有符号十进制整数(与%d相同)
%u 无符号十进制整数
%x(%X) 十六进制整数0f(0F) e.g. 0x1234
%p 指针
%% “%”

读入空格

cin.get(x) 读入单个char

x = getchar( ) 读入单个char，对应putchar( ) 输出单个char

getline(x) 读入string

内联函数read

内联是将代码内嵌到调用者代码处

inline int read() {
    int s = 0, w = 1;//s是数值，w是符号
    char ch = getchar();
    while (ch < '0' || ch > '9') {//将空格、换行与符号滤去
        if (ch == '-') {//出现负号表示是负数
            w = -1;
            ch = getchar();//继续读入
        }
    }
    while (ch >= '0' && ch <= '9'){ //循环读取每一位的数字
        s = s * 10 + ch - '0';//将每一位的结果累加进s
        ch = getchar();
    }
    return s * w;//乘上符号
}

内联函数write

void write(int v) {
    if (v<0) {
        putchar('-');
        v=-v;
    }
    if (v>9) write(v/10);
    putchar(v%10+'0');
}
puts(""); //换行

位运算

2^n 可以用 1<<n 来计算

异或 ^

时间复杂度

$n \le 30$ , 指数级别, dfs+剪枝，状态压缩dp
$n \le 100$ => $O(n^3)$ ，floyd，dp，高斯消元
$n \le 1000$ => $O(n^2)$ ， $O(n^2logn)$ ，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
$n \le 10000$ => $O(n * \sqrt n)$ ，块状链表、分块、莫队
$n \le 100000$ => $O(nlogn)$ => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
$n \le 1000000$ => $O(n)$ , 以及常数较小的 $O(nlogn)$ 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 $O(nlogn)$ 的做法：sort、树状数组、heap、dijkstra、spfa
$n \le 10000000$ => $O(n)$ ，双指针扫描、kmp、AC自动机、线性筛素数
$n \le 10^9$ => $O(\sqrt n)$ ，判断质数
$n \le 10^{18}$ => $O(logn)$ ，最大公约数，快速幂，数位DP
$n \le 10^{1000}$ => $O((logn)^2)$ ，高精度加减乘除
$n \le 10^{100000}$ => $O(logk \times loglogk)，k表示位数$ ，高精度加减、FFT/NTT