A. Andryusha and Socks 思路：模擬即可
#include<bits/stdc++.h>using namespace std;const int maxn=1e5+10;bool vis[maxn];int main(){ int n; scanf("%d",&n); memset(vis,false,sizeof(vis)); int now=0,maxx=0; for(int i=0;i<2*n;i++){ int temp; scanf("%d",&temp); if(!vis[temp]){ now+=1; vis[temp]=true; }else{ now-=1; } if(now>maxx) maxx=now; } B. The Meeting Place Cannot Be Changed 思路：二分搜索，如果時間t可以滿足所有人到達同一個點，則檢查t/2是否也可以，然后根據題目要求精度達到1e-7退出#include<bits/stdc++.h>using namespace std;const int maxn=60000+10;struct p{ int dis,v;};p per[maxn];int n;int md,sd;double s;double eps=1e-7;bool check(double t){ double a,b; for(int i=1;i<=n;i++){ double x=(double)per[i].dis-(double)per[i].v*t; double y=(double)per[i].dis+(double)per[i].v*t; if(i==1){ a=x,b=y; }else{ if(a>y || b<x) return false; if(a<=x) a=x; if(b>=y) b=y; } } return true;}int main(){ scanf("%d",&n); md=-1,sd=0x3f3f3f3f; for(int i=1;i<=n;i++){ scanf("%d",&per[i].dis); if(per[i].dis>md) md=per[i].dis; if(per[i].dis<sd) sd=per[i].dis; } for(int i=1;i<=n;i++){ scanf("%d",&per[i].v); } double l,r,ans; l=0,r=1e9; while(r-l>=eps){ double mid=(l+r)/2; if(check(mid)){ ans=mid; r=mid; }else l=mid; } printf("%.7f",ans);}C. Andryusha and Colored Balloons 思路：樹上dfs，每個節點的顏色是不和父親節點和祖父親節點相同的最小的未使用顏色。
#include<bits/stdc++.h>using namespace std;const int maxn=2*1e5+10;vector<int>E[maxn];int n;int ans[maxn];int fa[maxn];set<int>sum;void dfs(int now){ int cnt=1; for(int i=0;i<E[now].size();i++){ int p=E[now][i]; if(p!=fa[now]){ while(cnt==ans[now] || cnt==ans[fa[now]]) cnt++; ans[p]=cnt; sum.insert(cnt); fa[p]=now; dfs(p); cnt++; } }}int main(){ scanf("%d",&n); for(int i=1;i<n;i++){ int a,b; scanf("%d%d",&a,&b); E[a].push_back(b); E[b].push_back(a); } ans[1]=1; fa[1]=1; dfs(1); sum.insert(1); printf("%d/n",sum.size()); for(int i=1;i<=n;i++) printf("%d ",ans[i]);}新聞熱點
疑難解答
