【Codeforces Rockethon 2014】Solutions
分类:
IT文章
•
2022-06-04 08:34:50
转载请注明出处：http://www.cnblogs.com/Delostik/p/3553114.html
目前已有【A B C D E】
例行吐槽：趴桌子上睡着了
【A. Genetic Engineering】
http://codeforces.com/contest/391/problem/A
问最少插入几个字符，使得字符串不存在连续偶数个相同字母。不说什么
![]()
1 #include <iostream>
2 #include <string>
3 using namespace std;
4
5 string s;
6 int cnt;
7
8 int main(){
9 cin>>s;
10 s+=' ';
11 int n=s.size(),i,j;
12 for(i=0;i<n;){
13 for(j=i;j<n;j++)
14 if(s[j]!=s[i]){
15 if((j-i)%2==0) cnt++;
16 break;
17 }
18 i=j;
19 }
20 cout<<cnt<<endl;
21 }
View Code
【B. Word Folding】
http://codeforces.com/contest/391/problem/B
将字符串蛇形折叠，其中一列字母相同，问最多折叠几层。
若S[i]=S[j]且ij之间隔了偶数个（包括0）字母的时候，可以找到一个折叠点将S[i]和S[j]折叠并对齐。相同的那一列从上到下的下标一定是奇偶交替的。
![]()
1 #include <iostream>
2 #include <vector>
3 #include <cstring>
4 using namespace std;
5 typedef pair<int,int> PII;
6 template<class T>inline void gmax(T &a,T b){if(a<b)a=b;}
7
8 string s;
9 int ans;
10 vector<int> v;
11 bool vis[1010];
12
13 int main(){
14 cin>>s;
15 int n=s.size();
16 for(int k='A';k<='Z';k++){
17 v.clear();
18 for(int i=0;i<n;i++)
19 if(s[i]==k) v.push_back(i);
20 memset(vis,false,sizeof(vis));
21 for(int i=0;i<v.size();i++)
22 if(!vis[i]){
23 int cnt=1;
24 for(int j=i+1;j<v.size();j++)
25 if((v[j]%2)+(v[j-1]%2)==1) vis[j]=true,cnt++;
26 gmax(ans,cnt);
27 }
28 }
29 cout<<ans<<endl;
30 }
View Code
【C3. The Tournament】
http://codeforces.com/contest/391/problem/C3
与n个选手进行比赛，赢了自己得一分，输了对方得一分，n个选手有已经得到的分数p[i]和赢得比赛需要花费的代价e[i]，问至少花费多少代价可以排名前k，并列的参考胜负场关系。
转化为判定性问题。若最终得分为x，则p[i]>x的选手一定排名比我靠前；p[i]=x的选手如果赢了我那么分数变成p[i]+1排名比我靠前，如果输给我则按胜负关系比我靠后；p[i]=x-1的选手如果赢了我分数变成p[i]排名比我靠前。
所以我们需要纠结的仅仅是p[i]=x和p[i]=x-1的这两种人，选择其中的一部分人打败他们，使得自己的名次在前k即可。x的取值也很显然只有p[k]，p[k]+1,p[k]+2这三种（p排序后）。
![]()
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4 #include <queue>
5 #define p first
6 #define e second
7 #define inf ~0uLL>>1
8 using namespace std;
9 typedef pair<int,int> PII;
10 template<class T>inline void gmin(T &a,T b){if(a>b)a=b;}
11
12 int n,m;
13 long long ans=inf;
14 PII a[200010];
15
16 int main(){
17 cin>>n>>m;
18 m--;
19 for(int i=0;i<n;i++)
20 cin>>a[i].p>>a[i].e;
21 sort(a,a+n,greater<PII>());
22 for(int k=0;k<3;k++){
23 int top=0;
24 long long tmp=0;
25 priority_queue< int,vector<int>,less<int> > b;
26 priority_queue< int,vector<int>,greater<int> > c;
27 int des=a[m].p+k;
28 for(int i=0;i<n;i++){
29 if(a[i].p+1==des || a[i].p==des) b.push(a[i].e);
30 else{
31 if(a[i].p>des) top++;
32 c.push(a[i].e);
33 }
34 }
35 if(top>m) continue;
36 while(!b.empty()){
37 if(top<m){
38 top++;
39 c.push(b.top());
40 }else{
41 des--;
42 tmp+=b.top();
43 }
44 b.pop();
45 }
46 while(des>0 && !c.empty()){
47 tmp+=c.top();
48 c.pop();
49 des--;
50 }
51 if(des<=0) gmin(ans,tmp);
52 }
53 cout<<((ans==inf)?-1:ans)<<endl;
54 }
View Code
【D2. Supercollider】
http://codeforces.com/contest/391/problem/D2
有若干水平和垂直线段，问最大的一个+号的大小是多少。
暴力复杂度n^2。
仍然是转化问判定性问题。二分答案之后，只需要判定大小为mid的+是否存在即可。
若两条垂直线段(x1,y1)(x1,y2) (x2,y3)(x3,y3)可以组成一个大小为mid的+，那么中心点一定存在于线段 (x1,y1+mid)(x1,y2-mid) (x2+mid,y3)(x3-mid,y3)之中。也就是说把所有线段的两段都截去长度mid，然后判断是否存在交点就可以了。扫描线。
![]()
1 #include <iostream>
2 #include <algorithm>
3 #include <set>
4 using namespace std;
5
6 struct LINE{int x,y,l;}a[50010],b[50010],c[50010],p[100010];
7 int n,m;
8 set<int> M;
9
10 bool cmp(LINE a,LINE b){
11 return a.x<b.x || a.x==b.x && a.l>b.l;
12 }
13
14 bool check(int mid){
15 int tot1=0,tot2=0;
16 M.clear();
17 for(int i=0;i<n;i++)
18 if(a[i].l>=2*mid){
19 c[tot1].x=a[i].x;
20 c[tot1].y=a[i].y+mid;
21 c[tot1++].l=a[i].l-2*mid;
22 }
23 for(int i=0;i<m;i++)
24 if(b[i].l>=2*mid){
25 p[tot2].x=b[i].x+mid;
26 p[tot2].y=b[i].y;
27 p[tot2++].l=1;
28 p[tot2].x=b[i].x+b[i].l-mid+1;
29 p[tot2].y=b[i].y;
30 p[tot2++].l=0;
31 }
32 sort(c,c+tot1,cmp);
33 sort(p,p+tot2,cmp);
34 int j=0;
35 for(int i=0;i<tot1;i++){
36 for(;j<tot2 && p[j].x<=c[i].x;j++)
37 if(p[j].l) M.insert(p[j].y);
38 else M.erase(p[j].y);
39 set<int>::iterator tmp=M.lower_bound(c[i].y);
40 if(tmp!=M.end() && (*tmp)<=c[i].y+c[i].l) return 1;
41 }
42 return 0;
43 }
44
45 int main(){
46 cin>>n>>m;
47 for(int i=0;i<n;i++)
48 cin>>a[i].x>>a[i].y>>a[i].l;
49 for(int i=0;i<m;i++)
50 cin>>b[i].x>>b[i].y>>b[i].l;
51 int low=1,high=100000000;
52 while(low<=high){
53 int mid=(low+high)>>1;
54 if(check(mid)) low=mid+1;
55 else high=mid-1;
56 }
57 cout<<low-1<<endl;
58 }
View Code
Distances between {xi} and {yi}
Distances between {yi} and {zi}
Distances between pairs of vertices that were connected before we inserted the additional edges
Distances between {xi} and {zi}
The first component is equal to sum(d(X, xi) + d(Y1, yi) + 1, xi = 1..n1, yi = 1..n2). Note that the summands are independent, so it can be broken into sum(d(X, xi), xi = 1..n1) * n2 + sum(d(Y1, yi), yi = 1..n2) * n1 + n1 * n2.
Similarly, the second component is equal to sum(d(Z, zi), zi = 1..n3) * n2 + sum(d(Y2, yi), yi = 1..n2) * n3 + n2 * n2.
The third component is simply a sum of pairwise distances in each of the trees and is a constant.
The fourth component is equal to sum(d(X, xi) + d(Y1, Y2) + d(Z, zi) + 2, xi = 1..n1, zi = 1..n3) = sum(d(X, xi), xi = 1..n1) * n3 + sum(d(Z, zi), zi = 1..n3) + d(Y1, Y2) * n1 * n3 + 2 * n1 * n3.
前三部分都是可以被独立计算的，关键在于第四部分。可以在三棵树中分别找到一个连接点（一定是到达该点路径和最大的点），枚举三棵树的顺序（左中右），枚举中间那棵树的另一个连接点，这部分的复杂度是O(n)的。
![]()
1 #include <iostream>
2 #define mm 200010
3 #define mn 100010
4 using namespace std;
5 template<class T>inline void gmax(T &a,T b){if(a<b)a=b;}
6
7 long long ans,n[3];
8
9 struct TREE{
10
11 long long dist[mn],node[mn],pos,n,SUM,f[mn],sum[mn],maxd;
12
13 struct EDGE{
14 int pnt;
15 EDGE *pre;
16 EDGE(){}
17 EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
18 }Edge[mm],*SP,*edge[mn];
19
20 void addedge(int a,int b){
21 edge[a]=new(++SP)EDGE(b,edge[a]);
22 edge[b]=new(++SP)EDGE(a,edge[b]);
23 }
24
25 void build(int nn){
26 int a,b;
27 SP=Edge;
28 n=nn;
29 for(int i=1;i<n;i++){
30 cin>>a>>b;
31 addedge(a,b);
32 }
33 }
34 //dfs0用于计算连接点到其他各点的距离
35 void dfs0(int cur,int fa){
36 dist[cur]=dist[fa]+1;
37 for(EDGE *j=edge[cur];j;j=j->pre)
38 if(j->pnt!=fa){
39 dfs0(j->pnt,cur);
40 }
41 }
42 //dfs1 dfs2用于dp
43 void dfs1(int cur,int fa){
44 node[cur]=1;
45 sum[cur]=0;
46 for(EDGE *j=edge[cur];j;j=j->pre)
47 if(j->pnt!=fa){
48 dfs1(j->pnt,cur);
49 node[cur]+=node[j->pnt];
50 sum[cur]+=sum[j->pnt]+node[j->pnt];
51 }
52 }
53
54 void dfs2(int cur,int fa,long long val){
55 f[cur]=sum[cur]+val;
56 for(EDGE *j=edge[cur];j;j=j->pre)
57 if(j->pnt!=fa)
58 dfs2(j->pnt,cur,val+sum[cur]-sum[j->pnt]-node[j->pnt]+n-node[j->pnt]);
59 }
60
61 void solve(){
62 dfs1(1,0);
63 dfs2(1,0,0);
64 for(int i=1;i<=n;i++){
65 SUM+=f[i];
66 if(f[i]>maxd){
67 maxd=f[i];
68 pos=i;
69 }
70 }
71 dist[0]=-1;
72 dfs0(pos,0);
73 }
74 }T[3];
75
76 long long calc(TREE &TL,TREE &TM,TREE &TR){
77 long long res,ans=0;
78 int i=TM.pos;
79 for(int j=1;j<=TM.n;j++){
80 //三棵树各自内部的
81 res=(TL.SUM+TM.SUM+TR.SUM)/2;
82 //TL连向右边两棵
83 res+=TL.maxd*(TM.n+TR.n)+TM.n*TR.n;
84 //TR连向左边两棵
85 res+=TR.maxd*(TL.n+TM.n)+TM.n*TL.n;
86 //TL和TR
87 res+=(TM.dist[j]+2)*TL.n*TR.n+TL.n*TM.f[i]+TR.n*TM.f[j];
88 gmax(ans,res);
89 }
90 return ans;
91 }
92
93 int main(){
94 cin>>n[0]>>n[1]>>n[2];
95 for(int i=0;i<3;i++){
96 T[i].build(n[i]);
97 T[i].solve();
98 }
99 for(int i=0;i<3;i++)
100 for(int j=0;j<3;j++)
101 if(i!=j) gmax(ans,calc(T[i],T[j],T[3-i-j]));
102 cout<<ans<<endl;
103 }
104
