因为有好多人没有好好打，所以我认为我垫底了。
赛时rank 2，T1 0pts，T2 100pts，T3 0pts，T4 40pts，accoder上同分，rank 9。
T1 因为没输出挂了5pts，T4 爆搜挂了5pts，乐。
update：T3没有启发式合并被卡成rank 4了
神：wang5是下一个zh0ukangyang
岛屿
唐氏的推柿子题。
发现只有两种链，同色相连和异色相连，而且红红和蓝蓝的数量一样，假设\(f_{a,b}\)表示初始有\(a\)条同色链\(b\)条异色链时期望连通块数，目标为\(f_{X,Y}\)。
分类讨论。
- 红红蓝蓝相连，连通块为\(f_{a-1,b+1}\)
- 红红红蓝相连，为\(f_{a,b-1}\)
- 蓝蓝红蓝相连，为\(f_{a,b-1}\)
- 红蓝红蓝相连，为\(f_{a,b-1}\)或\(f_{a,b-1}+1\)
然后就有dp柿子了。
\[f_{a,b}=\begin{cases}\frac{1}{2a+b}(f_{a,b-1}+1)+\frac{2a+b-1}{2a+b}f_{a,b-1}&b>0\\f_{a-1,b+1}&b=0
\end{cases}\]
化简以后就变成了
\[f_{a,b}=\begin{cases}\frac{1}{2a+b}+f_{a,b-1}&b>0\\f_{a-1,1}=\frac{1}{2a-1}+f_{a-1,0}&b=0
\end{cases}\]
\(f_{0,0}=0\)。
\(f_{X,Y}=\sum\limits_{i=1}^Y\frac{1}{2X+i}+\sum\limits_{i=1}^X\frac{1}{2i-1}\)
点此查看代码
#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 LOCALFILE *InFile = Infile(in),*OutFile = Outfile(out);// FILE *ErrFile = Errfile(err);
#elseFILE *InFile = Infile(island),*OutFile = Outfile(island);
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
signed main(){cin.tie(nullptr)->sync_with_stdio(false);cout<<fixed<<setprecision(18);int x,y;cin>>x>>y;db ans = 0;rep(i,1,y,1) ans = ans + 1.0/(2*x+i);rep(i,1,x,1) ans = ans + 1.0/(2*i-1);cout<<ans<<'\n';
}
最短路
[USACO09JAN] Safe Travel G
签到题，虽然是紫。
由于\(1\sim i\)的最短路唯一，所以以\(1\)为根建出的最短路树唯一。
考虑当\(x\)的点被ban了以后，就要在其子树中找一条边连接其它子树，假如向外连边的点为\(u\)，连到的点为\(v\)，那么答案就是\(dist_v+w+dist_u-dist_x\)，只需要维护\(dist_u+w+dist_v\)的最小值即可，这个只要不是暴力，用啥维护都行，我用的set。
然后考虑什么时候一条边没有贡献，那么就是在\(lca(u,v)\)及以上时候，懒惰删除即可。
从根往下搜，启发式合并即可，时间复杂度\(O(n\log^2 n)\)。
题解用并查集实现的\(O(n\log m+n)\)的，比较厉害，挂一下。
点此查看代码
#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 LOCALFILE *InFile = Infile(in),*OutFile = Outfile(out);// FILE *ErrFile = Errfile(err);
#elseFILE *InFile = stdin,*OutFile = stdout;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 1e5 + 10,M = 2e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
#define eb emplace_back
#define pii pair<ll,int>
#define mk make_pair
struct EDGE{int to,next,w;}edge[M<<1];
int head[N],cnt = 1;
inline void add(int u,int v,int w){edge[++cnt] = {v,head[u],w};head[u] = cnt;}
vector<int> e[N];
int n,m,fa[N],fe[N],u[M],v[M],w[M],siz[N],son[N],top[N],dfn[N],rdfn[N],tim,dep[N];
int in[N],out[N];
ll dist[N],ans[N];
bitset<N> vis;bitset<M> ot;
vector<int> Ad[N],del[N];
inline void dijkstra(int s){memset(dist,0x3f,sizeof dist);vis.reset();dist[s] = 0;priority_queue<pii,vector<pii>,greater<pii> > q;q.push(mk(dist[s],s));while(q.size()){int x = q.top().second;q.pop();if(vis[x]) continue;vis[x] = true;for(int i = head[x]; i;i = edge[i].next){int y = edge[i].to;if(dist[y] > dist[x] + edge[i].w){fa[y] = x;fe[y] = i>>1;dist[y] = dist[x] + edge[i].w;q.push(mk(dist[y],y));}}}
}
set<pii> st[N];
bitset<M> have;
int rt[N];
void dfs1(int x){siz[x] = 1;dep[x] = dep[fa[x]] + 1;for(int y:e[x]){if(y == fa[x]) continue;dfs1(y);siz[x] += siz[y];if(siz[son[x]] < siz[y]) son[x] = y;}
}
void dfs2(int x,int t){rdfn[dfn[x] = ++tim] = x;in[x] = out[x] = tim;top[x] = t;if(son[x]) dfs2(son[x],t);else return;for(int y:e[x]){if(y == fa[x] || y == son[x]) continue;dfs2(y,y);}out[x] = tim;
}
inline int LCA(int x,int y){int fx = top[x],fy = top[y];while(fx ^ fy){if(dep[fx] < dep[fy]) swap(fx,fy),swap(x,y);x = fa[fx];fx = top[x];}if(dep[x] > dep[y]) swap(x,y);return x;
}
void Merge(int x,int y){for(auto i:st[y]) st[x].insert(i);set<pii> ().swap(st[y]);
}
void dfs(int x){ans[x] = inf;for(auto y:e[x]){dfs(y);}if(son[x]) rt[x] = rt[son[x]];for(auto y:e[x]){ if(y == son[x]) continue;Merge(rt[x],rt[y]);}for(auto i:Ad[x]){have[i] = true;st[rt[x]].insert(mk(dist[u[i]]+dist[v[i]]+w[i],i));}for(auto i:del[x]) have.reset(i);while(st[rt[x]].size()){if(have[(*st[rt[x]].begin()).second]){ans[x] = -dist[x]+(*st[rt[x]].begin()).first;break;}else{st[rt[x]].erase(st[rt[x]].begin());}}
}
inline void solve(){cin>>n>>m;rep(i,1,m,1){cin>>u[i]>>v[i]>>w[i];add(u[i],v[i],w[i]);add(v[i],u[i],w[i]);}dijkstra(1);rep(i,2,n,1) e[fa[i]].eb(i),ot.set(fe[i]);rep(i,1,n,1) rt[i] = i;dfs1(1);dfs2(1,1);rep(i,1,m,1){if(ot[i]) continue;int x = u[i],y = v[i],lca = LCA(x,y);Ad[v[i]].eb(i);Ad[u[i]].eb(i);del[lca].eb(i);}dfs(1);rep(i,2,n,1){if(ans[i] == inf) cout<<-1<<'\n';else cout<<ans[i]<<'\n';}
}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);solve();
}
这场模拟赛就是唐，不TM调了。
翻译跟√⑩一样，数据也和√⑩一样。
还TM赛后加hack，你有TM本事考完noip给CCF加hack啊。
BYD，不调了，挂题解上去得了。
