算法

和小哥哥一起刷洛谷(10)

二分答案进阶

SP1296 SUMFOUR - 4 values whose sum is 0（二分搜索）

思路

这题的数据量显然不能暴力枚举的（$O(n^4)=O(4000^4)$）

其实我们可以将四个数列中前两个数列中的数按不同排列两两加起来存进数组，后两个数列中的数按也不同排列两两加起来存进数组（其实不必要，本人脑子一时“抽搐”来着）。再遍历第一个数组中的每一个数，再从第二个数组中二分查找出一个与前一个数的和为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
32
33
34
35
36
37
38
39
40

#include<cstdio>
#include<algorithm>
using namespace std;
const int NR=4005;
const int MAXN=16000005;
int n,t=0,cnt=0,lf,rt,arr[4][NR],tb[2][MAXN];
inline int l_b(int l,int r,int k,int arr[]){
    int m;
    while(l<r){
        m=(l+r)>>1;
        if(arr[m]<k)l=m+1;
        else r=m;
    }
    return (arr[l]==k?l:-1);
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d%d%d",&arr[0][i],&arr[1][i],&arr[2][i],&arr[3][i]);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            tb[0][t++]=arr[0][i]+arr[1][j];
    sort(tb[0],tb[0]+t);
    t=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            tb[1][t++]=arr[2][i]+arr[3][j];
    sort(tb[1],tb[1]+t);
    for(int i=0;i<t;i++){
        lf=l_b(0,t-1,-tb[0][i],tb[1]);
        if(lf!=-1){
            int k=lf;
            while(tb[1][k]==-tb[0][i] && k<t)
                k++;
            cnt+=k-lf;
        }
    }
    printf("%d",cnt);
    return 0;
}

SP733 MTWALK - Mountain Walking

这题我一开始莫名其妙地错了，后来乱改一通却又莫名其妙的对了~【手动滑稽】

思路

如果你决定暴搜的话，那么我就只能跟你说一声「珍重再见」了。

标题大法好，看到这一章内容的标题赫然写着“二分”二字，显然就是该用二分答案做滴。

这题的二分答案，即二分出这个山峰的高度差，然而二分之后却又怎么写$check$函数呢？显然，我们还需要枚举路线中最低山峰的高度，计算出最高山峰=最低山峰+高度差，然后再开始$dfs$，而且$dfs​$中要求所有路线上的山峰高度大于等于最低山峰高度，小于等于最高山峰高度。

代码 

 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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NR=105;
const int wk[4][2]={
	{0,1},
	{1,0},
	{-1,0},
	{0,-1}};
int n,l,r,m,MX=-1,arr[NR][NR];
bool vis[NR][NR];
void dfs(int mn,int mx,int x,int y){
    if(x>n || x<1 || y>n || y<1)return;
    if(vis[x][y])return;
    if(arr[x][y]<mn || arr[x][y]>mx)return;
    vis[x][y]=1;
    for(int i=0;i<4;i++)
        dfs(mn,mx,x+wk[i][0],y+wk[i][1]);
}
inline bool check(int d){
    for(int i=max(vis[1][1]-d,0);i<=min(110,arr[1][1]+d);i++){
        memset(vis,0,sizeof(vis));
        dfs(i,i+d,1,1);
        if(vis[n][n])return 1;
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&arr[i][j]);
    l=0;r=110;
    while(l<r){
        m=(l+r)>>1;
        if(check(m))r=m;
        else l=m+1;
    }
    printf("%d\n",l);
    return 0;
}

总结

  • 要提升代码能力+打字速度
  • 查错能力