My Templates
ThisIsAName
2020-11-05 22:03:48
# My Templates
>蒟蒻11.5到11.6写的模板在这里了QAQ。
>
>就是分享模板吧，当然如果有dalao可以找到我的bug也是不错的。
>
>提及的题号是用于检测模板的题目。
>
------
## 程序构架
### 一般模板
注意是否需要读入负数
快读（不带负）
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
return 0;
}
```
快读（带负）
> P1001 A+B Problem
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
bool f=false;
while((c=getchar())<'0' || c>'9') if(c=='-') f=true;
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
if(f) x=-x;
}
template <typename T> void Wri(T x)
{
if(x > 9) Wri(x/10);
putchar(x%10^48);
}
template <typename T> void Oput(T x)
{
if(x < 0) putchar('-'), x=-x;
Wri(x);
}//快写一定要和快读判负一起修改
int main()
{
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
return 0;
}
```
## 基础算法
### 二分
二分查找
> P2249 【深基13.例1】查找
这种写法`l`刚好落在交界线右侧，`r`落在左侧。
```cpp
il int Binary(int x)
{
int l=1, r=n;
while(l <= r)
{
int mid = (l+r)>>1;
if(a[mid]<x) l=mid+1; //实现lower_bound
else r=mid-1;
}
return l;
}
```
二分答案
> P1182 数列分段 Section II
其实是另一种写法
```cpp
il LL Binary(LL l, LL r)
{
while(l != r)
{
LL mid = (l&r)+((l^r)>>1);
if(check(mid)) r=mid;
else l=mid+1;
}
return l;
}
```
### 排序
快排
> P1177 【模板】快速排序
```cpp
void qsort(int l, int r)
{
int i=l, j=r, mid=a[rand()%(r-l+1)+l];
do
{
while(a[i]<mid) ++i;
while(a[j]>mid) --j;
if(i<=j)
{
swap(a[i], a[j]);
++i, --j;
}
}while(i<=j);
if(i<r) qsort(i, r);
if(j>l) qsort(l, j);
}
```
第k大数：
> P1923 【深基9.例4】求第 k 小的数
```cpp
void kth_element(int l, int r, int k)
{
int i=l, j=r, mid=a[(l+r>>1)];
do
{
while(a[i]<mid) ++i;
while(a[j]>mid) --j;
if(i<=j)
{
swap(a[i], a[j]);
++i, --j;
}
}while(i<=j);
if(k<=j) kth_element(l, j, k);
else if(k>=i) kth_element(i, r, k);
}
```
归并
> P1177 【模板】快速排序
```cpp
int t[MAXN];
void msort(int l, int r)
{
if(l == r) return ;
int mid=(l+r)>>1, i=l, j=mid+1, k=l;
msort(l, mid);
msort(mid+1, r);
while(i<=mid && j<=r)
{
if(a[i]<a[j]) t[k++] = a[i++];
else t[k++] = a[j++];
}
while(i<=mid) t[k++] = a[i++];
while(j<=r) t[k++] = a[j++];
for(rg int m=l ; m<=r ; ++m)
a[m] = t[m];
}
```
归并求逆序对：
> P1908 逆序对
```cpp
LL ans; //注意long long
int t[MAXN];
void msort(int l, int r)
{
if(l == r) return;
int mid=(l+r)>>1, i=l, j=mid+1, k=l;
msort(l, mid);
msort(mid+1, r);
while(i<=mid && j<=r)
{
if(a[i]<=a[j]) t[k++] = a[i++];
else t[k++] = a[j++], ans += mid-i+1;
}
while(i<=mid) t[k++] = a[i++];
while(j<=r) t[k++] = a[j++];
for(rg int m=l ; m<=r ; ++m)
a[m] = t[m];
}
```
### 倍增
ST表
> P3865 【模板】ST表
```cpp
#define MAXN 100010
#define LOGN 17
int n, m;
int a[MAXN];
int Log[MAXN];
int st[MAXN][LOGN+1]; //数组开够
il void get_Log()
{
Log[0] = -1;
for(rg int i=1 ; i<=n ; ++i)
Log[i] = Log[i>>1] + 1;
}
il void prepare()
{
for(rg int i=1 ; i<=n ; ++i)
st[i][0] = a[i];
for(rg int i=1 ; i<=Log[n] ; ++i)
for(rg int j=1 ; j<=n&&(j+(1<<i-1))<=n ; ++j)//注意这个条件：会RE
st[j][i] = max(st[j][i-1], st[j+(1<<i-1)][i-1]);
}
il int query(int l, int r)
{
int t = Log[r-l+1];
return max(st[l][t], st[r-(1<<t)+1][t]);
}
int main()
{
Iput(n), Iput(m);
get_Log(); //线段树建树同理
for(rg int i=1 ; i<=n ; ++i)
Iput(a[i]);
prepare(); //线段树建树同理
for(rg int i=1 ; i<=m ; ++i)
{
int l, r;
Iput(l), Iput(r);
Oput(query(l, r));
putchar('\n');
}
return 0;
}
```
### 高精度
## 数据结构
### 链表
> P1996 约瑟夫问题
删除操作
```cpp
r[l[p]] = r[p];
l[r[p]] = l[p];
```
### 栈
### 队列
循环队列
```cpp
#define MAXQ (1<<...)
int q[MAXQ], l=1, r;
q[++r & MAXQ-1] = ...
q[l++ & MAXQ-1] = ...
q[--l & MAXQ-1] = ...
```
单调队列
```cpp
for(rg int i=1 ; i<=n ; ++i) //注意n的取值
{
if(l<=r && q[l]<i-m) ++l; //注意m的取值
...
while(l<=r && cmp(f(q[r]), f(i))) --r;
q[++r] = i;
}
```
优先队列（其实是堆 //STL香
```cpp
priority_queue <Type> q; //默认大根堆
```
### 堆
STL见上
对顶堆
> P1168 中位数
```cpp
priority_queue <int> bigq, smlq;
int main()
{
int n;
Iput(n);
for(rg int i=1 ; i<=n ; i++)
{
int t;
Iput(t);
if(i&1)
{
smlq.push(-t);
bigq.push(-smlq.top());
smlq.pop();
Oput(bigq.top());
putchar('\n');
}
else
{
bigq.push(t);
smlq.push(-bigq.top());
bigq.pop();
}
}
return 0;
}
//总之插入操作要先插入另一个堆再弹出top插入这一个堆（无视常数
```
### 并查集
> P3367 【模板】并查集
普通并查集
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 10010
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int n, m;
int pre[MAXN];
il void ini_f(int n)
{
for(rg int i=1 ; i<=n ; ++i)
pre[i] = i;
}
int find_f(int x)
{
if(pre[x] == x) return x;
return find_f(pre[x]);
}
il void union_f(int u, int v)
{
int fu = find_f(u), fv = find_f(v);
if(fu != fv) pre[fu] = fv;
}
il bool judge_f(int u, int v)
{
return find_f(u) == find_f(v);
}
int main()
{
Iput(n), Iput(m);
ini_f(n);
for(rg int i=1 ; i<=m ; ++i)
{
int op, x, y;
Iput(op), Iput(x), Iput(y);
if(op == 1)
{
union_f(x, y);
}
else
{
putchar(judge_f(x, y) ? 'Y' : 'N');
putchar('\n');
}
}
return 0;
}
```
自己口糊的按秩合并+路径压缩
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 10010
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int n, m;
int pre[MAXN];
il void ini_f()
{
memset(pre, -1, sizeof pre);
}
int find_f(int x)
{
if(pre[x] < 0) return x;
return pre[x] = find_f(pre[x]);
}
il void union_f(int a, int b)
{
int fa = find_f(a), fb = find_f(b);
if(fa == fb) return ;
if(pre[fa] < pre[fb]) pre[fa] += pre[fb], pre[fb] = fa;
else pre[fb] += pre[fa], pre[fa] = fb;
}
il bool judge_f(int u, int v)
{
return find_f(u) == find_f(v);
}
int main()
{
Iput(n), Iput(m);
ini_f(); //注意
for(rg int i=1 ; i<=m ; ++i)
{
int op, x, y;
Iput(op), Iput(x), Iput(y);
if(op == 1)
{
union_f(x, y);
}
else
{
putchar(judge_f(x, y) ? 'Y' : 'N');
putchar('\n');
}
}
return 0;
}
```
### 树状数组
普通板子
```cpp
struct TreeArr {
int c[MAXN];
il void add(int pos, int v)
{
for(rg int i=pos ; i<=n ; i+=i&-i)
c[i] += v;
}
il int ask(int pos)
{
int ret = 0;
for(rg int i=pos ; i ; i-=i&-i)
ret += c[i];
return ret;
}
}ta;
```
瞎搞平衡树：
> P3369 【模板】普通平衡树
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#define il inline
#define rg register
#define MAXN 100010
#define ENDL putchar('\n')
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
bool f=false;
while((c=getchar())<'0' || c>'9') if(c=='-') f=true;//这个板子gg了好多次都是因为快读判负
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
if(f) x=-x;
}
template <typename T> void Wri(T x)
{
if(x > 9) Wri(x/10);
putchar(x%10^48);
}
template <typename T> void Oput(T x)
{
if(x < 0) putchar('-'), x=-x;
Wri(x);
}//快写一定要和快读判负一起修改
int n;
struct Qs {
int op, x;
}q[MAXN];
int lsh[MAXN], top;
struct TreeArr {
int c[MAXN];
il void add(int pos)
{
for(rg int i=pos ; i<=top ; i+=i&-i)
++c[i];
}
il void del(int pos)
{
for(rg int i=pos ; i<=top ; i+=i&-i)
--c[i];
}
il int ask(int pos)
{
int ret = 0;
for(rg int i=pos ; i ; i-=i&-i)
ret += c[i];
return ret;
}
il int kth(int k)
{
int p = 0;
for(rg int i=17 ; ~i ; --i)
{
p += 1<<i;
if(p>top || c[p]>=k) //注意c[p](不是c[i]..)
p -= 1<<i;
else
k -= c[p];
}
return p+1;
}
il int lft(int x)
{
return kth(ask(x-1));
}
il int rit(int x)
{
return kth(ask(x)+1);
}
}ta;
int main()
{
Iput(n);
for(rg int i=1 ; i<=n ; ++i)
Iput(q[i].op), Iput(q[i].x), lsh[i] = q[i].x;
sort(lsh+1, lsh+n+1);
top = unique(lsh+1, lsh+n+1) - lsh - 1;
for(rg int i=1 ; i<=n ; ++i)
{
int op=q[i].op, x=q[i].x;
if(op != 4) x = lower_bound(lsh+1, lsh+top+1, x) - lsh;
if(op == 1)
{
ta.add(x);
}
else if(op == 2)
{
ta.del(x);
}
else if(op == 3)
{
Oput(ta.ask(x-1)+1);
ENDL;
}
else if(op == 4)
{
Oput(lsh[ta.kth(x)]);
ENDL;
}
else if(op == 5)
{
Oput(lsh[ta.lft(x)]);
ENDL;
}
else
{
Oput(lsh[ta.rit(x)]);
ENDL;
}
}
return 0;
}
```
### 线段树
普通线段树
> P3373 【模板】线段树 2
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 100010
using namespace std;
typedef long long LL; //注意
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int n, m, p;
LL a[MAXN];
il void Mod(LL &a)
{
if(a>=p) a%=p; //注意：最好不要用减
}
il void add(LL &a, LL b)
{
a += b;
Mod(a);
}
il void mul(LL &a, LL b)
{
a *= b;
Mod(a);
}
struct SGtree {
#define MID int mid=(l+r)>>1
#define L ls(k),l,mid
#define R rs(k),mid+1,r
struct Node {
LL v, la, lm;
}t[MAXN<<2];
il int ls(int k) {return k<<1;}
il int rs(int k) {return k<<1|1;}
il void pu(int k)
{
t[k].v = t[ls(k)].v +t[rs(k)].v;
Mod(t[k].v);
}
void build(int k, int l, int r)
{
t[k].la = 0;
t[k].lm = 1;
if(l == r)
{
t[k].v = a[l];
return ;
}
MID;
build(L);
build(R);
pu(k);
}
il void fa(int k, int l, int r, LL v)
{
add(t[k].v, v*(r-l+1));
add(t[k].la, v);
}
il void fm(int k, LL v)
{
mul(t[k].v, v);
mul(t[k].la, v);
mul(t[k].lm, v);
}
il void pd(int k, int l, int mid, int r)
{
fm(ls(k), t[k].lm);
fm(rs(k), t[k].lm);
fa(L, t[k].la);
fa(R, t[k].la);
t[k].la = 0;
t[k].lm = 1;
}
void modify_a(int k, int l, int r, int li, int ri, LL v)
{
if(li<=l && r<=ri) return fa(k, l, r, v);
MID;
pd(k, l, mid, r);
if(li<=mid) modify_a(L, li, ri, v);
if(mid<ri) modify_a(R, li, ri, v);
pu(k);
}
void modify_m(int k, int l, int r, int li, int ri, LL v)
{
if(li<=l && r<=ri) return fm(k, v);
MID;
pd(k, l, mid, r);
if(li<=mid) modify_m(L, li, ri, v);
if(mid<ri) modify_m(R, li, ri, v);
pu(k);
}
LL query(int k, int l, int r, int li, int ri)
{
if(li<=l && r<=ri) return t[k].v;
MID;
LL ret=0;
pd(k, l, mid, r);
if(li<=mid) add(ret, query(L, li, ri));
if(mid<ri) add(ret, query(R, li, ri));
return ret;
}
}sg;
int main()
{
Iput(n), Iput(m), Iput(p);
for(rg int i=1 ; i<=n ; ++i)
Iput(a[i]);
sg.build(1, 1, n);
for(rg int i=1 ; i<=m ; ++i)
{
int op, x, y, k;
Iput(op), Iput(x), Iput(y);
if(op == 1)
{
Iput(k);
sg.modify_m(1, 1, n, x, y, k);
}
else if(op == 2)
{
Iput(k);
sg.modify_a(1, 1, n, x, y, k);
}
else
{
Oput(sg.query(1, 1, n, x, y));
putchar('\n');
}
}
return 0;
}
```
扫描线
```cpp
```
### zkw线段树
> P3374 【模板】树状数组 1
```cpp
//记得加M啊
struct ZKW {
LL t[MAXN<<3];
int M;
il void pu(int k)
{
t[k] = t[k<<1] + t[k<<1|1];
}
il void build()
{
for(M=1 ; M<n+2 ; M<<=1);
for(rg int i=M+1 ; i<=M+n ; ++i)
Iput(t[i]);
for(rg int i=M ; i ; --i)
pu(i);
}
il void modify(int pos, LL v)
{
for(rg int i=M+pos ; i ; i>>=1)
t[i] += v;
}
il LL query(int l, int r)
{
LL ret = 0;
for(rg int i=M+l-1, j=M+r+1 ; i^j^1 ; i>>=1, j>>=1)
{
if(~i&1) ret += t[i^1];
if(j&1) ret += t[j^1];
}
return ret;
}
}sg;
```
### 分块
> P2357 守墓人
```cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#define il inline
#define rg register
#define int long long
#define MAXN 200010
#define RTN 500
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
bool f=false;
while((c=getchar())<'0' || c>'9') if(c=='-') f=true;
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
if(f) x=-x;
}
template <typename T> void Wri(T x)
{
if(x > 9) Wri(x/10);
putchar(x%10^48);
}
template <typename T> il void Oput(T x)
{
if(x < 0) putchar('-'), x=-x;
Wri(x);
}
int n, m, rtn;
int a[MAXN], lazy[RTN], pos[MAXN], sum[RTN];
il int L(int k)
{
return (pos[k]-1)*rtn+1;
}
il int R(int k)
{
return pos[k]*rtn;
}
il void change(int l, int r, int v)
{
for(rg int i=l, top=min(r, R(l)) ; i<=top ; ++i) a[i]+=v, sum[pos[i]]+=v;
for(rg int i=pos[l]+1 ; i<=pos[r]-1 ; ++i) lazy[i] += v;
if(pos[l] != pos[r])
for(rg int i=L(r) ; i<=r ; ++i)
a[i]+=v, sum[pos[i]]+=v;
}
il int query(int l, int r)
{
int ret = 0;
for(rg int i=l, top=min(r, R(l)) ; i<=top ; ++i) ret += a[i]+lazy[pos[i]];
for(rg int i=pos[l]+1 ; i<=pos[r]-1 ; ++i) ret += sum[i]+rtn*lazy[i];
if(pos[l] != pos[r])
for(rg int i=L(r) ; i<=r ; ++i)
ret += a[i]+lazy[pos[i]];
return ret;
}
signed main()
{
Iput(n), Iput(m);
rtn = sqrt(n);
for(rg int i=1 ; i<=n ; ++i)
{
Iput(a[i]);
pos[i] = (i-1)/rtn+1;
sum[pos[i]] += a[i];
}
for(rg int i=1 ; i<=m ; ++i)
{
int op, l, r, k;
Iput(op);
if(op == 1)
{
Iput(l), Iput(r), Iput(k);
change(l, r, k);
}
else if(op == 2)
{
Iput(k);
a[1] += k;
sum[1] += k;
}
else if(op == 3)
{
Iput(k);
a[1] -= k;
sum[1] -= k;
}
else if(op == 4)
{
Iput(l), Iput(r);
Oput(query(l, r));
putchar('\n');
}
else if(op == 5)
{
Oput(a[1]+lazy[1]);
putchar('\n');
}
}
return 0;
}
```
## 图论
### 最短路
#### Floyd
> P5905 【模板】Johnson 全源最短路(n^3 68分？)
```cpp
for(rg int i=1 ; i<=n ; ++i)
for(rg int j=1 ; j<=n ; ++j)
dis[i][j] = INF;
for(rg int i=1 ; i<=n ; ++i)
dis[i][i] = 0;
for(rg int i=1 ; i<=m ; ++i)
{
int u, v, w;
Iput(u), Iput(v), Iput(w);
Min(dis[u][v], w);
}
for(rg int k=1 ; k<=n ; ++k)
for(rg int i=1 ; i<=n ; ++i)
for(rg int j=1 ; j<=n ; ++j)
{
if(dis[i][k]==INF || dis[k][j]==INF) continue;
Min(dis[i][j], dis[i][k]+dis[k][j]);
}
for(rg int i=1 ; i<=n ; ++i) //负环
if(dis[i][i] < 0)
{
Oput(-1);
return 0;
}
```
#### SPFA(+带容错SLF)
> P3371 【模板】单源最短路径（弱化版）
```cpp
LL dis[MAXN];
#define MAXQ (1<<14)
int q[MAXQ], l=MAXN<<1, r=l-1;
bool in_q[MAXN];
il void spfa()
{
for(rg int i=1 ; i<=n ; ++i)
dis[i] = 0x7fffffff;
dis[s] = 0;
q[++r & MAXQ-1] = s;
in_q[s] = true;
while(l <= r)
{
int u = q[l++ & MAXQ-1];
in_q[u] = false;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x, w = e[i].w;
if(dis[v] > dis[u]+w)
{
dis[v] = dis[u]+w;
if(!in_q[v])
{
if(dis[v] > dis[q[l & MAXQ-1]]+1) q[++r & MAXQ-1] = v;
else q[--l & MAXQ-1] = v;
in_q[v] = true;
}
}
}
}
}
```
#### Dijkstra
> P4779 【模板】单源最短路径（标准版）
```cpp
int dis[MAXN];
priority_queue <pair<int, int> > q;
bool vis[MAXN];
il void dijkstra()
{
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
q.push(make_pair(0, s));
while(q.size())
{
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x, w = e[i].w;
if(dis[v] > dis[u]+w)
{
dis[v] = dis[u]+w;
q.push(make_pair(-dis[v], v));
}
}
}
}
```
#### Johnson
> P5905 【模板】Johnson 全源最短路
```cpp
#include<cstdio>
#include<iostream>
#include<queue>
#define il inline
#define rg register
#define MAXN 3010
#define MAXM 6010
#define INF 1000000000
using namespace std;
typedef long long LL;
template <typename T> il void Iput(T &x)
{
char c;
bool f=false;
while((c=getchar())<'0' || c>'9') if(c=='-') f=true;
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
if(f) x = -x;
}
template <typename T> void Wri(T x)
{
if(x > 9) Wri(x/10);
putchar(x%10^48);
}
template <typename T> il void Oput(T x)
{
if(x < 0) putchar('-'), x=-x;
Wri(x);
}
struct Edge {
int x, nex, w;
}e[MAXN+MAXM];
int head[MAXN], tote;
il void ae(int u, int v, int w)
{
e[++tote].x = v;
e[tote].w = w;
e[tote].nex = head[u];
head[u] = tote;
}
int n, m;
int h[MAXN];
#define MAXQ (1<<14)
int qs[MAXQ], l=MAXQ<<1, r=l-1;
bool in_q[MAXN];
int len[MAXN];
il bool spfa()
{
for(rg int i=1 ; i<=n ; ++i)
h[i] = INF;
h[0] = 0;
qs[++r & MAXQ-1] = 0;
in_q[0] = true;
while(l <= r)
{
int u = qs[l++ & MAXQ-1];
in_q[u] = false;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x, w = e[i].w;
if(h[v] > h[u]+w)
{
len[v] = len[u] + 1;
if(len[v] > n) return true; //注意应该>n，因为建了一个超级原点
h[v] = h[u]+w;
if(!in_q[v])
{
if(h[v] > h[qs[l & MAXQ-1]]+1) qs[++r & MAXQ-1] = v;
else qs[--l & MAXQ-1] = v;
in_q[v] = true;
}
}
}
}
return false;
}
priority_queue <pair<int, int> > q;
int dis[MAXN];
bool vis[MAXN];
il void dijkstra(int s)
{
for(rg int i=1 ; i<=n ; ++i)
{
dis[i] = INF;
vis[i] = 0;
}
dis[s] = 0;
q.push(make_pair(0, s));
while(q.size())
{
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x, w=e[i].w;
if(dis[v] > dis[u]+w)
{
dis[v] = dis[u]+w;
q.push(make_pair(-dis[v], v));
}
}
}
}
int main()
{
Iput(n), Iput(m);
for(rg int i=1 ; i<=m ; ++i)
{
int u, v, w;
Iput(u), Iput(v), Iput(w);
ae(u, v, w);
}
for(rg int i=1 ; i<=n ; ++i)
ae(0, i, 0);
if(spfa())
{
putchar('-');
putchar('1');
return 0;
}
for(rg int u=1 ; u<=n ; ++u)
for(rg int i=head[u] ; i ; i=e[i].nex)
e[i].w += h[u]-h[e[i].x];
for(rg int u=1 ; u<=n ; ++u)
{
LL ans = 0;
dijkstra(u);
for(rg int i=1 ; i<=n ; ++i)
ans += (LL)i*(dis[i]==INF ? INF : dis[i]-h[u]+h[i]);
Oput(ans);
putchar('\n');
}
return 0;
}
```
#### 差分约束
```cpp
```
### 最小生成树
> P3366 【模板】最小生成树
#### Prim
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 5010
#define MAXM 200010
#define INF 0x3f3f3f3f
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
struct Edge {
int x, nex, w;
}e[MAXM<<1];
int head[MAXN], tote;
il void ae(int u, int v, int w)
{
e[++tote].x = v;
e[tote].w = w;
e[tote].nex = head[u];
head[u] = tote;
}
int n, m;
int dis[MAXN];
bool vis[MAXN];
int main()
{
memset(dis, 0x3f, sizeof dis);
Iput(n), Iput(m);
for(rg int i=1 ; i<=m ; ++i)
{
int u, v, w;
Iput(u), Iput(v), Iput(w);
ae(u, v, w);
ae(v, u, w);
}
dis[1] = 0;
for(rg int k=1 ; k<n ; ++k)
{
int u = 0;
for(rg int i=1 ; i<=n ; ++i)
if(!vis[i] && (!u || dis[u]>dis[i]))
u = i;
vis[u] = true;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x, w = e[i].w;
if(!vis[v] && dis[v]>w) //注意dis的含义为最小生成树的边长
dis[v] = w;
}
}
int ans = 0;
for(rg int i=1 ; i<=n ; ++i)
{
if(dis[i] == INF)
{
printf("orz\n");
return 0;
}
ans += dis[i];
}
Oput(ans);
return 0;
}
```
#### Kruskal
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define il inline
#define rg register
#define MAXN 5010
#define MAXM 200010
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
struct Edge_k {
int u, v, w;
}e[MAXM];
bool operator < (Edge_k x, Edge_k y)
{
return x.w < y.w;
}
int pre[MAXN];
int find_f(int x)
{
if(pre[x] < 0) return x;
return pre[x] = find_f(pre[x]);
}
il void union_f(int a, int b)
{
int fa=find_f(a), fb=find_f(b);
if(fa == fb) return ;
if(pre[fa] < pre[fb]) pre[fa]+=pre[fb], pre[fb]=fa;
else pre[fb]+=pre[fa], pre[fa]=fb;
}
il bool judge_f(int a, int b)
{
return find_f(a) == find_f(b);
}
int n, m;
int ans;
int main()
{
memset(pre, -1, sizeof pre);
Iput(n), Iput(m);
for(rg int i=1 ; i<=m ; ++i)
Iput(e[i].u), Iput(e[i].v), Iput(e[i].w);
sort(e+1, e+m+1);
for(rg int i=1 ; i<=m ; ++i)
{
int u=e[i].u, v=e[i].v;
if(!judge_f(u, v))
{
union_f(u, v);
ans += e[i].w;
}
}
int fa = find_f(1);
for(rg int i=2 ; i<=n ; ++i)
if(find_f(i) != fa)
{
printf("orz\n");
return 0;
}
Oput(ans);
return 0;
}
```
### Tarjan
#### 割点
> P3388 【模板】割点（割顶）
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 20010
#define MAXM 100010
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
struct Edge {
int x, nex;
}e[MAXM<<1];
int head[MAXN], tote;
il void ae(int u, int v)
{
e[++tote].x = v;
e[tote].nex = head[u];
head[u] = tote;
}
il void Min(int &a, int b)
{
if(a > b) a = b;
}
int n, m;
int root;
int low[MAXN], dfn[MAXN], dtr;
bool cut[MAXN];
void tarjan(int u)
{
int flag = 0;
low[u] = dfn[u] = ++dtr;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x;
if(!dfn[v])
{
tarjan(v);
Min(low[u], low[v]);
if(dfn[u]<=low[v])
{
++flag;
if(u!=root || flag>1)
cut[u] = true;
}
}
else
{
Min(low[u], dfn[v]);
}
}
}
int main()
{
Iput(n), Iput(m);
for(rg int i=1 ; i<=m ; ++i)
{
int u, v;
Iput(u), Iput(v);
ae(u, v);
ae(v, u);
}
for(rg int i=1 ; i<=n ; ++i)
if(!dfn[i])
{
root = i;
tarjan(root);
}
int ans = 0;
for(rg int i=1 ; i<=n ; ++i)
if(cut[i])
++ans;
Oput(ans);
putchar('\n');
for(rg int i=1 ; i<=n ; ++i)
if(cut[i])
Oput(i), putchar(' ');
return 0;
}
```
#### 割边
```cpp
struct Edge {
int x, nex;
}e[MAXM<<1];
int head[MAXN], tote=1; //注意这里初值为1才满足异或配偶性质
il void ae(int u, int v)
{
e[++tote].x = v;
e[tote].nex = head[u];
head[u] = tote;
}
int n, m, ans;
int dfn[MAXN], dtr, low[MAXN];
bool cut[MAXM<<1];
void tarjan(int u, int in_edge) //较割点多一个参数：入边
{
//这里无须特判根节点，无须flag
low[u] = dfn[u] = ++dtr;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x;
if(!dfn[v])
{
tarjan(v, i);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u])
{
cut[i] = cut[i^1] = true;
++ans; //由于搜索树上每条边只被搜索一次，可直接++ans
}
}
else if(i != (in_edge^1)) //注意判反边，防止被父亲更新
{
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
...//Input
for(rg int i=1 ; i<=n ; ++i)
if(!dfn[i])
tarjan(i, 0); //这里注意不要写-1等等负数，不满足异或性质
Oput(ans);
return 0;
}
```
#### 强连通分量：缩点
> P3387 【模板】缩点
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 10010
#define MAXM 100010
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
struct Star {
struct Edge {
int x, nex;
}e[MAXM];
int head[MAXN], tote;
il void ae(int u, int v)
{
e[++tote].x = v;
e[tote].nex = head[u];
head[u] = tote;
}
}Nor, Scc;
il void Min(int &a, int b)
{
if(a > b) a = b;
}
il void Max(int &a, int b)
{
if(a < b) a = b;
}
int n, m;
int w[MAXN];
int low[MAXN], dfn[MAXN], dtr;
int scc, bel[MAXN], stk[MAXN], top, wscc[MAXN];
bool in_s[MAXN];
void tarjan(int u)
{
low[u] = dfn[u] = ++dtr;
stk[++top] = u;
in_s[u] = true;
for(rg int i=Nor.head[u] ; i ; i=Nor.e[i].nex)
{
int v = Nor.e[i].x;
if(!dfn[v])
{
tarjan(v);
Min(low[u], low[v]);
}
else if(in_s[v])
{
Min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u])
{
int t;
++scc;
do
{
t = stk[top--];
in_s[t] = false;
bel[t] = scc;
wscc[scc] += w[t];
}while(t != u);
}
}
int dp[MAXN], ans;
int main()
{
Iput(n), Iput(m);
for(rg int i=1 ; i<=n ; ++i)
Iput(w[i]);
for(rg int i=1 ; i<=m ; ++i)
{
int u, v;
Iput(u), Iput(v);
Nor.ae(u, v);
}
for(rg int i=1 ; i<=n ; ++i)
if(!dfn[i])
tarjan(i);
for(rg int u=1 ; u<=n ; ++u)
for(rg int i=Nor.head[u] ; i ; i=Nor.e[i].nex)
{
int v = Nor.e[i].x;
if(bel[u] != bel[v])
Scc.ae(bel[u], bel[v]);
}
for(rg int u=scc ; u ; --u)
{
dp[u] += wscc[u];
Max(ans, dp[u]);
for(rg int i=Scc.head[u] ; i ; i=Scc.e[i].nex)
Max(dp[Scc.e[i].x], dp[u]);
}
Oput(ans);
return 0;
}
```
### 树
#### 直径
```cpp
```
#### 倍增
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 500010
#define MAXM 500010
#define LOGN 19
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
struct Edge {
int x, nex;
}e[MAXM<<1];
int head[MAXN], tote;
il void ae(int u, int v)
{
e[++tote].x = v;
e[tote].nex = head[u];
head[u] = tote;
}
int n, m, s;
int fa[MAXN][LOGN+1], dep[MAXN]; //注意+1
void get_fa(int u, int f)
{
dep[u] = dep[f] + 1;
fa[u][0] = f;
for(rg int i=1 ; i<=LOGN ; ++i)
fa[u][i] = fa[fa[u][i-1]][i-1];
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x;
if(v == f) continue;
get_fa(v, u);
}
}
il int lca(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
for(rg int i=LOGN ; ~i ; --i)
if(dep[fa[u][i]] >= dep[v])
u = fa[u][i];
if(u == v) return u;
for(rg int i=LOGN ; ~i ; --i)
if(fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
return fa[u][0];
}
int main()
{
Iput(n), Iput(m), Iput(s);
for(rg int i=1 ; i<n ; ++i)
{
int u, v;
Iput(u), Iput(v);
ae(u, v);
ae(v, u);
}
get_fa(s, s);
for(rg int i=1 ; i<=n ; ++i)
{
int u, v;
Iput(u), Iput(v);
Oput(lca(u, v));
putchar('\n');
}
return 0;
}
```
#### 树剖
> P3384 【模板】轻重链剖分
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 100010
#define int long long
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
struct Edge {
int x, nex;
}e[MAXN<<1];
int head[MAXN], tote;
il void ae(int u, int v)
{
e[++tote].x = v;
e[tote].nex = head[u];
head[u] = tote;
}
int n, m, r, p;
int w[MAXN];
il void Mod(int &a)
{
if(a >= p) a %= p;
}
il void add(int &a, int b)
{
a += b;
Mod(a);
}
struct SGtree {
#define MID int mid=(l+r)>>1
#define L ls(k),l,mid
#define R rs(k),mid+1,r
int a[MAXN];
struct Node {
int v, lazy;
}t[MAXN<<2];
il int ls(int k) {return k<<1;}
il int rs(int k) {return k<<1|1;}
il void pu(int k)
{
t[k].v = t[ls(k)].v + t[rs(k)].v;
Mod(t[k].v); //注意取模
}
void build(int k, int l, int r)
{
if(l == r)
{
t[k].v = a[l];
Mod(t[k].v);
return ;
}
MID;
build(L);
build(R);
pu(k);
}
il void f(int k, int l, int r, int v)
{
add(t[k].v, v*(r-l+1));
add(t[k].lazy, v);
}
il void pd(int k, int l, int mid, int r)
{
if(!t[k].lazy) return ;
f(L, t[k].lazy);
f(R, t[k].lazy);
t[k].lazy = 0;
}
void modify(int k, int l, int r, int li, int ri, int v)
{
if(li<=l && r<=ri) return f(k, l, r, v);
MID;
pd(k, l, mid, r);
if(li<=mid) modify(L, li, ri, v);
if(mid<ri) modify(R, li, ri, v);
pu(k);
}
int query(int k, int l, int r, int li, int ri)
{
if(li<=l && r<=ri) return t[k].v;
MID, ret=0;
pd(k, l, mid, r);
if(li<=mid) add(ret, query(L, li, ri));
if(mid<ri) add(ret, query(R, li, ri)); //注意取模：写add
return ret;
}
}sg;
struct Decomposition {
int siz[MAXN], dep[MAXN], wson[MAXN], fa[MAXN], top[MAXN], dfn[MAXN], dtr;
void dfs1(int u, int f)
{
fa[u] = f;
dep[u] = dep[f] + 1;
siz[u] = 1;
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x;
if(v == f) continue;
dfs1(v, u);
siz[u] += siz[v];
if(!wson[u] || siz[wson[u]]<siz[v])
wson[u] = v;
}
}
void dfs2(int u, int topf)
{
top[u] = topf;
dfn[u] = ++dtr;
sg.a[dtr] = w[u];
if(!wson[u]) return ; //注意处理重儿子
dfs2(wson[u], topf);
for(rg int i=head[u] ; i ; i=e[i].nex)
{
int v = e[i].x;
if(v==fa[u] || v==wson[u]) continue;
dfs2(v, v);
}
}
il void modify_lca(int u, int v, int val)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
sg.modify(1, 1, n, dfn[top[u]], dfn[u], val);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
sg.modify(1, 1, n, dfn[u], dfn[v], val);
}
il int query_lca(int u, int v)
{
int ret = 0;
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
add(ret, sg.query(1, 1, n, dfn[top[u]], dfn[u]));
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v); //想清楚那个更浅
add(ret, sg.query(1, 1, n, dfn[u], dfn[v]));
return ret;
}
il void modify_son(int x, int val)
{
sg.modify(1, 1, n, dfn[x], dfn[x]+siz[x]-1, val);
}
il int query_son(int x)
{
return sg.query(1, 1, n, dfn[x], dfn[x]+siz[x]-1);
}
}dc;
signed main()
{
Iput(n), Iput(m), Iput(r), Iput(p);
for(rg int i=1 ; i<=n ; ++i)
Iput(w[i]);
for(rg int i=1 ; i<n ; ++i) //n-1边
{
int u, v;
Iput(u), Iput(v);
ae(u, v);
ae(v, u);
}
dc.dfs1(r, r); //remember
dc.dfs2(r, r);
sg.build(1, 1, n);
for(rg int i=1 ; i<=m ; ++i)
{
int op, x, y, z;
Iput(op);
if(op == 1)
{
Iput(x), Iput(y), Iput(z);
dc.modify_lca(x, y, z);
}
else if(op == 2)
{
Iput(x), Iput(y);
Oput(dc.query_lca(x, y));
putchar('\n');
}
else if(op == 3)
{
Iput(x), Iput(z);
dc.modify_son(x, z);
}
else
{
Iput(x);
Oput(dc.query_son(x));
putchar('\n');
}
}
return 0;
}
```
### 欧拉路
> P1341 无序字母对
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 'z'
#define MINN 'A'
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int n;
int mp[MAXN+10][MAXN+10];
int deg[MAXN+10];
int stk[10000], top;
void dfs(int u)
{
for(rg int i=MINN ; i<=MAXN ; ++i)
if(mp[u][i])
{
--mp[u][i];
--mp[i][u];
dfs(i);
}
stk[++top] = u;
}
int main()
{
Iput(n);
for(rg int i=1 ; i<=n ; ++i)
{
int u, v;
while(!( ((u=getchar())>='a'&&u<='z') || (u>='A'&&u<='Z') ));
while(!( ((v=getchar())>='a'&&v<='z') || (v>='A'&&v<='Z') ));
++mp[u][v];
++mp[v][u];
++deg[u];
++deg[v];
}
int ctr=0, s=0;
for(rg int i=MINN ; i<=MAXN ; ++i)
if(deg[i]&1)
{
if(!s) s=i;
++ctr;
}
if(!ctr)
{
for(rg int i=MINN ; i<=MAXN ; ++i)
if(deg[i])
{
if(!s) s=i;
break;
}
}
if(ctr!=0 && ctr!=2)
{
printf("No Solution\n");
return 0;
}
dfs(s);
if(top != n+1)
{
printf("No Solution\n");
return 0;
}
for(rg int i=top ; i ; --i)
putchar(stk[i]);
return 0;
}
```
## 数学相关
### 快速幂
> P1226 【模板】快速幂||取余运算
多取模
```cpp
int a, k, p;
il void Mod(int &a)
{
if(a >= p) a %= p;
}
il void mul(int &a, int b)
{
a *= b;
Mod(a);
}
il int qpow(int a, int k)
{
int ret = 1;
while(k)
{
if(k&1) mul(ret, a);
mul(a, a);
k >>= 1;
}
return ret%p; //不模的话这样会挂：x^0 mod 1=1
}
signed main()
{
Iput(a), Iput(k), Iput(p);
printf("%lld^%lld mod %lld=%lld\n", a, k, p, qpow(a, k));
return 0;
}
```
### 慢速乘
```cpp
int a, k, p;
il void Mod(int &a)
{
if(a >= p) a %= p;
}
il void add(int &a, int b)
{
a += b;
Mod(a);
}
il void mul(int &a, int b)
{
int ret = 0;
while(b)
{
if(b&1) add(ret, a);
add(a, a);
b >>= 1;
}
a = ret;
}
il int qpow(int a, int k)
{
int ret = 1;
while(k)
{
if(k&1) mul(ret, a);
mul(a, a);
k >>= 1;
}
return ret%p;
}
signed main()
{
Iput(a), Iput(k), Iput(p);
printf("%lld^%lld mod %lld=%lld\n", a, k, p, qpow(a, k));
return 0;
}
```
### 线性筛素数
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 100000010
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int N, q;
int prime[MAXN], mdiv[MAXN], tot;
il void get_prime(int n)
{
for(rg int i=2 ; i<=n ; ++i)
{
if(!mdiv[i])
{
prime[++tot] = i;
mdiv[i] = i;
}
for(rg int j=1 ; j<=tot&&prime[j]*i<=n ; ++j)
{
mdiv[i*prime[j]] = prime[j];
if(mdiv[i] == prime[j]) break;
}
}
}
int main()
{
Iput(N), Iput(q);
get_prime(N);
for(rg int i=1 ; i<=q ; ++i)
{
int t;
Iput(t);
Oput(prime[t]);
putchar('\n');
}
return 0;
}
```
### gcd
> P4549 【模板】裴蜀定理
```cpp
il int gcd(int a, int b)
{
while(a^=b^=a^=b%=a);
return b;
}
```
### exgcd
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define int long long
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
bool f=false;
while((c=getchar())<'0' || c>'9') if(c=='-') f=true;
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
if(f) x=-x;
}
template <typename T> void Wri(T x)
{
if(x > 9) Wri(x/10);
putchar(x%10^48);
}
template <typename T> il void Oput(T x)
{
if(x < 0) putchar('-'), x=-x;
Wri(x);
}
int T;
void exgcd(int a, int b, int &g, int &x, int &y)
{
if(!b)
{
x=1, y=0, g=a;
}
else
{
exgcd(b, a%b, g, y, x);
y -= x*(a/b);
}
}
signed main()
{
Iput(T);
for(rg int rp=1 ; rp<=T ; ++rp)
{
int a, b, c;
Iput(a), Iput(b), Iput(c);
int x, y, g;
exgcd(a, b, g, x, y);
if(c%g)
{
Oput(-1);
putchar('\n');
continue;
}
a /= g;
b /= g;
// c /= g;
x *= c/g;
y *= c/g;
int xmin = (x%b+b)%b;
int ymin = (y%a+a)%a;
if(!xmin) xmin += b;
if(!ymin) ymin += a;
a *= g;
b *= g;
// c *= g;
int xmax = (c-b*ymin)/a;
int ymax = (c-a*xmin)/b;
a /= g;
b /= g;
if(xmax<=0 || ymax<=0)
{
Oput(xmin);
putchar(' ');
Oput(ymin);
putchar('\n');
}
else
{
Oput((xmax-xmin)/b+1);
putchar(' ');
Oput(xmin);
putchar(' ');
Oput(ymin);
putchar(' ');
Oput(xmax);
putchar(' ');
Oput(ymax);
putchar('\n');
}
}
return 0;
}
```
### 高斯消元
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 55
using namespace std;
typedef double DB;
il DB Abs(DB x)
{
if(x < 0) return -x;
return x;
}
il bool e0(DB x)
{
return Abs(x) < 1e-7;
}
int n;
DB a[MAXN][MAXN];
il void gauss()
{
int rank = 0;
for(rg int c=1 ; c<=n ; ++c)
{
int pos = 0;
for(rg int r=rank+1 ; r<=n ; ++r)
if(!e0(a[r][c]))
{
pos = r;
break;
}
if(!pos) continue;
++rank;
for(rg int i=c ; i<=n+1 ; ++i)
swap(a[rank][i], a[pos][i]);
for(rg int r=1 ; r<=n ; ++r)
{
if(r == rank) continue;
DB t = -a[r][c]/a[rank][c];
for(rg int i=c ; i<=n+1 ; ++i)
a[r][i] += t*a[rank][i];
}
}
for(rg int i=rank+1 ; i<=n ; ++i)
if(!e0(a[i][n+1]))
{
putchar('-');
putchar('1');
return ;
}
if(rank < n)
{
putchar('0');
return ;
}
for(rg int i=1 ; i<=n ; ++i)
printf("x%d=%.2lf\n", i, a[i][n+1]/a[i][i]);
}
int main()
{
scanf("%d", &n);
for(rg int i=1 ; i<=n ; ++i)
for(rg int j=1 ; j<=n+1 ; ++j)
scanf("%lf", &a[i][j]);
gauss();
return 0;
}
```
### 矩阵快速幂
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 110
#define MOD 1000000007
#define int long long
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
bool f=false;
while((c=getchar())<'0' || c>'9') if(c=='-') f=true;
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
if(f) x=-x;
}
template <typename T> void Wri(T x)
{
if(x > 9) Wri(x/10);
putchar(x%10^48);
}
template <typename T> il void Oput(T x)
{
if(x < 0) putchar('-'), x=-x;
Wri(x);
}
int n, k;
struct Sqr {
int a[MAXN][MAXN];
Sqr() {memset(a, 0, sizeof a);}
}org;
Sqr operator * (Sqr x, Sqr y)
{
Sqr ret;
for(rg int k=1 ; k<=n ; ++k)
for(rg int i=1 ; i<=n ; ++i)
for(rg int j=1 ; j<=n ; ++j)
{
ret.a[i][j] += x.a[i][k]*y.a[k][j]%MOD;
ret.a[i][j] %= MOD;
}
return ret;
}
Sqr qpow(Sqr x, int k)
{
Sqr ret;
for(rg int i=1 ; i<=n ; ++i)
ret.a[i][i] = 1;
while(k)
{
if(k&1) ret = ret*x;
x = x*x;
k >>= 1;
}
return ret;
}
signed main()
{
Iput(n), Iput(k);
for(rg int i=1 ; i<=n ; ++i)
for(rg int j=1 ; j<=n ; ++j)
Iput(org.a[i][j]);
org = qpow(org, k);
for(rg int i=1 ; i<=n ; ++i)
for(rg int j=1 ; j<=n ; ++j)
Oput((org.a[i][j]%MOD+MOD)%MOD), putchar(j==n?'\n':' ');
return 0;
}
```
组合数的求法
高中数学..
## 字符串
### Hash
> P3370 【模板】字符串哈希
bitset开桶
```cpp
#include<cstdio>
#include<iostream>
#include<bitset>
#define il inline
#define rg register
#define BASE 131
#define MOD 1000000007
using namespace std;
typedef long long LL;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int n;
bitset <MOD> Hash; //120MB
int ans;
int main()
{
Iput(n);
for(rg int i=1 ; i<=n ; ++i)
{
char c;
while(!( ((c=getchar())>='0'&&c<='9') || (c>='a'&&c<='z') || (c>='A'&&c<='Z') ));
LL ret = c;
while( ((c=getchar())>='0'&&c<='9') || (c>='a'&&c<='z') || (c>='A'&&c<='Z') )
{
ret = ret*BASE+c;
if(ret >= MOD) ret %= MOD;
}
if(!Hash[ret])
{
Hash[ret] = 1;
++ans;
}
}
Oput(ans);
return 0;
}
```
离散化
```cpp
#include<cstdio>
#include<algorithm>
#define rg register
#define il inline
#define MAXN 10010
#define Base 26
#define MOD 2147483629
using namespace std;
typedef long long LL;
LL a[MAXN];
il LL hash(char c[])
{
LL ans = 1ll;
for(rg int i=0 ; c[i]!='\0' ; ++i)
{
ans = ans*26 + c[i];
if(ans > MOD)
ans %= MOD;
}
return ans;
}
int main()
{
int n, ans=0;
scanf("%d", &n);
for(rg int i=1 ; i<=n ; ++i)
{
char c[1510];
scanf("%s", c);
a[i] = hash(c);
}
sort(a+1, a+1+n);
printf("%d", unique(a+1, a+1+n) - a - 1);
return 0;
}
```
哈希表
```cpp
#include<cstdio>
#include<iostream>
#include<string>
#define il inline
#define rg register
#define MAXN 10010
#define BASE 131
#define MOD 1000003
using namespace std;
typedef long long LL;
struct Edge {
string s;
int nex;
}e[MAXN];
int head[MOD], tote;
il void ae(int Hash, string s)
{
e[++tote].s = s;
e[tote].nex = head[Hash];
head[Hash] = tote;
}
int n, ans;
int main()
{
cin >> n;
for(rg int i=1 ; i<=n ; ++i)
{
string t;
cin >> t;
LL ret = 0;
for(string::iterator it=t.begin() ; it!=t.end() ; ++it)
{
ret = ret*BASE+(*it);
if(ret >= MOD) ret %= MOD;
}
bool flag = false;
for(rg int j=head[ret] ; j ; j=e[j].nex)
if(e[j].s == t)
{
flag = true;
break;
}
if(!flag)
{
ae(ret, t);
++ans;
}
}
cout << ans;
return 0;
}
```
单字符串Hash
```cpp
il void make_base(int l)
{
b[0] = 1;
for(rg int i=1 ; i<=l ; ++i)
{
b[i] = b[i-1] * base % MOD;
if(b[i] < 0) b[i] += MOD;
}
}
il void make_hash(int l)
{
for(rg int i=1 ; i<=l ; ++i)
{
h[i] = (h[i-1] * base + str[i]-'a') % MOD;
if(h[i] < 0) h[i] += MOD;
}
}
il int hash(int l, int r)
{
return ((h[r] - b[r-l+1]*h[l-1])%MOD + MOD)%MOD;
}
```
### Trie
```cpp
struct Trie {
struct Node {
int ch[26], ctr;
}t[MAXN*MAXL]; //注意大小
int tot;
il void insert(char s[])
{
int p = 0;
int len=strlen(s);
for(rg int i=0 ; i<len ; ++i)
{
int c = s[i]-'a';
if(!t[p].ch[c]) t[p].ch[c] = ++tot;
p = t[p].ch[c];
}
++t[p].end;
}
il int find(char s[])
{
int p = 0;
int len=strlen(s);
for(rg int i=0 ; i<len ; ++i)
{
int c = s[i]-'a';
if(!t[p].ch[c]) return 0;
p = t[p].ch[c];
}
return t[p].end;
}
}trie;
```
### KMP
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#define il inline
#define rg register
#define MAXN 1000010
using namespace std;
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
char s[MAXN], t[MAXN];
int ls, lt;
int fail[MAXN];
int main()
{
scanf("%s%s", t+1, s+1); //注意1下标开始
lt = strlen(t+1);
ls = strlen(s+1);
for(rg int i=2, j=0 ; i<=ls ; ++i) //fail[1] = 0;
{
while(j && s[i]!=s[j+1]) j = fail[j];
if(s[i] == s[j+1]) ++j;
fail[i] = j;
}
for(rg int i=1, j=0 ; i<=lt ; ++i) //从1开始
{
while(j && t[i]!=s[j+1]) j = fail[j];
if(t[i] == s[j+1]) ++j;
if(j == ls)
{
Oput(i-ls+1);
putchar('\n');
}
}
for(rg int i=1 ; i<=ls ; ++i)
Oput(fail[i]), putchar(' ');
return 0;
}
```
### Manacher
```cpp
#include<cstdio>
#include<iostream>
#define il inline
#define rg register
#define MAXN 11000010
using namespace std;
template <typename T> il void Iput(T &x)
{
char c;
while((c=getchar())<'0' || c>'9');
x = c^48;
while((c=getchar())>='0' && c<='9') x = (x<<1) + (x<<3) + (c^48);
}
template <typename T> void Oput(T x)
{
if(x > 9) Oput(x/10);
putchar(x%10^48);
}
int n;
char s[MAXN];
int mid, mp; //mp为开区间
int ans;
int p[MAXN]; //包括自己的翼长
int main()
{
s[0] = 1; //注意这个
do
{
n += 2;
s[n] = getchar();
}while(s[n]>='a' && s[n]<='z');
s[n--] = 2; //注意这个
for(rg int i=1 ; i<=n ; ++i)
{
p[i] = i<mp ? min(mp-i, p[(mid<<1)-i]) : 1;
while(s[i-p[i]] == s[i+p[i]]) ++p[i];
if(i+p[i] > mp)
{
mp = i+p[i];
mid = i;
}
ans = max(ans, p[i]);
}
Oput(ans-1); //注意减1！！
return 0;
}
```
### 最小表示法
```cpp
```
## 其他知识和技巧
### 离散化
eg:
> P1496 火烧赤壁
```cpp
Iput(n);
for(rg int i=1 ; i<=n ; ++i)
{
Iput(a[i].l), Iput(a[i].r);
lsh[i] = a[i].l;
lsh[i+n] = a[i].r;
}
sort(lsh+1, lsh+(n<<1)+1); //注意离散化数组长度，并且记得开够
int len = unique(lsh+1, lsh+(n<<1)+1) - lsh - 1;
for(rg int i=1 ; i<=n ; ++i)
{
int ll = lower_bound(lsh+1, lsh+len+1, a[i].l) - lsh;
int rr = lower_bound(lsh+1, lsh+len+1, a[i].r) - lsh;
for(rg int j=ll ; j<rr ; ++j)
bt[j] = true;
}
```
### 康拓展开
```cpp
```
### 随机化算法