Return void

emmm,因为null记性实在太差,所以把一些模板整理一下,方便查阅和背代码

晨 读 内 容

模板&宏定义

可能存在一些奇怪的锅(auto),需要--std=c++11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define int long long
#define reg register
#define foreach(i,a,b) for(auto i = (a);i <= (b);++i)
#define rforeach(i,a,b) for(auto i = (a);i >= (b);--i)
typedef __int128 BigInt;
typedef long long ll;
typedef unsigned long long ull;
using std::cin;
using std::cout;
using std::vector;
template <typename T>
inline void read(T& x) {
x = 0;
T f = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') f= -1;
ch = getchar();
}
while(isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
template <typename T,typename ... Args>
inline void read(T& x,Args& ... args) {
read(x);
read(args...);
}
template <typename T>
inline void output(T x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) output(x/10);
putchar('0'+x%10);
}

普通版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define int long long
#define reg register
#define foreach(i,a,b) for(int i = (a);i <= (b);++i)
#define rforeach(i,a,b) for(int i = (a);i >= (b);--i)
typedef long long ll;
typedef unsigned long long ull;
using std::cin;
using std::cout;
using std::vector;
template <typename T>
inline void read(T& x) {
x = 0;
T f = 1;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') f= -1;
ch = getchar();
}
while(isdigit(ch)) {
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
template <typename T>
inline void output(T x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) output(x/10);
putchar('0'+x%10);
}

数论函数

GCD

辗转相处

1
2
3
int gcd(int a,int b) {
return !b ? a : gcd(b,a%b);
}

LCM

两数的最小公倍数为
$$
LCM(a,b) = a * b / GCD(a,b)
$$

1
2
3
inline int lcm(int a,int b) {
return a * b / gcd(a,b); // update 注意顺序,不要加括号,有可能溢出
}

素数筛

单个数

1
2
3
4
5
6
7
8
9
bool isPrime(int n)
{
if(n==1) return false;
if(n==2||n==3) return true;
if(n%6!=1&&n%6!=5) return false;
for(register int i=5;i*i<=n;i+=6)
if(n%i==0||n%(i+2)==0) return false;
return true;
} //常数优化版

欧拉筛

1
2
3
4
5
6
7
for(int i = 2;i <= n;++i) {
if(!isNotPrimer[i]) primer.push_back(i);
for(int j = 0;j <= primer.size() && primer[j] * i <= n; ++j) {
isNotPrimer[i * primer[j]] = true;
if( i % primer[j] == 0) break;
}
}

图论

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
namespace us {
int fa[MAXN];
void init() {
foreach(i,1,n) fa[i] = i;
}
void find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void isSame(int x,int y) {
return find(x) == find(y);
}
void merge(int x,int y) {
fa[find(x)] = find(y);
}
}

最短路

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
namespace spfa {
int dis[MAXN];
std::bitset<MAXN> in = 0;
queue<int> q;
void spfa(int s) {
for(int i = 0;i <= n;++i) dis[i] = INT_MAX;
dis[s] = 0;
in[s] = true;
q.push(s);
while(!q.empty()) {
int u = q.front();q.pop();
in[u] = false;
for(int i = ls::head[u];i;i = ls::G[i].next) {
int v = ls::G[i].to,w = ls::G[i].w;
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if(!in[v]) {
q.push(v);
in[v] = true;
}
}
}
}
}
}

Dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
namespace dijkstra {
struct Node {
int id,dis;
bool operator <(const Node &x) const {
return x.dis < dis;
}
};
bool cmp(Node x,Node y) {
return x.dis < y.dis;
}
int dis[MAXN];
bool vis[MAXN];
priority_queue<Node> q;
inline void dijkstra(int s) {
for(int i = 0;i <= n; ++i) {
dis[i] = INT_MAX;
vis[i] = false;
}
dis[s] = 0;
q.push( (Node) {s,0});
while (!q.empty()) {
Node now = q.top();q.pop();
if(vis[now.id]) continue;
vis[now.id] = true;
for(int i = ls::head[now.id];i;i = ls::G[i].next) {
int to = ls::G[i].to;
int w = ls::G[i].w;
if(dis[to] > dis[now.id] + w) {
dis[to] = dis[now.id] + w;
if(!vis[to]) {
q.push((Node) {to,dis[to]});
}
}
}
}
}
}

拓扑排序

Tarjan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
namespace tar {
int dfn[MAXN],low[MAXN],stack[MAXN],top,cnt;
int scc[MAXN];
bool vis[MAXN] = {false};
void tarjan(int now) {
dfn[now] = low[now] = ++cnt;
stack[++top] = now;
vis[now] = true;
for(int i = ls::head[now]; i; i = ls::G[i].next) {
int to = ls::G[i].to;
if(!dfn[to]) {
tarjan(to);
low[now] = std::min(low[now],low[to]);
} else if(vis[to]) {
low[now] = std::min(low[now],dfn[to]);
}
}
if(dfn[now] == low[now]) {
int y = 0;
while(y = stack[top--]) {
scc[y] = now;
vis[y] = false;
if(now == y) break;
po[now] += po[y]; // 合并点权,根据题目使用
}
}
}
}
for(int i = 1; i <= n; ++i) {
if(!tar::dfn[i]) tar::tarjan(i); //针对题目中可能不联通的情况
}
for(int i = 1; i <= m; ++i) {
int x = tar::scc[ls::G[i].from],y = tar::scc[ls::G[i].to];
if(x != y) {
ls2::addEdge(x,y); //缩点代码,将DAG储存在ls2中
in[y]++;
}
}

判负环

使用SPFA方法,根据进队次数判读(可能存在被卡可能)

仅能判断,不能找出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
namespace spfa {
bool in[MAXN];
int dis[MAXN],cnt[MAXN];
inline bool spfa(int s) {
std::queue<int> q;
for(int i = 0 ;i <= n;++i) dis[i] = INT_MAX;
dis[s] = 0;
in[s] = true;
q.push(s);
while(!q.empty()) {
int u = q.front();q.pop();in[u] = false;
if(cnt[u] > n) return true;
for(int i = ls::head[u];i;i = ls::G[i].next) {
int v = ls::G[i].to;
int w = ls::G[i].w;
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if(!in[v]) {
++cnt[v]; //判断入队次数
q.push(v);
in[v] = true;
if(cnt[v] >= n) return true;
}
}
}
}
return false;
}

}

判环

数据结构

ST

特点 $O(nlogn)$询问$O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll n,m;
ll log[MAXN] = {-1};
ll st[MAXN][32],a[MAXN];
void init() {
foreach(i,1,n) {
log[i] = log[i >> 1] + 1;
st[i][0] = a[i]; // a是原数据
}
foreach(i,1,log[n]) {
for(int j = 1;j+(1<<i)-1 <= n;++j) {
st[j][i] = std::max(st[j][i-1],st[j+(1 << (i-1))][i-1]);
}
}
}
void solve(void) {
init();
while(m--) {
reg ll l,r;
read(l,r);
int jump = log[r-l+1];
output(std::max(st[l][jump],st[r-(1<<(jump))+1][jump]));
puts("");
}
return;
}

常见DP模型

背包问题

树上DP

DAG上DP


 评论