蓝书第一章部分经典例题题解

发表于 | 评论数： | 阅读次数：

最近在读刘汝佳先生的《算法竞赛入门经典》，收获颇丰，特此记录一些自己以前未曾涉猎算法的经典例题题解。

UVA-10755 Garbage Heap（三维前缀和）

题目链接

Garbage Heap

解题思路

$UVA$上一定要用$%lld$！！！只有$CF$才需要$I64d$！！！空格换行要求也很严格！

大致思路是，把三维用前缀和表示，每次枚举两维，第三维再用前缀和的思想用类似求最大子序列的求法$O(n)$解决，总复杂度$O(n^5)$。

AC代码

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
#include<stdio.h>
#include<string.h>
#define For(i,a,b) for(i=a;i<=b;i++)
#define FFF For(i,1,a)For(j,1,b)For(k,1,c)
typedef long long ll;
ll m[25][25][25];
int a,b,c,t;
ll sumf(int x1,int x2,int y1,int y2,int z1,int z2){
    ll num=m[x2][y2][z2];
    num-=m[x1-1][y2][z2];
    num-=m[x2][y1-1][z2];
    num-=m[x2][y2][z1-1];
    num+=m[x1-1][y1-1][z2];
    num+=m[x1-1][y2][z1-1];
    num+=m[x2][y1-1][z1-1];
    num-=m[x1-1][y1-1][z1-1];
    return num;
}
int main(){
    int i,j,k,l,p;
    ll ans,minpre,sum;
    scanf("%d",&t);
    while(t--){
        ans=-1e18;
        memset(m,0,sizeof(m));
        scanf("%d%d%d",&a,&b,&c);
        FFF scanf("%lld",&m[i][j][k]);
        FFF m[i][j][k]+=m[i-1][j][k];
        FFF m[i][j][k]+=m[i][j-1][k];
        FFF m[i][j][k]+=m[i][j][k-1];
        For(i,1,a)For(j,i,a)For(k,1,b)For(l,k,b){
            minpre=0;
            For(p,1,c){
                sum=sumf(i,j,k,l,1,p);
                if(sum-minpre>ans)ans=sum-minpre;
                if(sum<minpre)minpre=sum;
            }
        }
        printf("%lld\n",ans);
        if(t)putchar('\n');
    }
    return 0;
}

UVA-1326 Jurassic Remains（中途相遇法）

题目链接

Jurassic Remains

解题思路

由于直接状态压缩的消耗太大，分成两部分状态压缩解决，通过保存第一部分的状态，枚举第二部分的状态时$O(lgn)$寻找（$STL$的$map$），时间复杂度从$O(2^n)$降到$O(2^{\frac n2}logn)​$。

AC代码

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
#include<cstdio>
#include<map>
using namespace std;
int n,state[50];
char s[100010];
map<int,int>m;
int count(int x){
    int p=0;
    while(x)p+=(x&1),x>>=1;
    return p;
}
int main(){
    int i,j;
    while(~scanf("%d",&n)&&n){
        m.clear();
        for(i=0;i<n;i++){
            scanf("%s",s);
            state[i]=0;
            for(j=0;s[j];j++)state[i]^=(1<<(s[j]-'A'));
        }
        int n1=n/2,n2=n-n1,ans=0;
        for(i=0;i<(1<<n1);i++){
            int x=0,cnt=0;
            for(j=0;j<n1;j++)if(i&(1<<j))x^=state[j],cnt++;
            if(!m.count(x)||cnt>count(m[x]))m[x]=i;
        }
        for(i=0;i<(1<<n2);i++){
            int x=0;
            for(j=0;j<n2;j++)if(i&(1<<j))x^=state[j+n1];
            if(m.count(x)&&count(m[x])+count(i)>count(ans))
                ans=(i<<n1)^m[x];
        }
        printf("%d\n",count(ans));
        int flag=0;
        for(i=0;i<n;i++)if(ans&(1<<i)){
            if(!flag)printf("%d",i+1);
            else printf(" %d",i+1);
            flag=1;
        }
        printf("\n");
    }
    return 0;
}