ACM-ICPC 2015 Shenyang Preliminary Contest

在计蒜客上打的一次重现赛。

本来是 12:00 开始，但学校中午要午睡，13:30 才到机房。

也就打了四道水题，全程题目看不懂。

C. Minimum Cut

题目是真的读不懂，还好学长英语水平高。

大概是给你一张图和它的一棵生成树，求切最少的边使得图不连通且这些边里只有一条树边。

我：这么水？？学长：这不是英语能力竞赛题吗？？

结果就一发 A 了，结果我就跑出了机房。

 1 #include<bits/stdc++.h>
 2 #define rep(i,a,b) for(register int i=a;i<=b;++i)
 3 #define rpd(i,a,b) for(register int i=a;i>=b;--i)
 4 #define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
 5 typedef long long ll;
 6 const int N=2e4+5,M=2e5+5;
 7 using namespace std;
 8 inline int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
11     while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 int T,n,m,ans;int a[N],b[N];
15 int main(){
16     T=read();
17     rep(t,1,T){
18         printf("Case #%d: ",t);n=read();m=read();
19         memset(a,0,sizeof(a));memset(b,0,sizeof(b));
20         ans=2000000000;
21         rep(i,1,n-1){int u=read(),v=read();a[u]+=1;a[v]+=1;}
22         rep(i,n,m){int u=read(),v=read();b[u]+=1;b[v]+=1;}
23         rep(i,1,n)if(a[i]==1)ans=min(ans,b[i]+1);
24         printf("%d
",ans);
25     }
26     //system("pause");
27     return 0;
28 }
View Code

F. Fang Fang

有一些子串，f0 = " f "，f1 = " ff "，f2 = " cff "，fn = fn-1 + " f "

然后给你一个环，求这个环最少由几个子串拼成

我：这不是把 f 丢到后面然后数 c 就好了吗？？

评测结果：WA

我：好像没判全 f 的情况

评测结果：WA

我：……

想了很久，发现判 -1 时不能有其它的字母出现，结果就 A 了

 1 #include<bits/stdc++.h>
 2 #define rep(i,a,b) for(register int i=a;i<=b;++i)
 3 #define rpd(i,a,b) for(register int i=a;i>=b;--i)
 4 #define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
 5 typedef long long ll;
 6 using namespace std;
 7 inline int read(){
 8     int x=0,f=1;char ch=getchar();
 9     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
10     while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
11     return x*f;
12 }
13 int T;string s;
14 int main(){
15     T=read();
16     rep(t,1,T){
17         cin>>s;int ans=0;s=' '+s;printf("Case #%d: ",t);
18         int first_c=0,n=s.length()-1;bool ff=0;
19         rep(i,1,n)if(s[i]!='c'&&s[i]!='f'){ff=1;break;}
20         if(ff){puts("-1");continue;}
21         rep(i,1,n)if(s[i]=='c'){first_c=i;break;}
22         if(first_c==0){printf("%d
",(n+1)>>1);continue;}
23         rep(i,1,first_c-1)n+=1,s=s+'f';n+=1,s=s+'c';
24         int last_c=first_c;bool f=0;
25         rep(i,first_c+1,n)if(s[i]=='c'){
26             if(i-last_c<=2){f=1;break;}
27             else ans+=1,last_c=i;
28         }
29         f?puts("-1"):printf("%d
",ans);
30     }
31     //system("pause");
32     return 0;
33 }
View Code

J. Jesus Is Here

给你一些子串，s3​ = " cff "，s4 ​= " ffcff "，s5 ​= " cffffcff "，sn = sn-2 + sn-1

求 sn 中所有 " cff " 两两之间的距离和

维护一个前缀和一个后缀，就可以直接递推了（我才不会告诉你我是最后才调出来的呢）

 1 #include<bits/stdc++.h>
 2 #define rep(i,a,b) for(register int i=a;i<=b;++i)
 3 #define rpd(i,a,b) for(register int i=a;i>=b;--i)
 4 #define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
 5 typedef long long ll;
 6 const int N=201314+5;
 7 const ll Mod=530600414LL;
 8 using namespace std;
 9 inline int read(){
10     int x=0,f=1;char ch=getchar();
11     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
12     while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 int T;ll ans[N],qz[N],hz[N],num[N],len[N];
16 void add(ll &x,ll y){x+=y;if(x>=Mod)x-=Mod;}
17 int main(){
18     ans[5]=5LL;qz[5]=5LL;hz[5]=9LL;num[5]=2LL;len[5]=8LL;
19     ans[6]=16LL;qz[6]=11LL;hz[6]=19LL;num[6]=3LL;len[6]=13LL;
20     rep(i,7,N-5){
21         if(i%2==1){
22             add(len[i],len[i-1]);add(len[i],len[i-2]);
23             add(num[i],num[i-1]);add(num[i],num[i-2]);
24             add(ans[i],ans[i-1]);add(ans[i],ans[i-2]);
25             add(ans[i],(((hz[i-2]+3LL*num[i-2])%Mod)*num[i-1])%Mod);
26             add(ans[i],(qz[i-1]*num[i-2])%Mod);
27             add(qz[i],qz[i-2]);add(qz[i],(qz[i-1]+(num[i-1]*(len[i-2]+2LL))%Mod)%Mod);
28             add(hz[i],hz[i-1]);add(hz[i],(hz[i-2]+(num[i-2]*len[i-1])%Mod)%Mod);
29         }
30         else{
31             add(len[i],len[i-1]);add(len[i],len[i-2]);
32             add(num[i],num[i-1]);add(num[i],num[i-2]);
33             add(ans[i],ans[i-1]);add(ans[i],ans[i-2]);
34             add(ans[i],(((hz[i-2]+num[i-2])%Mod)*num[i-1])%Mod);
35             add(ans[i],(qz[i-1]*num[i-2])%Mod);
36             add(qz[i],qz[i-2]);add(qz[i],(qz[i-1]+(num[i-1]*(len[i-2]+Mod-2LL))%Mod)%Mod);
37             add(hz[i],hz[i-1]);add(hz[i],(hz[i-2]+(num[i-2]*len[i-1])%Mod)%Mod);
38         }
39     }
40     T=read();
41     rep(t,1,T)printf("Case #%d: %lld
",t,ans[read()]);
42     //system("pause");
43     return 0;
44 }
View Code

L. Largest Point

给你 a ，b 和 n 个数 t1 ... tn

求 a * ti2 + b * tj （ i ! = j ）的最大值

分 a 和 b 的正负讨论，细节特别多，可能还有更好的方法。

 1 #include<bits/stdc++.h>
 2 #define rep(i,a,b) for(register int i=a;i<=b;++i)
 3 #define rpd(i,a,b) for(register int i=a;i>=b;--i)
 4 #define rep1(i,x) for(register int i=head[x];i;i=nxt[i])
 5 typedef long long ll;
 6 const int N=5e6+5;
 7 using namespace std;
 8 inline int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
11     while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 int T,n,a,b;int t[N];
15 bool cmp(int i,int j){return 1LL*i*i>1LL*j*j;}
16 int main(){
17     T=read();
18     rep(j,1,T){
19         n=read();a=read();b=read();ll ans=0;
20         rep(i,1,n)t[i]=read();sort(t+1,t+n+1,cmp);
21         printf("Case #%d: ",j);
22         if(n==2){
23             printf("lld
",max(1LL*a*t[1]*t[1]+1LL*b*t[2],1LL*a*t[2]*t[2]+1LL*b*t[1]));
24             continue;
25         }
26         if(a>=0){
27             if(b>=0){
28                 int fz=0,sz=0,f=1;
29                 rep(i,1,n)if(t[i]>=0){fz=i;break;}
30                 rep(i,fz+1,n)if(t[i]>=0){sz=i;break;}
31                 if(!fz){
32                     printf("%lld
",1LL*a*t[1]*t[1]+1LL*b*t[n]);
33                     continue;
34                 }
35                 if(fz!=1){
36                     printf("%lld
",1LL*a*t[1]*t[1]+1LL*b*t[fz]);
37                     continue;
38                 }
39                 if(!sz){
40                     printf("%lld
",max(1LL*a*t[1]*t[1]+1LL*b*t[n],1LL*a*t[2]*t[2]+1LL*b*t[1]));
41                     continue;
42                 }
43                 printf("%lld
",max(1LL*a*t[1]*t[1]+1LL*b*t[sz],1LL*a*t[2]*t[2]+1LL*b*t[1]));
44             }
45             else{
46                 int fz=0,sz=0,f=1;
47                 rep(i,1,n)if(t[i]<=0){fz=i;break;}
48                 rep(i,fz+1,n)if(t[i]<=0){sz=i;break;}
49                 if(!fz){
50                     printf("%lld
",1LL*a*t[1]*t[1]+1LL*b*t[n]);
51                     continue;
52                 }
53                 if(fz!=1){
54                     printf("%lld
",1LL*a*t[1]*t[1]+1LL*b*t[fz]);
55                     continue;
56                 }
57                 if(!sz){
58                     printf("%lld
",max(1LL*a*t[1]*t[1]+1LL*b*t[n],1LL*a*t[2]*t[2]+1LL*b*t[1]));
59                     continue;
60                 }
61 
62                 printf("%lld
",max(1LL*a*t[1]*t[1]+1LL*b*t[sz],1LL*a*t[2]*t[2]+1LL*b*t[1]));
63             }
64         }
65         else{
66             if(b>=0){
67                 int fz=0,sz=0,f=1;
68                 rep(i,1,n)if(t[i]>=0){fz=i;break;}
69                 rep(i,fz+1,n)if(t[i]>=0){sz=i;break;}
70                 if(!fz){
71                     printf("%lld
",max(1LL*a*t[n]*t[n]+1LL*b*t[n-1],1LL*a*t[n-1]*t[n-1]+1LL*b*t[n]));
72                     continue;
73                 }
74                 if(fz!=n){
75                     printf("%lld
",1LL*a*t[n]*t[n]+1LL*b*t[fz]);
76                     continue;
77                 }
78                 printf("%lld
",max(1LL*a*t[n]*t[n]+1LL*b*t[n-1],1LL*a*t[n-1]*t[n-1]+1LL*b*t[n]));
79             }
80             else{
81                 int fz=0,sz=0,f=1;
82                 rep(i,1,n)if(t[i]<=0){fz=i;break;}
83                 rep(i,fz+1,n)if(t[i]<=0){sz=i;break;}
84                 if(!fz){
85                     printf("%lld
",max(1LL*a*t[n]*t[n]+1LL*b*t[n-1],1LL*a*t[n-1]*t[n-1]+1LL*b*t[n]));
86                     continue;
87                 }
88                 if(fz!=n){
89                     printf("%lld
",1LL*a*t[n]*t[n]+1LL*b*t[fz]);
90                     continue;
91                 }
92                 printf("%lld
",max(1LL*a*t[n]*t[n]+1LL*b*t[n-1],1LL*a*t[n-1]*t[n-1]+1LL*b*t[n]));
93             }
94         }
95     }
96     //system("pause");
97     return 0;
98 }
View Code

其它题就来不及做了…………

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/maximumhanyu/p/11421846.html