因为有好多人没有好好打，所以我认为我垫底了。
赛时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 LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err);
#else
FILE *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';
}
最短路
签到题，虽然是紫。
由于\(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 LOCAL
FILE *InFile = Infile(in),*OutFile = Outfile(out);
// FILE *ErrFile = Errfile(err);
#else
FILE *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，不调了，挂题解上去得了。
