板子集

前言

码风解释

define

typedef long long llt;
const int SIZ = 1e111;
const double eps = 1e-111;

关于时间复杂度

注：from：OI竞赛的时间复杂度与数据要求_初级新手村-CSDN博客

时间复杂度	数据范围
$O(n)$	$n \leq 10^8$
$O(n\log n)$	$n \leq 10^6$
$O(n \sqrt n)$	$n \leq 10^5$
$O(n^2)$	$n \leq 5 \times 10^3$
$O(n^3)$	$n \leq 300$
$O(2^n)$	$n \leq 25$
$O(n!)$	$n \leq 11$

基本算法

快读

int Read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') 
        {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}

__int128

i128 read() {
    i128 x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') 
        {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}

void print(i128 x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

一种比较 ex 的输入方式

int read() {
    int x = 0,f = 1;
    char ch = getchar();
    while(ch <  '0' || ch >  '9') {
        if (ch == '\n') return INF;
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
        x = (x<<3) + (x<<1) + (ch^48), ch = getchar();
    return x * f;
}

高精

显然这不是我写的

#include<bits/stdc++.h>
#define MAXN 1005
#define BASE 10000
using namespace std;
struct hp{
    int len,s[MAXN];
    hp(){
        len=1;
        memset(s,0,sizeof s);
    }
    inline void write(char a[]){
        int lena=strlen(a);
        int k=1;
        for(int i=0;i<lena;++i)
        {
            s[len]+=(a[lena-i-1]-'0')*k;
            k*=10;
            if(k==BASE)++len,k=1;
        }
    }
    inline void zero(){
        while(len>1&&s[len]==0)
            --len;
    }
    inline void read(){
        char a[4*MAXN];
        scanf("%s",a);
        write(a);
    }
    inline void print(){
        zero();
        printf("%d",s[len]);
        for(int i=len-1;i>=1;--i)
            printf("%04d",s[i]);
    }
    inline hp operator = (const int b){
        char a[MAXN*4];
        sprintf(a,"%d",b);
        write(a);
        return *this;
    }
    inline hp operator + (hp b)const{
        hp c;
        c.len=max(len,b.len)+1;
        for(int i=1;i<c.len;++i)
        {
            c.s[i]+=s[i]+b.s[i]; 
            c.s[i+1]=c.s[i]/BASE;
            c.s[i]%=BASE;
        }
        c.zero();
        return c;
    }
    inline hp operator - (hp b){
        hp c;
        c.len=len;
        for(int i=1;i<=c.len;++i)
        {
            c.s[i]=s[i]-b.s[i];
            if(c.s[i]<0)
            {
                --s[i+1];
                c.s[i]+=BASE;
            }
        }
        c.zero();
        return c;
    }
    inline hp operator * (hp b)const{
        hp c;
        c.len=len+b.len+1;
        for(int i=1;i<=len;++i)
        {
            int k=0;
            for(int j=1;j<=b.len;j++)
            {
                c.s[i+j-1]+=s[i]*b.s[j]+k;
                k=c.s[i+j-1]/BASE;
                c.s[i+j-1]%=BASE;
            }
            c.s[i+b.len]=k;
        }
        c.zero();
        return c;
    }
    inline hp operator / (hp b)const{
        hp c;
        hp temp;
        c.len=len;
        for(int i=len;i>=1;--i)
        {
            temp=temp*BASE+s[i];
            int l=0,r=BASE,ans=0;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(b*mid<=temp)
                {
                    ans=mid;
                    l=mid+1;
                }
                else
                    r=mid-1;
            }
            temp=temp-b*ans;
            c.s[i]=ans;
        }
        c.zero();
        return c;
    }
    inline hp operator % (hp b){
        return *this-*this/b*b;
    }
    inline hp operator + (int b)const{
        hp c;
        c=b;
        return *this+c;
    }
    inline hp operator - (int b){
        hp c;
        c=b;
        return *this-c;
    }
    inline hp operator * (int b)const{
        hp c;
        c=b;
        return *this*c;
    }
    inline hp operator / (int b)const{
        hp c;
        c=b;
        return *this/c;
    }
    inline hp operator % (int b){
        hp c;
        c=b;
        return *this%c;
    }
    inline bool operator <  (hp b)const{
        if(len<b.len) return true;
        if(len>b.len) return false;
        for(int i=len;i>=1;--i)
        {
            if(s[i]<b.s[i]) return true;
            else if(s[i]>b.s[i]) return false;
        }
        return false;
    }
    inline bool operator >  (hp b)const{
        return b<*this;
    }
    inline bool operator <= (hp b)const{
        return !(*this>b);
    }
    inline bool operator >= (hp b)const{
        return !(*this<b);
    }
    inline bool operator == (hp b)const{
        return (!(b>*this)&&!(b<*this));
    }
    inline bool operator != (hp b)const{
        return !(b==*this);
    }
    inline bool operator <  (int b)const{
        hp c;
        c=b;
        return *this<c;
    }
    inline bool operator >  (int b)const{
        hp c;
        c=b;
        return *this>c;
    }
    inline bool operator <= (int b)const{
        hp c;
        c=b;
        return *this<=c;
    }
    inline bool operator >= (int b)const{
        hp c;
        c=b;
        return *this>=c;
    }
    inline bool operator == (int b)const{
        hp c;
        c=b;
        return *this==c;
    }
    inline bool operator != (int b)const{
        hp c;
        c=b;
        return *this!=c;
    }
}a, b, sum;
int main(){
    a.read();
    b.read();
    sum = a + b;
    sum.print();
    return 0;
}

FFT A*B

#include<bits/stdc++.h>
using namespace std;
typedef long double ldb;

const int maxn = 3e6+6;
const int mx = 3e6;
const ldb Pi = acos(-1.0);

int n, m, q = 1;
int c[maxn];
char aa[maxn], bb[maxn];

struct Complex {
    ldb x, y;
    friend Complex operator + (Complex a, Complex b) {return {a.x+b.x, a.y+b.y};}
    friend Complex operator - (Complex a, Complex b) {return {a.x-b.x, a.y-b.y};}
    friend Complex operator * (Complex a, Complex b) {return {a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x};}
} x1[maxn], x2[maxn];

void change(Complex x[], int len) {
    for (int i=1, j=len/2, k; i < len-1; i++) {
        if (i < j) swap(x[i], x[j]);
        k = len / 2;
        while (j >= k) j -= k, k /= 2;
        j += k;
    }
}

void FFT(Complex x[], int len, int im) {
    change(x, len);
    for (int d = 1; d <= len; d <<= 1) {
        Complex wn = {cos(Pi * 2 / d), sin(im * 2 * Pi / d)};
        for (int j = 0; j < len; j += d) {
            Complex w = {1, 0};
            for (int k = j; k < j + d / 2; k++) {
                Complex u = x[k], t = w * x[k + d / 2];
                x[k] = u + t;
                x[k + d / 2] = u - t;
                w = w * wn;
            }
        }
    }
    if (im == -1)
        for (int i = 0; i < len; i++)
            x[i].x /= len;
}

int main() {
    cin >> aa >> bb;
    n = strlen(aa); for (int i = 0; i < n; i++) x1[n-i-1] = {(ldb)aa[i]-48, 0}; 
    m = strlen(bb); for (int i = 0; i < m; i++) x2[m-i-1] = {(ldb)bb[i]-48, 0};
    while(q <= (n + m)) q <<= 1;
    FFT(x1, q, 1), FFT(x2, q, 1);
    for (int i = 0; i <= q; i++) x1[i] = x1[i] * x2[i];
    FFT(x1, q, -1);
    for (int i = 0; i <= q; i++) {
        c[i] += (int)(x1[i].x + 0.5);
        if (c[i] >= 10)
            c[i+1] += c[i] / 10, c[i] %= 10, q += (i == q);
    }
    while (!c[q] && q) q--; q++;
    while (--q >= 0) printf("%d", c[q]); puts("");
    return 0;
}

位运算

二进制操作

(n>>k)&1;     // Get_bit
n&((1<<k)-1); // Get_zeroTOk
n|(1<<k);     // Change_to_one
n&(~(1<<k));  // Change_to_zero
n^(1<<k);     // Change_xor
// STL 大法好
// bitset <=> int / long long
// like: num = 2147483647;
bitset<SIZ> num;
num.count();
num.size();
num.any();
num.all();
num.to_ullong();

快速幂

llt FastPower (llt a, llt b, llt p) {
    llt res = 1;
    for( ; b; b >>= 1, a = a * a % p)
        if(b & 1) res = res * a % p;
    return res;
}

P1226 【模板】快速幂||取余运算

龟(慢)速乘

llt SlowMul (llt a, llt b, llt p) {
    llt res = 0;
    for( ; b; b >>= 1, a = a * 2 % p) 
        if(b & 1) res = (res + a) % p;
    return res;
}

int128

const llt p = 1e18
struct int128 {llt hig, low;};
int128 Max (int128 a, int128 b) {
    if (a.hig > b.hig) return a;
    if (a.hig < b.hig) return b;
    if (a.low > b.low) return a;
    if (a.low < b.low) return b;
    return a;
}
int128 operator + (int128 a, int128 b) {
    int128 c;
    c.low = (a.low + b.low) % p;
    c.hig = (a.hig + b.hig) + (a.low + b.low) / p;
    return c;
}
// b == 2;
int128 operator * (int128 a, int b) {
    int128 c;
    c.low = (a.low + b.low) % p;
    c.hig = (a.hig + b.hig) + (a.low + b.low) / p;
    return c;
}
// 低位补零
void print (int128 a) {
    if (a.hig == 0) printf("%lld", a.low);
    else printf("%lld%018lld", a.hig, a.low);
}

Lowbit

int Lowbit (int n) {
    // return n & (-n + 1);
    return n & (-n);
}

十进制取位

inline int GetNum (llt x, int i) {   
    x %= (llt)pow (10, i);
    return i == 1 ? x : x / (llt)pow (10, i-1);
}

HASH

void HASH () {
    sort (map +1, map +(n<<1) +1);
    int m = unique (map +1, map +(n<<1) +1) - map +1;
    for (int i = 1; i <= n; i++) {
        dat[i].x = lower_bound (map+1, map+m+1, dat[i].x) - map;
        dat[i].y = lower_bound (map+1, map+m+1, dat[i].y) - map;
        if (dat[i].x > dat[i].y) swap(dat[i].x, dat[i].y);
    }
}

void HASH () {
    sort (b +1, b +n +1);
    int m = unique (b +1, b +n +1) - b -1;
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound (b +1, b +m +1, a[i]) - b -1;
}

前缀和与差分

前缀和

scanf("%d", &n);
for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    pre[i] = pre[i-1] + a[i];
}

二分

二分答案

while(l <= r) {
    int mid = (l + r) >> 1;
    if(check(mid)) l = mid + 1;
    else r = mid - 1;
}
printf("%d\n", r);

bool Check (int x) {
    // ···
}
int main() {
    // ···
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(Check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    printf("%d\n", r); // ans
    // ···
}

排序

sort $O(n\ logn)$

sort(a + 1, a + n + 1);

倍增

ST 表

int query(int l, int r){
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1<<k) + 1][k]);
}
int main(){
    for(int i = 1; i <= n; i++)
        f[i][0]=read();
    for(int j = 1; j <= 17; j++)
        for(int i = 1; i+(1<<j)-1 <= n; i++)
            f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}

LCA

#include<bits/stdc++.h>
#define MAXN 500500
using namespace std;
int n,m,s,tot;
int head[MAXN],dep[MAXN],p[MAXN][21];
struct node{
    int v,nxt;
}e[MAXN*2];
void add(int u,int v){
    e[++tot].v=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    p[u][0]=fa;
    for(int i=1;(1<<i) <= dep[u];i++){
        p[u][i]=p[ p[u][i-1] ][i-1];
    }
    for(int i=head[u];i!=-1;i=e[i].nxt){
        if(e[i].v!=fa)dfs(e[i].v,u);
    }
}
int lca(int x,int y){
    if(dep[x] > dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[x] <= dep[y]- (1<<i) ){
            y=p[y][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(p[x][i]==p[y][i])continue;
        else {
            x=p[x][i];y=p[y][i];
        }
    }
    return p[x][0];
}
int main(){
    memset(head,-1,sizeof(head));
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        add(a,b);add(b,a);
    }
    dfs(s,0);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}

数据结构

并查集

int find (int x) {
    if (fa[x] == x) return x;
    else return fa[x] = find (fa[x]);
}
void merge (int x, int y) {
    fa[find (x)] = find (y);
}
void init () {
    for (int i = 1; i <= n<<1; i++)
        fa[i] = i;
}

单调栈

for(int i = 1; i <= n; i++)
    cin >> a[i];
for(int i = 1; i <= n; i++){
    while(top && a[i] > a[st[top]]){
        ans[st[top]] = i;
        top--;
    }
    st[++top] = i;
}

单调队列

#include<bits/stdc++.h>
#define Max 1000100
using namespace std;
// struct node{minn,maxn}ans[Max];
int n, j, k, a[Max];
deque<int> q;
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++){
        while(!q.empty() && q.back() >= a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i-j >= k && a[j] == q.front()){
            j++; q.pop_front();
        }
        if(i-j >= k && a[j] != q.front()){
            j++;
        }
        if(i >= k) cout << q.front() << " ";
    }
    cout << endl;
    q.clear();
    j = 0;
    for(int i = 1; i <= n; i++){
        while(!q.empty() && q.back() <= a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i-j >= k && a[j] == q.front()){
            j++; q.pop_front();
        }
        if(i-j >= k && a[j] != q.front()){
            j++;
        }
        if(i >= k) cout << q.front() << " ";
    }
}

树状数组

逆序对

// 树状数组
#include<bits/stdc++.h>
#define llt long long
#define Max 500050
using namespace std;
int n, tre[Max], rak[Max];
llt ans;
struct node{
    int num, val;
}f[Max];
bool cmp(node a, node b){
    if(a.val == b.val) return a.num < b.num;
    else return a.val < b.val;
}
void add(int a, int b){
    for(; a <= n; a += a&-a)
        tre[a] += b;
}
int query(int a){
    int tot = 0;
    for(; a; a -= a&-a)
        tot += tre[a];
    return tot;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> f[i].val, f[i].num = i;
    sort(f + 1, f + n + 1, cmp);
    for(int i = 1; i <= n; i++)
        rak[f[i].num] = i;
    for(int i = 1; i <= n; i++)
        add(rak[i], 1), ans += i-query(rak[i]);
    cout << ans << endl;
    return 0;
}

线段树

#include<cstdio>
#define LI (i<<1)
#define RI (i<<1|1)
#define llt long long
using namespace std;
const int siz = 1001000;
struct Tre {
    int l, r; llt sum, tag;
    int len() {return r - l + 1;}
} tre[siz];
int n, m;
llt data[siz];
void push_up (int i) {
    tre[i].sum = tre[LI].sum + tre[RI].sum;
}
void push_down (int i) {
    tre[LI].sum += tre[LI].len() * tre[i].tag;
    tre[RI].sum += tre[RI].len() * tre[i].tag;
    tre[LI].tag += tre[i].tag;
    tre[RI].tag += tre[i].tag;
    tre[i ].tag =  0;
}
void build (int l, int r, int i) {
    tre[i].l = l, tre[i].r = r;
    if (l == r) {
        tre[i].sum = data[l];
        return;
    }
    int mid = (l + r) >> 1;
    build (l,   mid, LI);
    build (mid+1, r, RI);
    push_up (i);
}
void change (int l, int r, llt k, int i) {
    if (l <= tre[i].l && tre[i].r <= r) {
        tre[i].sum += tre[i].len() * k;
        tre[i].tag += k;
        return;
    }
    push_down (i);
    if (l <= tre[LI].r) change (l, r, k, LI);
    if (tre[RI].l <= r) change (l, r, k, RI);
    push_up (i);
}
llt query (int l, int r, int i) {
    if (l <= tre[i].l && tre[i].r <= r) {
        return tre[i].sum;
    }
    push_down (i);
    llt res = 0;
    if (l <= tre[LI].r) res += query (l, r, LI);
    if (tre[RI].l <= r) res += query (l, r, RI);
    return res;
}
int main () {
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf ("%lld", &data[i]);
    build (1, n, 1);
    for (int i = 1; i <= m; i++) {
        int opt, l, r; llt k;
        scanf ("%d%d%d", &opt, &l, &r);
        if (opt == 1) scanf ("%lld", &k), change (l, r, k, 1);
        else printf ("%lld\n", query (l, r, 1));
    }
    return 0;
}

莫队

#include<algorithm>  // ~~Mo_Queue~~
#include<cstdio>
#include<cmath>
#define Max 100100
using namespace std;
int n, q, len, maxn, a[Max], pos[Max], cnt[Max<<1], sum[Max];
struct node{
    int l, r, id, ans;
}query[Max<<1];
bool cmp1(node x, node y){
    if(pos[x.l] != pos[y.l]) return pos[x.l] < pos[y.l];
    else return x.r < y.r;
}
bool cmp2(node x, node y){
    return x.id < y.id;
}
void add(int x){
    sum[++cnt[a[x]]]++;
    maxn = max (maxn, cnt[a[x]]);
    return;
}
void del(int x){
    if(sum[cnt[a[x]]] == 1 && maxn == cnt[a[x]]) maxn--;
    sum[cnt[a[x]]--]--;
    return;
}
int main(){
    scanf("%d%d", &n, &q);
    len = sqrt(n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        a[i] += Max-100;  // 离散化
    }
    for(int i = 1; i <= q; i++){
        scanf("%d%d",&query[i].l, &query[i].r);
        query[i].id = i;
    }
    for(int i = 1; i <= n; i++){
        pos[i] = (i-1)/len + 1;
    }
    sort(query+1, query+q+1, cmp1);
    int l = 1, r = 0;
    for(int i = 1; i <= q; i++){
        while(l < query[i].l) del(l++);
        while(l > query[i].l) add(--l);
        while(r < query[i].r) add(++r);
        while(r > query[i].r) del(r--);
        query[i].ans = maxn;
    }
    sort(query+1, query+q+1, cmp2);
    for(int i = 1; i <= q; i++){
        printf("%d\n", query[i].ans);
    }
    return 0;
}

左偏树

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100100;

struct Tree{
    int ls, rs, val, dist, root;
} tre[maxn];

int n, m;

void build(int x, int val) {
    tre[x].root = x;
    tre[x].val = val;
}

int merge(int x, int y) {
    if (!x || !y)
        return x | y;
    if (tre[x].val > tre[y].val || (tre[x].val == tre[y].val && x > y)) 
        swap(x, y);
    tre[x].rs = merge(tre[x].rs, y);
    if (tre[tre[x].rs].dist > tre[tre[x].ls].dist) 
        swap(tre[x].ls, tre[x].rs);
    tre[tre[x].ls].root = tre[tre[x].rs].root = tre[x].root = x;
    tre[x].dist = tre[tre[x].rs].dist + 1;
    return x;
}

int pop(int x) {
    tre[x].val = -1;
    tre[tre[x].ls].root = tre[x].ls;
    tre[tre[x].rs].root = tre[x].rs;
    return tre[x].root =  merge(tre[x].ls, tre[x].rs);
}

int get(int x) {
    return tre[x].root == x ? x : tre[x].root = get(tre[x].root);
}

int main() {
    scanf("%d %d", &n, &m);
    tre[0].dist = -1;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        build(i, x);
    }
    for (int i = 1; i <= m; i++) {
        int opt, x, y;
        scanf("%d %d", &opt, &x);
        if (opt == 1) {
            scanf("%d", &y);
            if (tre[x].val == -1 || tre[y].val == -1)
                continue;
            x = get(x), y = get(y);
            if (x != y)
                tre[x].root = tre[y].root = merge(x, y);
        }
        else {
            if (tre[x].val == -1)
                puts("-1");
            else
                printf("%d\n", tre[get(x)].val), pop(get(x));
        }
    }
    return 0;
}

字符串

manacher

string ch;
char str[Max<<1];
int p[Max<<1], ans, len;
int main () {
    cin >> ch;
    len = ch.length();
    str[0] = '#';
    for (int i = 0; i <= len; i++) { 
        str[i * 2 + 1] = '|';
        str[i * 2 + 2] = ch[i];
    }
    int mr = 0, ct = 0; len = len * 2 + 1;
    for (int i = 1; i < len; i++) {
        if (i <= mr) 
            p[i] = min (p[(ct << 1) - i], mr - i + 1);
        while (str[i - p[i]] == str[i + p[i]]) 
            p[i]++;
        if (p[i] + i > mr) 
            mr = p[i] + i - 1, ct = i;
        ans = max (ans, p[i]); 
    }
    cout << ans-1 << endl;
    return 0;
}

KMP

#include<bits/stdc++.h>
using namespace std;
const int siz = 1000100;
char aaa[siz], ccc[siz];
int nxt[siz];
int main () {
    cin >> ccc+1 >> aaa+1;
    for (int i = 2, j = 0; aaa[i]; i++) {
        while (aaa[i] != aaa[j+1] && j)
            j = nxt[j];
        if (aaa[i] == aaa[j+1])
            j++;
        nxt[i] = j;
    }
    for (int i = 1, j = 0; ccc[i]; i++) {
        while (ccc[i] != aaa[j+1] && j)
            j = nxt[j];
        if (ccc[i] == aaa[j+1])
            j++;
        if (j == strlen(aaa+1))
            printf ("%d\n", i - strlen(aaa+1) +1);
    }
    for (int i = 1; aaa[i]; i++)
        printf ("%d ", nxt[i]);
    return 0;
}

trie

struct TRIE {
    int tre[sizw][26], ctl[sizw], cnt;
    bool mark[sizw], node[sizw];
    void insert (string s) { 
        int u = 0;
        for (int i = 0; s[i]; i++) {
            int c = s[i] - 'a';
            if (!tre[u][c]) tre[u][c] = ++cnt;
            ctl[tre[u][c]] = c + 'a';
            u = tre[u][c];
        }
        mark[u] = 1;
    }
    void find (string s) {
        int u = 0;
        for (int i = 0; s[i]; i++) {
            int c = s[i] - 'a';
            node[tre[u][c]] = 1;
            u = tre[u][c];
        }
    }
    void dfs (int c) {
        if (mark[c]) 
            tot++, way += "P";
        if (tot == n) {
            printf ("%d\n", way.length ());
            for (int i = 0; way[i]; cout << way[i] << endl, i++) ;
        }
        for (int i = 0; i < 26; i++) {
            if (!node[tre[c][i]] && tre[c][i]) {
                way += ctl[tre[c][i]];
                dfs (tre[c][i]);
                way += '-';
            }
        }
        for (int i = 0; i < 26; i++) {
            if (node[tre[c][i]] && tre[c][i]) {
                way += ctl[tre[c][i]];
                dfs (tre[c][i]);
                way += '-';
            }
        }
    }
} trie;

AC 自动机

#include<bits/stdc++.h>
using namespace std;

namespace automaton {
    const int MAXN = 1e6+6;
    int cnt, mx;
    char p[222][155], str[MAXN];
    int tre[MAXN][26], val[MAXN], fail[MAXN];
    int ans[222];
    queue<int> q;

    void clear() {
        cnt = mx = 0;
        memset(tre, 0, sizeof tre);
        memset(val, 0, sizeof val);
        memset(ans, 0, sizeof ans);
        memset(fail, 0, sizeof fail);
    }

    void insert(int pos) {
        int u = 0;
        for (int i = 1; p[pos][i]; i++) {
            if (!tre[u][p[pos][i]-'a'])
                tre[u][p[pos][i]-'a'] = ++cnt;
            u = tre[u][p[pos][i]-'a'];
        }
        val[u] = pos;
    }

    void build() {
        for (int i = 0; i < 26; i++)
            if (tre[0][i]) q.push(tre[0][i]);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < 26; i++) {
                if (tre[u][i])
                    fail[tre[u][i]] = tre[fail[u]][i],
                    q.push(tre[u][i]);
                else
                    tre[u][i] = tre[fail[u]][i];
            }
        }
    }

    int query() {
        int u = 0;
        for (int i = 1; str[i]; i++) {
            u = tre[u][str[i]-'a'];
            for (int j = u; j; j = fail[j]) {
                if (val[j])
                    ans[val[j]]++;
                // printf("%d %d\n", ans[val[j]], val[j]);
                if (j)
                    mx = max(mx, ans[val[j]]);
            }
        }
        return mx;
    }   
}
using namespace automaton;

int main() {
    int n;
    while (~scanf("%d", &n) && n) {
        clear();
        for (int i = 1; i <= n; i++)
            cin >> p[i]+1, insert(i);
        build();
        cin >> str+1;
        printf("%d\n", query());
        for (int i = 1; i <= n; i++)
            if (ans[i] == mx)
                cout << p[i]+1 << endl;
    }
    return 0;
}

SA && SAM

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+6;

int n, m = 128, cnt;
int sa[MAXN], rk[MAXN], t[MAXN], d[MAXN];
char str[MAXN];

int main() {
    cin >> str+1;
    n = strlen(str+1);
    for (int i = 1; i <= n; i++)
        rk[i] = str[i], t[rk[i]]++;
    for (int i = 1; i <= m; i++)
        t[i] += t[i-1];
    for (int i = n; i >= 1; i--)
        sa[t[rk[i]]] = i, t[rk[i]]--;
    for (int k = 1; k <= n; k <<= 1) {
        cnt = 0;
        for (int i = n-k+1; i <= n; i++)
            d[++cnt] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > k) d[++cnt] = sa[i] - k;
        for (int i = 1; i <= m; i++)
            t[i] = 0;
        for (int i = 1; i <= n; i++)
            t[rk[d[i]]]++;
        for (int i = 1; i <= m; i++)
            t[i] += t[i - 1];
        for (int i = n; i >= 1; i -= 1) 
            sa[t[rk[d[i]]]] = d[i], t[rk[d[i]]]--;
        swap(d, rk);
        rk[sa[1]] = cnt = 1;
        for (int i = 2; i <= n; i++) {
            if (d[sa[i]] == d[sa[i - 1]] && d[sa[i] + k] == d[sa[i - 1] + k])
                rk[sa[i]] = cnt;
            else rk[sa[i]] = ++cnt;
        }
        if (cnt == n) break;
        m = cnt;
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", sa[i]); puts("");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

namespace SAM {
    const int MAXN = 2e6+6;
    int siz, lst, ans;
    int len[MAXN], cnt[MAXN], lik[MAXN], tre[MAXN][26];
    char str[MAXN];

    void insert(int c) {
        int cur = ++siz, p;
        len[cur] = len[lst] + 1;
        cnt[cur] = 1;
        for (p = lst; p && !tre[p][c]; p = lik[p])
            tre[p][c] = cur;
        if (!p) 
            lik[cur] = 1;
        else {
            int x = tre[p][c];
            if (len[p]+1 == len[x])
                lik[cur] = x;
            else {
                int y = ++siz;
                len[y] = len[p] + 1;
                memcpy(tre[y], tre[x], sizeof tre[x]);
                lik[y] = lik[x];
                lik[cur] = lik[x] = y;
                while (p && tre[p][c] == x)
                    tre[p][c] = y, p = lik[p];
            }
        }
        lst = cur;
    }

    vector<int> nxt[MAXN];
    void dfs(int x) {
        for (int i = 0; i < nxt[x].size(); i++)
            dfs(nxt[x][i]),
            cnt[x] += cnt[nxt[x][i]];
        if (cnt[x] != 1)
            ans = max(ans, cnt[x] * len[x]);
    }
}
using namespace SAM;

int main() {
    cin >> str+1;
    siz = lst = 1;
    for (int i = 1; str[i]; i++)
        insert(str[i]-'a');
    for (int i = 2; i <= siz; i++)
        nxt[lik[i]].push_back(i);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

数论

质数 && 筛法

注：参照：筛法 - OI Wiki

筛法优化（以下 code 未对此优化）

• 筛至平方根
• 只筛奇数

Eratosthenes 筛 （埃氏筛） $O(n\ log\ logn)$

注：根据 bitset - OI Wiki 中关于速度测试的内容可以近乎认为其时间复杂度为 $O(n)$ （需要吸氧！否则时间是 bool 的五倍以上）

bitset<SIZ> vis; 
void GetPrimes () {
    for (int i = 2; i <= n; i++) {
        if (vis[i]) continue;
        prime[++cnt] = i;
        for (int j = i; j <= n / i; j++)
            vis[i*j] = 1;
    }
}

欧拉筛（线性筛法） $O(n)$

// tedukuri version  <Maybe MLE>
int vis[SIZ], prime[SIZ];
void GetPrimes () {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) 
            vis[i] = i, prime[++cnt] = i;
        for (int j = 1; j <= cnt; j++) {
            if (prime[j] > vis[i] || prime[j] > n / i)
                break;
            vis[ i*prime[j] ] = prime[j];
        }
    }
}

P3383 【模板】线性筛素数

一些定理

(扩展)欧几里得算法

$O(log n)$

// STL: __gcd ();
int Gcd (int a, int b) {
    return b ? Gcd(b, a % b) : a;
}

int x, y;
int ExGcd (int a, int b) {
    if (!b) {x = 1, y = 0; return a;}
    int d = ExGcd(b, a % b);
    int z = x; x = y; y = z - y * (a - b);
    return d;
}
// if (!d|c) printf("NoSolution!");

// an other version
int ExGcd (int a, int b, int &x, int &y) {
    // ···
}

// an other version
void ExGcd (int a, int b, int &x, int &y) {
    if (!b) x = 1, y = 0;
    else ExGcd (b, a % b, y, x), y -= a / b * x;
}

Lucas 定理

llt Lucas (llt n, llt m) {
    if(!m) return 1;
    return C (n % p, m % p) * lucas (n / p, m / p) % p;
}

中国剩余定理（孙子定理） (Ex)CRT

for (int i = 1; i <= n; i++) {
    scanf("%lld%lld", &mod[i], &c[i]);
    ModMax *= mod[i];
}
for (int i = 1; i <= n; i++) {
    llt Mi = ModMax / mod[i];
    x = y = 0;
    ExGcd(Mi, mo[i]);
    ans += c[i] * Mi * (x < 0 ? x + mod[i] : x);
}

llt mod[siz], rst[siz];
llt ExCRT () {
    for (int i = 1; i < n; i++) {
        llt a = mod[i], b = mod[i+1], c = rst[i+1] - rst[i],
            gcd = Gcd (a, b), k1, k2;
        if (c % gcd) return -1;
        a /= gcd, b/= gcd, c /= gcd;
        ExGcd (a, b, k1, k2);
        k1 = ((k1 * c) % b + b) % b;
        mod[i + 1] = mod[i] / Gcd(mod[i], mod[i + 1]) * mod[i + 1] ;
        rst[i + 1] = (mod[i] * k1 % mod[i + 1] + rst[i]) % mod[i + 1];
    }
    return rst[n];
}

BSGS

#include<bits/stdc++.h>
using namespace std;
typedef long long llt;
map<llt, int> mp;
llt p, b, n, len;
llt QPow (llt a, llt b) {
    llt res = 1;
    for ( ; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
    return res;
}
int main () {
    scanf ("%lld%lld%lld", &p, &b, &n);
    len = ceil (sqrt (p));
    for (llt i = 0, j = n; i <= len-1; i++, j = j * b % p)
        mp[j] = i;
    for (llt i = 1, k=QPow(b,len), j = k; i <= len; i++, j=j*k%p)
        if (mp.count (j)){printf("%lld\n", i*len-mp[j]);return 0;}
    puts ("no solution");
    return 0;
}

i128 BSGS (i128 a, i128 b) {
    map <i128, i128> mp; mp.clear();
    b %= p;
    i128 t = (i128)sqrt ((llt)p) + 1;
    for (i128 j = 0; j < t; j++) {
        i128 val = b * QPow(a, j) % p;
        mp[val] = j;
    }
    a = QPow(a, t);
    if (!a) return (!b) ? 1 : -1;
    for (i128 i = 0; i <= t; i++) {
        i128 val = QPow (a, i);
        i128 j = mp.find(val) == mp.end() ? -1 : mp[val];
        if (j >= 0 && i * t - j >= 0)
            return i * t - j;
    }
    return -1;
}

高斯消元

double f[111][111];
int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + 1; j++)
            scanf("%lf", &f[i][j]);
    for (int i = 1; i <= n; i++) {
        int maxi = i;
        for (int j = i + 1; j <= n; j++)
            if (fabs(f[j][i]) > fabs(f[maxi][i]))
                maxi = j;
        for (int j = 1; j <= n + 1; j++)
            swap(f[i][j], f[maxi][j]);
        if (!f[i][i]) {
            puts("No Solution"); return 0;}
        for (int j = 1; j <= n; j++) {
            if (j == i) continue;
            double tmp = f[j][i] / f[i][i];
            for (int k = i + 1; k <= n + 1; k++)
                f[j][k] -= f[i][k] * tmp;
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%0.2lf\n", f[i][n+1] / f[i][i]);
    return 0;
}

矩阵 Matrix

矩阵快速幂

注：适用情况：$n \leq 100\ , \ k \leq 10^{12}$

struct Mar {
    llt mar[SIZ][SIZ];
    friend Mar operator * (Mar x, Mar y) {
        Mar z; memset(z.mar, 0, sizeof(z.mar));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                for(int k = 1; k <= n; k++)
                    z.mar[i][j] += x.mar[i][k] * y.mar[k][j],
                        z.mar[i][j] %= MOD;
        return z;
    }
} a;
Mar QPow (Mar a, llt b) {
    Mar res; memset(res.mar, 0, sizeof(res.mar));
    for(int i = 1; i <= n; i++)
        res.mar[i][i] = 1;
    for( ; b; b >>= 1, a = a * a)
        if(b & 1) res = res * a;
    return res;
}

矩阵求逆

#include<bits/stdc++.h>
using namespace std;
typedef long long llt;
const int maxn = 444;
const int p = 1e9+7;

llt a[maxn][maxn << 1];
int n;

llt Pow(llt a, llt b) {
    int res = 1;
    for ( ; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
    return res;
}

llt Inv(llt a) {
    return Pow(a, p-2);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        a[i][i + n] = 1;
        for (int j = 1; j <= n; j++) 
            scanf("%d", &a[i][j]);
    }
    int r;
    for (int i = 1; i <= n; i++) {
        r = i;
        for (int j = i + 1; j <= n; j++)
            if (a[j][i] > a[r][i]) r = j;
        if (r != i) swap(a[i], a[r]);
        if (!a[i][i]) {
            puts("No Solution");
            return 0;
        }
        int inv = Inv(a[i][i]);
        for (int k = 1; k <= n; k++) {
            if (i == k) continue;
            int q = a[k][i] * inv % p;
            for (int j = i; j <= (n << 1); j++)
                a[k][j] = ((a[k][j] - a[i][j] * q) % p + p) % p;
        }
        for (int j = 1; j <= (n << 1); j++)
            a[i][j] = a[i][j] * inv % p;
    }
    for (int i = 1; i <= n; i++, puts("")) 
        for (int j = n + 1; j <= (n << 1); j++)
            printf("%lld ", a[i][j]);
    return 0;
}

高斯消元

#include<bits/stdc++.h>
using namespace std;

double f[111][111];
int n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n + 1; j++)
            scanf("%lf", &f[i][j]);
    for (int i = 1; i <= n; i++) {
        int mx = i;
        for (int j = i + 1; j <= n; j++)
            if (fabs(f[j][i]) > fabs(f[mx][i]))
                mx = j;
        for (int j = 1; j <= n + 1; j++)
            swap(f[i][j], f[mx][j]);
        if (!f[i][i])
            puts("No Solution"), exit (0);
        for (int j = 1; j <= n; j++)
            if (i != j)
                for (int k = i + 1; k <= n + 1; k++)
                    f[j][k] -= f[i][k] * f[j][i] / f[i][i];
    }
    for (int i = 1; i <= n; i++)
        printf("%0.2lf\n", f[i][n+1] / f[i][i]);
    return 0;
}

多项式

FFT

#include<bits/stdc++.h>
using namespace std;
typedef double ldb;

const int maxn = 3e6+6;
const ldb Pi = acos(-1.0);

int n, m, q = 1;
int a[maxn], b[maxn], c[maxn];

struct Complex {
    ldb x, y;
    friend Complex operator + (Complex a, Complex b) {return {a.x+b.x, a.y+b.y};}
    friend Complex operator - (Complex a, Complex b) {return {a.x-b.x, a.y-b.y};}
    friend Complex operator * (Complex a, Complex b) {return {a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x};}
} x1[maxn], x2[maxn];

void change(Complex x[], int len) {
    for (int i=1, j=len/2, k; i < len-1; i++) {
        if (i < j) swap(x[i], x[j]);
        k = len / 2;
        while (j >= k) j -= k, k /= 2;
        j += k;
    }
}

void FFT(Complex x[], int len, int im) {
    change(x, len);
    for (int d = 1; d <= len; d <<= 1) {
        Complex wn = {cos(Pi * 2 / d), sin(im * 2 * Pi / d)};
        for (int j = 0; j < len; j += d) {
            Complex w = {1, 0};
            for (int k = j; k < j + d / 2; k++) {
                Complex u = x[k], t = w * x[k + d / 2];
                x[k] = u + t;
                x[k + d / 2] = u - t;
                w = w * wn;
            }
        }
    }
    if (im == -1)
        for (int i = 0; i < len; i++)
            x[i].x /= len;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; i++) scanf("%d", &a[i]), x1[i]={(ldb)a[i], 0};
    for (int i = 0; i <= m; i++) scanf("%d", &b[i]), x2[i]={(ldb)b[i], 0};
    while(q <= (n + m + 2)) q <<= 1;
    FFT(x1, q, 1), FFT(x2, q, 1);
    for (int i = 0; i <  q; i++) x1[i] = x1[i] * x2[i];
    FFT(x1, q, -1);
    for (int i = 0; i <  q; i++) c[i] = (int)(x1[i].x + 0.5);
    q = n + m;
    for (int i = 0; i <= q; i++) printf("%d ", c[i]); puts("");
    return 0;
}

朗格朗日插值

#include<bits/stdc++.h>
using namespace std;
typedef long long  llt;
const int p =998244353;
const int maxn = 3e3+3;

int n, k;
llt ans, u, v, x[maxn], y[maxn];

llt qpzc(llt a, llt b) {
    llt res = 1;
    for ( ; b; b >>= 1, a = a * a % p)
        if (b & 1) res = res * a % p;
    return res;
}

llt inv(llt a) {
    return qpzc(a, p - 2);
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) 
        scanf("%lld %lld", &x[i], &y[i]);
    for (int i = 1; i <= n; i++) {
        u = y[i] % p; v = 1ll;
        for (int j = 1; j <= n; j++)
            if (i != j)
                u = u * ((k - x[j]) % p + p) % p,
                v = v * ((x[i] - x[j] % p + p) % p) % p;
        ans = (ans + u * inv(v) % p) % p;
    }
    printf("%lld\n", ans);
}

类欧几里得

#include<bits/stdc++.h>
using namespace std;
typedef long long llt;
const llt p = 998244353;
const llt inv2 = 499122177;
const llt inv6 = 166374059;

struct zerc {
    llt f, g, h;
    void mod() {
        f = (f % p + p) % p, 
        g = (g % p + p) % p, 
        h = (h % p + p) % p;
    }
};

zerc calc(llt n, llt a, llt b, llt c) {	
    // printf("|> %lld %lld %lld %lld\n", n, a, b, c);
    llt m = ((a * n + b) / c - 1);
    llt n1bc = ((n + 1) * (b / c)) % p;
    llt n1bc2= ((n + 1) * (b / c) % p * (b / c) % p) % p;
    llt n2ac = (n * (n + 1) % p * inv2 % p * (a / c) % p) % p;
    llt n2bc = (n * (n + 1) % p * inv2 % p * (b / c) % p) % p;
    llt n21acbc = (n * (n + 1) % p * (a / c) % p * (b / c) % p) % p;
    llt n3ac = (n * (n + 1) % p * (n * 2 + 1) % p * inv6 % p * (a / c) % p)  % p;
    llt n3ac2= (n * (n + 1) % p * (n * 2 + 1) % p * inv6 % p * (a / c) % p * (a / c) % p)  % p;
    zerc d, e;
    if (!a) {
        d.f = n1bc;
        d.g = n2bc;
        d.h = n1bc2;
        return d;
    }
    if (a >= c || b >= c) {
        d.f = n2ac + n1bc;
        d.g = n3ac + n2bc;
        d.h = n3ac2 + n1bc2 + n21acbc;
        d.mod();
        e = calc(n, a % c, b % c, c);
        d.f += e.f;
        d.g += e.g;
        d.h += e.h + (b / c) * 2 * e.f % p + (a / c) * 2 * e.g % p;
        d.mod();
        return d;
    }
    if (a < c && b < c) {
        e = calc(m, c, c - b - 1, a);
        d.f = (n * (m + 1) % p - e.f) % p;
        d.mod();
        d.g = (n * (m + 1) % p * (n + 1) % p - e.h - e.f) % p * inv2 % p;
        d.mod();
        d.h = (n * (m + 1) % p * (m + 2) % p - e.g * 2 % p - e.f * 2 % p - d.f) % p;
        d.mod();
        return d;
    }
    return d;
}

int main() {
// 	freopen("P5170_6.in", "r", stdin);
// 	freopen("P5170.out", "w", stdout);
    int T; scanf("%d", &T); while (T--) {
        llt n, a, b, c;
        scanf("%lld %lld %lld %lld", &n, &a, &b, &c);
        zerc ans = calc(n, a, b, c);
        printf("%lld %lld %lld\n", ans.f, ans.h, ans.g);
    }
    return 0;
}

组合数学

第 II 类斯特林数

s[0][0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        s[i][j] = s[i-1][j] * j + s[i-1][j-1];

组合数

void init() {
    fac[0] = 1;
    for (int i = 1; i <= p; i++)
        fac[i] = (fac[i-1] * i) % p;
}
llt C (llt n, llt m) {
    if(m > n) return 0;
    return ((fac[n] * FastPower (fac[m], p-2, p)) % p * FastPower (fac[n-m], p-2, p) %p);
}

typedef long long llt;
const int siz = 100100;
const int p = 998244353;
const int ed = 200000;
int n;
char qp[siz];
llt fac[siz<<1], inv[siz<<1];
llt FastPower (llt a, llt b) {
    llt res = 1;
    for( ; b; b >>= 1, a = a * a % p)
        if(b & 1) res = res * a % p;
    return res;
}
llt C(int n, int m) {
    if (m > n) return 0; 
    return fac[n] * inv[m] % p * inv[n-m] % p;
}
void init () {
    fac[0] = 1;
    for (int i = 1; i <= ed; i++)
        fac[i] = fac[i-1] * i % p;
    inv[ed] = FastPower(fac[ed], p-2);
    for (int i = ed; i >= 1; i--)
        inv[i-1] = inv[i] * i % p;
}

计算几何

凸包 && 旋转卡壳

struct Dot {
    double x, y;
}p[SIZ], stack[SIZ];

double Len(Dot a, Dot b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double MulStar(Dot c, Dot a, Dot b) {
    return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}

bool Cmp(Dot a, Dot b) {
    if(MulStar(p[1], a, b) < 0) return 1;
    if(MulStar(p[1], a, b) == 0 && Len(a, p[1]) < Len(b, p[1])) return 1;
    return 0;
}

void GetConHull() {
    sort(p + 2, p + n + 1, Cmp);
    stack[++top] = p[1];
    for(int i = 2; i <= n; i++) {
        while(top > 1 && MulStar(stack[top], stack[top-1], p[i]) <= 0)
            --top;
        stack[++top] = p[i];
    }
    stack[top+1] = p[1];
}

double GetMaxD () {
    if(top == 1) return 0;
    if(top == 2) return Len(stack[top], stack[top-1]);
    for(int i = 1, j = 2; i <= top; i++) {
        while(MulStar(stack[i+1], stack[i], stack[j]) <= 
              MulStar(stack[i+1], stack[i], stack[j+1]))
            j = j == top ? 1 : j+1;
        ans = max (ans, Len(stack[i], stack[j]));
        ans = max (ans, Len(stack[i+1], stack[j]));
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lf%lf", &p[i].x, &p[i].y);
        if(p[i].y < p[1].y || (p[i].y == p[1].y && p[i].x < p[1].x))
            swap(p[1], p[i]);
    }
    // ···
}

半平main交

#include<algorithm>
#include<cstdio>
#include<cmath>
#define eps 1e-13
#define SIZ 100010
using namespace std;
int n, m, cnt, l, r;
struct Vector {
    double x, y;
    double Len() {return sqrt(x * x + y * y);}
    void operator += (const Vector &a) {
        x += a.x, y += a.y;}
    void operator -= (const Vector &a) {
        x -= a.x, y -= a.y;}
    void operator *= (const double &a) {
        x *= a, y *= a;}
    void operator /= (const double &a) {
        x /= a, y /= a;}
} input[SIZ], point[SIZ];
Vector operator + (const Vector &a, const Vector &b) {
    return ((Vector){a.x + b.x, a.y + b.y});}
Vector operator - (const Vector &a, const Vector &b) {
    return ((Vector){a.x - b.x, a.y - b.y});}
Vector operator * (const Vector &a, const double &b) {
    return ((Vector){a.x * b, a.y * b});}
Vector operator / (const Vector &a, const double &b) {
    return ((Vector){a.x / b, a.y / b});}
double MulDot (const Vector &a, const Vector &b) {
    return a.x * b.x + a.y * b.y;}
double MulCro (const Vector &a, const Vector &b) {
    return a.x * b.y - a.y * b.x;}
struct Line {
    Vector st, ed;
    double sigma;
    void MakeLine (const Vector &a, const Vector &b) {
        st = a, ed = b; sigma = atan2(b.y, b.x);}
} line[SIZ], que[SIZ];
bool OnRight (const Line &a, const Vector &b) {
    return MulCro(a.ed, b - a.st) <= -eps;}
bool Cmp (const Line &a, const Line &b) {
    return a.sigma < b.sigma;}
Vector Intersect (const Line &a, const Line &b) {
    return a.st + a.ed * (MulCro(b.ed, a.st - b.st) / MulCro(a.ed, b.ed));}
double PolyArea (int n, Vector *line) {
    double res = 0;
    for (int i = 1; i < n; i++) res += MulCro(line[i], line[i+1]);
    res += MulCro(line[n], line[1]);
    return res / 2;}
bool HalfPlane (int n, Line *a, Vector *point) {
    sort(line + 1, line + n + 1, Cmp);
    l = r = 0; que[0] = line[1];
    for (int i = 2; i <= n; i ++) {
        while (l < r && OnRight(line[i], point[r  ])) r--;
        while (l < r && OnRight(line[i], point[l+1])) l++;
        que[++r] = line[i];
        if (fabs(MulCro(que[r].ed, que[r-1].ed)) <= eps) {
            if (OnRight(que[r], que[r-1].st) && MulDot(que[r].ed, que[r-1].ed)<=eps) 
                return 0;
            r--;
            if (!OnRight(que[r], line[i].st)) que[r] = line[i];
        }
        if (l < r) point[r] = Intersect(que[r], que[r-1]);
    }
    while (l < r && OnRight(que[l], point[r])) r--;
    if (r - l <= 1) return 0;
    point[l] = Intersect (que[l], que[r]);
    return 1;
}
int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &m);
        for (int i = 1; i <= m; i++) 
            scanf("%lf%lf", &input[i].x, & input[i].y);
        for (int i = 1; i <  m; i++) 
            line[++cnt].MakeLine(input[i], input[i+1] - input[i]);
            line[++cnt].MakeLine(input[m], input[1] - input[m]);
    }
    if (!HalfPlane(cnt, line, point)) 
        printf("0.000");
    else 
        printf("%0.3lf\n", PolyArea(r - l + 1, point + l -1));
    return 0;
}

平main最近点对（随机旋转坐标系）

非正解

struct Point {
    double x, y;
    bool friend operator < (Point a, Point b) {
        return a.x < b.x;
    }
} point[200200];
double Len (Point a, Point b) {
    return sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void Revolve (double theta) {
    for (int i = 1; i <= n; i++) {
        double xx = point[i].x, yy = point[i].y;
        point[i].x = cos (theta) * xx - sin (theta) * yy;
        point[i].y = sin (theta) * xx + cos (theta) * yy;
    }
    sort (point + 1, point + n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= i + 100 && j <= n; j++)
            ans = min (ans, Len (point[i], point[j]));
}
int main () {
    srand (time (NULL));
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf ("%lf%lf", &point[i].x, &point[i].y);
    Revolve (0);
    Revolve ( rand() %360);
    Revolve ( rand() %360);
    Revolve ( rand() %360);
    printf ("%0.4lf", ans);
    return 0;
}

// max
    for (int i = 1; i <= 10; i++)
        for (int j = max (n - 100, 1); j <= n; j++)
            maxn = max (maxn, Len (point[i], point[j]));

图论

Dij

struct Edge {
    int tto, nxt, val;
} edge[siz<<1];
void add (int u, int v, int w) {
    edge[++cnt] = (Edge){v, head[u], w};
    head[u] = cnt;
}
void Dij () {
    memset (dis, 0x3f, sizeof(dis));
    dis[st] = 0;
    q.push ((ver){0, st});
    while (!q.empty()) {
        int uu = q.top ().i; q.pop();
        if (! vis[uu]) {
            vis[uu] = true;
            for (int i = head[uu]; i; i = edge[i].nxt) {
                int tt = edge[i].tto;
                if (dis[tt] > dis[uu] + edge[i].val) {
                    dis[tt] = dis[uu] + edge[i].val;
                    q.push ((ver){dis[tt], tt});
                }
            }
        }
    }
}

差分约束

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+3;

int n, m, cnt, head[maxn], dis[maxn], tot[maxn];
struct edge {int v, nxt, w;} e[maxn << 1];
bool vis[maxn];
queue<int> q;

void add(int u, int v, int w) {
    e[++cnt] = {v, head[u], w}, head[u] = cnt;
}

bool spfa(int u) {
    for (int i = 1; i <= n; i++)
        dis[i] = INT_MAX;
    vis[u] = 1;
    q.push(u);
    while (!q.empty()) {
        u = q.front(); q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            int w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    vis[v] = 1, tot[v]++;
                    q.push(v);
                    if (tot[v] == n + 1) {
                        return 0;
                    }
                }
            }
        }
    }
    return 1;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        add(0, i, 0);
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add(v, u, w);
    }
    if (spfa(0)) {
        for (int i = 1; i <= n; i++) {
            printf("%d ", dis[i]);
        }
    }
    else {
        printf("NO\n");
    }
    return 0;
}

最小生成树 kruskal

#include<bits/stdc++.h>
using namespace std;
long long ans;
int f[5050];
int n, m, now;
struct node{
    int u, v, w;
}tre[200020];
bool cmp(node x, node y){
    return x.w < y.w;
}
int find(int x){
    if(x == f[x]) return x;
    else f[x] = find(f[x]);
}
void kruskal(){
    for(int i = 1; i <= m; i++){
        int u = find(tre[i].u);
        int v = find(tre[i].v);
        if(u == v) continue;
        ans += tre[i].w;
        f[u] = v;
        now++;
        if(now == n - 1) break;
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        f[i] = i;
    for(int i = 1; i <= m; i++)
        cin >> tre[i].u >> tre[i].v >> tre[i].w;
    sort(tre + 1, tre + m + 1, cmp);
    kruskal();
    if(now == n - 1) cout << ans << endl;
    else cout << "orz" << endl;
    return 0;
}

网络流

最大流

#include<bits/stdc++.h>
using namespace std;
typedef long long llt;

const int maxn = 222;
const int maxm = 5555 << 1;

struct edge { int to, nxt, flow; }  e[maxm];
int cnt=1, head[maxn], dis[maxn], cur[maxm];
int n, m, s, t;

void add (int u, int v, int w) {
    e[++cnt] = {v, head[u], w}; head[u] = cnt;
    e[++cnt] = {u, head[v], 0}; head[v] = cnt;
}

bool bfs (int s, int t) {
    memset (dis, 0, sizeof dis);
    memcpy (cur, head, sizeof head);
    int x;  queue<int> q;
    q.push (s); dis[s] = 1;
    while (!q.empty ()) {
        x = q.front (); q.pop ();
        for (int i = head[x]; i; i = e[i].nxt) {
            if (e[i].flow && !dis[e[i].to]) {
                dis[e[i].to] = dis[x] + 1;
                q.push (e[i].to);
                if (e[i].to == t) return 1;
            }
        }
    }
    return 0;
}

llt dfs (int x, llt flow) {
    if (x == t) return flow;
    llt rest = flow; int i;
    for (i = cur[x]; i; i = e[i].nxt) {
        if (e[i].flow && dis[e[i].to] == dis[x] + 1) {
            llt k = dfs (e[i].to, min (rest, (llt)e[i].flow));
            if (!k) dis[e[i].to] = -1;
            e[ i ].flow -= k;
            e[i^1].flow += k;
            if (!(rest -= k)) break;
        }
    }
    cur[x] = i;
    return flow - rest;
}

llt Dinic () {
    llt maxflow = 0;
    while (bfs (s, t))
        maxflow += dfs (s, LLONG_MAX);
    return maxflow;
}

int Read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') 
        {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * f;
}

int main () {
    n=Read(), m=Read(), s=Read(), t=Read();
    // scanf ("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u = Read(), v=Read(), w=Read();
        // scanf ("%d %d %d", &u, &v, &w);
        add (u, v, w);
    }
    printf ("%lld\n", Dinic ());
}

随机化算法

随机数生成

srand (time (NULL));
int R = rand() %p;

随机化算法

随机旋转坐标系

数论 -> 计算几何

对拍

随机数据

对拍

注：from：tedukuri .

#include<cstdlib>
#include<cstdio>
#include<ctime>
int main() {
    for (int T = 1; T <= 10000; T++) {
        // 自行设定适当的路径
        system("C:\\random.exe");
        // 返回当前程序已经运行的CPU时间，windows下单位ms，类unix下单位s
        double st = clock();
        system("C:\\sol.exe");
        double ed = clock();
        system("C:\\bf.exe");
        if (system("fc C:\\data.out C:\\data.ans")) {
            puts("Wrong Answer");
            // 程序立即退出，此时data.in即为发生错误的数据，可人工演算、调试
            return 0;
        }
        else {
            printf("Accepted, 测试点 #%d, 用时 %.0lfms\n", T, ed - st);
        }
    }
}