省赛选拔赛——组队赛第二场

发表于 分类于 Disqus：

Rank 5。
2013年通化全国邀请赛的题。比赛时出了2道题，打完之后才知道杭电G++编译器有问题，D题同样的代码C++能AC，G++一直超时。一开始A题交了好久次才过罚 时好多，一着急就乱了，改一个地方就提交，这个必须改。
A：HDU 4493
给出12个月的工资，求平均薪水，貌似是因为数据大和浮点数精度问题WA了好几次，最后用long long过的。

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
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        LL sum=0;
        LL tmp1,tmp2;
        for(int i=0;i<12;++i){
            scanf("%I64d.%I64d",&tmp1,&tmp2);
            sum+=tmp1*100;
            sum+=tmp2;
        }
        sum=(LL)floor((double)sum/12.0+0.5);
        printf("$%I64d",sum/100);
        sum%=100;
        if(sum!=0){
            if(sum%10) printf(".%02I64d",sum);
            else printf(".%I64d",sum/10);
        }
        printf("\n");
    }
    return 0;
}

D：HDU 4496
判断连通块个数，倒着做一遍并查集，然后计数储存就好了。比赛时G++编译器超时，赛后用C++补过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
using namespace std;
const int maxn=10010;
int n,m,p[maxn];
int u[maxn*10],v[maxn*10],ans[maxn*10];
inline int findx(int x){
    return p[x]==x?x:p[x]=findx(p[x]);
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<m;++i) scanf("%d%d",&u[i],&v[i]);
        int cnt=0;
        for(int i=0;i<n;++i) p[i]=i;
        for(int i=m-1;i>=0;--i){
            if((ans[i]=n-cnt)==1) continue;
            int x=findx(u[i]),y=findx(v[i]);
            if(x!=y) {++cnt,p[x]=y;}
        }
        for(int i=0;i<m;++i) printf("%d\n",ans[i]);
    }
    return 0;
}

H：HDU 4597
博弈问题，有两堆牌，每次可以从堆顶或堆底拿一张，两人都足够聪明，求先手最大得分。DP解决，因为状态没找好，所以直接分类讨论了。赛后看了学长代码重写了一遍。

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
重写后的：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=22;
int n,a[maxn],b[maxn];
int d[maxn][maxn][maxn][maxn];
int dp(int l1,int r1,int l2,int r2,int sum){
    int& k=d[l1][r1][l2][r2];
    if(k!=-1) return k;
    if(l1<=r1){
        k=max(k,sum-dp(l1+1,r1,l2,r2,sum-a[l1]));
        k=max(k,sum-dp(l1,r1-1,l2,r2,sum-a[r1]));
    }
    if(l2<=r2){
        k=max(k,sum-dp(l1,r1,l2+1,r2,sum-b[l2]));
        k=max(k,sum-dp(l1,r1,l2,r2-1,sum-b[r2]));
    }
    return max(0,k);
}
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(d,-1,sizeof(d));
        cin>>n;
        int sum=0;
        for(int i=1;i<=n;++i) cin>>a[i],sum+=a[i];
        for(int i=1;i<=n;++i) cin>>b[i],sum+=b[i];
        cout<<dp(1,n,1,n,sum)<<endl;
    }
    return 0;
}


原代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=22;
const int inf=1<<30;
int d[maxn][maxn][maxn][maxn],a[maxn],b[maxn];
int dp(int i,int j,int i2,int j2){
    int &k=d[i][j][i2][j2];
    if(k!=-1) return k;
    if(!(i-i2)&&!(j-j2)) return k=0;
    if(!(i-i2)){
        if(j-j2==1) return k=b[j];
        return k=max(min(dp(i,j-2,i2,j2),dp(i,j-1,i2,j2+1))+b[j],min(dp(i,j,i2,j2+2),dp(i,j-1,i2,j2+1))+b[j2+1]);
    }
    if(!(j-j2)){
        if(i-i2==1) return k=a[i];
        return k=max(min(dp(i-2,j,i2,j2),dp(i-1,j,i2+1,j2))+a[i],min(dp(i-1,j,i2+1,j2),dp(i,j,i2+2,j2))+a[i2+1]);
    }
    if(i-i2==1&&j-j2==1) return k=max(a[i],b[j]);
    if(i-i2==1){
        int cur=0;
        cur=max(cur,min(dp(i-1,j-1,i2,j2),dp(i-1,j,i2,j2+1))+a[i]);
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j-1,i2,j2));
            ccur=min(ccur,dp(i,j-2,i2,j2));
            ccur=min(ccur,dp(i,j-1,i2,j2+1));
            cur=max(cur,ccur+b[j]);
        }
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j,i2,j2+1));
            ccur=min(ccur,dp(i,j-1,i2,j2+1));
            ccur=min(ccur,dp(i,j,i2,j2+2));
            cur=max(cur,ccur+b[j2+1]);
        }
        return k=cur;
    }
    if(j-j2==1){
        int cur=0;
        cur=max(cur,min(dp(i-1,j-1,i2,j2),dp(i,j-1,i2+1,j2))+b[j]);
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j-1,i2,j2));
            ccur=min(ccur,dp(i-1,j,i2+1,j2));
            ccur=min(ccur,dp(i-2,j,i2,j2));
            cur=max(cur,ccur+a[i]);
        }
        {
            int ccur=inf;
            ccur=min(ccur,dp(i-1,j,i2+1,j2));
            ccur=min(ccur,dp(i,j-1,i2+1,j2));
            ccur=min(ccur,dp(i,j,i2+2,j2));
            cur=max(cur,ccur+a[i2+1]);
        }
        return k=cur;
    }
    int cur=0;
    {
        int ccur=inf,ci=i-1;
        ccur=min(ccur,dp(ci-1,j,i2,j2));
        ccur=min(ccur,dp(ci,j-1,i2,j2));
        ccur=min(ccur,dp(ci,j,i2+1,j2));
        ccur=min(ccur,dp(ci,j,i2,j2+1));
        cur=max(cur,ccur+a[i]);
    }
    {
        int ccur=inf,cj=j-1;
        ccur=min(ccur,dp(i-1,cj,i2,j2));
        ccur=min(ccur,dp(i,cj-1,i2,j2));
        ccur=min(ccur,dp(i,cj,i2+1,j2));
        ccur=min(ccur,dp(i,cj,i2,j2+1));
        cur=max(cur,ccur+b[j]);
    }
    {
        int ccur=inf,ci2=i2+1;
        ccur=min(ccur,dp(i-1,j,ci2,j2));
        ccur=min(ccur,dp(i,j-1,ci2,j2));
        ccur=min(ccur,dp(i,j,ci2+1,j2));
        ccur=min(ccur,dp(i,j,ci2,j2+1));
        cur=max(cur,ccur+a[i2+1]);
    }
    {
        int ccur=inf,cj2=j2+1;
        ccur=min(ccur,dp(i-1,j,i2,cj2));
        ccur=min(ccur,dp(i,j-1,i2,cj2));
        ccur=min(ccur,dp(i,j,i2+1,cj2));
        ccur=min(ccur,dp(i,j,i2,cj2+1));
        cur=max(cur,ccur+b[j2+1]);

    }
    return k=cur;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        memset(d,-1,sizeof(d));
        int n;
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int i=1;i<=n;++i) cin>>b[i];
        cout<<dp(n,n,0,0)<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章