Codeforces Round #575 (Div. 3)
出题：A-B-D1-D2
补题：C-E-F
总结：B看错题，导致浪费非常多的时间，D2用前缀和分成三个写就超时，可能是我姿势不对。。。逃，心态炸了没读读懂C。。。还是太辣鸡了
A. Three Piles of Candies
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int main(){ long long a,b,c; int n; while(~scanf("%d",&n)){ while(n--){ scanf("%lld%lld%lld",&a,&b,&c); printf("%lld\n",(a+b+c)/2); } } return 0; }
B. Odd Sum Segments
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<vector> using namespace std; const int maxx = 2e5+6; int a[maxx]; int main(){ int t; int n,k; scanf("%d",&t); while(t--){ vector<int>pos; scanf("%d%d",&n,&k); int cnt=0; for (int i=1;i<=n;i++){ scanf("%d",&a[i]); if (a[i]%2==1){ cnt++; pos.push_back(i); } } if (cnt<k || (cnt-k)%2==1){ printf("NO\n"); }else { int s=1; printf("YES\n"); for (int i=1;i<pos.size();i++){ if (s==k)break; printf("%d ",pos[i]-1); s++; } printf("%d\n",n); } } return 0; }
C. Robot Breakout
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<vector> using namespace std; int main(){ int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); int x,y; int max_x=1e5,max_y=1e5,min_x=-1e5,min_y=-1e5; int a,b,c,d; for (int i=1;i<=n;i++){ scanf("%d%d",&x,&y); scanf("%d%d%d%d",&a,&b,&c,&d); if (a==0){ min_x=max(min_x,x); } if (b==0){ max_y=min(max_y,y); } if (c==0){ max_x=min(max_x,x); } if (d==0){ min_y=max(min_y,y); } } if (max_x<min_x || max_y<min_y){ printf("0\n"); }else { printf("1 %d %d\n",max_x,max_y); } } return 0; }
D1. RGB Substring (easy version)
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int maxx = 2e5+6; char str[maxx]; int main(){ int t; scanf("%d",&t); int len,n; while(t--){ scanf("%d%d",&n,&len); scanf("%s",str); int ans=0; for (int i=0;i<n-len+1;i++){ int cnt=0; for (int j=1;j<=3;j++){ cnt=0; if (j==1){ for (int k=0;k<len;k++){ // cout<<i+k<<" "; if (k%3==0 && str[i+k]=='B')cnt++; if (k%3==1 && str[i+k]=='R')cnt++; if (k%3==2 && str[i+k]=='G')cnt++; } }else if (j==2){ for (int k=0;k<len;k++){ // cout<<i+k<<" "; if (k%3==0 && str[i+k]=='R')cnt++; if (k%3==1 && str[i+k]=='G')cnt++; if (k%3==2 && str[i+k]=='B')cnt++; } }else { for (int k=0;k<len;k++){ // cout<<i+k<<" "; if (k%3==0 && str[i+k]=='G')cnt++; if (k%3==1 && str[i+k]=='B')cnt++; if (k%3==2 && str[i+k]=='R')cnt++; } } // cout<<endl; // cout<<cnt<<endl; ans=max(ans,cnt); } } printf("%d\n",len-ans); } return 0; }
D2. RGB Substring (hard version)
三种情况的三种不同前缀和，最后查询一遍即可
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int maxx = 2e5+6; char str[maxx]; int pre[maxx][3]; int main() { int t; scanf("%d",&t); int len,n; while(t--) { scanf("%d%d",&n,&len); scanf("%s",str+1); for (int i=1; i<=n; i++) { pre[i][0]=0; pre[i][1]=0; pre[i][2]=0; } int cnt1=0; int cnt2=0; int cnt3=0; for (int i=1; i<=n; i++) { if ((i-1)%3==0) { if (str[i]=='R')cnt1++; if (str[i]=='G')cnt2++; if (str[i]=='B')cnt3++; pre[i][0]=cnt1; pre[i][1]=cnt2; pre[i][2]=cnt3; } else if ((i-1)%3==1) { if (str[i]=='G')cnt1++; if (str[i]=='B')cnt2++; if (str[i]=='R')cnt3++; pre[i][0]=cnt1; pre[i][1]=cnt2; pre[i][2]=cnt3; } else { if (str[i]=='B')cnt1++; if (str[i]=='R')cnt2++; if (str[i]=='G')cnt3++; pre[i][0]=cnt1; pre[i][1]=cnt2; pre[i][2]=cnt3; } } int ans=0; for (int j=1; j<=n-len+1; j++) { int w=max(pre[j+len-1][0]-pre[j-1][0],max(pre[j+len-1][1]-pre[j-1][1],pre[j+len-1][2]-pre[j-1][2])); ans=max(ans,w); } printf("%d\n",len-ans); } return 0; }
E. Connected Component on a Chessboard
假如B<W,那么我们可以通过尽量构造1黑周围3个白，让差值减小2。不断减小
当然如果差值为1的时候，我们可以通过构造1黑周围2个白，差值减小1，然后使得B和W的个数相同
这个时候，直接B和W之间相邻构造就行了。
然后把坐标保存下来，如果B>W个数，我们仍然按照上述构造，然后全部横坐标+1即可。
也就是说，我们构造一条竖线，一定是黑白相间的，我们在竖线周围加上黑或者白多的那个，这样构造出来。
动笔画画图就出来了。。。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define pii pair<int,int> #define mp make_pair using namespace std; vector<pii> ans; int main() { int t,b,w; scanf("%d",&t); while(t--) { scanf("%d%d",&b,&w); int three=0,two=0,one=0; ans.clear(); int flag=0; if (b>w) { flag=1; swap(b,w); } if (3*b+1<w) { printf("NO\n"); } else { printf("YES\n"); int s_x=2,s_y=3; while(w>=1 && b>=1) { if (w-b>=2) { ans.push_back(mp(s_x,s_y)); ans.push_back(mp(s_x+1,s_y)); ans.push_back(mp(s_x-1,s_y)); ans.push_back(mp(s_x,s_y+1)); w-=3; b-=1; s_y+=2; } else if (w-b>=1) { ans.push_back(mp(s_x,s_y)); ans.push_back(mp(s_x,s_y+1)); ans.push_back(mp(s_x+1,s_y)); w-=2; b-=1; s_y+=2; } else { ans.push_back(mp(s_x,s_y)); ans.push_back(mp(s_x,s_y+1)); w-=1; b-=1; s_y+=2; } } if (w==1) { ans.push_back(mp(2,2)); } if (flag) { for (int i=0; i<ans.size(); i++) { printf("%d %d\n",ans[i].first,ans[i].second+1); } } else { for (int i=0; i<ans.size(); i++) { printf("%d %d\n",ans[i].first,ans[i].second); } } } } return 0; }
F. K-th Path
这个题是个好题啊，点赞，题目就说是，给一些点，以及一些边，我们需要找出这些点集之间的第K短的路。
。。。拿到就没什么想法，暴力弗洛伊德在1e5数据的下面，显然不现实，也没啥好的想法。。。
后面大佬代码，看到一位大佬非常优秀的代码。
考虑这样一个东西K，K实在太小了，小到只有400，那么其实你可以想到，我们的最坏情况，就是把边排序后的第400条边。
我们把这K条边重新建图，那么这图就小的可怜了。。。
点集不超过200，那么nlogn的最短路也就绰绰有余了。
跑完最短路后，枚举点之间距离，放入小根堆，最后丢掉前K-1个即可
#include<iostream> #include<stdio.h> #include<algorithm> #include<queue> #include<string.h> #define pii pair<int,int> #define pli pair<long long,int> #define mp make_pair #define LL long long using namespace std; const int maxx = 2e5+6; const LL INF = 1e18; struct node{ int x,y,w; }a[maxx]; int order[maxx]; struct Edge{ int v,w,n; }edge[maxx]; bool cmp(node a,node b){ return a.w<b.w; } int tot; int head[maxx]; LL dis[maxx]; bool vis[maxx]; void add(int x,int y,int z){ edge[++tot]=(Edge){y,z,head[x]}; head[x]=tot; } void dij(int s){ priority_queue<pli>q; for (int i=1;i<=2e5+4;i++){ dis[i]=INF; } memset(vis,0,sizeof(vis)); q.push(mp(0,s)); dis[s]=0; int x,y; while(q.size()){ x=q.top().second; q.pop(); if (vis[x])continue; vis[x]=1; for (int i=head[x];i;i=edge[i].n){ y=edge[i].v; if (dis[y]>dis[x]+edge[i].w){ dis[y]=dis[x]+edge[i].w; q.push(mp(-dis[y],y)); } } } } int main(){ int n,m,k; while(~scanf("%d%d%d",&n,&m,&k)){ tot=1; memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); memset(edge,0,sizeof(edge)); for (int i=1;i<=m;i++){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w); } sort(a+1,a+1+m,cmp); int cnt=0; for (int i=1;i<=min(k,m);i++){ add(a[i].x,a[i].y,a[i].w); add(a[i].y,a[i].x,a[i].w); if (!vis[a[i].x])vis[a[i].x]=1,order[++cnt]=a[i].x; if (!vis[a[i].y])vis[a[i].y]=1,order[++cnt]=a[i].y; } priority_queue<LL>ans; while(ans.size())ans.pop(); for (int i=1;i<=cnt;i++){ dij(order[i]); for (int j=i+1;j<=cnt;j++){ ans.push(-dis[order[j]]); } } for (int i=1;i<k;i++){ ans.pop(); } printf("%lld\n",-ans.top()); } return 0; }
查看4道真题和解析
