CSP 模拟 52

Ishar-zdl的博客 / 2024-11-07 / 原文

A 岛屿

没看懂这个题是什么东西，质量不知道该咋评价。
首先这是一个二分图，一开始是一个完美匹配，然后需要再给它添加一个完美匹配，求最后的联通块期望个数，首先最后的状态一定是若干个环和链，只有链的端点能去连边，分为三种串，红蓝链，红红链，蓝蓝链，简单观察后发现红红链和蓝蓝链的数量总是一样，设 $f_{i,j}$ 表示有 $i$ 个红红/蓝蓝链，$j$ 个红蓝链时的答案，考虑给所有红端点去找匹配。

红红连蓝蓝，形成一个红蓝链，成为 $f_{i-1,j+1}$。
红红连红蓝，形成一个红红链，成为 $f_{i,j-1}$。
蓝蓝链红蓝，形成一个蓝蓝链，成为 $f_{i,j-1}$。
红蓝连红蓝，第一种，连到了自己，成为 $f_{i,j-1}+1$，没连到自己，形成一个红蓝链，成为 $f_{i,j-1}$。

本质上就是固定红点的顺序，然后给蓝点全排列，所以匹配的顺序没有任何影响，那就考虑先让红蓝链的端点匹配，状态转移方程如下：

\[\large \begin{aligned} f_{i,j}=\begin{cases} \frac{1}{2i+j}(f_{i,j-1}+1)+\frac{2i+j-1}{2i+j}f_{i,j-1}&j>0\\ f_{i-1,j+1}&j=0 \end{cases} \end{aligned} \]

简单整理后如下：

\[\large \begin{aligned} f_{i,j}=\begin{cases} \frac{1}{2i+j}+f_{i,j-1}&j>0\\ f_{i-1,1}=\frac{1}{2i-1}+f_{i-1,0}&j=0 \end{cases} \end{aligned} \]

$f_{0,0}=0$，然后推下式子得到 $f_{i,j}=\sum_{k=1}^{i}\frac{1}{2k+j}+\sum_{k=1}^{i}\frac{1}{2k-1}$，然后 $\mathcal{O}(n)$ 就可以计算这个式子了，然后这个玩意是调和级数，在 $n$ 比较的的时候可以 $\mathcal{O}(1)$ 求出近似值，有 $F(n)=\ln n+\gamma +\frac{1}{2n}$，其中 $\gamma=0.577215\dots$，为欧拉常数。

B 最短路

先建出最短路 DAG，保证最短路径唯一，所以建出来的 DAG 是一棵树。考虑一个点的答案可以由谁来更新，假设当前点为点 $u$，它的 dfs 序控制范围是 $l,r$。首先，它可以由子树外除了父亲的节点来更新，形如 ans[u]=dis[v]+w，它也可以由子树内的节点更新，路径形如 1->zc->v->u，要求中转点 $zc$ 必须在 $u$ 的子树外，形式化的来说 $ans_u=\min(dis_{zc}+w_{zc\to v})+w_{v\to u}[1\le dfn_{zc}<l\lor r<dfn_{zc}\le n]$，然后问题就成了一个单点修改，区间查询最小值的问题，从下往上线段树合并即可，时间复杂度 $\mathcal{O}(n\log n)$，常数比较小，比大部分并查集做法要快。

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int RR(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+10,mod=998244353;
const int inf=1e18;
inline void Min(ll &x,ll y){if(x>y)x=y;}
inline void Max(int &x,int y){if(x<y)x=y;}
inline void W(int &x,int y){x=(x+y)%mod;}
int n,m,in[N],head[N],headg[N],tot,fa[N],L[N],R[N],dn,rub[N*20],num;
ll dis[N],ans[N];
struct EDGE{int v,next,w;}e[N<<2],g[N<<1];
inline void adde(int u,int v,int w){e[++tot]={v,head[u],w};head[u]=tot;}
inline void addg(int u,int v,int w){g[++tot]={v,headg[u],w};headg[u]=tot;}
bool vis[N],zhan[N<<2];
struct NODE{
	int pos;ll w;
	inline bool operator<(const NODE &A)const{return w>A.w;}
};
std::priority_queue<NODE> q;
inline int fan(int x){if(x&1)return x+1;else return x-1;}
inline void dij(){
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;q.push({1,0});
	while(!q.empty()){
		int u=q.top().pos;q.pop();
		if(vis[u])continue;vis[u]=1;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				zhan[in[v]]=0;zhan[fan(in[v])]=0;
				in[v]=i;zhan[in[v]]=zhan[fan(in[v])]=1;fa[v]=u;
				if(!vis[v]){q.push({v,dis[v]});}
			}
		}
	}
}
int root[N],cnt;
struct TREE{ll res;int ls,rs;}t[N*20];
inline int NEW(){int wk=num?rub[num--]:++cnt;t[wk]={inf,0,0};return wk;}
inline void Del(int &p){t[p]={inf,0,0};rub[++num]=p;}
inline void update(int p){
	t[p].res=std::min(t[t[p].ls].res,t[t[p].rs].res);
}
inline void insert(int &p,int l,int r,int pos,ll x){
	if(!p)p=NEW();
	if(l==r){Min(t[p].res,x);return;}
	int mid=l+r>>1;if(pos<=mid)insert(t[p].ls,l,mid,pos,x);
	else insert(t[p].rs,mid+1,r,pos,x);update(p);
}
inline int merge(int a,int b,int l,int r){
	if(!a||!b)return a|b;
    if(l==r){Min(t[a].res,t[b].res);Del(b);return a;}
    int mid=l+r>>1;
    t[a].ls=merge(t[a].ls,t[b].ls,l,mid);
    t[a].rs=merge(t[a].rs,t[b].rs,mid+1,r);
    update(a);Del(b);return a;
}
inline ll query(int p,int l,int r,int L,int R){
	if(t[p].res>=inf)return inf;
	if(L>R)return inf;
	if(l>=L&&r<=R)return t[p].res;
	int mid=l+r>>1;ll res=inf;
	if(L<=mid)Min(res,query(t[p].ls,l,mid,L,R));
	if(R>mid)Min(res,query(t[p].rs,mid+1,r,L,R));
	return res;
}
inline void init(int u){
	L[u]=++dn;
	for(int i=headg[u];i;i=g[i].next)init(g[i].v);
	R[u]=dn;
}
inline void dfs(int u,ll dep){
	for(int i=headg[u];i;i=g[i].next){
		dfs(g[i].v,dep+g[i].w);
		root[u]=merge(root[u],root[g[i].v],1,n);
	}
	if(u==1)return;
	Min(ans[u],std::min(query(root[u],1,n,1,L[u]-1),query(root[u],1,n,R[u]+1,n))-dep);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(zhan[i]||L[v]>=L[u]&&R[v]<=R[u])continue;
		ll res=dis[v]+e[i].w;insert(root[u],1,n,L[v],res+dep);
		Min(ans[u],res);
	}
}
signed main(){
    freopen("path.in","r",stdin);freopen("path.out","w",stdout);
    // freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read(),m=read();for(int i=1;i<=m;++i){int u=read(),v=read(),w=read();adde(u,v,w);adde(v,u,w);}
    dij();tot=0;for(int i=2;i<=n;++i)addg(fa[i],i,e[in[i]].w);
	init(1);t[0].res=inf;for(int i=1;i<=n;++i)ans[i]=inf;
    dfs(1,0);
	for(int i=2;i<=n;++i)std::cout<<(ans[i]>=1e17?-1:ans[i])<<'\n';
}

C 列表

这种题先大力手玩，发现有一些位置上的数很灵活，可以在多个时间拿到，仔细观察，从这点入手，比如序列一开始为 $1,2,3,4,5,6,7$，$4$ 肯定是在第一个拿，这个改变不了，观察 $5$，显然它可以第二个拿，如果不拿，只要先删除右边后再删除左边就可以第三个拿到它。其实，我们可以随时控制想要拿的数，如果拿左边就删右边，反之同理，所以每一个数拿的时间都是一个后缀区间，设 $m=2n+1$，一个位置所对应的后缀区间就是 $[\min(i,m-i+1),n+1]$。
假设现在想要拿的值域范围是 $[l,r]$，那么这些数拿的时间都要一一对应上，发现这个东西很像二分图完美匹配，考虑 $\text{Hall}$ 定理检测合法性，当且仅当所有要拿的数对应的时间区间长度大于等于后缀起点在这个区间里的数的个数是，方案一定能全部匹配，$\text{Hall}$ 定理证明。
此时直接枚举答案是 $n^2$ 的，如果值域 $[l,r]$ 合法，那么 $[l+1,r]$ 一定也合法，答案具有单调性，所以能二分答案，但是为什么不上双指针呢，枚举右端点，移动左端点，拿线段树来维护 Hall 定理即可，时间复杂度 $\mathcal{O}(n\log n)$。

停停停!

这是个集贸的 $\text{Hall}$ 定理，众所周知，二分图只要匹配上即可，而这道题有着严格的时间顺序，比如 $1,2,3,4,5,6,7$，如果要同时拿 $5$ 和 $6$，就一定是先拿 $5$，再拿 $6$，所以这根本不是一个匹配问题，这是一个贪心问题，让每个数去匹配最早时间，这样一定是最优的，在线段树上维护的其实也是这个东西，只不过 $\text{Hall}$ 定理也适用于这个罢了，所以这本质上就是一个贪心的过程，没有什么高深的理论，整个证明就是题解中的引理 1，不知道为什么讲评扯上了 $\text{Hall}$ 定理，挂一下真正的题解。

#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define fi frist
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=4e5+10,mod=998244353,inf=1e9;
int n,a[N];
struct tree{int sum,min;}t[N<<2];
inline void update(int p){t[p].min=std::min(t[rs].min-t[ls].sum,t[ls].min);t[p].sum=t[ls].sum+t[rs].sum;}
inline void build(int p,int l,int r){
    if(l==r){t[p].min=l;return;}int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);update(p);
}
inline void change(int p,int l,int r,int pos,int x){
    if(l==r){t[p].sum+=x;t[p].min-=x;return;}
    int mid=l+r>>1;if(pos<=mid)change(ls,l,mid,pos,x);else change(rs,mid+1,r,pos,x);
    update(p);
}
signed main(){
    freopen("list.in","r",stdin);freopen("list.out","w",stdout);
    // freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
    n=read();int m=n*2+1;
    for(int i=1,x;i<=m;++i)x=read(),a[x]=std::min(i,m-i+1);
    build(1,1,n+1);
    int l=1,ans=0;
    for(int i=1;i<=m;++i){
        change(1,1,n+1,a[i],1);
        while(t[1].min<0){change(1,1,n+1,a[l++],-1);}
        ans=std::max(ans,i-l+1);
    }
    std::cout<<ans<<'\n';
}