板子集

zerc · 2022-06-01 11:50:22 · 个人记录

前言

部分 code 来自《算法竞赛进阶指南》和 OI-WiKi，对引用的 code 已标明出处 .
此文章只是为了整理归纳，或以备忘 .
所有 code 不保证能够不 CE, RE, TLE, MLE, WA. 不要复制粘贴， ~~（有的是懒得翻 AC 过的而在 Typora 里现写~~ . 如有错，评论 .

码风解释

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;
}

一种比较 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;
}

位运算

二进制操作

(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;
}

数据结构

单调栈

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;
}

字符串

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;

数论

dalao's blog

质数 && 筛法

注：参照：筛法 - 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;
}

高斯消元

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;
}

组合数学

第 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]));

图论

并查集

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;
}

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});
                }
            }
        }
    }
}

最小生成树 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;
}

随机化算法

随机数生成

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);
        }
    }
}