Fork me on GitHub

考前模板整理

$Noip$之前在这里整理一波模板….
集成了一下所有的$TG$和$PJ$应该会考的模板

PS:所有模板纯属现场手搓,不保证正确性(比如手抖打错字母什么的),如果找到错误请及时告知我qwq

快速排序

最基本的板子了吧,$C++$选手表示开心$qaq$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <cstdio>

const int N = 1e5 + 10

int n;
int num[N];

int main ( void ) {
scanf ( "%d" , &n );
for ( int i = 1 ; i <= n ; i++ )
scanf ( "%d" , &num[i] );
sort ( num + 1 , num + 1 + n );
for ( int i = 1 ; i <= n ; i++ )
printf ( "%d%c" , num[i] , i == n ? '\n' : ' ' );
return 0;
}

并查集

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 <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

const int N = 1e5 + 10;
int n , m;

int find ( int x ) {
if ( x != father[x] )
father[x] = find ( father[x] );
return father[x];
}
int main ( void ) {
scanf ( "%d%d" , &n , &m );
for ( int i = 1 ; i <= n ; i++ )
father[i] = i;
for ( int i = 1 ; i <= m ; i++ ) {
int x , y , z;
scanf ( "%d%d%d" , &z , &x , &y );
if ( z == 1 ) {
x = find ( x ) , y = find ( y );
father[x] = y;
}
else if ( z == 2 ) {
x = find ( x ) , y = find ( y );
if ( x == y )
puts ( "Y" );
else
puts ( "N" );
}
}
return 0;
}

快速幂

个人感觉这个还是个挺重要的板子了吧…..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

inline int Fast_Power ( int x , int y ) {
int sum = 1;
while ( y ) {
if ( y & 1 )
sum = sum * x;
x = x * x;
y >>= 1;
}
return sum;
}

int main ( void ) {
int n , m;
scanf ( "%d%d" , &n , &m );
printf ( "%d\n" , Fast_Power ( n , m ) );
return 0;
}

线性筛素数

这个其实只是筛素数的话是挺简单的,但是我决定连$\phi$一起筛出来(如果用不到的话就把$phi$数组自动忽略掉就好了)

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

const int N = 5e5 + 10;

int n , cnt;
int prime[N] , phi[N];
bool flag[N];

int main ( void ) {
flag[1] = 1;
phi[1] = 1;
scanf ( "%d" , &n );
for ( int i = 2 ; i <= n ; i++ ) {
if ( !flag[i] ) {
flag[i] = 1;
prime[++cnt] = i;
phi[i] = i - 1;
}
for ( int j = 1 ; j <= cnt && i * prime[j] <= n ; j++ ) {
flag[i * prime[j]] = 1;
if ( i % prime[j] == 0 ) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
for ( int i = 1 ; i <= cnt ; i++ )
printf ( "%d " , prime[i] );
puts ( "" );
for ( int i = 1 ; i <= n ; i++ )
printf ( "%d " , phi[i] );
return 0;
}

【模板】堆

又是一个$C++$党的福利$qwq$,直接用$priority$_$queue$模拟就好啦

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using std :: priority_queue;

int n;
priority_queue < int , std :: vector < int > , std :: greater < int > > qu;

int main ( void ) {
scanf ( "%d" , &n );
for ( int i = 1 ; i <= n ; i++ ) {
int opts;
scanf ( "%d" , &opts );
if ( opts == 1 ) {
int x;
scanf ( "%d" , &x );
qu.push ( x );
}
else if ( opts == 2 )
printf ( "%d\n" , qu.top () );
else if ( opts == 3 )
qu.pop ();
}
return 0;
}

字符串蛤希

其实我个人比较倾向于写自然溢出或者直接随机一个质数$qwq$

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

typedef unsigned long long ull;
const ull base = 233;
const int N = 1e4;
const int M = 1e3;

int n;
char s[N][M];
ull has[N];

int main ( void ) {
scanf ( "%d" , &n );
for ( int i = 1 ; i <= n ; i++ )
scanf ( "%s" , s[i] + 1 );
for ( int i = 1 ; i <= n ; i++ ) {
int len = strlen ( s[i] + 1 );
for ( int j = 1 ; j <= len ; j++ )
has[i] = has[i] * base + s[i][j];
}
std :: sort ( has + 1 , has + 1 + n );
int ans = 0;
for ( int i = 1 ; i <= n ; i++ )
if ( has[i] != has[i + 1] )
ans++;
printf ( "%d\n" , ans );
return 0;
}

最小生成树

不会写$prim$的蒟蒻瑟瑟发抖….

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

const int N = 1e4 + 10;
const int M = 2e5 + 10;

int n , m;
struct Edge {
int from;
int to;
int data;
}e[M];
int father[N];

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
inline bool cmp ( Edge x , Edge y ) {
return x.data < y.data;
}
int find ( int x ) {
if ( x != father[x] )
father[x] = find ( father[x] );
return father[x];
}
void Union ( int x , int y ) {
x = find ( x ) , y = find ( y );
father[x] = y;
return;
}
inline bool Judge ( int x , int y ) {
x = find ( x ) , y = find ( y );
return ( x == y ) ? true : false;
}

int main ( void ) {
n = read () , m = read ();
for ( int i = 1 ; i <= n ; i++ )
father[i] = i;
for ( int i = 1 ; i <= m ; i++ ) {
int x = read () , y = read () , z = read ();
e[i].from = x;
e[i].to = y;
e[i].data = z;
}
std :: sort ( e + 1 , e + 1 + m , cmp );
int NowEdge = 0 , NowVal = 0;
for ( int i = 1 ; i <= m ; i++ ) {
int l = e[i].from , r = e[i].to;
if ( Judge ( l ,r ) )
continue;
Union ( l , r );
NowEdge++;
NowVal += e[i].data;
if ( NowEdge == n - 1 )
break;
}
if ( NowEdge == n - 1 )
printf ( "%d\n" , NowVal );
else
puts ( "orz" );
return 0;
}

单源最短路 (有负权边)

这张图有负权边,所以只能写某已经死掉的$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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e4 + 10;
const int M = 1e5 + 10;
using std :: queue;

int n , m , t;
struct Edge {
int to;
int data;
int next;
}e[M];
int head[N] , dis[N];
bool inque[N];

inline int read () {
int s = 0;
bool flag = 0;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '0' ) flag = 1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return ( flag ) ? -s : s;
}
void Spfa ( int x ) {
memset ( dis , 0x3f3f3f3f , sizeof ( dis ) );
inque[x] = 1;dis[x] = 0;
qu.push ( x );
while ( !qu.empty () ) {
int j = qu.front ();
qu.pop ();
inque[j] = 0;
for ( int i = head[j] ; i ; i = e[i].next ) {
int k = e[i].to;
if ( dis[k] > dis[j] + e[i].data ) {
dis[k] = dis[j] + e[i].data;
if ( !inque[k] ) {
inque[k] = 1;
qu.push ( k );
}
}
}
}
return;
}

int main ( void ) {
n = read () , m = read ();
for ( int i = 1 ; i <= m ; i++ ) {
int x = read () , y = read () , z = read ();
add ( x , y , z );
}
Spfa ( 1 );
for ( int i = 1 ; i <= n ; i++ )
printf ( "%d%c" , dis[i] == 0x3f3f3f3f ? 2147483647 : dis[i] , i == n ? '\n' : ' ' );
return 0;
}

单源最短路 (无负权边)

在题目明确说没有负权边的情况下,跑堆优化的$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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#define F(i,a,b) for ( int i = a ; i <= b ; i++ )
#define MP std::make_pair
#define se second
#define fi first

typedef std::pair < int , int > pll;
const int N = 1e5 + 10;
const int M = 4e5 + 20;

std::priority_queue < pll , std::vector < pll > , std::greater < pll > > qu;
int n , m , s , t;
struct Edge {
int to;
int data;
int next;
}e[M];
int head[N] , dis[N];
bool inque[N];

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}
void add ( int x , int y , int z ) {
e[++t].to = y;
e[t].data = z;
e[t].next = head[x];
head[x] = t;
return;
}
inline void Heap_Dijkstra ( int x ) {
memset ( dis , 0x3f3f3f3f , sizeof ( dis ) );
dis[x] = 0;
qu.push ( MP ( dis[x] , x ) );
while ( !qu.empty () ) {
int j = qu.top ().se;
qu.pop ();
if ( inque[j] )
continue;
inque[j] = 1;
for ( int i = head[j] ; i ; i = e[i].next ) {
int k = e[i].to;
if ( dis[k] > dis[j] + e[i].data ) {
dis[k] = dis[j] + e[i].data;
qu.push ( MP ( dis[k] , k ) );
}
}
}
return;
}

int main ( void ) {
n = read ();
m = read ();
s = read ();
F ( i , 1 , m ) {
int x = read () , y = read () , z = read ();
add ( x , y , z );
}
Heap_Dijkstra ( s );
F ( i , 1 , n )
printf ( "%d " , dis[i] );
return 0;
}

割点

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

const int N = 20005;
const int M = 200005;

int n , m , t , idx;
int head[N] , dfn[N] , low[N];
bool flag[N];

struct Edge {
int to;
int next;
} e[M];

inline void add ( int x , int y ) {
e[++t].to = y;
e[t].next = head[x];
head[x] = t;
return;
}
void Tarjan ( int cur , int father ) {
int child = 0;
dfn[cur] = low[cur] = ++idx;
for ( int i = head[cur] ; i ; i = e[i].next ) {
int j = e[i].to;
if ( !dfn[j] ) {
Tarjan ( j , father );
low[cur] = std :: min ( low[cur] , low[j] );
if ( low[j] >= dfn[cur] && cur != father )
flag[cur] = 1;
if ( cur == father )
child++;
}
low[cur] = std :: min ( low[cur] , dfn[j] );
}
if ( father == cur && child >= 2 )
flag[cur] = 1;
return;
}

int main ( void ) {
n = read () , m = read ();
for ( int i = 1 ; i <= m ; i++ ) {
int x = read () , y = read ();
add ( x , y );
add ( y , x );
}
for ( int i = 1 ; i <= n ; i++ )
if ( !dfn[i] )
Tarjan ( i , i );
for ( int i = 1 ; i <= n ; i++ )
if ( flag[i] )
printf ( "%d\n" , i );
return 0;
}

线性求逆元

1
2
3
4
5
6
7
const int HA = 998244353;
int main ( void ) {
inv[1] = 1;
for ( int i = 2 ; i <= n ; i++ )
inv[i] = ( HA - HA / i ) * inv[HA % i] % HA;
return 0;
}

树状数组区间修改区间求和

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define ll long long
#define MP make_pair
#define F(i,a,b) for(int i=a;i<=b;i++)
#define D(i,a,b) for(int i=a;i>=b;i--)
#define PB push_back

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

const int N = 100005;

int n , m;
ll num[N];

inline int lowbit ( int x ) {
return x & -x;
}

struct Tree {
ll tree[N];

inline void add ( ll x , int pos ) {
while ( pos <= n ) {
tree[pos] += x;
pos += lowbit ( pos );
}
return;
}

inline ll query ( int pos ) {
ll res = 0;
while ( pos ) {
res += tree[pos];
pos -= lowbit ( pos );
}
return res;
}

}t[2];

int main ( void ) {
n = read () , m = read ();
for ( int i = 1 ; i <= n ; i++ ) {
num[i] = read ();
t[0].add ( num[i] - num[i - 1] , i );
t[1].add ( ( num[i] - num[i - 1] ) * i , i );
}
for ( int i = 1 ; i <= m ; i++ ) {
int opts = read () , l = read () , r = read ();
if ( opts == 1 ) {
ll val = read ();
t[0].add ( val , l );
t[0].add ( -val , r + 1 );
t[1].add ( val * l , l );
t[1].add ( -val * ( r + 1 ) , r + 1 );
}
else if ( opts == 2 ) {
ll ValR = ( r + 1 ) * t[0].query ( r ) - t[1].query ( r );
ll ValL = ( l ) * t[0].query ( l - 1 ) - t[1].query ( l - 1 );
printf ( "%lld\n" , ValR - ValL );
}
}
return 0;
}

矩阵快速幂(求fib数列)

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
struct Matx {
ll rec[3][3];
} ms , lab , ans , st;

Matx operator * ( Matx x , Matx y ) {
Matx tmp;
for ( ll i = 0 ; i < 3 ; i++ ) for ( ll j = 0 ; j < 3 ; j++ ) tmp.rec[i][j] = 0;
for ( ll i = 1 ; i <= 2 ; i++ )
for ( ll j = 1 ; j <= 2 ; j++ )
for ( ll k = 1 ; k <= 2 ; k++ )
tmp.rec[i][j] = ( tmp.rec[i][j] + ( 1ll * x.rec[i][k] * y.rec[k][j] ) % HA ) % HA;
return tmp;
}

int main ( void ) {
m = read ();
while ( m-- ) {
std :: cin >> s;
ll nn = read ();
for ( ll i = 0 ; i < 3 ; i++ ) for ( ll j = 0 ; j < 3 ; j++ ) ans.rec[i][j] = 0;
ms.rec[1][1] = 0 , ms.rec[1][2] = 1 , ms.rec[2][1] = 1 , ms.rec[2][2] = 1;
lab.rec[1][1] = 1 , lab.rec[1][2] = 0 , lab.rec[2][1] = 0 , lab.rec[2][2] = 1;
st.rec[1][1] = 1 , st.rec[1][2] = 1;
ll yy = nn;
while ( yy ) {
if ( yy & 1ll )
lab = lab * ms;
ms = ms * ms;
yy >>= 1ll;
}
for ( ll i = 1 ; i <= 1 ; i++ )
for ( ll j = 1 ; j <= 2 ; j++ )
for ( ll k = 1 ; k <= 2 ; k++ )
ans.rec[i][j] = ( ans.rec[i][j] + ( 1ll * st.rec[i][k] * lab.rec[k][j] ) % HA ) % HA;
writeln ( ans.rec[1][1] );
puts ( "" );
}
return 0;
}

扩展欧几里得(同余方程)

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define int long long

using namespace std;

int a , b , x , y;

void exgcd ( int a , int b ) {
if ( !b ) {
x = 1;
y = 0;
return;
}
exgcd ( b , a % b );
int tx = x;
x = y;
y = tx - a / b * y;
return;
}

signed main ( void ) {
cin >> a >> b;
exgcd ( a , b );
x = ( x % b + b ) % b;
cout << x << endl;
return 0;
}

树的直径

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;

int n , t;
int head[N] , f[N][3];
struct Edge {
int to;
int date;
int next;
}e[N << 2];

inline void add ( int x , int y , int z ) {
e[++t].to = y;
e[t].date = z;
e[t].next = head[x];
head[x] = t;
return;
}
void dfs1 ( int x , int fa ) {
for ( int i = head[x] ; i ; i = e[i].next ) {
int y = e[i].to;
if ( y == fa )
continue;
dfs1 ( y , x );
int temp = f[y][0] + e[i].date;
if ( temp >= f[x][0] ) {
f[x][1] = f[x][0];
f[x][0] = temp;
}
else if ( temp > f[x][1] )
f[x][1] = temp;
}
return;
}
void dfs2 ( int x , int fa ) {
for ( int i = head[x] ; i ; i = e[i].next ) {
int y = e[i].to;
if ( f[x][0] == f[y][0] + e[i].date )
f[y][2] = max ( f[x][2] , f[x][1] ) + e[i].date;
else
f[y][2] = max ( f[x][2] , f[x][0] ) + e[i].date;
dfs2 ( y , x );
}
return;
}
int main ( void ) {
while ( scanf ( "%d" , &n ) != EOF ) {
t = 0;
memset ( f , 0 , sizeof ( f ) );
memset ( head , 0 , sizeof ( head ) );
for ( int i = 2 ; i <= n ; i++ ) {
int x , y;
scanf ( "%d%d" , &x , &y );
add ( x , i , y );
}
dfs1 ( 1 , 0 );
dfs2 ( 1 , 0 );
for ( int i = 1 ; i <= n ; i++ )
printf ( "%d\n" , max ( f[i][0] , f[i][2] ) );
}
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想