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

发表于 分类于 Disqus：

Rank 3。
这次的题是第七届浙江省省赛的题，出了6道，感觉还可以，第一次打组队，配合上稍有欠缺。
当时做题的细节记不清了，大体顺序还记得，开场我看B简单就先做了，CE一次WA一次。。
后来跟榜出了L和A，后来易神说K题类似欧拉回路，开始想K，我开始敲E题。出了E之后，易神过来写K，庄神和我看其他题，除了G太长其他的都看了。。我们感觉F有希 望，看出来是唯一分解和贪心了。易神K题样例没过，我去Debug，他和庄神一块看F。E提出了之后一直在搞F不过，中途看有人出G，就跟了。一直到结束没出F。。
A：ZOJ 3322
读入之后对比，没难度。

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
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b,c;
        int x,y,z;
        scanf("%d%d%d%d%d%d",&a,&b,&c,&x,&y,&z);
        if(a!=x){
            if(a<x) printf("javaman\n");
            else printf("cpcs\n");
        }
        else if(b!=y){
            if(b<y) printf("javaman\n");
            else printf("cpcs\n");
        }
        else if(c==z) printf("same\n");
        else if(c<z) printf("javaman\n");
        else printf("cpcs\n");
    }
    return 0;
}

B：ZOJ 3323
读入之后，不是数字的输出。水题出现很大的失误，少头文件CE一次，忘记换行WA一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=30;
char s[maxn];
int main(){
    int t;
    scanf("%d",&t);
    getchar();
    while(t--){
        gets(s);
        int n=strlen(s);
        for(int i=0;i<n;++i)
            if(!isdigit(s[i])) putchar(s[i]);
        printf("\n");
    }
    return 0;
}

E：ZOJ 3326
月份和日子都是素数时能吃糖，求能吃糖的总天数。直接暴力出来的。一开始读错了题WA一次。

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
#include<cstdio>
using namespace std;
int mon[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
int candy[0];
bool np[35]={1,1};
inline bool isrun(int y){
    return y%400==0||(y%4==0&&y%100!=0);
}
inline void pre(){
    for(int i=0;i<35;++i){
        if(!np[i]){
            for(int j=i*i;j<35;j+=i)
                np[j]=true;
        }
    }
    return;
}
int main(){
    pre();
    int t;
    scanf("%d",&t);
    while(t--){
        int cnt=0;
        int year1,mon1,day1,year2,mon2,day2;
        scanf("%d%d%d%d%d%d",&year1,&mon1,&day1,&year2,&mon2,&day2);
        bool flag=true;
        while(1){
            if(!flag) break;
            if(year1>year2) break;
            while(1){
                if(!np[mon1]){
                    if(!flag) break;
                    if(year1==year2&&mon1>mon2) break;
                    while(1){
                        if(year1==year2&&mon1==mon2&&day1>day2){ flag=false;break;}
                        if(!np[day1]) cnt++;
                        day1++;
                        if(day1>mon[isrun(year1)][mon1]){
                            day1%=mon[isrun(year1)][mon1];
                            break;
                        }
                    }
                    mon1++;
                }
                else {
                    mon1++;
                    day1=1;
                }
                if(mon1>12){
                    mon1%=12;
                    break;
                }

            }
            year1++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

F：ZOJ 3327
后来大部分时间都在想这道题，想到唯一分解和贪心了，可是只是枚举了所有的二元变换，一直WA，赛后重写过的。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cstring>
using namespace std;
string s;
int a[4];
void resolve(char& c){
    switch(c) {
        case '1':break;
        case '2':++a[0];break;
        case '3':++a[1];break;
        case '4':a[0]+=2;break;
        case '5':++a[2];break;
        case '6':++a[0],++a[1];break;
        case '7':++a[3];break;
        case '8':a[0]+=3;break;
        case '9':a[1]+=2;break;
    }
    c='1';
    return;
}
bool make_up(char c){
    switch(c) {
        case '2':if(a[0]>=1){--a[0];return true;}break;
        case '3':if(a[1]>=1){--a[1];return true;}break;
        case '4':if(a[0]>=2){a[0]-=2;return true;}break;
        case '5':if(a[2]>=1){--a[2];return true;}break;
        case '6':if(a[0]>=1&&a[1]>=1){--a[0],--a[1];return true;}break;
        case '7':if(a[3]>=1){--a[3];return true;}break;
        case '8':if(a[0]>=3){a[0]-=3;return true;}break;
        case '9':if(a[1]>=2){a[1]-=2;return true;}break;
    }
    return false;
}
void ev(int pos){
    if(!pos&&s[pos]=='9'){
        s[pos]='0';
        cout<<1;
        return;
    }
    if(s[pos]!='9'){s[pos]+=1;return;}
    s[pos]='0';
    ev(pos-1);
    return;
}
int main(){
    int t;
    cin>>t;
    cin.get();
    while(t--){
        memset(a,0,sizeof(a));
        int pos=-1;
        s.resize(0);
        getline(cin,s);
        for(int i=0;i<(int)s.length();++i){
            if(s[i]!='0') continue;
            if(i!=(int)s.length()-1){
                ev((int)s.length()-1);
                cout<<s<<endl;
                goto END;
            }
            else{
                ev((int)s.length()-2);
                cout<<s<<endl;
                goto END;
            }
        }
        for(int i=(int)s.length()-1;i>=0;--i){
            bool flag=false;
            char c=s[i];
            resolve(s[i]);
            for(char j=c+1;j<='9';++j)
                if(make_up(j)){
                    s[i]=j;
                    pos=i;
                    flag=true;
                    break;
                }
            if(flag) break;
        }
        if(pos==-1) cout<<1;
        for(int i=(int)s.length()-1;i>pos;--i){
            for(char j='9';j>'1';--j)
                if(make_up(j)){
                    s[i]=j;
                    break;
                }
        }
        cout<<s<<endl;
    END:;
    }
    return 0;
}

G：ZOJ 3328
本场最水的一道题，就是n/2，四个多小时的时候，看有人过了，代码很短，跟的。。

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n&&n)
        cout<<n/2<<endl;
    return 0;
}

H：ZOJ 3329
概率DP，比赛时没出，赛后补的。状态当前点数剩余步数的期望，将期望用 ** dp[i]=a[i]*dp[0]+b[i] ** 代换，然后递归求出a[i]和b[i]。

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
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=550;
double p[20],A[maxn],B[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(p,0,sizeof(p));
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        int n,k1,k2,k3,a,b,c;
        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
        for(int i=1;i<=k1;++i)
            for(int j=1;j<=k2;++j)
                for(int k=1;k<=k3;++k)
                    if(a!=i||b!=j||c!=k) ++p[i+j+k];
        int sum=k1+k2+k3;
        p[0]=1.0/k1/k2/k3;
        for(int i=3;i<=sum;++i) p[i]/=k1*k2*k3;
        for(int i=n;i>=0;--i){
            A[i]=p[0],B[i]=1;
            for(int j=sum;j>=3;--j)
                A[i]+=p[j]*A[i+j],B[i]+=p[j]*B[i+j];
        }
        printf("%.15lf\n",B[0]/(1-A[0]));
    }
    return 0;
}

J：ZOJ 3331
比赛的时候看出来是个DP了，没想出来状态转移方程，赛后看学长代码才明白应该用当前任务编号和A、B两个机器的工作时间差作为状态。后来补了这道。

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
const int inf=0x3f3f3f3f;
int a[maxn],b[maxn],d[maxn][maxn*2];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(d,0x3f,sizeof(d));
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;++i) scanf("%d%d",&a[i],&b[i]);
        d[0][maxn]=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<maxn*2;++j)
                if(j>maxn){
                    d[i+1][j-b[i]]=min(d[i+1][j-b[i]],d[i][j]+max(0,b[i]-(j-maxn)));
                    d[i+1][maxn+a[i]]=min(d[i+1][maxn+a[i]],d[i][j]+a[i]);
                }
                else{
                    d[i+1][maxn-b[i]]=min(d[i+1][maxn-b[i]],d[i][j]+b[i]);
                    d[i+1][j+a[i]]=min(d[i+1][j+a[i]],d[i][j]+max(0,a[i]-(maxn-j)));
                }
        int ans=inf;
        for(int i=0;i<maxn*2;++i) ans=min(ans,d[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

K：ZOJ 3332
看官方报告，是个竞赛图的哈密顿路，我们是暴力过的。。

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
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=110;
bool g[maxn][maxn];
int cnt[2][maxn],n;
int road[maxn];
bool vis[maxn],find0;
bool pan(int i,int cur){
    road[cur]=i+1;
    if (cur==n) return find0=true;
    for (int j=0;j<n;j++){
        if (g[i][j]&&!vis[j]){
            vis[j]=true;
            if(pan(j,cur+1)) return true;
            vis[j]=false;
        }
    }
    return false;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(g,0,sizeof(g));
        memset(cnt,0,sizeof(cnt));
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        int num=n*(n-1)/2;
        for(int i=0;i<num;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u-1][v-1]=true;
        }
        find0=false;
        for (int i=0;i<n;i++){
            memset(vis,0,sizeof(vis));
            vis[i]=true;
            if(pan(i,1)) break;
        }
        if(find0){
            printf("%d",road[1]);
            for (int i=2;i<=n;++i)
                printf(" %d",road[i]);
            printf("\n");
        }
        else printf("impossible\n");
    }
    return 0;
}

L：ZOJ 3333
直接比大小就行，物品价格没有用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(b>c) printf("A\n");
        else printf("B\n");
    }
    return 0;
}

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

相关文章