nenu contest3 The 5th Zhejiang Provincial Collegiate Programming Contest

ZOJ Problem Set - 2965 Accurately Say "CocaCola"! http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2965

打表。求含有7或者是7的倍数的数。题目输入p，输出第一个连续出现p个满足条件的头。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int M=1024;
 7 bool vis[M];
 8 bool isgood(int x){
 9     while(x){
10         if(x%10==7) return true;
11         x/=10;
12     }
13     return false;
14 }
15 int ans[M];
16 int main(){
17     mt(vis,0);
18     for(int i=1;i<M;i++){
19         if(isgood(i)||!(i%7)){
20             vis[i]=true;
21         }
22     }
23     for(int i=1;i<=99;i++){
24         ans[i]=M;
25     }
26     int s=1,t=1;
27     for(int i=1;i<M;i++){
28         if(!vis[i]){
29             s=t=i;
30         }
31         else{
32             t++;
33             ans[t-s]=min(ans[t-s],s+1);
34         }
35     }
36     int n;
37     scanf("%d",&t);
38     while(t--){
39         scanf("%d",&n);
40         printf("%d
",ans[n]);
41     }
42     return 0;
43 }

View Code

ZOJ Problem Set - 2966 Build The Electric System http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2966

最小生成树 prim

 1 #include<cstdio>
 2 const int inf=0x3f3f3f3f;
 3 class Prim { ///最小生成树(无向图)o(MV^2)要保证图连通
 4     typedef int typec;///边权的类型
 5     static const int MV=512;///点的个数
 6     int n,i,j,k,pre[MV];///pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1
 7     bool vis[MV];
 8     typec mat[MV][MV],dist[MV],res;
 9 public:
10     void init(int tn) { ///传入点数，点下标0开始
11         n=tn;
12         for(i=0; i<n; i++)
13             for(j=0; j<n; j++)
14                 mat[i][j]=i==j?0:inf;///不相邻点边权inf
15     }
16     void add(int u,int v,typec w) {
17         if(mat[u][v]>w) {
18             mat[u][v]=w;
19             mat[v][u]=w;
20         }
21     }
22     typec solve() { ///返回最小生成树的长度
23         for(res=i=0; i<n; i++) {
24             dist[i]=inf;
25             vis[i]=false;
26             pre[i]=-1;
27         }
28         for(dist[j=0]=0; j<n; j++) {
29             for(k=-1,i=0; i<n; i++) {
30                 if(!vis[i]&&(k==-1||dist[i]<dist[k])) {
31                     k=i;
32                 }
33             }
34             for(vis[k]=true,res+=dist[k],i=0; i<n; i++) {
35                 if(!vis[i]&&mat[k][i]<dist[i]) {
36                     dist[i]=mat[pre[i]=k][i];
37                 }
38             }
39         }
40         return res;
41     }
42 }gx;
43 int main(){
44     int t,n,m,u,v,w;
45     scanf("%d",&t);
46     while(t--){
47         scanf("%d%d",&n,&m);
48         gx.init(n);
49         while(m--){
50             scanf("%d%d%d",&u,&v,&w);
51             gx.add(u,v,w);
52         }
53         printf("%d
",gx.solve());
54     }
55     return 0;
56 }

View Code

Kruskal

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int inf=0x3f3f3f3f;
 7 class Kruskal { ///最小生成树(无向图)o(ME*logME)
 8     typedef int typec;///边权的类型
 9     static const int ME=512*512;///边的个数
10     static const int MV=512;///点的个数
11     class UnionFindSet { ///并查集
12         int par[MV];
13     public:
14         void init() {
15             mt(par,-1);
16         }
17         int getroot(int x) {
18             int i=x,j=x,temp;
19             while(par[i]>=0) i=par[i];
20             while(j!=i) {
21                 temp=par[j];
22                 par[j]=i;
23                 j=temp;
24             }
25             return i;
26         }
27         bool unite(int x,int y) {
28             int p=getroot(x);
29             int q=getroot(y);
30             if(p==q)return false;
31             if(par[p]>par[q]) {
32                 par[q]+=par[p];
33                 par[p]=q;
34             } else {
35                 par[p]+=par[q];
36                 par[q]=p;
37             }
38             return true;
39         }
40     } f;
41     struct E {
42         int u,v;
43         typec w;
44         friend bool operator < (E a,E b) {
45             return a.w<b.w;
46         }
47     } e[ME];
48     int le,num,n;
49     typec res;
50 public:
51     void init(int tn){///传入点的个数
52         n=tn;
53         le=res=0;
54         f.init();
55         num=1;
56     }
57     void add(int u,int v,typec w) {
58         e[le].u=u;
59         e[le].v=v;
60         e[le].w=w;
61         le++;
62     }
63     typec solve(){///返回-1不连通
64         sort(e,e+le);
65         for(int i=0; i<le&&num<n; i++) {
66             if(f.unite(e[i].u,e[i].v)) {
67                 num++;
68                 res+=e[i].w;
69             }
70         }
71         if(num<n) res=-1;
72         return res;
73     }
74 }gx;
75 int main(){
76     int t,n,m,u,v,w;
77     scanf("%d",&t);
78     while(t--){
79         scanf("%d%d",&n,&m);
80         gx.init(n);
81         while(m--){
82             scanf("%d%d%d",&u,&v,&w);
83             gx.add(u,v,w);
84         }
85         printf("%d
",gx.solve());
86     }
87     return 0;
88 }

View Code

ZOJ Problem Set - 2969 Easy Task http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1968

给式子的系数，求导完输出系数，如果全为零输出零，否则从第一个不为零的开始输出。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int M=128;
 5 int a[M];
 6 int main(){
 7     int t,n;
 8     scanf("%d",&t);
 9     while(t--){
10         scanf("%d",&n);
11         for(int i=n;i>=0;i--){
12             scanf("%d",&a[i]);
13         }
14         int id=-1;
15         for(int i=n;i>=1;i--){
16             a[i]*=i;
17             if(a[i]){
18                 id=max(id,i);
19             }
20         }
21         if(id==-1){
22             puts("0");
23             continue;
24         }
25         for(int i=id;i>=1;i--){
26             if(i!=id) printf(" ");
27             printf("%d",a[i]);
28         }
29         puts("");
30     }
31     return 0;
32 }

View Code

ZOJ Problem Set - 2970 Faster, Higher, Stronger http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1969

f就找最小，其他找最大。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int inf=0x3f3f3f3f;
 5 int main(){
 6     int t,n,a;
 7     scanf("%d",&t);
 8     char op[16];
 9     while(t--){
10         scanf("%s%d",op,&n);
11         bool sma=false;
12         int ans=-inf;
13         if(op[0]=='F'){
14             sma=true;
15             ans=inf;
16         }
17         for(int i=0;i<n;i++){
18             scanf("%d",&a);
19             if(sma){
20                 ans=min(ans,a);
21             }
22             else{
23                 ans=max(ans,a);
24             }
25         }
26         printf("%d
",ans);
27     }
28     return 0;
29 }

View Code

ZOJ Problem Set - 2971 Give Me the Number http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1970

3个3个处理，然后加起来。

 1 #include<cstdio>
 2 #include<cstring>
 3 const int M=32;
 4 char a[M*M],b[M][M];
 5 int ans[M],val[M];
 6 char gewei[M][M]={"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
 7 char shiwei[M][M]={"ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
 8 char jishi[M][M]={"twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
 9 int main(){
10     int t;
11     scanf("%d",&t);
12     getchar();
13     while(t--){
14         gets(a);
15         int cnt=0,lb=0;
16         for(int i=0;a[i];i++){
17             if(a[i]==' '){
18                 b[cnt][lb]=0;
19                 cnt++;
20                 lb=0;
21             }
22             else{
23                 b[cnt][lb++]=a[i];
24             }
25         }
26         b[cnt][lb]=0;
27         cnt++;
28         for(int i=1;i<=3;i++){
29             ans[i]=0;
30             val[i]=1;
31         }
32         int sta=3;
33         for(int i=cnt-1;i>=0;i--){
34             if(!strcmp(b[i],"and")) continue;
35             int now=-1;
36             for(int j=0;j<10;j++){
37                 if(!strcmp(b[i],gewei[j])){
38                     now=j;
39                     break;
40                 }
41             }
42             if(now==-1){
43                 for(int j=0;j<10;j++){
44                     if(!strcmp(b[i],shiwei[j])){
45                         now=j+10;
46                         break;
47                     }
48                 }
49             }
50             if(now==-1){
51                 for(int j=0;j<8;j++){
52                     if(!strcmp(b[i],jishi[j])){
53                         now=(j+2)*10;
54                         break;
55                     }
56                 }
57             }
58             if(~now){
59                 ans[sta]+=now*val[sta];
60             }
61             else{
62                 if(!strcmp(b[i],"hundred")){
63                     val[sta]=100;
64                     continue;
65                 }
66                 if(!strcmp(b[i],"thousand")){
67                     sta=2;
68                     continue;
69                 }
70                 if(!strcmp(b[i],"million")){
71                     sta=1;
72                     continue;
73                 }
74             }
75         }
76         int sum=0;
77         for(int i=1;i<=3;i++){
78             sum*=1000;
79             sum+=ans[i];
80         }
81         printf("%d
",sum);
82     }
83     return 0;
84 }

View Code

ZOJ Problem Set - 2972 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1971

dp i j 表示第 i 个位置还剩 j 的体力能获得的最小时间，有三种方式转移，根据题目输入来转移。用t1就要浪费f1 用t2不变，用t3还能挣点体力，注意体力上限m

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int inf=0x3f3f3f3f;
 5 const int M=128;
 6 struct G{
 7     int T1,T2,T3,F1,F2;
 8 }sta[M];
 9 int dp[M][M];
10 int main(){
11     int t,n,m;
12     scanf("%d",&t);
13     while(t--){
14         scanf("%d%d",&n,&m);
15         for(int i=1;i<=n;i++){
16             scanf("%d%d%d%d%d",&sta[i].T1,&sta[i].T2,&sta[i].T3,&sta[i].F1,&sta[i].F2);
17         }
18         for(int i=0;i<=n;i++){
19             for(int j=0;j<=m;j++){
20                 dp[i][j]=inf;
21             }
22         }
23         dp[0][m]=0;
24         for(int i=0;i<=n;i++){
25             for(int j=0;j<=m;j++){
26                 if(j>=sta[i+1].F1){
27                     dp[i+1][j-sta[i+1].F1]=min(dp[i+1][j-sta[i+1].F1],dp[i][j]+sta[i+1].T1);
28                 }
29                 dp[i+1][j]=min(dp[i+1][j],dp[i][j]+sta[i+1].T2);
30                 dp[i+1][min(m,j+sta[i+1].F2)]=min(dp[i+1][min(m,j+sta[i+1].F2)],dp[i][j]+sta[i+1].T3);
31             }
32         }
33         int ans=inf;
34         for(int j=0;j<=m;j++){
35             ans=min(ans,dp[n][j]);
36         }
37         printf("%d
",ans);
38     }
39     return 0;
40 }

View Code

ZOJ Problem Set - 2975 Kinds of Fuwas http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1974

求四个角相等的矩形个数。n^3的做法。枚举两列n^2，on枚举这两列有几对一样的，然后他们可以组成C n选2 种矩形。

 1 #include<cstdio>
 2 typedef long long LL;
 3 const int M=256;
 4 char a[M][M];
 5 char cp[]={'B','J','H','Y','N'};
 6 int main(){
 7     int t,n,m;
 8     scanf("%d",&t);
 9     while(t--){
10         scanf("%d%d",&n,&m);
11         for(int i=0;i<n;i++){
12             scanf("%s",a[i]);
13         }
14         LL ans=0;
15         for(int k=0;k<5;k++){
16             for(int x=0;x<m;x++){
17                 for(int y=x+1;y<m;y++){
18                     LL sum=0;
19                     for(int i=0;i<n;i++){
20                         if(cp[k]==a[i][x]&&cp[k]==a[i][y]){
21                             sum++;
22                         }
23                     }
24                     ans+=sum*(sum-1)/2;
25                 }
26             }
27         }
28         printf("%lld
",ans);
29     }
30     return 0;
31 }

View Code

ZOJ Problem Set - 2976 Light Bulbs http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1975

因为是格点，整点，所以200*200枚举点，对每个点枚举灯算总和。4*10^6*case

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 const int M=128;
 6 struct point3 {
 7     double x,y,z,I;
 8 } p[M],now;
 9 double Distance(point3 p1,point3 p2) {
10     return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
11 }
12 int main() {
13     int t,n;
14     scanf("%d",&t);
15     while(t--) {
16         scanf("%d",&n);
17         for(int i=0;i<n;i++){
18             scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z,&p[i].I);
19         }
20         double ans=0;
21         for(int x=-100;x<=100;x++){
22             for(int y=-100;y<=100;y++){
23                 now.x=x;
24                 now.y=y;
25                 now.z=0;
26                 double sum=0;
27                 for(int i=0;i<n;i++){
28                     double dist=Distance(now,p[i]);
29                     sum+=p[i].I*p[i].z/dist/dist/dist;
30                 }
31                 ans=max(ans,sum);
32             }
33         }
34         printf("%.2f
",ans);
35     }
36     return 0;
37 }

View Code

end