首页 算法

# commit 命名规范

  • feat: 一个新功能
  • fix: 一个 bug 修复
  • docs: 仅仅修改了文档，比如 README, CHANGELOG, CONTRIBUTE 等
  • style: 不影响代码逻辑的修改，比如空格、格式缩进、删除分号等
  • refactor: 代码重构
  • perf: 提升性能的改动
  • test: 增加或修改测试
  • chore: 改变构建流程、或者增加辅助工具、依赖库等

# 2020.04.05 修改：

  • 2020.02 中的所有修改作废。

# 2020.02 修改：

  • 最近喜欢用 inline 。

  • 尽量避免强制类型转换。

  • 使用构造函数。

# 2020.01 修改：

  • 凡继承自 C 语言的库，均使用 <xxx.h> 而不是 <cxxx> 。

  • 以下情况中，运算符前后一定不加空格：

    • for 循环括号内内容较短时（e.g. for(int i=1; i<=n; ++i) ）

    • 运算符前后关系较密切时

  • 以下情况中，运算符前后一般不加空格：

    • 变量名长度为 1 时

  • 以下情况中，运算符前后可能不加空格：

    • 考试即将结束时

  • 以下情况中，运算符前后不可能不加空格：

    • 除以上情况之外的所有情况

  • typedef long long LL 。

# e.g.

（ 2-SAT 模板节选）

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <stack>
using namespace std;
const int N = 2e6 + 10;
struct node {
    int u, v, next;
    node() {}
    node(int _u, int _v, int _next): u(_u), v(_v), next(_next) {}
} e[N];
int h[N], tot = 0;
void add(int u, int v) {
    e[++tot] = node(u, v, h[u]);
    h[u] = tot;
}
int dfn[N], low[N], tag = 0;
int id[N], num = 0;
stack<int> s;
int n, m;
void tarjan(int u) {
    dfn[u] = low[u] = ++tag;
    s.push(u);
    for(int i = h[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(dfn[v]) {
            if(!id[v]) low[u] = min(low[u], dfn[v]);
        } else {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if(dfn[u] == low[u]) {
        id[u] = ++num;
        for(; s.top() != u; s.pop()) 
            id[s.top()] = num;
        s.pop();
    }
}
int main() {
    
    freopen("p4782.in", "r", stdin);
    
    scanf("%d%d", &n, &m);
    for(int i=1, _i, a, _j, b, u, v; i<=m; ++i) {
        scanf("%d%d%d%d", &_i, &a, &_j, &b);
        u = (_i-1)*2 + a, v = (_j-1)*2 + b;
        add(u^1, v);
        add(v^1, u);
    }
    
    for(int i=0; i<(n<<1); ++i)
        if(!dfn[i]) tarjan(i);
    
    for(int i=0; i<(n<<1); i+=2) {
        if(id[i] == id[i^1]) {
            printf("IMPOSSIBLE\n");
            return 0;
        }
    }
    
    printf("POSSIBLE\n");
    for(int i=0; i<(n<<1); i+=2) 
        printf("%d ", id[i] < id[i^1] ? 0 : 1);
    
    return 0;
}
# 考场码风：
（牛客 CSP-S 提高组赛前集训营 2 T3 - 维护序列 2019.10.31 ）
#include <cstdio>
 
const int N = 100005, INF = 0x7fffffff;
int abs(int x) { return x > 0 ? x : -x; }
int min(int a, int b) { return a > b ? b : a; }
 
struct node {
    int a, b, f, s;
    node *l, *r;
} *root, pool[4*N];
 
struct pair {
    int l, r;
} tmpx[N], tmpy[N];
 
int id = -1, cntx, cnty;
int s[N];
node *newnode(int a, int b) {
    pool[++id] = (node) {a, b, s[a], 0, NULL, NULL};
    return &pool[id];
}
 
void build(node *&root, int a, int b) {
    root = newnode(a,b);
    if(a<b) {
        int mid = (a+b) >> 1;
        build(root->l, a, mid);
        build(root->r, mid+1, b);
        if(root->l->f == root->r->f) root->f = root->l->f;
        else root->f = 0;
    }
}
 
bool check(node *root, int x) {
     
    if(root->f) return (root->f == x);
 
    bool s1 = check(root->l, x);
    bool s2 = check(root->r, x);
    return (s1 or s2);
     
}
 
 
void edit(node *root, int a, int b, int x) {
    if(a <= root->a and root->b <= b) {
        root->f = x;
        return;
    }
    if(root->f) {
        root->l->f = root->f;
        root->r->f = root->f;
        root->f = 0;
    }
    int mid = (root->a + root->b) >> 1;
    if(a <= mid) edit(root->l, a, b, x);
    if(mid < b) edit(root->r, a, b, x);
}
bool query(node *root, int x, int y) {
     
    if(root->f) {
        if(root->f == x) tmpx[++cntx] = (pair) {root->a, root->b};
        else if(root->f == y) tmpy[++cnty] = (pair) {root->a, root->b};
        else return false;
        return true;
    }
     
    bool s1 = query(root->l, x, y);
    bool s2 = query(root->r, x, y);
     
    return (s1 or s2);
}
 
inline int read() {
    char c = getchar();
    int x=0, f=1;
    while(c < '0' or c > '9') { f = (c == '-') ? -1 : f; c = getchar(); }
    while(c >='0' and c <='9') { x = (x<<3) + (x<<1) + (c-'0'); c = getchar(); }
    return x*f;
}
 
int lastans = 0;
int main() {
     
    int n = read(), m = read(), flag = read();
    for(int i=1; i<=n; ++i) s[i] = read();
    build(root, 1, n);
     
    for(int ii=1; ii<=m; ++ii) {
        if(!flag) lastans = 0;
        int opt = read();
        if(opt == 1) {
            int l = read()^lastans, r = read()^lastans, x = read()^lastans;
            edit(root, l, r, x);
        }
        if(opt == 2) {
            int x = read()^lastans, y = read()^lastans;
            if(x == y) {
                bool f = check(root, x);
                lastans = 0;
                printf("%d\n", f ? 0 : -1);
                continue;
            }
            cntx = cnty = 0;
            bool f = query(root, x, y);
            if(!f or !cntx or !cnty) {
                printf("-1\n");
                lastans = 0;
                continue;
            }
            lastans = INF;
            for(int i=1; i<=cntx; ++i) {
                for(int j=1; j<=cnty; ++j) {
                    lastans = min(lastans, abs(tmpx[i].r - tmpy[j].l));
                    lastans = min(lastans, abs(tmpx[i].l - tmpy[j].r));
                }
            }
            printf("%d\n", lastans);
        }
         
    }
     
    return 0;
}
 
 更新于