$Noip$之前在这里整理一波模板….
集成了一下所有的$TG$和$PJ$应该会考的模板
PS:所有模板纯属现场手搓，不保证正确性（比如手抖打错字母什么的），如果找到错误请及时告知我qwq
快速排序
最基本的板子了吧,$C++$选手表示开心$qaq$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 |
|
快速幂
个人感觉这个还是个挺重要的板子了吧…..1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
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
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
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
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
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
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 |
|
线性求逆元
1 | const int HA = 998244353; |
树状数组区间修改区间求和
1 |
|
矩阵快速幂(求fib数列)
1 | struct Matx { |
扩展欧几里得(同余方程)
1 |
|
树的直径
1 |
|
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想