Spaceless

算法竞赛模板

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

快读

1
2
3
4
5
6
7
8
9
10
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
29
#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