Others
binary search
1 | //求最小的i，使得a[i] = key，若不存在，则返回-1 |
蔡勒公式
求星期
1 | int week(int y,int m,int d){ |
DLX算法
精准覆盖问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67int a[N];
struct node{
int l,r,u,d,col,row;
};
struct DLX{
node p[M];
int len;
int size[N],last[N];
inline void make(int l,int r,int u,int d,int col,int row){len++;p[len].l=l;p[len].r=r;p[len].u=u;p[len].d=d;p[len].col=col;p[len].row=row;}
inline void ud_del(int x){p[p[x].u].d=p[x].d;p[p[x].d].u=p[x].u;}
inline void ud_res(int x){p[p[x].u].d=p[p[x].d].u=x;}
inline void lr_del(int x){p[p[x].l].r=p[x].r;p[p[x].r].l=p[x].l;}
inline void lr_res(int x){p[p[x].l].r=p[p[x].r].l=x;}
inline void init(int m){//m - number of column
len=0;
p[0].l=p[0].r=p[0].u=p[0].d=0;
for(int i=1;i<=m;i++){
size[i]=0;
last[i]=i;
make(i-1,p[i-1].r,i,i,i,0);
lr_res(i);
}
}
inline void add(int row){
if(a[0]==0)return;
make(len+1,len+1,last[a[1]],p[last[a[1]]].d,a[1],row);
ud_res(len);
size[a[1]]++;
last[a[1]]=len;
for(int i=2;i<=a[0];i++){
make(len,p[len].r,last[a[i]],p[last[a[i]]].d,a[i],row);
ud_res(len);
lr_res(len);
size[a[i]]++;
last[a[i]]=len;
}
}
inline void del(int x){
lr_del(x);
for(int i=p[x].u;i!=x;i=p[i].u){
for(int j=p[i].l;j!=i;j=p[j].l)ud_del(j),size[p[j].col]--;
}
}
inline void res(int x){
lr_res(x);
for(int i=p[x].u;i!=x;i=p[i].u){
for(int j=p[i].l;j!=i;j=p[j].l)ud_res(j),size[p[j].col]++;
}
}
int dance(int dep){
if(!p[0].r)return dep;
int c,mi=inf;
for(int i=p[0].r;i;i=p[i].r){
if(size[p[i].col]<mi)mi=size[p[i].col],c=i;
}
if(mi==0)return 0;
del(c);
for(int i=p[c].u;i!=c;i=p[i].u){
for(int j=p[i].l;j!=i;j=p[j].l)del(p[j].col);
int tt=dance(dep+1);
if(tt)return tt;
for(int j=p[i].r;j!=i;j=p[j].r)res(p[j].col);
}
res(c);
return 0;
}
}dlx;
最小重复覆盖
允许列重复，求满足覆盖的最小行数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82int a[N];
struct node{
int l,r,u,d,col,row;
};
int ans;
struct DLX{
node p[M];
int len;
int size[N],last[N];
inline void make(int l,int r,int u,int d,int col,int row){len++;p[len].l=l;p[len].r=r;p[len].u=u;p[len].d=d;p[len].col=col;p[len].row=row;}
inline void ud_del(int x){p[p[x].u].d=p[x].d;p[p[x].d].u=p[x].u;}
inline void ud_res(int x){p[p[x].u].d=p[p[x].d].u=x;}
inline void lr_del(int x){p[p[x].l].r=p[x].r;p[p[x].r].l=p[x].l;}
inline void lr_res(int x){p[p[x].l].r=p[p[x].r].l=x;}
inline void init(int x){
len=0;
p[0].l=p[0].r=p[0].u=p[0].d=0;
for(int i=1;i<=x;i++){
size[i]=0;last[i]=i;
make(i-1,p[i-1].r,i,i,i,0);
lr_res(i);
}
}
inline void add(int row){
if(a[0]==0)return;
make(len+1,len+1,last[a[1]],p[last[a[1]]].d,a[1],row);
ud_res(len);
size[a[1]]++;
last[a[1]]=len;
for(int i=2;i<=a[0];i++){
make(len,p[len].r,last[a[i]],p[last[a[i]]].d,a[i],row);
ud_res(len);
lr_res(len);
size[a[i]]++;
last[a[i]]=len;
}
}
inline void del(int x){
for(int i=p[x].u;i!=x;i=p[i].u){
lr_del(i);
}
}
inline void res(int x){
for(int i=p[x].u;i!=x;i=p[i].u){
lr_res(i);
}
}
bool vis[N];
int ex(){//使用 A* 的期望函数来剪枝
int cnt=0;
mem0(vis);
for(int i=p[0].r;i;i=p[i].r){
if(vis[i])continue;
cnt++;
vis[i]=1;
for(int j=p[i].u;j!=i;j=p[j].u){
for(int k=p[j].l;k!=j;k=p[k].l)vis[p[k].col]=1;
}
}
return cnt;
}
void dance(int dep){
if(dep+ex()>=ans)return;
if(!p[0].r){
ans=min(ans,dep);
return;
}
int first,mi=inf;
for(int i=p[0].r;i;i=p[i].r){
if(size[p[i].col]<mi)mi=size[p[i].col],first=i;
}
if(mi==0)return;
for(int i=p[first].u;i!=first;i=p[i].u){
del(i);
for(int j=p[i].l;j!=i;j=p[j].l)del(j);
dance(x+1);
for(int j=p[i].r;j!=i;j=p[j].r)res(j);
res(i);
}
return ;
}
}dlx;
读入挂
整数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16inline void read(ll &x) {
ll f=1;
x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
x*=f;
}
inline void write(ll x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x >= 10)write(x / 10);
putchar(x % 10 + '0');
}
实数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32inline bool scan_lf(double &num) {
char in;
double Dec = 0.1;
bool IsN = false, IsD = false;
in = getchar();
if (in == EOF) return false;
while (in != '-' && in != '.' && (in < '0' || in > '9')) in = getchar();
if (in == '-') {
IsN = true;
num = 0;
} else if (in == '.') {
IsD = true;
num = 0;
} else num = in - '0';
if (!IsD) {
while (in = getchar(), in >= '0' && in <= '9') {
num *= 10;
num += in - '0';
}
}
if (in != '.') {
if (IsN) num = -num;
return true;
} else {
while (in = getchar(), in >= '0' && in <= '9') {
num += Dec * (in - '0');
Dec *= 0.1;
}
}
if (IsN) num = -num;
return true;
}
分数
1 | ll gcd(ll a,ll b){ |
归并排序
1 | void merge_core(int arr[], int begin, int mid, int end){//将两个有序数组合并成一个 |
利用归并排序求逆序对
1 | int tmpA[100005], cnt = 0; |
hash_table
1 | const int seed = N; |
快速排序
1 | void quick_sort(int l,int r,int m[]){ |
曼哈顿距离和切比雪夫距离
曼哈顿距离
$\large dis_m=|x1-x2|+|y1-y2|$
切比雪夫距离
$\large dis_q=max(|x1-x2|,|y1-y2|)$
转换
- 将坐标 $(x,y)\to(x+y,x-y)$ ，原坐标的 $dis_m$ 等于新坐标的 $dis_q$
- 将坐标 $(x,y)\to(\frac {x+y}2,\frac {x-y}2)$ ，原坐标的 $dis_q$ 等于新坐标的 $dis_m$
位运算
按位与运算符（&）
运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;
x & (x - 1)
1.用于消去x最后一位的1
2.检查n是否为2的幂次
3.计算在一个 32 位的整数的二进制表式中有多少个 1
4.如果要将整数A转换为B，需要改变多少个bit位：对A^B进行操作Lowbit(x)
1
2x&(-x)
x&(x^(x-1))枚举所有集合的子集
1
2
3
4
5for (int S=1,len=1<<n; S<len; S++){
for (int T=(S-1)&S; T ; T=(T-1)&S){ //枚举S的所有非空真子集
//do something.
}
}
按位或运算符（|）
- 运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1
异或运算符（$\text{^}$）
- 运算规则：$\text{0^0=0； 0^1=1； 1^0=1； 1^1=0；}$
- 性质：
1.交换律
2.结合律 $\text{即(a^b)^c == a^(b^c)}$
3.对于任何数 x，都有 $\text{x^x=0，x^0=x}$
4.自反性: $\text{a^b^b=a^0=a;}$ - $\text{a ^ b ^ b = a}$
数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数
线性递推式
1 |
|