其他

二维差分

设$d[][]$为$a[][]$的差分数组，则有

$$d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$$

使用二维差分可以做到二维区间修改，单点查询，比如（借用知乎大佬的图片）：

在图一所示的差分数组的地方加d，则对应原数组（图三）的区域都加d

因此，在左上角$(x_1,y_1)$，右下角$(x_2,y_2)$的区域上都加上v，有：

$$d[x_1][y_1]+=v$$

$$d[x_2+1][y_1]-=v$$

$$d[x_1][y_2+1]-=v$$

$$d[x_2+1][y_2+1]+=v$$

在差分数组中进行二维前缀和，就可以得到原数据

LIS

$O(n log n)$ 的求LIS做法

cpp
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
#include<iostream>
#include<algorithm>
using namespace std;

int a[1000006];
int s[1000006],tot;//栈 

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	s[++tot]=a[1];//把第一个数入栈
	for(int i=2;i<=n;i++){
		if(a[i]>s[tot]) s[++tot]=a[i];
		else{
			int tmp=lower_bound(s+1,s+tot+1,a[i])-s;//在栈中查找第一个大于等于a[i]的数，然后替换掉
			s[tmp]=a[i]; 
			
		}
	} 
	cout<<tot;
	return 0;
} 

高精度算法

• string转Lint部分，没有去除前导零

• 所有的加减乘除都默认是两个正整数操作，没有考虑0和负数

• 比较大小的时候倒序循环！

• 除法注意c.len可能为负数，需要变成0

• Lint含参构造器中无法再去调用无参构造函数，需要直接把代码复制过来

结构体

cpp
1
2
3
4
5
6
7
8
9
10
11
12
struct Lint{
	int num[maxn*2],len;char op;
	Lint(){memset(num,0,sizeof(num));len=1;op='+';}
	Lint(string str){memset(num,0,sizeof(num));len=1;op='+';
		if(str[0]=='-') op='-',str.erase(0,1);
		for(int i=1;i<=str.size();i++) num[i]=(int)(str[str.size()-i])-'0';
		len=str.size();
	}
	Lint(int a,int t=0){memset(num,0,sizeof(num));len=1;op='+';
		for(;a;len=++t,a/=10) num[t]=a%10;
	}
};

大小比较

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool operator>(Lint a,Lint b){
	if(a.op!=b.op) return a.op=='+';
	if(a.len>b.len) return a.op=='+';
	if(a.len<b.len) return a.op!='+';
	for(int i=a.len;i>=1;i--){
		if(a.num[i]>b.num[i]) return a.op=='+';
		else if(a.num[i]<b.num[i]) return a.op!='+';
	}
	return false;
}
bool operator==(Lint a,Lint b){
	if(a.len!=b.len) return false;
	for(int i=a.len;i>=1;i--) if(a.num[i]!=b.num[i]) return false;
	return true;
}
bool operator<(Lint a,Lint b){
	return (!(a>b)&&!(a==b));
}

加减乘

cpp
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
Lint operator+(Lint a,Lint b){
	Lint c;c.len=max(a.len,b.len);
	for(int i=1;i<=c.len;i++) c.num[i]=a.num[i]+b.num[i];
	for(int i=1;i<=c.len;i++)
		if(c.num[i]>=10)
			c.num[i+1]+=c.num[i]/10,c.num[i]%=10,c.len=max(c.len,i+1);
	while(c.len>0&&!c.num[c.len]) c.len--;
	return c;
}
Lint operator-(Lint a,Lint b){
	Lint c;c.len=max(a.len,b.len);
	if(b>a) c.op='-',swap(a,b);
	for(int i=1;i<=c.len;i++) c.num[i]=a.num[i]-b.num[i];
	for(int i=1;i<=c.len;i++)
		if(c.num[i]<0) 
			c.num[i]+=10,c.num[i+1]-=1;
	while(c.len>0&&!c.num[c.len]) c.len--;
	return c;
}
Lint operator*(Lint a,Lint b){
	Lint c;
	c.len=a.len+b.len+1;
	for(int i=1;i<=a.len;i++)
		for(int j=1;j<=b.len;j++) c.num[i+j-1]+=a.num[i]*b.num[j];
	for(int i=1;i<=c.len;i++)
		if(c.num[i]>=10)
			c.num[i+1]+=c.num[i]/10,c.num[i]%=10,c.len=max(c.len,i+1);
	while(c.len>0&&!c.num[c.len]) c.len--;
	return c;
}

除/取模

cpp
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
Lint numcpy(Lint a,int l){
	Lint b;
	for(int i=1;i<=a.len;i++) b.num[i+l-1]=a.num[i];
	return b.len=a.len+l-1,b;
}
Lint operator/(Lint a,Lint b){
	Lint c;
	c.len=a.len-b.len+1;
	for(int i=c.len;i>=1;i--){
		Lint t=numcpy(b,i);
		while(a>t||a==t){
			c.num[i]++,a=a-t;
			while(a.len>0&&!a.num[a.len]) a.len--;
		}
	}
	if(c.len<0) c.len=0;
	while(c.len>0&&!c.num[c.len]) c.len--;
	return c;
}
Lint operator/(Lint a,int b){
	Lint c;c.len=a.len;
	for(int i=a.len,d=0;i>=1;i--){
		c.num[i]=(d=d*10+a.num[i])/b;
		d%=b;
	}
	while(c.len>0&&!c.num[c.len]) c.len--;
	return c;
} 
Lint operator %(Lint a,Lint b){
	for(int i=a.len-b.len+1;i>=1;i--){
		Lint t=numcpy(b,i);
		while(a>t||a==t){
			a=a-t;
			while(a.len>0&&!a.num[a.len]) a.len--;
		}
	} 
	return a;
}

贪心

（1）选择不相交区间：按照区间右端点排序，依次选择

cpp
1
2
3
4
5
6
7
8
9
10
11
signed main(){
    n=read();
    for(int i=1;i<=n;i++) line[i].s=read(),line[i].t=read();
    sort(line+1,line+n+1,[](Line x,Line y){return x.t<y.t;});
    int p=0,ans=0;
    for(int i=1;i<=n;i++){
        if(line[i].s>=p) ans++,p=line[i].t;
    }
    cout<<ans;
    return 0;
}

（原题给的区间是左闭右开的）

（2）区间选点问题：按照区间右端点排序，依次解决

cpp
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
signed main(){
    n=read(),h=read();
    for(int i=1;i<=h;i++) line[i].s=read(),line[i].t=read(),line[i].x=read();
    sort(line+1,line+h+1,cmp);
    int ans=0;
    for(int i=1;i<=h;i++){
        int s=line[i].s,t=line[i].t,x=line[i].x;
        int tmp=query(t)-query(s-1);//先判断已经覆盖了几个点
        if(tmp>=x) continue;//已经覆盖完毕
        x-=tmp;//没有覆盖完，计算还剩多少
        ans+=x;//先贡献答案
        int p=t;//从区间右端点开始暴力选点
        while(x){
            if(p<s) break;
            if(mark[p]){
                p--;
                continue;
            }
            x--;
            mark[p]=true;
            modify(p,1);
            p--;
        }
    }
    cout<<ans;
    return 0;
}

（3）区间覆盖问题：按照区间左端点排序。t为当前已覆盖区间的右端点。然后依次选择区间，选择能覆盖t，且右端点最大的区间，选择后用这个区间的右端点更新t，继续选择。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
sort(line+1,line+n+1,cmp);
double now=0;
int i=1,ans=0,fail=0;
while(now<L){//now为当前已经覆盖的右端点
	ans++;
	double s=now;
	for(;line[i].l<=s&&i<=n;i++) now=max(now,line[i].r);
	if(now==s&&now<L){//没有找到可以覆盖右端点的区间，说明无解
		cout<<-1<<endl;
		fail=1;
		break;
	}
}
if(!fail) cout<<ans<<endl;

（4）流水作业调度问题：$a_i$，$b_i$ 分别表示在A机器和B机器上执行需要消耗的时间。$m_i=min(a_i,b_i)$，然后将 $m[]$ 排序。然后，有两个指针 $l=0,r=n+1$，$ans[]$ 为答案序列。遍历 $m_i$，如果 $m_i=a_i$，那么 $ans[++l]=i$，反之 $ans[--r]=i$

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sort(task+1,task+n+1,cmp);
int l=1,r=n;
for(int i=1;i<=n;i++){
	if(task[i].a<task[i].b) li[l++]=task[i].index;
	else li[r--]=task[i].index;
}
//按照下面的方法计算方案所用时间
int ta=0,tb=0;
for(int i=1;i<=n;i++){
	ta+=t[li[i]].a;
	if(tb<ta) tb=ta;
	tb+=t[li[i]].b;
}
cout<<tb<<endl;
for(int i=1;i<n;i++) cout<<li[i]<<' ';
cout<<li[n];

（5）带限期和罚款的单位时间任务调度：将罚款从大到小排序。对于一个任务，从任务到期时间开始从后往前枚举时间点，如果枚举到的时间点没有被安排，那么安排当前任务。如果没有一个时间点都被安排，那么就罚款

康拓展开

康托展开可以求一个排列的在全部排列中的排名

如求842697513是长度为9的排列中按字典序排序的第几个排列

我们先求出比给定排列小的排列的数量

可以有如下过程求解：

• 第一位取1到7，都可以满足，第一位贡献答案为 $7\times 8!$

• 第一位取8，第二位取1到3，都可以满足，第二位贡献答案为 $3\times 7!$

• 第一位取8，第二位取4，第三位取1到1，都可以满足，第三位贡献答案为 $1\times 6!$

• 第一位取8，第二位取4，第三位取2，第四位取1到5，都可以满足，注意这里，第四位实际上可取的数字只有1、3、5，因为2、4已经被前面取完了，因此第四位贡献答案为 $3\times 5!$

...

上述统计这一位能取到的数字有几个，可以用树状数组维护

正康拓展开

cpp
1
2
3
4
5
6
7
8
9
10
11
inline int kt(char s[8]){
	int res=0;
	for(int i=0;i<8;i++){
		int tot=0;
		for(int j=i+1;j<8;j++){
			if(s[j]<s[i]) tot++;//找后面比当前数还要小的 
		}
		res+=tot*fac(7-i);//能够枚举到几，就用几减去i 
	}
	return res+1;
}

还可以结合树状数组优化

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fac[100005],in[100005];
void init(){
	fac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
	for(int i=1,i<=n;i++) add(i,1);
}

int kt(){
	int res=0;
	for(int i=1;i<=n;i++){
		int tot=sum(in[i])-1;
		add(in[i],-1);
		res+=tot*fac[n-i];
	}
	return res+1;
}

逆康拓展开

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void get(int o){
	o--;//和正康拓展开一样
	memset(bu,0,sizeof(bu));
	for(int i=1;i<=n;i++){
		int t=o/fac[n-i]+1;//当前这个数的排名，注意加一
		int now=0,j=1;//j为枚举的数，now为当前排名
		for(;j<=n;j++){
			if(bu[j]) continue;//之前已经枚举了，跳过
			now++;
			if(now==t) break;//排名枚举完毕
		} 
		bu[j]=true;
		cout<<j<<' ';//输出
		o%=fac[n-i];//再模一下。注意还是能枚举到的最大数-当前枚举数
	}
	cout<<endl;
}

双向bfs

以poj1915为例

cpp
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
        qa.push(make_pair(ax,ay));//起点 
		qb.push(make_pair(bx,by));//终点 
		while(!qa.empty()&&!qb.empty()){//两个都不能为空 
			pii nowa=qa.front();qa.pop();//两个队列各取一个			
			pii nowb=qb.front();qb.pop();
			//遍历的状态重合 
			if(visa[nowb.first][nowb.second]||visb[nowa.first][nowa.second]){
				cout<<cnta[nowb.first][nowb.second]+cntb[nowb.first][nowb.second]<<endl;
				break;
			}
			for(int i=0;i<8;i++){
                //两边各自扩展
				int nx,ny;
				nx=nowa.first+dx[i];
				ny=nowa.second+dy[i];
				if(nx>=0&&nx<k&&ny>=0&&ny<k){
					if(!visa[nx][ny]){
						cnta[nx][ny]=cnta[nowa.first][nowa.second]+1;
						visa[nx][ny]=true;
						qa.push(make_pair(nx,ny));
					}
					
				}
				
				nx=nowb.first+dx[i];
				ny=nowb.second+dy[i];
				if(nx>=0&&nx<k&&ny>=0&&ny<k){
					if(!visb[nx][ny]){
						cntb[nx][ny]=cntb[nowb.first][nowb.second]+1;
						visb[nx][ny]=true;
						qb.push(make_pair(nx,ny));
					}
				}
			}			
		}	

cpp
1
if(p==b.size()) ans++,p=0; //p=0，防止重复匹配

模拟退火

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const double dt=0.9112;
int ans=0x3f3f3f3f3f3f3f3f;//先有个全局答案
void sa(double t){
    int tmp=0x3f3f3f3f3f3f3f3f;//有个局部答案
	while(t>1e-10){
        //这里进行随机操作
        //记录下操作前的答案A和操作后的答案B
		int d=B-A;//拿操作后的减去操作前的，这里是答案越小越好。反之就A-B。总之d为答案的差距，必须为正
		if(d<0||(exp(d/t)*RAND_MAX<rand())){
            //接受答案了
		}else{//如果答案不优，且温度下降到临界，就不接受答案
			//这里进行撤销操作
		}
		t*=dt;
	}
	ans=min(ans,tmp);//将局部答案推送到全局
} 

一般要进行1000-3000多次模拟退火，具体可以卡时

又一个例子

P3878 [TJOI2010]分金币

cpp
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
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
#define int long long
using namespace std;

int in[31],n,bl[31],sum[3],cnt[3],t;
const double dt=0.9112;
int ans=0x3f3f3f3f3f3f3f3f;

void sa(double t){
    //先随机出一个方案
	cnt[1]=0,cnt[2]=0;
	sum[1]=0,sum[2]=0;
	for(int i=1;i<=n;i++){
		if(cnt[1]>cnt[2]){
			bl[i]=2;
			cnt[2]++;
			sum[2]+=in[i];
		}else if(cnt[2]>cnt[1]){
			bl[i]=1;
			cnt[1]++;
			sum[1]+=in[i];
		}else{
			bl[i]=rand()%2+1;
			cnt[bl[i]]++;
			sum[bl[i]]+=in[i];
		}
	}
	int tmp=abs(sum[1]-sum[2]);
    //然后开始模拟退火
	while(t>1e-10){
        //每次随机交换两个位置
		int x=rand()%n+1;
		int y=rand()%n+1;
		
		sum[bl[x]]-=in[x];
		sum[bl[y]]-=in[y];
		swap(in[x],in[y]);
		sum[bl[x]]+=in[x];
		sum[bl[y]]+=in[y];
		int back=tmp;
        //先接受答案
		tmp=abs(sum[1]-sum[2]);
		int d=tmp-back;
		if(d<0||(exp(d/t)*RAND_MAX<rand())){
			//cout<<"ac"<<endl;
		}else{//如果答案不优，且温度下降到临界，就不接受答案
			sum[bl[x]]-=in[x];
			sum[bl[y]]-=in[y];
			swap(in[x],in[y]);
			sum[bl[x]]+=in[x];
			sum[bl[y]]+=in[y];
			tmp=back;
		}
		t*=dt;
	}
	ans=min(ans,tmp);//将局部答案推送到全局
} 

void subtask(int k){
	ans=0x3f3f3f3f3f3f3f3f;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>in[i];
	for(int i=1;i<=1000;i++) sa(5000);//多次模拟退火
	cout<<ans<<endl;
}

signed main(){
	srand((unsigned)time(NULL));
	cin>>t;
	for(int i=1;i<=t;i++){
		subtask(i);
	}
	return 0;
}