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

C Constellation

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

#include 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)return 1;return 0;
}struct Star{double x,y;int id;double ang;bool operator<(const Star& other)const{return ang100010];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;iscanf("%lf %lf",&stars[i].x,&stars[i].y);stars[i].id = i+1;}for(int i=1;iif(stars[i].y==stars[0].y){if(stars[i].x0].x){swap(stars[0],stars[i]);}}else if(stars[i].y0].y){swap(stars[0],stars[i]);}}for(int i=1;iatan2(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;kif(dist2(k,0)0)){ans1=k;}if(!isEqual(stars[k].ang,stars[k+1].ang))break;}//k++;int ans2=k;for(;kif(dist2(k,0)0)){ans2=k;}if(!isEqual(stars[k].ang,stars[k+1].ang))break;}cout<0].id<<" "<" "<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 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;iint 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;iint 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<return 0;
}

E Robot Arm

待补。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！