又双叒叕垫底啦！！！
rank 22，T1 0，T2 20，T3 0，T4 30。
逆天模拟赛，逆天题面，怕你赛场上不会打暴力真是煞费苦心出了一场暴力专场。
小h的几何
高斯消元求圆心精度被卡炸了，乐了。咋还考向量啊，不学文化课，输了。
九点圆的圆心是外心\(O\)和垂心\(H\)的中点，且\(\overrightarrow{OH}=\overrightarrow{OA}+\overrightarrow{OB}+\overrightarrow{OC}\)，因为\(O\)为原点，所以\(\Omega(A,B,C)=\frac{A+B+C}{2}\)。
证明的话不好写，机房没有条件，画图太难受的。可以百度一下。
用到向量的相关知识，文化课好题。
upd:发现有大佬写了，挂一下。come from DrRatio。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
FILE *ErrFile = Errfile(err);
#else
FILE *InFile = Infile(geometry),*OutFile = Outfile(geometry);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 5e5 + 10;
const ldb pi = 3.1415926535897932384626;
struct node{ldb x,y;}p[N];
int n,ct[N];
ldb res,ansx,ansy;
inline void solve(){
cin>>n;
res = 3.0/n/(n-1)/(n-2);
rep(i,1,n,1){
int q;cin>>q;
ldb ct = 1.0*q/1e9*pi;
p[i].x = cos(ct),p[i].y = sin(ct);
}
ldb ansx = 0,ansy = 0;
ll tot = 1ll*(n-1)*(n-2)/2;
rep(i,1,n,1){
ansx += tot*p[i].x*res;
ansy += tot*p[i].y*res;
}
cout<<fixed<<setprecision(16)<<ansx<<' '<<ansy<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}
小w的代数
想等学了圆方树以后去打\(O(n^2)\)的做法，仙姑了。
小y的数论
难题。
膜拜神已经要切了。
小j的组合
简单题，没场切挺遗憾的。
考虑求出树的直径以后，答案\(g=n-|树的直径|\)。
证明的话，考虑贪心一下，跑dfs，如果要走哈密顿路的话最后肯定是一条链。
考虑到如果要让新增的节点数最少的话肯定要让dfs回溯所经过边的最少，那么肯定是除了树的直径以外的其余边回溯，直接求树的直径即可。
然后求树的直径，暴力建边，dfs求哈密顿路，注意直径上的点要最后走。
时间复杂度\(O(n+m)\)
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t; i += p)
#define drep(i,s,t,p) for(int i = s;i >= t; i -= p)
#define Infile(x) freopen(#x".in","r",stdin)
#define Outfile(x) freopen(#x".out","w",stdout)
#define Ansfile(x) freopen(#x".ans","w",stdout)
#define Errfile(x) freopen(#x".err","w",stderr)
#ifdef LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err);
#else
FILE *InFile = Infile(combo),*OutFile = Outfile(combo);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#define eb emplace_back
const int N = 210;
vector<int> e[N];
int n,s,t,dep[N],fa[N],siz[N],son[N],ed[N],bf[N];
bitset<N> vis,flag;
inline int bfs(int s){
queue<int> q;q.push(s);
rep(i,1,n,1) dep[i] = bf[i] = 0;
vis.reset();bf[s] = 0;dep[s] = 1;
int mxdep = 0,far = s;
while(q.size()){
int x = q.front();q.pop();vis[x] = true;
for(int y:e[x]){
if(vis[y]) continue;
dep[y] = dep[x] + 1;
if(dep[y] > mxdep){mxdep = dep[y],far = y;}
bf[y] = x;
q.push(y);
}
}
return far;
}
vector<int> ans;
inline void Bfs(int x){
queue<int> q;q.push(x);
while(q.size()){
int x = q.front();q.pop();vis[x] = true;
for(int y:e[x]){
if(flag[y] || vis[y]) continue;
q.push(y);ans.eb(x);
}
}
}
vector<int> out;
void dfs(int x,int f){
out.eb(x);
vis[x] = true;
int to = 0;
for(int y:e[x]){
if(vis[y]) continue;
if(flag[y]){to = y;continue;}
dfs(y,x);
}
if(to && !vis[to]) dfs(to,x);
}
inline void solve(){
cin>>n;rep(i,1,n-1,1){int u,v;cin>>u>>v;e[u].eb(v),e[v].eb(u);}
s = bfs(t = bfs(1));
int x = s;vis.reset();
do{flag.set(x),x = bf[x];}while(x);
rep(i,1,n,1) if(flag[i]) Bfs(i);
int now = n+1;
for(auto x:ans){
for(int y:e[x]) e[y].eb(now),e[now].eb(y);
now++;
}now--;
vis.reset();dfs(s,0);
cout<<ans.size()<<'\n';
for(auto i:ans) cout<<i<<' ';
cout<<'\n';
for(auto i:out) cout<<i<<' ';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
solve();
}