Spaceless

算法竞赛模板

说来惭愧,上次整理算法模板是最后一次前NOIP做了个PDF,感觉已经过去了很久,现在重新整理一遍好了w

快读

1
2
3
4
5
6
7
8
9
int read(){
int re=0,ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){
re=re*10+ch-'0';
ch=getchar();
}
return re;
}

快读压成一行

1
int read(){int re=0,ch=getchar();while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9'){re=re*10+ch-'0';ch=getchar();}return re;}

ST表

首先先喷luogu这题卡cin==真的蛋疼

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
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

int n,m;
int Max[1000005][21];

int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&Max[i][0]);
for(int j=1;j<=20;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
int k=log2(r-l+1);
printf("%d\n",max(Max[l][k],Max[r-(1<<k)+1][k]));
}
return 0;
}
//ST表模板题
//MDZZ洛谷,模板题卡cin

ST表是解决RMQ问题(区间最值问题)的一种强有力的工具

它可以做到O(nlogn)预处理,O(1)查询最值

ST表是利用的是倍增的思想

拿最大值来说

我们用Max(i,j)表示,从i位置开始的2^j个数中的最大值,例如Max(i,1)表示的是i位置和i+1位置中两个数的最大值

那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值(注意这里的编号是从1开始的)

img

查询的时候先计算出log2区间长度

再对于左端点和右端点分别进行查询,这样可以保证一定可以覆盖查询的区间

img

从右端点开始查的时候左端点是r-2^k+1

二分

一般来说,二分是个很有用的优化途径,因为这样会直接导致减半运算,而对于能否二分,有一个界定标准:状态的决策过程或者序列是否满足单调性或者可以局部舍弃性。 什么叫做局部舍弃性呢,如洛谷P1083 借教室这个题里,因为如果前一份订单都不满足,那么之后的所有订单都不用继续考虑;而如果后一份订单都满足,那么之前的所有订单一定都可以满足,符合局部舍弃性,所以可以二分订单数量。

差分

这个是从 https://www.luogu.com.cn/problemnew/solution/P1083 这个题目的题解看的。很惭愧,我一直不知道这东西居然有名字叫做差分==

(接下来都是拷贝自_皎月半洒花的(有微小的改动),我觉得花老师讲的挺好的,原作者博客 在Ta的博客查看

在介绍差分之前,需要介绍前缀和思想

(qwq此处当然只会讲一维线性的前缀和啦)

我们有一组数(个数小于等于一千万),并且有一大堆询问——给定区间l、r,求l、r之间所有数之和(询问个数小于等于一千万)

此处暴力肯定不行啊(O(NQlength)),那么我们来观察前缀和是怎么做的:用sum[i]来存储前i个数的和,然后用sum[r]-sum[l-1]来表示lr之间所有数的和。(l-1原因是lr只看要包含l)而sum数组便可以通过简单的递推求出来

代码核心:

1
2
for(int i=1;i<=n;i++) {cin>>a[i];sum[i]=sum[i-1]+a[i];}
for(int i=1;i<=q;i++) {cin>>l>>r;cout<<sum[r]-sum[l-1]<<" ";}

而所谓的差分数组,即是前缀和数组的逆运算:

我们给定前i个数相邻两个数的差(1<=i<=n),求每一项a[i](1<=i<=n)。

此时无非就是用作差的方式求得每一项,此时我们可以有一个作差数组diff,diff[i]用于记录a[i]-a[i-1],所以a[i]=diff[i]+a[i-1],然后对于每一项a[i],我们可以递推出来:

1
2
for(int i=1;i<=n;i++) {cin>>diff[i];a[i]=diff[i]+a[i-1];}
for(int i=1;i<=n;i++) {cout<<a[i];}

到这儿,我们可以看出来,前缀和是用元数据求元与元之间的并集关系,而差分则是根据元与元之间的逻辑关系求元数据,是互逆思想(qwq但是有时元数据和关系数据不是很好辨别或者产生角色反演啊)

但是,理解了前缀和&差分,并不代表肯定能做到模板题:毕竟,思想只能是辅助工具

(拷贝结束)

以下是我的luogu P1083代码,二分+差分模板题

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
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int MAXN=1000003;
int n,m;
int day[MAXN];//不要把这个东西定义在函数体内,mgj会爆
int r[MAXN],d[MAXN],s[MAXN],t[MAXN];//第i天可用教室数,租借数量,开始,结束
//int debug_sum;

bool judgemid(int mid)
{
//printf("%d\n",++debug_sum);
memset(day,0,sizeof(day));
for(int i=1;i<=mid;i++)
{
day[s[i]]+=d[i];
day[t[i]+1]-=d[i];
}
if(day[1]>r[1]) return true;
for(int i=2;i<=n;i++)
{
day[i]+=day[i-1];
if(day[i]>r[i]) return true;
}
return false;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) scanf("%d",r+i);
for(int i=1; i<=m; i++) scanf("%d%d%d",d+i,s+i,t+i);
int le=1,ri=m;
while(le<ri)
{
int mid=(le+ri)>>1;
//printf("%d\n",mid);
if(judgemid(mid)) ri=mid;
else le=mid+1;
}
if(m!=ri) printf("-1\n%d",ri);
else printf("0");
return 0;
}

GCD

1
2
3
4
inline int gcd(int a,int b) {
return b>0 ? gcd(b,a%b):a;
}
//此段代码a、b可以为0
1
2
3
4
5
inline int gcd(int a,int b) {
while(b^=a^=b^=a%=b);
return a;
}
//此段代码a、b不能为0