会有一些之前已经发过文章的算法，这里只是在最后一次Noip前进行一次模板总结，为最后一次Noip做准备（带去考场，误）。本人水平有限大家看到特别不爽的地方还是忍忍吧。
下面马上就开始了：
首先是宏模板
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
|
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <ctime>
#include <bitset>
#define FOR(i,s,e) for(int i=s;i<e;i++)
#define REP(i,s,e) for(int i=s;i<=e;i++)
#define ROF(i,s,e) for(int i=s;i>e;i--)
#define PER(i,s,e) for(int i=s;i>=e;i--)
#define FI(a) freopen(a,"r",stdin)
#define FO(a) freopen(a,"w",stdout)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)>(b)?(b):(a))
#define ABS(a) ((a)>0?(a):(-(a)))
#define INF 0x3f3f3f3f
#define SPEEDUP ios::sync_with_stdio(false)
#define N
using namespace std;
int main(void){
return 0;
}
|
读入优化模板
正整数版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
template<typename T>
void read(T &a){
char temp=getchar();
while(temp<'0'||temp>'9'){
temp=getchar();
}
a=temp-'0';
temp=getchar();
while(temp>='0'&&temp<='9'){
a=a*10+temp-'0';
temp=getchar();
}
}
|
实数版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
template<typename T>
void read(T &a){
char temp=getchar();
bool sign=false;
while(temp<'0'||temp>'9'){
if(temp=='-'){
sign=true;
}
temp=getchar();
}
a=temp-'0';
temp=getchar();
while(temp>='0'&&temp<='9'){
a=a*10+temp-'0';
temp=getchar();
}
if(sign){
a=-a;
}
}
|
快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int fastpow(int a,int b,int k){
int ans=1;
while(b){
if(b&1){
ans*=a;
ans%=k;
}
b=b>>1;
a*=a;
a%=k;
}
return a;
}
|
并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#define SIZE 100
int father[SIZE];
void start(){
for(int i=0;i<SIZE;i++){
father[i]=i;
}
}
int getfather(int x){
if(father[x]==x){
return x;
}else{
return father[x]=getfather(father[x]);
}
}
void add(int x,int y){
int xx=getfather(x);
int yy=getfather(y);
father[xx]=yy;
}
|
最大公因数，最小公倍数
1
2
3
4
5
6
7
8
9
10
11
|
int gcd(int a,int b){
if(b==0){
return a;
}else{
return gcd(b,a%b);
}
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
|
最短路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
|
#define SIZE 100
int dis[SIZE];
bool vis[SIZE];
struct way{
int to,num;
};
vector<way> v[SIZE];
int spfa(int s,int e){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
vis[s]=true;
deque<int> q;
q.push_back(s);
while(!q.empty()){
int temp=q.front();
q.pop_front();
for(int i=0;i<v[temp].size();i++){
if(dis[v[temp][i].to]>dis[temp]+v[temp][i].num){
dis[v[temp][i].to]=dis[temp]+v[temp][i].num;
if(!vis[v[temp][i].to]){
vis[v[temp][i].to]=true;
if(!q.empty()){
if(dis[v[temp][i].to]>dis[q.front()]){
q.push_back(v[temp][i].to);
}else{
q.push_front(v[temp][i].to);
}
}else{
q.push_back(v[temp][i].to);
}
}
}
}
vis[temp]=false;
}
return dis[e];
}
|
弗洛伊德
1
2
3
4
5
6
7
8
9
10
11
12
|
#define SIZE 100
int dis[SIZE][SIZE];
void floyd(){
for(int k=0;k<SIZE;k++){
for(int i=0;i<SIZE;i++){
for(int j=0;j<SIZE;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
|
弗洛伊德最小环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#define N 100
int dis[N][N],ma[N][N];
int floyd(){
int mi;
for(int k=0;k<N;k++){
for(int i=0;i<k;i++){
for(int j=i+1;j<k;j++){
mi=min(mi,dis[i][j]+ma[i][k]+ma[k][j]);
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
return mi;
}
|
迪杰斯特拉
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
|
#define SIZE 100
struct way{
int to,num;
};
vector<way> v[SIZE];
int dis[SIZE];
int dijkstra(int s,int e){
typedef pair<int,int> P;
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
priority_queue<P,vector<P>,greater<P> > q;
q.push(P(0,s));
while(!q.empty()){
P p=q.top();
q.pop();
int temp=p.second;
if(dis[temp]<p.first){
continue;
}
for(vector<way>::iterator it=v[temp].begin();it!=v[temp].end();it++){
if(dis[it->to]>dis[temp]+it->num){
dis[it->to]=dis[temp]+it->num;
q.push(P(dis[it->to],it->to));
}
}
}
return dis[e];
}
|
高精度
只敲了加法和乘法，减法和加法差不多，除法用减法模拟就好了。
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#define LEN 100
struct Big{
int num[LEN];
Big(){
clear();
}
Big(char *a){
start(a);
}
Big(const Big &a){
for(int i=0;i<LEN;i++){
num[i]=a.num[i];
}
}
void clear(){
memset(num,0,sizeof(num));
num[0]=1;
}
void read(){
char word[LEN];
scanf("%s",word);
start(word);
}
void start(char *a){
num[0]=strlen(a);
for(int i=num[0];i>0;i--){
num[i]=a[num[0]-i]-'0';
}
}
void print(){
for(int i=num[0];i>0;i--){
printf("%d",num[i]);
}
printf("\n");
}
bool big(Big &a){
if(num[0]>a.num[0]){
return true;
}else if(num[0]<a.num[0]){
return false;
}
for(int i=num[0];i>0;i--){
if(num[i]>a.num[i]){
return true;
}else if(num[i]<a.num[i]){
return false;
}
}
return true;
}
void minmin(){
int i=1;
while(num[i]==0){
num[i]=9;
i++;
}
num[i]--;
if(!num[num[0]]){
num[0]--;
}
}
void plusplus(){
int i=1;
while(num[i]==9){
num[i]=0;
i++;
}
num[i]++;
if(num[num[0]+1]){
num[0]++;
}
}
}a;
void swap(Big &a,Big &b){
Big c=a;
a=b;
b=c;
}
Big add(Big &a,Big &b){
Big c;
c.num[0]=max(a.num[0],b.num[0]);
for(int i=1;i<=c.num[0];i++){
c.num[i]+=(a.num[i]+b.num[i])%10;
c.num[i+1]=(a.num[i]+b.num[i])/10;
}
if(c.num[c.num[0]+1]){
c.num[0]++;
}
return c;
}
Big mul(Big &a,Big &b){
Big c;
for(int i=1;i<a.num[0];i++){
for(int j=1;j<b.num[0];j++){
c.num[i+j-1]+=a.num[i]*b.num[j];
c.num[i+j]+=c.num[i+j-1]/10;
c.num[i+j-1]%=10;
}
}
c.num[0]=a.num[0]+b.num[0];
if(c.num[c.num[0]]){
c.num[0]--;
}
return c;
}
|
质数试除法
1
2
3
4
5
6
7
8
9
10
|
bool prime(int a){
int temp=sqrt(a)+0.5;
for(int i=2;i<=temp;i++){
if(a%i==0){
return false;
}
}
return true;
}
|
质数筛法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#define N 100
bool flag[N+5];
void prime(){
int temp=sqrt(N)+0.5;
for(int i=2;i<=temp;i++){
if(!flag[i]){
for(int j=i*2;j<=N;j+=i){
flag[j]=true;
}
}
}
}
|
模运算法则
1
2
3
4
5
|
(a+b)%c=(a%c+b%c)%c
(a-b)%c=(a%c-b%c+c)%c
(a*b)%c=(a%c*b%c)%c
(a^b)%c=((a%c)^b)%c
|