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