A

题意：给一个 $n$ 个点的完全图，以及单调不降的数组 $a$ 。若两点 $(i,j)$ 连通则产生 $a_{|j-i|}$ 的代价。对于每个 $k$ 求图上删去 $k$ 条边的最小代价。

观察性质。发现：

由于 $a$ 单调不降，一个连通块内的编号一定是连续的。
由于答案随删去的边数递减，也就是随使用的边数递增，所以每个连通块内尽可能多的使用边（也就是每两个点都连一条边）一定不劣。

直接 dp。令 $f_{i,j}$ 表示前 $i$ 个点，使用了小于等于 $j$ 条边的最小代价。转移：

f_{i,j}+cost_k\to f_{i+k,j+\frac{k(k-1)}{2}}

其中 $cost_k$ 表示一个长度为 $k$ 的区间内的数形成连通块的代价。

最终，使用了 $i$ 条边（即删去 $\frac{n(n-1)}{2}-i$ 条边）的答案为 $\min\limits_{j\ge i} f_{n,j}$ 。

时间复杂度 $O(n^4)$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,M=5005;
const int inf=1e18;
void upd(int &x,int y){
	x=min(x,y);
}
int n,m,a[N],cost[N];
int f[N][M];
void cl(){
	memset(a,0,sizeof(a));
	memset(cost,0,sizeof(cost));
}
void sol(){
	cin>>n;
	m=(n-1)*n/2;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			for(int k=j+1;k<=i;k++){
				cost[i]+=a[k-j];
			}
		}
	}
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=m;j++){
			if(f[i][j]>=inf) continue;
			for(int k=1;k<=n-i;k++){
				upd(f[i+k][j+k*(k-1)/2],f[i][j]+cost[k]);
			}
		}
	}
	int ans=inf;
	for(int j=m;j>=0;j--){
		upd(ans,f[n][j]);
		cout<<ans<<" ";
	}
	cout<<"\n";
}
signed main(){
	freopen("cut.in","r",stdin);
	freopen("cut.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int cs,ct=1;
	cin>>cs>>ct;
	while(ct--){
		sol();
		cl();
	}
}

B

题意：给 $n$ 个长度为 $m$ 的字符串，以及 $q$ 次询问 $l,r$ ，求把所有字符串的第 $[l,r]$ 位删去后本质不同的字符串数量。

对 $r$ 扫描线，计算所有字符串 $[r+1,n]$ 位置的哈希值并据此将所有串分为若干个集合，每个集合内的串的 $[r+1,n]$ 位全部相同。对于每个集合，将其中的所有串进行字典序排序，然后计算排序后相邻两串的 $\operatorname{lcp}$ 。将 $l$ 从 $r$ 向 $1$ 扫。每扫到一个 $\operatorname{lcp}$ 就在并查集中合并这两个串。答案就是当前并查集的集合数。

时间复杂度 $O(nm\log n+q)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
const int N=1e3+5,M=1e5+5;
const ul base=1e9+7;
struct uset{
	int fa[N],sz[N],cnt;
	uset(){
		iota(fa,fa+N,0);
		fill(sz,sz+N,1);
		cnt=0;
	}
	int getfa(int x){
		if(fa[x]==x) return x;
		return fa[x]=getfa(fa[x]);
	}
	void un(int x,int y){
		x=getfa(x),y=getfa(y);
		if(x==y) return;
		if(sz[x]<sz[y]) swap(x,y);
		fa[y]=x;
		sz[x]+=sz[y];
		cnt++;
	}
}t;
ul pw[N];
void init(){
	pw[0]=1;
	for(int i=1;i<N;i++){
		pw[i]=pw[i-1]*base;
	}
}
int n,m,q,a[N][N],ans[M];
ul hs[N][N];
int lcp[N][N];
vector<int> g[N][N];
int sa[N],rk[N];
void cl(){
	memset(sa,0,sizeof(sa));
	memset(rk,0,sizeof(rk));
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			g[i][j]={};
		}
	}
	memset(lcp,0,sizeof(lcp));
	memset(hs,0,sizeof(hs));
	memset(a,0,sizeof(a));
	memset(ans,0,sizeof(ans));
}
ul get_hs(int x,int l,int r){
	return hs[x][r]-hs[x][l-1];
}
void sol(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char x;
			cin>>x;
			a[i][j]=x-'a';
			hs[i][j]=hs[i][j-1]+x*pw[j];
		}
	}
	for(int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		g[r][l].push_back(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int le=0,ri=m;
			while(le<ri){
				int mid=(le+ri+1)>>1;
				if(get_hs(i,1,mid)==get_hs(j,1,mid)) le=mid;
				else ri=mid-1;
			}
			lcp[i][j]=lcp[j][i]=le;
		}
	}
	iota(sa+1,sa+n+1,1);
	sort(sa+1,sa+n+1,[&](int x,int y){
		int w=lcp[x][y];
		if(w==m) return false;
		return a[x][w+1]<a[y][w+1];
	});
	for(int i=1;i<=n;i++){
		rk[sa[i]]=i;
	}
	for(int r=1;r<=m;r++){
		unordered_map<ul,int> idx;
		int tot=0;
		vector<int> sc[N];
		vector<pair<int,int>> op[N];
		for(int i=1;i<=n;i++){
			ul w=get_hs(i,r+1,m);
			if(!idx[w]) idx[w]=++tot;
			sc[idx[w]].push_back(i);
		}
		for(int i=1;i<=tot;i++){
			sort(sc[i].begin(),sc[i].end(),[&](int x,int y){
				return rk[x]<rk[y];
			});
			for(int j=0;j<(int)sc[i].size()-1;j++){
				int u=sc[i][j],v=sc[i][j+1];
				int w=lcp[u][v];
				if(w>=r-1) op[r].push_back({u,v});
				else op[w+1].push_back({u,v});
			}
		}
		t={};
		for(int l=r;l>=1;l--){
			for(auto [x,y]:op[l]){
				t.un(x,y);
			}
			for(int id:g[r][l]){
				ans[id]=n-t.cnt;
			} 
		}
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<"\n";
	}
}
signed main(){
	freopen("delete.in","r",stdin);
	freopen("delete.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	init(); 
	int cs,ct=1;
	cin>>cs>>ct;
	while(ct--){
		sol();
		cl();
	}
}

D

题意：一棵树和 $m$ 种病毒，第 $i$ 种病毒在 $tim_i$ 时间出现在点 $pos_i$ 且每过一个时间就会向相邻点扩散。多次询问在 $t$ 时刻同时被编号在 $[l,r]$ 内的所有病毒感染的点数。

考虑被多个病毒同时感染需要满足什么条件。先考虑两个病毒 $(x,y)$ ，令 $tim_x\le tim_y$ 。注意到两个病毒的限制可以等价的变化为一个病毒：记 $d=\operatorname{dis}(x,y),v=tim_y-tim_x$ ，则不难得到新病毒 $z$ 的 $pos_z,tim_z$ 为：

$d<v$ ，此时 $x$ 的限制完全无效（被 $y$ 感染的一定也被 $x$ 感染）。则 $pos_z=pos_y,tim_z=tim_y$ 。
$d\ge v$ ，此时 $pos_z$ 为 $x$ 向 $y$ 走 $\frac{d+v}{2}$ 步到达的点， $tim_z=tim_y+\frac{d-v}{2}$ 。

至此我们已经可以将“同时满足两个病毒的限制”合并为一个病毒。那么，我们使用线段树维护每个病毒的限制，对于一个查询 $[l,r]$ ，在线段树中查询得到将 $[l,r]$ 中的所有病毒合成的新病毒即可。

于是，问题就转化为每次询问都只有一个病毒。也就是询问到点 $pos_i$ 的距离 $\le t-len_i$ 的点数。这是点分树板子，直接做就行。

实现中，由于存在“跳 $\frac{1}{2}$ 步”等操作，我们在每条边的中点加一个辅助点，并把所有时间乘 $2$ 。这样操作后，可以证明，无论怎么合并， $pos,tim$ 都是整数。

时间复杂度 $O(n\log^2 n)$ 。

#include<bits/stdc++.h>
#define mid (((le)+(ri))>>1)
#define ls ((u)<<1)
#define rs (((u)<<1)|1)
#define lp ls,le,mid
#define rp rs,mid+1,ri
using namespace std;
const int N=2e5+5;
struct bit{
	int s[N];
	vector<pair<int,int>> op;
	int lowbit(int x){
		return x&(-x);
	}
	void add(int x,int k){
		op.push_back({x,k});
		x++;
		while(x<N){
			s[x]+=k;
			x+=lowbit(x);
		}
	}
	int sum(int x){
		x++;
		int res=0;
		while(x){
			res+=s[x];
			x-=lowbit(x);
		}
		return res;
	}
	void cl(){
		auto vec=op;
		for(auto [x,k]:vec){
			add(x,-k);
		}
		op.clear();
	}
}t;
int n,q,m,a[N],at[N];
int c,ql[N],qr[N],qt[N],ans[N];
vector<int> e[N];
int fr[N][22],dep[N],sz[N];
int pos[N<<2],tim[N<<2];
vector<pair<int,int>> g[N];
int vis[N];
void cl(){
	memset(vis,0,sizeof(vis));
	fill(g,g+N,vector<pair<int,int>>());
	memset(pos,0,sizeof(pos));
	memset(tim,0,sizeof(tim));
	memset(fr,0,sizeof(fr));
	memset(dep,0,sizeof(dep));
	memset(sz,0,sizeof(sz));
	fill(e,e+N,vector<int>());
	memset(ql,0,sizeof(ql));
	memset(qr,0,sizeof(qr));
	memset(qt,0,sizeof(qt));
	memset(ans,0,sizeof(ans));
	memset(a,0,sizeof(a));
	memset(at,0,sizeof(at));
	n=q=m=c=0;
	t.cl();
}
void get_sz(int u,int fa){
	sz[u]=1;
	for(int v:e[u]){
		if(v==fa||vis[v]) continue;
		get_sz(v,u);
		sz[u]+=sz[v];
	}
}
void get_rt(int u,int fa,int &rt,int tot){
	int ok=1;
	for(int v:e[u]){
		if(v==fa||vis[v]) continue;
		get_rt(v,u,rt,tot);
		if(sz[v]>tot/2) ok=0;
	}
	if(tot-sz[u]>tot/2) ok=0;
	if(ok) rt=u;
}
void append(int u,int fa,int dep,vector<pair<int,int>> &res){
	res.push_back({u,dep});
	for(int v:e[u]){
		if(v==fa||vis[v]) continue;
		append(v,u,dep+1,res);
	}
}
void cal(int u){
	get_sz(u,0);
	int rt=0;
	get_rt(u,0,rt,sz[u]);
	u=rt;
	if(u<=n){
		t.add(0,1);
	}
	for(int i=0;i<(int)e[u].size();i++){
		int v=e[u][i];
		if(vis[v]) continue;
		vector<pair<int,int>> res;
		append(v,u,1,res);
		for(auto [w,dep]:res){
			for(auto [len,id]:g[w]){
				int z=len-dep;
				if(z<0) continue;
				ans[id]+=t.sum(z);
			}
		}
		for(auto [w,dep]:res){
			if(w<=n){
				t.add(dep,1);
			}
		}
	}
	for(auto [len,id]:g[u]){
		ans[id]+=t.sum(len);
	}
	t.cl();
	for(int i=e[u].size()-1;i>=0;i--){
		int v=e[u][i];
		if(vis[v]) continue;
		vector<pair<int,int>> res;
		append(v,u,1,res);
		for(auto [w,dep]:res){
			for(auto [len,id]:g[w]){
				int z=len-dep;
				if(z<0) continue;
				ans[id]+=t.sum(z);
			}
		}
		for(auto [w,dep]:res){
			if(w<=n){
				t.add(dep,1);
			}
		}
	}
	t.cl();
	vis[u]=1;
	for(int v:e[u]){
		if(vis[v]) continue;
		cal(v);
	}
}
void dfs0(int u,int fa){
	fr[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int v:e[u]){
		if(v==fa) continue;
		dfs0(v,u);
	}
}
void init_lca(){
	for(int j=1;j<=18;j++){
		for(int i=1;i<2*n;i++){
			fr[i][j]=fr[fr[i][j-1]][j-1];
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int j=18;j>=0;j--){
		int u=fr[x][j];
		if(dep[u]>=dep[y]) x=u;
	}
	if(x==y) return x;
	for(int j=18;j>=0;j--){
		int u=fr[x][j],v=fr[y][j];
		if(u!=v) x=u,y=v;
	}
	return fr[x][0];
}
int dis(int x,int y){
	int w=lca(x,y);
	return dep[x]+dep[y]-2*dep[w];
}
int kfa(int x,int k){
	for(int j=18;j>=0;j--){
		if((k>>j)&1){
			x=fr[x][j];
		}
	}
	return x;
}
int gs(int x,int y,int k){
	int w=lca(x,y);
	if(k<=dis(x,w)) return kfa(x,k);
	return kfa(y,dis(x,y)-k);
}
pair<int,int> mer(int x,int xt,int y,int yt){
	if(xt>yt){
		swap(x,y);
		swap(xt,yt);
	}
	int d=dis(x,y);
	int v=yt-xt;
	if(d<v){
		return {y,yt};
	}
	else{
		int z=gs(x,y,(d+v)/2);
		int zt=yt+(d-v)/2;
		return {z,zt};
	}
}
void push_up(int u){
	tie(pos[u],tim[u])=mer(pos[ls],tim[ls],pos[rs],tim[rs]);
}
void build(int u,int le,int ri){
	if(le==ri){
		pos[u]=a[le];
		tim[u]=at[le];
		return;
	}
	build(lp);
	build(rp);
	push_up(u);
}
pair<int,int> que(int u,int le,int ri,int x,int y){
	if(x<=le&&ri<=y){
		return {pos[u],tim[u]};
	}
	pair<int,int> res;
	int vis=0;
	if(x<=mid){
		vis=1;
		res=que(lp,x,y);
	}
	if(y>mid){
		if(!vis){
			res=que(rp,x,y);
		}
		else{
			auto [pos1,tim1]=que(rp,x,y);
			res=mer(res.first,res.second,pos1,tim1);
		}
	}
	return res;
}
void sol(){
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		e[x].push_back(n+i);
		e[n+i].push_back(x);
		e[y].push_back(n+i);
		e[n+i].push_back(y);
	}
	for(int i=1;i<=q;i++){
		int op;
		cin>>op;
		if(op==1){
			m++;
			cin>>a[m]>>at[m];
			at[m]*=2;
		}
		else{
			c++;
			cin>>ql[c]>>qr[c]>>qt[c];
			qt[c]*=2;
		}
	}
	dfs0(1,0);
	init_lca();
	build(1,1,m);
	for(int i=1;i<=c;i++){
		auto [pos,tim]=que(1,1,m,ql[i],qr[i]);
		if(qt[i]<tim) continue;
		g[pos].push_back({min(qt[i]-tim,2*n-1),i});
	}
	cal(1);
	for(int i=1;i<=c;i++){
		cout<<ans[i]<<"\n";
	}
}
signed main(){
	freopen("infect.in","r",stdin);
	freopen("infect.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int cs,ct=1;
	cin>>cs>>ct;
	while(ct--){
		sol();
		cl();
	}
}

No comments so far...

做题记录（题解）（仅 A,B,D 题）

A

B

D

0 comments

Status

Development

Support

About