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可以滿足所有人到達(dá)同一個點(diǎn)，則檢查t/2是否也可以，然后根據(jù)題目要求精度達(dá)到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，每個節(jié)點(diǎn)的顏色是不和父親節(jié)點(diǎn)和祖父親節(jié)點(diǎn)相同的最小的未使用顏色。
#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]);}新聞熱點(diǎn)
疑難解答
