CSP2024 前集训：多校A层冲刺NOIP2024模拟赛10
前言
不想说啥了最简单的一题是紫，去死吧只改了 T1、T2，T2 原题翻译和赛时题面描述都很唐，赛后断断续续加了好多 hack。
T1 岛屿
设 \(f_{a,b}\) 表示 \(a\) 条两端同色链，\(b\) 条两端异色链时连通块数量的期望。
- 红红蓝蓝相连得到红蓝 \(\to f_{a-1,b+1}\)。
- 红红红蓝相连得到红红 \(\to f_{a,b-1}\)。
- 蓝蓝红蓝相连得到蓝蓝 \(\to f_{a,b-1}\).
- 红蓝红蓝相连得到红蓝 \(\to f_{a,b-1}\) 或 \(f_{a,b-1}+1\)，\(+1\) 表示首尾相连。
顺序不影响结果，不妨先匹配红蓝端的链，固有转移：
\[f_{a,b}=\begin{cases}\frac{1}{2a+b}(f_{a,b-1}+1)+\frac{2a+b-1}{2a+b}f_{a,b-1}=f_{a,b-1}+\frac{1}{2a+b} &b>0 \\
f_{a-1,1}=\frac{1}{2a-1}+f_{a-1,0} &b=0 \\
\end{cases}\]
\(f_{0,0}=0,ans=f_{x,y}=\sum\limits_{i=1}^y\frac{1}{2x+i}+\sum\limits_{i=1}^x\frac{1}{2a-1}\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int x,y; double ans;
signed main()
{
freopen("island.in","r",stdin),freopen("island.out","w",stdout);
scanf("%d%d",&x,&y);
for(int i=1;i<=x;i++) ans+=1.0/(2*i-1);
for(int i=1;i<=y;i++) ans+=1.0/(2*x+i);
printf("%.8lf",ans);
}
T2 最短路
- 原题：P2934 [USACO09JAN] Safe Travel G。
建出最短路树，设当前点为 \(x\)，其子树对应 dfs 序上区间 \([l,r]\)，他的答案可以由子树外的原图子节点直接更新，即 \(dis_y+w_{(x,y)}\)，也可以由子树内的原图子节点节点间接更新，设 \(z\) 表示子树外的任意节点，则可以通过 \(1\to z\to y\to x\) 更新 \(ans_x\)，即 \(dis_z+w_{(z,y)}+w_{(y,x)}\)。
发现是单点修改区间查询最小值问题，可以从下往上线段树合并，树上差分直接维护，复杂度 \(O(m\log m+n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define mid (l+r>>1)
using namespace std;
const int N=1e5+10,M=2e6+10; const ll inf=2e17;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar_unlocked();
for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
for(;isdigit(c);c=getchar_unlocked()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,tot,fa[N],in[N],out[N],ban[N]; ll dis[N],ans[N];
bitset<N>vis; bitset<(N<<2)>yet;
struct edge
{
int tot,head[N],nxt[N<<2],to[N<<2],w[N<<2];
inline void add(int x,int y,int z)
{nxt[++tot]=head[x],to[tot]=y,w[tot]=z,head[x]=tot;}
}e,g;
struct tree
{
int tot,top,rt[N],ls[M],rs[M],rub[M]; ll val[M];
inline int add(int p=0) {return val[p=top?rub[top--]:++tot]=inf,p;}
inline void del(int &p) {ls[p]=rs[p]=0,rub[++top]=p,p=0;}
void change(int &p,int l,int r,int x,ll d)
{
(!p)&&(p=add());
if(l==r) return val[p]=min(val[p],d),void();
x<=mid?change(ls[p],l,mid,x,d):change(rs[p],mid+1,r,x,d);
val[p]=min(val[ls[p]],val[rs[p]]);
}
ll ask(int p,int l,int r,int vl,int vr,ll res=inf)
{
if(val[p]>=inf||vl>vr) return inf;
if(vl<=l&&vr>=r) return val[p];
if(vl<=mid) res=min(res,ask(ls[p],l,mid,vl,vr));
if(vr>mid) res=min(res,ask(rs[p],mid+1,r,vl,vr));
return res;
}
void merge(int &x,int y,int l,int r)
{
if(!x||!y) return x|=y,void();
if(l==r) return val[x]=min(val[x],val[y]),del(y),void();
merge(ls[x],ls[y],l,mid),merge(rs[x],rs[y],mid+1,r);
val[x]=min(val[ls[x]],val[rs[x]]),del(y);
}
}T;
inline int oth(int x) {return !x?0:((x&1)?x+1:x-1);}
void dijkstra()
{
memset(dis,0x3f,sizeof(dis)),dis[1]=0;
priority_queue<pair<ll,int> >q; q.push({0,1});
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue; vis.set(x);
for(int i=e.head[x],y;y=e.to[i];i=e.nxt[i]) if(dis[y]>dis[x]+e.w[i])
{
dis[y]=dis[x]+e.w[i],fa[y]=x,q.push({-dis[y],y});
yet[ban[y]]=yet[oth(ban[y])]=0,yet[ban[y]=i]=yet[oth(i)]=1;
}
}
for(int i=2;i<=n;i++) g.add(fa[i],i,e.w[ban[i]]);
}
void dfs(int x)
{
in[x]=++tot;
for(int i=g.head[x],y;y=g.to[i];i=g.nxt[i]) dfs(y);
out[x]=tot;
}
void solve(int x,ll dep)
{
for(int i=g.head[x],y;y=g.to[i];i=g.nxt[i])
solve(y,dep+g.w[i]),T.merge(T.rt[x],T.rt[y],1,n);
if(x==1) return ;
ans[x]=min(ans[x],min(T.ask(T.rt[x],1,n,1,in[x]-1),T.ask(T.rt[x],1,n,out[x]+1,n))-dep);
for(int i=e.head[x],y;y=e.to[i];i=e.nxt[i])
{
if(yet[i]||(in[y]>=in[x]&&out[y]<=out[x])) continue;
T.change(T.rt[x],1,n,in[y],dis[y]+e.w[i]+dep);
ans[x]=min(ans[x],dis[y]+e.w[i]);
}
}
signed main()
{
freopen("path.in","r",stdin),freopen("path.out","w",stdout);
read(n,m),memset(ans,0x3f,sizeof(ans)),T.val[0]=inf;
for(int i=1,x,y,z;i<=m;i++) read(x,y,z),e.add(x,y,z),e.add(y,x,z);
dijkstra(),dfs(1),solve(1,0);
for(int i=2;i<=n;i++) write(ans[i]>=(inf>>1)?-1:ans[i]),puts("");
}
T3 列表
咕了。
T4 种植
咕了咕了。