Codeforces Wunder Fund Round 2016 C D E

本文主要是介绍Codeforces Wunder Fund Round 2016 C D E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这场题目质量比上一场有了显著的提升！

C Constellation

首先找一个肯定在凸包上的点，比如最左下角的点 $p_0$ ，然后对其他所有点进行极角排序。然后挑出角度最小的点中离 $p_0$ 最近的点 $p_1$ ，还有角度第二小的点中离 $p_0$ 最近的点 $p_2$ 。
题虽然简单，但是比赛的时候手贱写了eps=1e-8挂掉了，如果用eps必须设得非常小（其实直接比较浮点数就好了），因为可以构造出一个角度极小的角。

#include <bits/stdc++.h>using namespace std;#define ll long longconst ll mod = 1e9+7;const double eps = 1e-28;inline bool isEqual(double a,double b){if(abs(a-b)<eps)return 1;return 0;
}struct Star{double x,y;int id;double ang;bool operator<(const Star& other)const{return ang<other.ang;}
}stars[100010];double dist2(int a,int b){return (stars[a].x-stars[b].x)*(stars[a].x-stars[b].x) + (stars[a].y-stars[b].y)*(stars[a].y-stars[b].y);
}int main(){int n;cin>>n;for(int i=0;i<n;i++){scanf("%lf %lf",&stars[i].x,&stars[i].y);stars[i].id = i+1;}for(int i=1;i<n;i++){if(stars[i].y==stars[0].y){if(stars[i].x<stars[0].x){swap(stars[0],stars[i]);}}else if(stars[i].y<stars[0].y){swap(stars[0],stars[i]);}}for(int i=1;i<n;i++){stars[i].ang = atan2(stars[i].y-stars[0].y,stars[i].x-stars[0].x);}sort(stars+1,stars+n);int ans1=1;int k;for(k=1;k<n;k++){if(dist2(k,0)<dist2(ans1,0)){ans1=k;}if(!isEqual(stars[k].ang,stars[k+1].ang))break;}//k++;int ans2=k;for(;k<n;k++){if(dist2(k,0)<dist2(ans2,0)){ans2=k;}if(!isEqual(stars[k].ang,stars[k+1].ang))break;}cout<<stars[0].id<<" "<<stars[ans1].id<<" "<<stars[ans2].id<<endl;return 0;
}

D Hamiltonian Spanning Tree

比赛时我的想法时，不断找直径，然后切下来，再剩下的树中继续找直径…其实这样做是不对的。
正解肯定是分两种情况：
当 $y{\le}x$ 时，答案为 $y*(n-1)$ ，但有个例外，如果有 $n-1$ 个点都连接到同一个点上，答案为 $y*(n-2)+x$ 。
当 $y{\gt}x$ 时，问题转化为最少把生成树分为多少条链，可以进行一次dfs解决。对于每个节点，统计它有多少子节点“可连接”。当可连接数为0时，将自己设为可连接；当可连接数为1时，连接那个子节点，并将自己设为可连接；当可连接数大于1时，连接任意两个子节点，并将自己设为不可连接。

#include <bits/stdc++.h>using namespace std;#define ll long longconst ll mod = 1e9+7;const int maxn = 200010;vector<int> adj[maxn];ll ans = 0;
int n;
ll x,y;bool vis[maxn];
int son[maxn];
bool flag[maxn];
int deg[maxn];void dfs(int u){vis[u] = 1;int sz = adj[u].size();int cnt = 0;for(int i=0;i<sz;i++){int v = adj[u][i];if(vis[v])continue;dfs(v);if(flag[v])son[u]++;cnt++;}if(son[u]==0){flag[u]=1;ans += y*cnt;}else if(son[u]==1){flag[u]=1;ans += x;ans += y*(cnt-1);}else{ans += x*2;ans += y*(cnt-2);}
}int main(){cin>>n;cin>>x>>y;for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);adj[u].push_back(v);adj[v].push_back(u);deg[u]++;   deg[v]++;}if(y<=x){ans = y*(n-1);for(int i=1;i<=n;i++){if(deg[i]==n-1){ans-=y;ans+=x;break;}}}else{dfs(1);}cout<<ans<<endl;return 0;
}