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

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博客 ,格式可能有所偏差。