Blog Detail

C20250053's blog
省集笔记（5.3~5.5）
C20250053 LV 9 @ 2026-5-28 11:33:55

闲话：为啥 hydro 有博客长度限制...

5.3

A

原题 QOJ3652

写的貌似不是正解但是懒了。

就是我们维护一棵线段树，然后每个节点上有一些传感器，维护并查集，然后支持查询某个 $x$ 坐标 $p$ 上高度 $<h$ 的最大高度，具体地，我们对于包含 $p$ 的 $\log n$ 个线段树区间进行二分，找到 $<h$ 的最大位置并用并查集定位到第一个没有被删除的位置。

然后用优先队列维护事件，把同一时间的撞击事件取出来一起处理。

最坏时间复杂度是 $\mathcal{O}(nm\log (nm))$ ，也不知道为什么能过。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXC = 3e5 + 10;

int n,m;
int X[MAXN],Y[MAXN];
int L[MAXN],R[MAXN],V[MAXN];
int b[MAXC],cnt=0;
int ans[MAXN];
bool dely[MAXN],delv[MAXN];

struct Dat{
	int t,i,j;
	friend bool operator<(const Dat &p,const Dat &q){
		return p.t>q.t;
	}
};
priority_queue<Dat>q;
vector<Dat>Vc,Evt;

bool cmp(int p,int q){
	return V[p]<V[q];
}

struct Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	struct node{
		int l,r;
		vector<int>Vc;
		vector<int>fa;
	}t[MAXC<<2];
	int find(int x,int y){
		if(y==-1) return -1;
		if(t[x].fa[y]==y) return y;
		return t[x].fa[y]=find(x,t[x].fa[y]);
	}
	void update(int x,int l,int r,int L,int R,int id){
		if(L<=l&&r<=R){
			t[x].Vc.push_back(id);
			return ;
		}
		int mid=(l+r)>>1;
		if(L<=mid) update(ls,l,mid,L,R,id);
		if(R>mid) update(rs,mid+1,r,L,R,id);
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r;
		if(!t[x].Vc.empty()){
			sort(t[x].Vc.begin(),t[x].Vc.end(),cmp);
			t[x].fa.resize(t[x].Vc.size());
			for(int i=0;i<(int)t[x].Vc.size();i++) t[x].fa[i]=i;
		}
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
	}
	int query(int x,int p,int h){
		int res=-1;
		if(!t[x].Vc.empty()){
			int l=0,r=(int)t[x].Vc.size()-1;
			int ps=-1;
			while(l<=r){
				int mid=(l+r)>>1;
				if(V[t[x].Vc[mid]]<=h) ps=mid,l=mid+1;
				else r=mid-1;
			}
			if(ps!=-1) ps=find(x,ps);
			while(ps!=-1&&delv[t[x].Vc[ps]]){
				int nxt=(!ps?-1:find(x,ps-1));
				t[x].fa[ps]=nxt,ps=nxt;
			}
			if(ps!=-1) res=t[x].Vc[ps];
		}
		if(t[x].l==t[x].r) return res;
		int mid=(t[x].l+t[x].r)>>1;
		if(p<=mid){
			int resL=query(ls,p,h);
			return (res==-1?resL:(resL==-1?res:(V[res]>V[resL]?res:resL)));
		}
		else{
			int resR=query(rs,p,h);
			return (res==-1?resR:(resR==-1?res:(V[res]>V[resR]?res:resR)));
		}
	}
}T;

int main(){
	scanf("%d%d",&n,&m);
	FL(i,1,n) scanf("%d%d",&X[i],&Y[i]),b[++cnt]=X[i];
	FL(i,1,m){
		scanf("%d%d%d",&L[i],&R[i],&V[i]);
		b[++cnt]=L[i],b[++cnt]=R[i];
	}
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	FL(i,1,n) X[i]=lower_bound(b+1,b+cnt+1,X[i])-b;
	FL(i,1,m)
		L[i]=lower_bound(b+1,b+cnt+1,L[i])-b,
		R[i]=lower_bound(b+1,b+cnt+1,R[i])-b,
		T.update(1,1,cnt,L[i],R[i],i);
	T.build(1,1,cnt);
	FL(i,1,n){
		int j=T.query(1,X[i],Y[i]);
		if(j!=-1) q.push({Y[i]-V[j],i,j});
	}
	while(!q.empty()){
		int t=q.top().t;
		Vc.clear(),Evt.clear();
		Vc.push_back(q.top());
		q.pop();
		while(!q.empty()&&q.top().t==t) Vc.push_back(q.top()),q.pop();
		for(auto p:Vc){
			int i=p.i,j=p.j;
			if(dely[i]) continue;
			if(delv[j]){
				int nj=T.query(1,X[i],Y[i]);
				if(nj!=-1) q.push({Y[i]-V[nj],i,nj});
			}
			else Evt.push_back(p);
		}
		for(auto p:Evt){
			int i=p.i,j=p.j;
			dely[i]=1,delv[j]=1;
			ans[i]=V[j];
		}
	}
	FL(i,1,n) printf("%d\n",ans[i]);
}

B

原题 QOJ5504

考虑一条限制什么时候不合法，当 $(\exist i\in [a,b],x_i=1)\land (\exist j\in [c,d],x_j=0)$ 时同时不满足两个条件。

为了禁止这种情况，需要对任意 $i\in [a,b],j\in [c,d]$ ，都有若 $x_i=1$ ，那么 $x_j=1$ ，于是我们在 $i,j$ 之间建 $i\to j$ 的有向边。

然后显然直接建边边数 $\mathcal{O}(qn^2)$ 的，于是我们线段树优化建图，建一个新点然后将 $i$ 的区间连向新点再从新点连向 $j$ 的区间即可，总边数 $\mathcal{O}(q\log n)$ 。

如果两个点 $u,v$ 在同一个强连通分量里，那么它们的 $x_i$ 一定要相等。

于是我们 tarjan 缩点并记 $siz_i$ 表示编号为 $i$ 的 SCC 中原始点的数量，我们要找出一些 SCC 使得 $(\sum siz)\in [n,2n]$ ，且这些 SCC 无法到达没有选中的 SCC。

把 SCC 按大小分为 $3$ 类： $siz>2n,n\le siz\le 2n,siz<n$ 。

如果存在某个 SCC 的 $siz>2n$ 那么无解，因为无论染成 $0/1$ 都会超过 $2n$ 个。

如果存在 $n\le siz\le 2n$ 的 SCC $id$ ，若我们要将 $id$ 染为 $1$ ，我们尝试将其能到达的 SCC 全部染为 $1$ ，若 $sum\le 2n$ 那么就是答案，将这些 SCC 中的点全部染为 $1$ ，其余点染为 $0$ 即可，否则可以到达 $id$ 的所有 SCC 均不能染为 $1$ ，于是尝试将 $id$ 和能到达它的所有 SCC（这个在反图上跑）全部染为 $0$ ，同理若 $sum\le 2n$ 就是答案。

否则均不存在，那么我们一定能按逆拓扑序选出 $siz<n$ 的 SCC 集合凑出一个在 $[n,2n]$ 中的数，也就是按逆拓扑序让 $sum\to sum+siz$ ，当 $sum\ge n$ 时结束，此时合法，显然逆拓扑序符合闭合的条件。

时间复杂度 $\mathcal{O}(n+q\log n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 1.2e5 + 10;
const int MAXM = 2e6 + 10;

int n,q,tot=0;
int dfn[MAXM],low[MAXM],idx=0;
int st[MAXM],top=0;
int scc[MAXM],siz[MAXM],num=0;
vector<int>G[MAXM],E[MAXM],Vs;
bool ins[MAXM],vis[MAXM],mk[MAXM];

struct Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	struct node{
		int l,r;
		int idI,idO;
	}t[MAXN<<2];
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r;
		if(l==r){
			t[x].idI=t[x].idO=l;
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		t[x].idI=++tot;
		G[t[ls].idI].push_back(t[x].idI);
		G[t[rs].idI].push_back(t[x].idI);
		t[x].idO=++tot;
		G[t[x].idO].push_back(t[ls].idO);
		G[t[x].idO].push_back(t[rs].idO);
	}
	void UpdI(int x,int l,int r,int id){
		if(l<=t[x].l&&t[x].r<=r){
			G[t[x].idI].push_back(id);
			return ;
		}
		int mid=(t[x].l+t[x].r)>>1;
		if(l<=mid) UpdI(ls,l,r,id);
		if(r>mid) UpdI(rs,l,r,id);
	}
	void UpdO(int x,int l,int r,int id){
		if(l<=t[x].l&&t[x].r<=r){
			G[id].push_back(t[x].idO);
			return ;
		}
		int mid=(t[x].l+t[x].r)>>1;
		if(l<=mid) UpdO(ls,l,r,id);
		if(r>mid) UpdO(rs,l,r,id);
	}
}T;

void tarjan(int u){
	dfn[u]=low[u]=++idx;
	st[++top]=u,ins[u]=1;
	for(int v:G[u]){
		if(!dfn[v])
			tarjan(v),low[u]=min(low[u],low[v]);
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		siz[++num]=0,mk[num]=0;
		scc[u]=num,ins[u]=0;
		while(st[top]!=u) scc[st[top]]=num,ins[st[top]]=0,top--;
		top--;
	}
}


int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%d",&n,&q),num=idx=0;
		FL(i,1,tot) dfn[i]=low[i]=0,G[i].clear(),E[i].clear();
		tot=3*n;
		T.build(1,1,3*n);
		FL(i,1,q){
			int A,B,C,D,id;
			scanf("%d%d%d%d",&A,&B,&C,&D),id=++tot;
			T.UpdI(1,A,B,id);
			T.UpdO(1,C,D,id);
		}
		FL(i,1,n*3) if(!dfn[i]) tarjan(i);
		FL(i,1,n*3) siz[scc[i]]++;
		bool fg=1;
		FL(i,1,num){
			if(siz[i]>2*n){
				fg=0;
				break;
			}
		}
		if(!fg){
			puts("No");
			continue;
		}
		Vs.clear();
		FL(i,1,num)
			if(n<=siz[i]&&siz[i]<=2*n) Vs.push_back(i);
		if(!Vs.empty()){
			FL(u,1,tot)
				for(int v:G[u]) E[v].push_back(u);
			for(int id:Vs){
				int St=-1,cnt1=0,cnt0=0;
				FL(i,1,3*n) if(scc[i]==id) St=i;
				assert(St!=-1);
				queue<int>q;
				FL(i,1,tot) vis[i]=0;
				vis[St]=1,q.push(St);
				while(!q.empty()){
					int u=q.front();
					q.pop();
					if(u<=3*n) cnt1++;
					for(int v:G[u])
						if(!vis[v]) vis[v]=1,q.push(v);
				}
				if(cnt1<=2*n){
					puts("Yes"),fg=0;
					FL(i,1,3*n) putchar(vis[i]?'1':'0');
					puts("");
					break;
				}
				FL(i,1,tot) vis[i]=0;
				vis[St]=1,q.push(St);
				while(!q.empty()){
					int u=q.front();
					q.pop();
					if(u<=3*n) cnt0++;
					for(int v:E[u])
						if(!vis[v]) vis[v]=1,q.push(v);
				}
				if(cnt0<=2*n){
					puts("Yes"),fg=0;
					FL(i,1,3*n) putchar(vis[i]?'0':'1');
					puts("");
					break;
				}
			}
			if(fg) puts("No");
			continue;
		}
		else{
			int sum=0;
			FL(i,1,num){
				sum+=siz[i],mk[i]=1;
				if(sum>=n) break;
			}
			puts("Yes");
			FL(i,1,3*n) putchar(mk[scc[i]]?'1':'0');
			puts("");
		}
	}
}

C

原题 QOJ6350

考虑我们固定了点集 $S$ （其中 $|S|=2k$ ）后，怎么将点集中的点配对。

从边的贡献的角度考虑，对于树上的边 $e$ ，将树分成了两个连通块，设 $S$ 中有 $cnt$ 个在一侧，另一侧有 $2k-cnt$ 个点，那么最多可以有 $\min(cnt,2k-cnt)$ 对点经过边 $e$ 。

所以固定点集 $S$ 时，最大配对距离和的上界为：

\sum_{e\in E} w_e\cdot\min(cnt_e,2k-cnt_e)

我们对于点集 $S$ 定义重心 $rt$ ，保证删除 $rt$ 后每个连通块内包含的 $S$ 中的点数不超过 $k$ 。

（这样的 $rt$ 不是唯一的，会构成重心链，选择任意一个即可）。

于是对于每条边， $\min(cnt_e,2k-cnt_e)$ 都是以 $rt$ 为根时其远离重心一侧的子树中 $S$ 的点数，所以我们可以看作所有 $S$ 中的点 $x$ 都走到 $rt$ 。

然后我们把删除 $rt$ 之后在同一连通块中的 $S$ 中的点称作一类，而每类点不超过 $k$ 个，一定可以做到每个点都匹配类型不同的点，也就是经过 $rt$ ， $dis(x,y)=dis(x,rt)+dis(rt,y)$ 。

所以最后答案式子变成：

\sum_{x\in S}dis(rt,x)

我们第一反应是加点，考虑从空集开始，每次加入 $2$ 个点，但发现加点时维护重心比较麻烦，于是考虑从全集开始，每次删除离当前重心最近的点（这个拿线段树维护，因为当重心移动到儿子/父亲时，对子树内点的距离减小/增大，对子树外点距离增大/减小，dfn 序连续所以是区间修改）。

考虑具体怎么维护。

假设当前点数为 $i$ ，重心为 $rt$ ，

如果 $rt$ 子树内当前点数 $<\frac{i}{2}$ ，那么 $rt$ 子树外点数 $>\frac{i}{2}$ ， $rt$ 需要往父亲方向移动。

考虑如何移动，假设 $rt$ 子树中有 dfn 序在全局排名为 $(l,r]$ 的节点（显然排名一定连续），那么 $rt$ 会先移动到和排名为 $l$ 或者 $r+1$ 的节点取 $\mathrm{lca}$ 后， $\mathrm{lca}$ 较深的哪个，也就是找到深度最大的点，使得 $rt$ 的子树和排名为 $l$ 或者 $r+1$ 的节点的子树同时成为这个点的子树，因为 $i$ 每次只变化 $1$ ，所以这次移动后， $rt$ 的子树外点数一定 $<\frac{i}{2}$ 。

（经典结论根据 dfn 序排序后，dfn 序越靠近和 $dfn_{rt}$ 的 $\mathrm{lca}$ 深度越大）。

然后此时若存在 $rt$ 的某个儿子 $x$ ，使得 $x$ 子树内当前点数 $>\frac{i}{2}$ ， $rt$ 需要往这个儿子方向移动。

寻找儿子也是简单的，假设 $rt$ 子树除了 $rt$ 之外还有未删除节点，如果存在儿子 $x$ 子树大小 $>\frac{i}{2}$ ，那么排名为 $\lfloor\frac{l+r+1}{2}\rfloor$ 的节点一定在 $x$ 子树内，所以查询这个节点在 $rt$ 的哪个儿子的子树内并看是否需要移动即可。

移动时，设该子树 $x$ 内 DFS 序最小和最大的当前点为 $p,q$ ，新的重心为 $\mathrm{lca}(p,q)$ ，因为此时 $x$ 子树大小一定是刚好 $>\frac{i}{2}$ ，移动到 $\mathrm{lca}(p,q)$ 是最浅可以将 $x$ 的子树分成更小的子树的节点。

时间复杂度 $\mathcal{O}(n\log n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,int>
using namespace std;
const int MAXN = 1e6 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n,rt=-1;
ll nw=0;
ll ans[MAXN];
int siz[MAXN],mx[MAXN];
vector<PII>G[MAXN];
vector<int>E[MAXN];
int L[MAXN],R[MAXN],qid[MAXN],idx=0;
int dep[MAXN],f[20][MAXN];
ll dis[MAXN];

struct BIT{
	#define lowbit(x) (x&(-x))
	int c[MAXN];
	void update(int x,int k){
		while(x<=n){
			c[x]+=k;
			x+=lowbit(x);
		}
	}
	int query(int x){
		int res=0;
		while(x){
			res+=c[x];
			x-=lowbit(x);
		}
		return res;
	}
	int find(int s){
		int x=0;
		for(int k=(1<<19);k;k>>=1)
			if(x+k<=n&&s>c[x+k]) s-=c[x+k],x+=k;
		return qid[x+1];
	}
}T1;
struct Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	struct node{
		int l,r;
		PII mn;
		ll tg;
		void tag(ll k){
			tg+=k;
			mn.first+=k;
		}
	}t[MAXN<<2];
	void pushup(int x){
		t[x].mn=min(t[ls].mn,t[rs].mn);
	}
	void pushdown(int x){
		if(!t[x].tg) return ;
		t[ls].tag(t[x].tg);
		t[rs].tag(t[x].tg);
		t[x].tg=0;
	}
	void build(int x,int l,int r){
		t[x].l=l,t[x].r=r;
		if(l==r){
			t[x].mn={dis[qid[l]],qid[l]};
			return ;
		}
		int mid=(t[x].l+t[x].r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(x);
	} 
	void update(int x,int l,int r,ll k){
		if(l<=t[x].l&&t[x].r<=r){
			t[x].tag(k);
			return ;
		}
		pushdown(x);
		int mid=(t[x].l+t[x].r)>>1;
		if(l<=mid) update(ls,l,r,k);
		if(r>mid) update(rs,l,r,k);
		pushup(x);
	}
}T2;

void Get_rt(int u,int fth){
	siz[u]=1,mx[u]=0;
	for(auto i:G[u]){
		int v=i.first;
		if(v==fth) continue;
		Get_rt(v,u);
		mx[u]=max(mx[u],siz[v]);
		siz[u]+=siz[v];
	} 
	mx[u]=max(mx[u],n-siz[u]);
	if(rt==-1||mx[rt]>mx[u]) rt=u;
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	FR(i,19,0) if(dep[f[i][x]]>=dep[y]) x=f[i][x];
	if(x==y) return x;
	FR(i,19,0) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];
	return f[0][x];
}

void dfs1(int u,int fth){
	L[u]=++idx,qid[idx]=u;
	dep[u]=dep[fth]+1,f[0][u]=fth;
	FL(i,1,19) f[i][u]=f[i-1][f[i-1][u]];
	for(auto i:G[u]){
		int v=i.first,w=i.second;
		if(v==fth) continue;
		E[u].push_back(v);
		dis[v]=dis[u]+w,dfs1(v,u);
	}
	R[u]=idx;
}

bool cmp(int p,int q){
	return L[p]<L[q];
}

int main(){
	scanf("%d",&n);
	FL(i,1,n-1){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	rt=-1,Get_rt(1,0);
	dfs1(rt,0);
	FL(u,1,n) sort(E[u].begin(),E[u].end(),cmp);
	FL(i,1,n) T1.update(L[i],1),nw+=dis[i];
	T2.build(1,1,n);
	if(!(n&1)) ans[n/2]=nw;
	FR(i,n-1,2){
		int ps=T2.t[1].mn.second;
		ll val=T2.t[1].mn.first;
		nw-=val,T1.update(L[ps],-1),T2.update(1,L[ps],L[ps],inf);
		int l=T1.query(L[rt]-1),r=T1.query(R[rt]);
		if((r-l)*2<i){
			int u=lca(T1.find(l),rt),v=lca(T1.find(r+1),rt);
			if(dis[u]<dis[v]) swap(u,v);
			nw-=(dis[rt]-dis[u]),T2.update(1,1,n,-(dis[rt]-dis[u])),T2.update(1,L[rt],R[rt],((dis[rt]-dis[u])<<1));
			rt=u,l=T1.query(L[rt]-1),r=T1.query(R[rt]);
		}
		if(l<r){
			auto it=upper_bound(E[rt].begin(),E[rt].end(),T1.find((l+r+1)/2),cmp);
			int x=*prev(it),xl=T1.query(L[x]-1),xr=T1.query(R[x]);
			if((xr-xl)*2>i){
				int u=lca(T1.find(xl+1),T1.find(xr));
				nw-=(dis[u]-dis[rt]),T2.update(1,1,n,-(dis[rt]-dis[u])),T2.update(1,L[u],R[u],((dis[rt]-dis[u])<<1)),rt=u;
			}
		}
		if(!(i&1)) ans[i/2]=nw;
	}
	FL(i,1,n/2) printf("%lld ",ans[i]);
	puts("");
}

5.4

A

首先是经典 LIS 做法，维护 $f_i$ 表示在序列 $P=(a_1,a_2,\cdots,a_q)$ 中长度为 $i$ 的上升子序列的最小结尾值，若不存在长度为 $i$ 的上升子序列那么 $f_i=\infty$ 。

根据 $f_i$ 我们可以对未加入的数定义等级 $g_i=\min\{i|f_i>x\}$ 。

假设当前选择了数 $x$ ，那么 $f_{g_x}$ 更新为 $x$ ，然后一些数 $y$ 的 $g_y$ 也会改变，具体地，所有满足 $y>x$ 且 $g_y=c$ 的 $y$ ， $g_y=g_y+1$ 。

所以如果我们把所有剩余数按照 $(g_y,y)$ 从小到大排序，那么选择一个数 $x$ 的影响就是删除 $x$ 并把它后面同等级的数等级 $+1$ 。

考虑 $op=1$ 的情况：

若存在等级为 $k$ 的数 $x$ ，那么当前操作的人立即获胜，方案数就是等级为 $k$ 的 $x$ 的数量。
否则所有数的等级都 $<k$ 。
- 考虑我们如果选了等级为 $k-1$ 的 $x$ ，那么所有比 $x$ 大的等级为 $k-1$ 的数等级都会变为 $k$ ，对手必胜，所以我们只能选择等级为 $k-1$ 的数中，最大的那个数。
- 否则我们选择等级 $<k-1$ 的数 $x$ ，最多提升一些数到 $k-1$ ，游戏继续。
此时两个人都不会选择将必胜局面送给对手，所以最后一定是 $S$ 被取光了导致游戏结束，判断 $m=n-q$ 的奇偶性即可，若 $m$ 为偶数那么先手必败，否则先手必胜，方案数为等级 $<k-1$ 的数的个数，如果有等级为 $k-1$ 的数再加上等级为 $k-1$ 的最大数。

然后考虑 $op=2$ 的情况。

规则等价于等级为 $k$ 的数不能选，选了就立刻输。

我们把数分成三类，等级 $<k-1$ 的， $=k-1$ 的， $>k-1$ 的。

显然第三类完全不能操作，我们不考虑它。

我们考虑第二类数，设有 $r$ 个，分别为 $b_1\sim b_r(b_1<b_2<\cdots<b_r)$ 。

假设我们选了 $b_i$ ，那么 $b_{i}$ 被删除， $b_{i+1}\sim b_r$ 变为等级 $k$ ，于是第二类数剩下 $b_1\sim b_{i-1}$ ，共 $i-1$ 个。

设第一类数有 $t$ 个，我们分类讨论 $r$ 的大小：

若 $r=0$ 那么大家都只能操作第一类数，当 $t$ 为偶数时先手必败，否则必胜，方案数为等级 $<k-2$ 的数的个数，如果有 $c$ 个等级 $=k-2$ 的数那么 $+\min(c,2)$ ，即选择等级 $=k-2$ 的最大数和第二大数，此时新的 $(t',r')$ 都是先手必胜，否则后手会拿到 $r'\ge 2$ 的局面，必胜。
若 $r=1$ ，那么可以操作 $t+1$ 个数，当 $t$ 为奇数时先手必败，否则必胜，方案数为等级 $<k-2$ 的数的个数 $+1$ （这里的 $1$ 是唯一一个等级为 $k-1$ 的数），如果有等级 $=k-2$ 的数那么 $+1$ ，也就是等级 $=k-2$ 的最大数，如果选的不是最大数那么对手拿到的局面 $r'\ge 2$ 。
若 $r\ge 2$ ，先手可以根据 $t$ 的奇偶性决定剩下 $1/0$ 个第二类数，一定能变成先手必胜的局面，方案数为 $1$ 。

时间复杂度 $\mathcal{O}(q\log n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int MAXN = 1e5 + 10;
const int inf = 0x3f3f3f3f;

int Typ;
int n,m,q,K;
int f[MAXN],a[MAXN];
vector<int>S;
bool us[MAXN];

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%d%d%d",&n,&Typ,&q,&K),m=n-q;
		FL(i,1,n) f[i]=inf,us[i]=0;
		FL(i,1,q){
			scanf("%d",&a[i]),us[a[i]]=1;
			int p=lower_bound(f+1,f+n+1,a[i])-f;
			f[p]=a[i];
		}
		int L=lower_bound(f+1,f+n+1,inf)-f-1;
		S.clear();
		FL(i,1,n) if(!us[i]) S.push_back(i);
		int mx=S.back(),mn1=S.front(),mn2=(m<1?inf:S[1]);
		int f1=(K-1<=0?0:(K-1>n?inf:f[K-1])),f2=(K-2<=0?0:(K-2>n?inf:f[K-2])),f3=(K-3<=0?0:(K-3>n?inf:f[K-3]));
		if(Typ==1){
			if(mx>f1){
				int cnt=0;
				for(int x:S) if(x>f1) cnt++;
				printf("YES %d\n",cnt);
			}
			else{
				if(!(m&1)) puts("NO");
				else{
					int cnt=0;
					for(int x:S) if(x<=f2) cnt++;
					printf("YES %d\n",cnt+(mx>f2));
				}
			}
			continue;
		}
		else{
			int t=0,r=0;
			vector<int>T;
			for(int x:S){
				if(x<=f2) t++,T.push_back(x);
				else if(x<=f1) r++;
			}
			if((!(t&1)&&!r)||((t&1)&&r==1)) puts("NO");
			else{
				if(!(t&1)&&r){
					if(r!=1) puts("YES 1");
					else{
						int cnt=1;
						for(int x:T) if(x<=f3) cnt++;
						printf("YES %d\n",cnt+(!T.empty()&&T.back()>f3));
					}
				}
				else if((t&1)&&!r){
					int cnt=0;
					for(int x:T) if(x<=f3) cnt++;
					printf("YES %d\n",cnt+(!T.empty()&&T.back()>f3)+(T.size()>=2&&T[T.size()-2]>f3));
				} 
				else if((t&1)&&r>1) puts("YES 1");
				else assert(0);
			}
			continue;
		}
	}
}

B

还是比较常见的转化。

就是对于矩阵 $A_x$ 我们把 $(i,j)$ 看作 $i\to j$ 的一条边权为 $A_{x,i,j}$ 的边。

那么 $(A_{\sigma(1)}A_{\sigma(2)}\cdots A_{\sigma(n)})_{1,1}$ 就相当于从点 $1$ 出发依次使用 $A_{\sigma(1)}\sim A_{\sigma(n)}$ 中选出的边，最后回到点 $1$ ，求这样的路径的边权乘积之和。

我们发现从 $\sigma$ 的角度算很麻烦，因为要记录当前用过的矩阵集合。

所以我们不妨先对每个矩阵 $A_i$ 选一条边 $u\to v$ ，边权为 $A_{i,u,v}$ ，此时 $n$ 条边都是带编号的，于是问这 $n$ 条边有多少种排列方式，使得从点 $1$ 出发，每条边用一次，最后回到点 $1$ ，变成一个有向图欧拉回路计数问题。

首先要满足每个点 $u$ 的 $in_u=out_u$ ，然后根据 BEST 定理，设每个点的出度为 $deg_u$ ，那么从点 $1$ 出发的欧拉回路数量为：

T_1\cdot deg_1!\prod_{v\not=1}(deg_v-1)!

其中 $T_1$ 表示以 $1$ 为根的内向生成树数量，因为图上只有 $3$ 个点，所以我们只需要记录 $2/3$ 是否有连出来的树边即可，我们认为从 $2$ 连出来且不为 $2\to 2$ 的边都可以作为树边， $3$ 是同理的。

我们设计 dp 状态，令 $f_{i,o_2,o_3,i_2,i_3,op_2,op_3}$ 表示点 $2/3$ 的出度为 $o_2/o_3$ ，入度为 $i_2/i_3$ ， $op_2/op_3$ 表示点 $2/3$ 是否有树边时，所有方案的权值乘积之和。

每次转移时枚举在 $A_{i+1}$ 中选的边 $(u,v)$ 即可。

最后答案是 $f_{n,o_2,o_3,o_2,o_3,(o_2>0),(o_3>0)}\cdot o_1!\cdot \max(o_2-1,0)!\cdot\max(o_3-1,0)!$。

（这里要判 $o_2>0/o_3>0$ 是因为如果 $2/3$ 不在欧拉回路里那么它不需要在生成树里）。

但是我们发现我们会算出一种不合法的生成树，也就是 $2,3$ 选择的树边分别为 $2\to 3,3\to 2$ ，此时会成环，而不是生成树，于是我们钦定它们成环并再跑一次 dp 算这样不合法的情况的个数，再从答案减去即可。

时间复杂度 $\mathcal{O}(n^5)$ ，因为空间开不下 $\mathcal{O}(n^5)$ 所以 $f$ 第一维要滚动一下。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 40 + 1;
const int mod = 998244353;

int n,ans=0;
int fac[MAXN];
int A[MAXN][4][4];
int f[2][MAXN][MAXN][MAXN][MAXN][2][2];

void Add(int &x,int y){
	x+=y;
	if(x>=mod) x-=mod;
}
void Del(int &x,int y){
	x-=y;
	if(x<0) x+=mod;
}

int main(){
	scanf("%d",&n);
	fac[0]=1;
	FL(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;
	FL(i,1,n)
		FL(j,1,3)
			FL(k,1,3)
				scanf("%d",&A[i][j][k]);
	f[0][0][0][0][0][0][0]=1;
	FL(i,1,n){
		int now=(i&1);
		FL(o2,0,i) FL(o3,0,i-o2) FL(i2,0,i) FL(i3,0,i-i2) FL(op2,0,1) FL(op3,0,1) f[now][o2][o3][i2][i3][op2][op3]=0;
		FL(o2,0,i-1){
			FL(o3,0,i-1-o2){
				FL(i2,0,i-1){
					FL(i3,0,i-1-i2){
						FL(op2,0,1){
							FL(op3,0,1){
								if(!f[now^1][o2][o3][i2][i3][op2][op3]) continue;
								FL(j,1,3){
									FL(k,1,3){
										if(!A[i][j][k]) continue;
										int val=1ll*f[now^1][o2][o3][i2][i3][op2][op3]*A[i][j][k]%mod;
										int no2=o2+(j==2),no3=o3+(j==3),ni2=i2+(k==2),ni3=i3+(k==3);
										if(!op2&&j==2&&k!=2) Add(f[now][no2][no3][ni2][ni3][1][op3],val);
										if(!op3&&j==3&&k!=3) Add(f[now][no2][no3][ni2][ni3][op2][1],val);
										Add(f[now][no2][no3][ni2][ni3][op2][op3],val);
									}
								}
							}
						}
					}
				}
			}
		}
	}
	FL(o2,0,n)
		FL(o3,0,n-o2)
			Add(ans,1ll*f[n&1][o2][o3][o2][o3][(o2>0)][(o3>0)]*fac[n-o2-o3]%mod*fac[max(o2-1,0)]%mod*fac[max(o3-1,0)]%mod);
	FL(op2,0,1) FL(op3,0,1) f[0][0][0][0][0][op2][op3]=0;
	f[0][0][0][0][0][0][0]=1;
	FL(i,1,n){
		int now=(i&1);
		FL(o2,0,i) FL(o3,0,i-o2) FL(i2,0,i) FL(i3,0,i-i2) FL(op2,0,1) FL(op3,0,1) f[now][o2][o3][i2][i3][op2][op3]=0;
		FL(o2,0,i-1){
			FL(o3,0,i-1-o2){
				FL(i2,0,i-1){
					FL(i3,0,i-1-i2){
						FL(op2,0,1){
							FL(op3,0,1){
								if(!f[now^1][o2][o3][i2][i3][op2][op3]) continue;
								FL(j,1,3){
									FL(k,1,3){
										if(!A[i][j][k]) continue;
										int val=1ll*f[now^1][o2][o3][i2][i3][op2][op3]*A[i][j][k]%mod;
										int no2=o2+(j==2),no3=o3+(j==3),ni2=i2+(k==2),ni3=i3+(k==3);
										if(!op2&&j==2&&k==3) Add(f[now][no2][no3][ni2][ni3][1][op3],val);
										if(!op3&&j==3&&k==2) Add(f[now][no2][no3][ni2][ni3][op2][1],val);
										Add(f[now][no2][no3][ni2][ni3][op2][op3],val);
									}
								}
							}
						}
					}
				}
			}
		}
	}
	FL(o2,1,n)
		FL(o3,1,n-o2)
			Del(ans,1ll*f[n&1][o2][o3][o2][o3][1][1]*fac[n-o2-o3]%mod*fac[o2-1]%mod*fac[o3-1]%mod);
	printf("%d\n",ans);
}

C

发现因为 $T$ 是一棵树，所以当我们去掉 $A$ 的邻边，我们会得到一个孤立点以及若干棵树。

我们不妨以 $T_1$ 中点的编号为我们输出的边集中点的编号。

我们任选 $T_1$ 中的一个孤立点作为 $A$ ，任选 $T_2$ 中的一个孤立点作为 $B$ ，枚举 $B$ 在 $T_1$ 中的编号 $i$ 。

考虑 $i$ 所在的 $T_1$ 连通块 $C$ ，因为 $T_1$ 是删除了 $A$ 的邻边得到的，所以 $A$ 会连向 $C$ 中的某个点，然后我们如果在 $C$ 中删去 $i$ ， $i$ 的每个邻居都会裂出一棵树，不妨记为 $P_1\sim P_d$

我们不妨假设 $A$ 连向 $P_t$ （ $t$ 也可能不存在，这种情况就是 $A$ 连向 $i$ ），那么删除 $B$ 得到的 $T_2$ 的形态是孤立点 $B$ ， $P_1\sim P_{t-1},P_{t+1}\sim P_d$ 以及 $A$ 、可能存在的 $P_t$ 和 $T_1$ 中其他连通块合并的得到的大连通块。

因为编号不一样所以我们只能用树哈希比较形态，记 $H(S)$ 为 $S$ 集合中的点和边集作为无根树时的哈希值。

我们先统计出 $T_2$ 中除了孤立点 $B$ 外每种哈希值出现的次数 $cnt_{hsh}$ ，然后临时在 $T_1$ 中删除 $i$ ，令 $cnt_{H(P_1)}\sim cnt_{H(P_d)}$ 减 $1$ 。

如果有 $cnt_{hsh}=-1$ ，那么 $hsh$ 对应的连通块就是 $P_t$ ，如果有 $cnt_{hsh}=1$ ，那么 $hsh$ 对应的就是 $A$ 在 $T_2$ 中对应的点所在的连通块。

如果 $+1$ 没有或不唯一（因为保证 $A\not=B$ ）， $-1$ 不唯一，或者有 $|cnt_{hsh}|>1$ 那么说明当前 $i$ 不可能是 $B$ 。

然后我们还需要确定 $T_2$ 中 $A$ 对应的点，设其为 $j$ 。

如果删除 $j$ ，那么它周围裂出的所有部分应该对应 $T_1$ 中除 $i$ 所在连通块之外的所有连通块，以及 $P_t$ 。

对 $j$ 裂出的所有部分的哈希值求和看是否等于 $T_1$ 对应部分的哈希和即可。

当我们找到合法的 $i,j$ ，我们构造原树。

以 $T_1$ 的边集为基础，如果不存在 $P_t$ 那么 $A$ 连向 $i$ 。

我们遍历 $T_2$ 中 $j$ 的邻居，用 $tmp$ 集合记录临时删除 $j$ 分裂出的子树以 $j$ 的邻居为根时的哈希值，这里需要用有根树哈希，因为连向 $A$ 的点不同，形成的大连通块结构也可能不同。

对于 $T_1$ 其余连通块以及 $P_t$ ，找到连通块中以哪个点为根时，可以匹配 $tmp$ 中的哈希值，将这个点连向 $A$ 。

输出答案即可。

时间复杂度 $\mathcal{O}(n^2)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e3 + 10;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n;
ull sum=0,X,Y;
unordered_map<ull,int>cnt,tmp,id1,id2;
vector<int>Ans[MAXN];

struct Tree{
	int m,Id=-1;
	int fa[MAXN];
	int deg[MAXN],f[MAXN],siz[MAXN];
	ull sF[MAXN],hs1[MAXN],hs2[MAXN],hs[MAXN];
	vector<int>G[MAXN],V[MAXN];
	vector<int>Vc,mxR;
	int vs[MAXN],idx=0;
	ull F(ull x){
		return x*X+Y;
	}
	int find(int x){
		if(fa[x]==x) return x;
		return fa[x]=find(fa[x]);
	}
	void dfs2(int u,int fth){
		Vc.push_back(u);
		siz[u]=1;
		for(int v:G[u]){
			if(v==fth||vs[v]==idx) continue;
			dfs2(v,u);
			siz[u]+=siz[v];
		}
	}
	void Get_F(int u,int fth){
		sF[u]=1;
		for(int v:G[u]){
			if(v==fth||vs[v]==idx) continue;
			Get_F(v,u);
			sF[u]*=sF[v];
		}
		sF[u]=F(sF[u]);
	}
	ull Get_rths(int u){
		Get_F(u,0);
		return sF[u];
	}
	int Get_rt(int x){
		Vc.clear();
		dfs2(x,0);
		for(int u:Vc){
			ull hsh=Get_rths(u);
			if(tmp[hsh]){
				tmp[hsh]--;
				return u;
			}
		}
		return x;
	}
	ull Get_hs(int x,int y){
		if(f[x]==y) return hs1[x];
		else return hs2[y];
	}
	ull Get(int x){
		Vc.clear(),mxR.clear();
		dfs2(x,0);
		int cnt=(int)Vc.size();
		for(int u:Vc){
			int mx=0;
			for(int v:G[u]){
				if(vs[v]==idx) continue;
				if(siz[v]>siz[u]) mx=max(mx,cnt-siz[u]);
				else mx=max(mx,siz[v]);
			}
			if(mx<=cnt/2) mxR.push_back(u);
		}
		ull mx=0;
		for(int u:mxR)
			Get_F(u,0),mx=max(mx,sF[u]);
		return F(mx);
	}
	void dfs1(int u,int fth){
		for(int v:G[u]){
			if(v==fth) continue;
			dfs1(v,u);
			f[v]=u;
			vs[u]=++idx;
			hs1[v]=Get(v);
			vs[v]=++idx;
			hs2[v]=Get(u);
		}
	}
	void init(){
		idx=0;
		FL(i,1,n) fa[i]=i,G[i].clear(),V[i].clear(),deg[i]=vs[i]=0;
		scanf("%d",&m);
		FL(i,1,m){
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
			deg[u]++,deg[v]++;
			fa[find(u)]=find(v);
		}
		FL(i,1,n) if(!deg[i]) Id=i;
		FL(i,1,n)
			if(i!=Id) V[find(i)].push_back(i);
		FL(i,1,n) if(find(i)==i) dfs1(i,0);
		idx++;
		FL(i,1,n)
			if(!V[i].empty()) hs[i]=Get(i);
	}
}T1,T2;

int main(){
	scanf("%d",&n),X=rnd(),Y=rnd();
	T1.init(),T2.init();
	FL(i,1,n)
		if(!T2.V[i].empty())
			cnt[T2.hs[i]]++,id2[T2.hs[i]]=i;
	FL(i,1,n)
		if(!T1.V[i].empty()) sum+=T1.hs[i];
	FL(i,1,n){//i:T1->B
		if(i==T1.Id) continue;
		T1.vs[i]=++T1.idx,id1.clear();
		for(int v:T1.G[i]){
			ull hsh=T1.Get_hs(v,i);
			cnt[hsh]--,id1[hsh]=v;
		}
		int rtA=0,rtB=0;
		bool fg=1;
		for(auto it:cnt){
			ull hsh=it.first;
			int num=it.second;
			if(!num) continue;
			if(abs(num)>1){
				fg=0;
				break;
			}
			if(num==1){
				if(rtA){
					fg=0;
					break;
				}
				rtA=id2[hsh];
			}
			else if(num==-1){
				if(rtB){
					fg=0;
					break;
				}
				rtB=id1[hsh];
			}
		}
		if(!fg){
			for(int v:T1.G[i]){
				ull hsh=T1.Get_hs(v,i);
				cnt[hsh]++;
			}
			continue;
		}
		ull nw1=sum-T1.hs[T1.find(i)]+(rtB?T1.Get_hs(rtB,i):0);
		FL(j,1,n){
			if(T2.find(j)!=rtA) continue;
			T2.vs[j]=++T2.idx;
			ull nw2=0;
			for(int v:T2.G[j])
				nw2+=T2.Get_hs(v,j);
			if(nw1==nw2){
				vector<PII>Edg;
				if(!rtB) Edg.push_back({T1.Id,i});
				T1.vs[i]=++T1.idx;
				for(int v:T2.G[j])
					T2.Get_F(v,0),tmp[T2.sF[v]]++;
				if(rtB) Edg.push_back({T1.Id,T1.Get_rt(rtB)});
				FL(x,1,n)
					if(!T1.V[x].empty()&&x!=T1.find(i))
						Edg.push_back({T1.Id,T1.Get_rt(x)});
				FL(u,1,n) Ans[u]=T1.G[u];
				for(auto it:Edg){
					int u=it.first,v=it.second;
					Ans[u].push_back(v);
					Ans[v].push_back(u);
				}
				FL(u,1,n)
					for(int v:Ans[u])
						if(u<v) printf("%d %d\n",u,v);
				exit(0);
			}
		}
		for(int v:T1.G[i]){
			ull hsh=T1.Get_hs(v,i);
			cnt[hsh]++;
		}
	}
	puts("Error");
};

5.5

A

原题 P12936

考场上做出来的第一道没有被降紫的黑题。

首先肯定是令 $m=\frac12 \sum d_i$ ，如果 $m<n-1$ 或 $\sum d_i$ 不是偶数那么无解。

发现 $d_i$ 全是偶数是容易构造的，

具体地，如果 $d_i$ 均等于 $2$ ，那么构造一个首尾相接的环。

否则最大的偶度数点的 $d_i>2$ ，我们想到一个很简单的结构三角形，我们用 $2$ 个 $2$ 度点让最大的偶度数点的 $d_i$ 减 $2$ ，直到 $d_i$ 均等于 $2$ （如果不存在两个 $2$ 度点且不成环那么无解）。

于是 $d_i$ 全为偶数构造完了。

然后考虑奇数，考虑 $d_u=1$ 的点 $u$ ，我们要把它挂到另一个点 $v$ 上，然后删去 $u$ ， $d_v\to d_v-1$ 。

我们肯定希望优先消耗奇度数点，把 $>1$ 的奇度数点变成偶度数点，如果没有 $>1$ 的奇度数点那么选偶度数点，如果都没有那么只能连同样度数为 $1$ 的点。

不断找 $1/2$ 度点即可。

显然这样构造出的一定是仙人掌。

是由一些叶子边，一些三角形和一个大环组成的，没有一条边属于多于一个简单环。

时间复杂度 $\mathcal{O}(n^2)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e3 + 10;

int n,m;
int d[MAXN];
vector<PII>Edg;
set<PII>st;

int main(){
	scanf("%d",&n);
	FL(i,1,n) scanf("%d",&d[i]),m+=d[i],st.insert({d[i],i});
	if(m&1) puts("-1"),exit(0);
	m/=2;
	if(m<n-1) puts("-1"),exit(0);
	while(!st.empty()){
		auto its=st.begin();
		if(its->first==1){
			int u=its->second;
			st.erase(its);
			if(st.empty()) puts("-1"),exit(0);
			auto ito=st.end(),ite=st.end();
			for(auto it=st.begin();it!=st.end();it++){
				if((it->first)&1) ito=it;
				else ite=it;
			}
			auto itt=st.end();
			if(ito!=st.end()&&(ito->first)>1) itt=ito;
			else if(ite!=st.end()) itt=ite;
			else itt=ito;
			int v=itt->second,dg=itt->first;
			st.erase(itt);
			Edg.push_back({u,v}),dg--;
			if(dg>0) st.insert({dg,v});
		}
		else{
			auto itt=prev(st.end());
			if(itt->first==2){
				if((int)st.size()<3) puts("-1"),exit(0);
				Edg.push_back({its->second,itt->second});
				int prv=0;
				for(auto it=st.begin();it!=st.end();it++){
					if(prv) Edg.push_back({prv,it->second});
					prv=it->second;
				}
				st.erase(itt);
				break;
			}
			else{
				auto it1=its,it2=next(its);
				if(it1==st.end()||it2==st.end()) puts("-1"),exit(0);
				if(it1->first!=2||it2->first!=2) puts("-1"),exit(0);
				int u1=it1->second,u2=it2->second;
				st.erase(it1),st.erase(it2);
				if(st.empty()) puts("-1"),exit(0);
				itt=prev(st.end());
				int v=itt->second,dg=itt->first;
				st.erase(itt);
				Edg.push_back({u1,u2});
				Edg.push_back({u1,v});
				Edg.push_back({u2,v});
				dg-=2;
				if(dg>0) st.insert({dg,v});
			}
		}
	}
	if((int)Edg.size()<m) puts("-1"),exit(0);
	printf("%d\n",m);
	for(auto i:Edg) printf("%d %d\n",i.first,i.second);
}

B

我们如果暴力枚举点对，那么复杂度是 $\mathcal{O}(n^2)$ 的，直接排序是 $\mathcal{O}(n^2\log(n^2))$ 的。

然后看到求前 $k$ 小想到二分，我们二分 $mid$ ，如果有 $\ge k$ 对球 $\lceil d(i,j)\rceil$ 不超过 $mid$ 那么说明第 $k$ 小的 $\lceil d(i,j)\rceil$ 不超过 $mid$ 。

于是我们求出第 $k$ 小的值 $ans$ ，把 $\lceil d(i,j)\rceil<ans$ 的点对找出来排序然后如果不足 $k$ 个就补 $\lceil d(i,j)\rceil=ans$ 直到有 $k$ 个。

我们考虑距离公式 $d(i,j)=\max(0,D_{i,j}-r_i-r_j)$ ，我们要求 $d(i,j)\le mid$ ，则：

$$D_{i,j}-r_i-r_j\le mid\\ \Rightarrow D_{i,j}\le r_i+r_j+mid\\ \Rightarrow D_{i,j}\le (r_i+\frac{mid}{2})+(r_j+\frac{mid}{2})$$

就等价于令 $r_i\to r_i+\frac{mid}{2},r_j\to r_j+\frac{mid}{2}$ ，然后问两个球是否相交，为了避免处理小数我们对 $x_i,y_i,z_i,r_i$ 都 $\times 2$ 。

然后我们按照半径分层，设未处理的球中最大半径为 $R$ ，我们把半径在 $[\frac{R}{2},R]$ 中的球称为大球，半径 $<\frac{R}{2}$ 的称为小球，然后建立边长为 $2R$ 的三维网格，对于两个半径 $\le R$ 的球，如果它们相交，那么球心距一定 $D\le r_i+r_j\le 2R$ ，所以只可能在相邻的 $3\times 3\times 3=27$ 个格子。

一个球所在格子坐标为 $\big(\lfloor\frac{x_i}{2R}\rfloor,\lfloor\frac{y_i}{2R}\rfloor,\lfloor\frac{z_i}{2R}\rfloor\big)$，我们枚举相交的大球和大球，相交的小球和大球，球心距 $D\le r_i+r_j<\frac{R}{2}+R= \frac32R<2R$ ，因为相交的小球和小球的球心距 $D\le r_i+r_j<\frac{R}{2}+\frac{R}{2}=R$ ，所以它们会集中在相邻的一些格子，复杂度可能退化，于是我们递归到下一层处理。

因为 $m$ 很小，所以我们查找 $\mathcal{O}(n\sqrt{k})$ 次就能找到 $k$ 对。

一次 check 的时间复杂度 $\mathcal{O}(n\log V+n\sqrt{k})$ ，总时间复杂度 $\mathcal{O}(n\log^2V+n\sqrt{k}\log V)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e5 + 10;
const int MAXV = 1e6 + 10;
const int P = 1e6 + 5;

int n,m;
struct Dat{
	ll x,y,z,r;
}a[MAXN];
vector<PII>V;
vector<int>Ans;

ll Calc(int p,int q){
	return max((ll)ceil((sqrtl((a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y)+(a[p].z-a[q].z)*(a[p].z-a[q].z))-a[p].r-a[q].r)/2),0ll);
}

ll Get_id(int x,int y,int z){
	return 1ll*x*P*P+1ll*y*P+z; 
} 

void Solve(int n){
	if(!n) return ;
	int ps=0;
	while(ps+1<=n&&a[ps+1].r<(a[n].r+1)/2) ps++;
	unordered_map<ll,vector<int> >mp;
	FL(i,ps+1,n){
		int x=a[i].x/(a[n].r<<1),y=a[i].y/(a[n].r<<1),z=a[i].z/(a[n].r<<1);
		FL(dx,-1,1){
			FL(dy,-1,1){
				FL(dz,-1,1){
					ll t=Get_id(x+dx,y+dy,z+dz);
					if(mp.find(t)!=mp.end()){
						for(auto j:mp[t])
							if(!Calc(i,j))
								V.push_back({i,j});
						if((int)V.size()>=m) return ; 
					}
				}
			}
		}
		mp[Get_id(x,y,z)].push_back(i); 
	}
	FL(i,1,ps){
		int x=a[i].x/(a[n].r<<1),y=a[i].y/(a[n].r<<1),z=a[i].z/(a[n].r<<1);
		FL(dx,-1,1){
			FL(dy,-1,1){
				FL(dz,-1,1){
					ll t=Get_id(x+dx,y+dy,z+dz);
					if(mp.find(t)!=mp.end()){
						for(auto j:mp[t])
							if(!Calc(i,j))
								V.push_back({i,j});
						if((int)V.size()>=m) return ;
					}
				}
			}
		}
	}
	Solve(ps);
}

bool check(int mid){
	FL(i,1,n) a[i].r+=mid;
	V.clear(),Solve(n);
	FL(i,1,n) a[i].r-=mid;
	return ((int)V.size()>=m);
}

bool cmp(Dat p,Dat q){
	return p.r<q.r;
}

int main(){
	scanf("%d%d",&n,&m);
	FL(i,1,n)
		scanf("%lld%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z,&a[i].r),
		a[i].x<<=1,a[i].y<<=1,a[i].z<<=1,a[i].r<<=1;
	sort(a+1,a+n+1,cmp);
	int l=0,r=(int)2e6,ans=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	assert(ans!=-1);
	if(!ans){
		FL(i,1,m) printf("0 ");
		puts(""),exit(0);
	}
	check(ans-1);
	for(auto i:V) Ans.push_back(Calc(i.first,i.second));
	sort(Ans.begin(),Ans.end());
	while((int)Ans.size()<m) Ans.push_back(ans);
	for(ll i:Ans) printf("%lld ",i);
	puts("");
}

C

假设第 $i$ 组被连续攻击了 $t$ 次，那么剩余血量为 $a_iH-tD$ ，剩余小兵数为 $\lceil\frac{a_iH-tD}{H}\rceil$ 。

对于一组当前有 $x$ 个小兵的敌人，如果连续攻击 $t$ 次，那么已经杀掉的小兵数可以看成 $\min(x,\lfloor\frac{tD}{H}\rfloor)$ ，第 $k$ 个小兵至少需要攻击 $\lceil\frac{kH}{D}\rceil$ 次才会死亡。

我们把 $D,H$ 约分记 $P=\frac{D}{\gcd(D,H)},Q=\frac{H}{\gcd(D,H)}$ 。

我们把每一组小兵的死亡过程拆成若干个连续块。一个块 $(p,q)$ 表示：这段中有 $p$ 个小兵死亡，需要 $q$ 次攻击，效率为 $\frac{p}{q}$ 。假设有两个块 $A=(p_A,q_A),B=(p_B,q_B)$ ，如果先打 $A$ 再打 $B$ 那么会额外造成 $p_Bq_A$ 点伤害，同理先打 $B$ 再打 $A$ 会造成 $p_Aq_B$ 点额外伤害，

所以先打 $A$ 更优当且仅当 $p_Bq_A\le p_Aq_B$ ，移项得到： $\frac{p_A}{q_A}\ge\frac{p_B}{q_B}$ ，因此所有块应该按照 $\frac{p}{q}$ 从大到小排序。

对于一组当前有 $x$ 个小兵的敌人，第一块应该是所有前缀中效率最大的块，即找到最大的 $\frac{p}{q}$ 满足 $p\le x\land \frac{p}{q}\le \frac{P}{Q}$ 。

（这个可以做类似二分的操作，记录 $L=\frac{p_L}{q_L},R=\frac{p_R}{q_R}$ ，我们希望 $L,R$ 一直满足 $L< \frac{P}{Q}\le R$ ，每次我们取 $L,R$ 中间分数 $\frac{p_L+p_R}{q_L+q_R}$ ，然后如果其 $>\frac{P}{Q}$ ，那么我们让 $R\to R+L$ ，移动 $t$ 次后 $R'=\frac{p_R+tp_L}{q_R+tq_L}$ ，我们希望 $R'$ 仍 $>\frac{P}{Q}$ ，所以 $t$ 最大为 $\lfloor\frac{Qp_R-Pq_R-1}{Pq_L-Qp_L}\rfloor$ ，中间分数 $<\frac{P}{Q}$ 时我们移动 $L$ ，是同理的）。

由于这个块是最大效率前缀，记 $T_i$ 表示前 $i$ 个小兵死亡的时间，有 $T_p=q$ ，可以证明剩余死亡时间满足 $T_{p+r}-T_p=T_r$ 。

具体地，显然有 $T_{p+r}\le T_p+T_r$ ，所以我们希望证明不会出现 $T_{p+r}<T_p+T_r$ 。

假设出现了，那么 $T_{p+r}\le q+T_r-1$ ，此时存在合法块 $(p+r,q+T_r-1)$ ，效率为 $\frac{p+r}{q+T_r-1}$ ，实际 $q'$ 可能 $<q+T_r-1$ ，但 $(p+r,q')$ 的效率严格不劣于 $(p+r,q+T_r-1)$ ，所以拿这个计算。因为 $T_r-1=\lceil\frac{rQ}{P}\rceil-1<\frac{rQ}{P}$ ，然后因为原块合法所以 $\frac{p}{q}\le \frac{P}{Q}$ ，移项得到 $q\ge \frac{pQ}{P}$ ，于是 $rq\ge \frac{rpQ}{P}>p(T_r-1)$ ，所以 $\frac{r}{T_r-1}>\frac{p}{q}$ ，推出 $\frac{p+r}{q+T_r-1}>\frac{p}{q}$ ，效率更高， $(p,q)$ 不优。

所以一定有 $T_{p+r}=T_p+T_r$ 。取出这个块后，剩下 $x-p$ 个小兵可以当成一组新的满血小兵继续处理，没有后效性。

然后考虑计算答案，对于块 $(p,q)$ ，第 $k$ 个小兵的死亡时间为 $\lceil\frac{kq}{p}\rceil$ ，总共造成的伤害就是 $\sum_{k=1}^p\Big(\lceil\frac{kq}{p}\rceil-1\Big)$ 。

于是答案加上 $\sum_{k=1}^p\lceil\frac{kq}{p}\rceil=\frac{(p+1)(q+1)-\gcd(p,q)-1}{2}$，减去 $p$ ，再加上当前块之后才会死亡的小兵数量 $sum$ 在这段时间 $q$ 的贡献。

设有 $T$ 个块，那么时间复杂度 $\mathcal{O}(T\log (D+H)+T\log T)$ ， $T$ 的量级大概是 $\mathcal{O}\Big(\sum_{i=1}^n\log a_i\Big)$ 的。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;
const int MAXN = 1e6 + 10;

int n,tot=0;
ll D,H,sum=0,ans=0;
PII a[MAXN];

PII Get(ll lim,ll P,ll Q){
	ll pL=0,qL=1,pR=1,qR=0;
	while(1){
		if(pL+pR>lim)break;
		if(P==pL+pR&&Q==qL+qR){
			pL=P,qL=Q;
			break;
		}
		if(P*(qL+qR)<Q*(pL+pR)){
			ll t=(Q*pR-P*qR-1)/(P*qL-Q*pL);
			if(pL&&pL*t+pR>=lim){
				t=(lim-pR)/pL;
				pR+=t*pL,qR+=t*qL;
				break;
			}
			pR+=t*pL,qR+=t*qL;
		}
		else{
			ll t=(P*qL-Q*pL-1)/(Q*pR-P*qR);
			if(pR&&pR*t+pL>=lim){
				t=(lim-pL)/pR;
				pL+=t*pR,qL+=t*qR;
				break;
			}
			pL+=t*pR,qL+=t*qR;
		}
	}
	return {pL*(lim/pL),qL*(lim/pL)};
}

bool cmp(PII p,PII q){
	return p.first*q.second>q.first*p.second;
}

signed main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%lld%lld",&n,&D,&H),ans=sum=tot=0;
		ll d=__gcd(D,H);
		D/=d,H/=d;
		FL(i,1,n){
			ll x;
			scanf("%lld",&x),sum+=x;
			while(x)
				a[++tot]=Get(x,D,H),x-=a[tot].first;
		}
		sort(a+1,a+tot+1,cmp);
		FL(i,1,tot) sum-=a[i].first,ans+=sum*a[i].second+((a[i].first+1)*(a[i].second+1)-__gcd(a[i].first,a[i].second)-1)/2-a[i].first; 
		printf("%lld\n",ans+1);
	}
}

省集笔记（5.3~5.5）

5.3

A

B

C

5.4

A

B

C

5.5

A

B

C

Status

Development

Support

About

省集笔记（5.3~5.5）

5.3

A

B

C

5.4

A

B

C

5.5

A

B

C

Status

Development

Support

About

SIGN IN