专栏文章

【抽象】2025 sm的NOIP模拟赛 第一篇

FFenki_lo
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minczppo
此快照首次捕获于
2025/12/02 00:23
3 个月前
此快照最后确认于
2025/12/02 00:23
3 个月前
查看原文

R33 T3

P13785 [eJOI 2022] Longest Unfriendly Subsequence

题意

称一个长度为 nn 序列的 bb 是不友好的，当且仅当：
  • ∀i∈[1,n],∀∣i−j∣≤2,bi≠bj\forall i\in[1,n],\forall \lvert i-j\rvert\le 2,b_i\ne b_j。
现在给定一个长度为 nn 的整数序列 aa，求最长的不友好子序列。
1≤n≤2×1051\le n\le 2\times 10^5。

思路

首先不难想到一个 O(n3)\Omicron(n^3) 的dp：设 fi,jf_{i,j} 表示第 ii 个数上一个数为 jj 的最长长度，转移是简单的。
然后使用前后缀 max⁡\max 优化不难做到 O(n2)\Omicron(n^2)，但这样状态就锁死了，没前途。
考虑贪心+去除无用状态trick。
设选取的子序列为 ss，那么在原序列上 sis_i 与 si+1s_{i+1} 两个位置之间，不同的数的种类一定不能超过 44 个，否则显然可以多取一种数插入中间。
然后把相同段合并，记录 fi,jf_{i,j} 表示前 ii 个数选中了第 ii 个位置并且上一个数的位置到 ii 中间有 jj 种不同的数的最长长度，转移依旧简单。
复杂度 O(nS2)\Omicron(nS^2)，其中 SS 为钦定的最大中间不同种数个数，可以取到 44。

代码

CPP
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second 
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=2e5+10,M=2e3+10,S=5;
const bool att=1;
ll f[N][S],a[N],lst[N][S],t[N],cnt,n;
void solve(){
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++){
		for(int j=0;j<S;j++) f[i][j]=0;
	}
	cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=a[i-1]) t[++cnt]=a[i];
	}
	for(int i=1;i<=cnt;i++){
		lst[i][0]=i-1;
		ll pos=1;
		for(int j=0;j<S;j++){
			if(t[lst[i-1][j]]!=t[i]) lst[i][pos++]=lst[i-1][j];
		}
	}
	ll ans=0;
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<S;j++){
			for(int k=0;k<S;k++){
				if(t[i]!=t[lst[lst[i][j]][k]]) f[i][j]=max(f[i][j],f[lst[i][j]][k]+1);
			}
			ans=max(ans,f[i][j]);
		}
	}
	write(ans);
	putchar('\n');
}
int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	int T;
	read(T);
	while(T--) solve();
	return 0;
}
/*
设 f(i,j) 表示前i个数上一个为j且i为最后一个的最长长度。 

考虑优化计算

注意到每一次更新数组实际上只会更新n个f[a[i]][j]

考虑从这个方面下手

还有1h，先n^2 
*/

R33 T4

P10764 [BalticOI 2024] Wall

题意

你想要修建一个围墙，它是由 NN 个墙组成的，每个墙 ii 可能的高度是 aia_i 或 bib_i，对于每个可能的围墙序列 hh，你想要求出它的积水量之和。
例如下图展示了一个 N=10N = 10，围墙高度分别为 4,2,1,8,6,2,7,1,2,34, 2, 1, 8, 6, 2, 7, 1, 2, 3 的例子，它的实际积水高度是 4,4,4,8,7,7,7,3,3,34, 4, 4, 8, 7, 7, 7, 3, 3, 3。
对于某个 ii 雨后应有的水位 HH，需要满足存在两个数 l,r (l≤i,r≥i)l,r\ (l \leq i,r\geq i)，有 hl≥H,hr≥Hh_l \geq H,h_r \geq H，且 HH 最大，此时 ii 的积水量为 H−hiH-h_i。
输出所有可能情况的积水量之和对 109+710^9 +7 取模的值。
1≤n≤5×105,∀i∈[1,n],ai≠bi1\le n\le 5\times 10^5,\forall i\in[1,n],a_i\ne b_i。

思路

首先将 a,ba,b 离散化。
假设我们已经确定了每个城墙的高度 hih_i，记 preipre_i 表示前缀城墙高度最大值，sucisuc_i 表示后缀最大值，那么对于一个城墙，它贡献的水为 min⁡(prei,suci)−hi\min(pre_i,suc_i)-h_i。
考虑 min⁡max⁡\min\max 转换trick，变为 prei+suci−max⁡(prei,suci)−hipre_i+suc_i-\max(pre_i,suc_i)-h_i。设 gg 为全局最大值，最终答案为所有情况的 ∑i=1nprei+suci−g−hi\sum_{i=1}^n pre_i+suc_i-g-h_i。
考虑将四种东西拆分计算。
对于 prepre 与 sucsuc，它们的计算只有正序与倒序的区别，这里只讲 prepre 的计算。
设 fi,jf_{i,j} 表示前 ii 个数最大值为 jj 的方案数。转移时考虑 aia_i 或 bib_i 是否成为最大值。为了方便，我们强制使 ai<bia_i<b_i。
于是有转移
fi,j={fi−1,j×([ai<j]+[bi<j])+∑j=1aifi,jj=ai+∑j=1bifi,jj=bif_{i,j}= \begin{cases} f_{i-1,j}\times([a_i<j]+[b_i<j])\\ +\sum_{j=1}^{a_i} f_{i,j} & j=a_i\\ +\sum_{j=1}^{b_i} f_{i,j} & j=b_i\\ \end{cases}
于是 ∑pre\sum pre 为 ∑i=1n2n−i∑x×fi,x\sum_{i=1}^n2^{n-i}\sum x\times f_{i,x}。
整体都可以在线段树维护，只需要维护区间乘，区间求和，单点加。
对于 ∑g\sum g，考虑在所有位置的贡献以及 ∑x×fn,x\sum x\times f_{n,x}，为 n∑x×fn,xn\sum x\times f_{n,x}。
对于 ∑h\sum h，这个非常简单，考虑每个位置的贡献即可，为 ∑i=1n2n−1(ai+bi)\sum_{i=1}^n 2^{n-1}(a_i+b_i)。
复杂度 O(nlog⁡n)\Omicron(n\log n)。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
#define L (p<<1)
#define R (p<<1|1)
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=5e5+10,mod=1e9+7;
ll n,a[N],b[N],ans,t[N<<1],cnt,_2[N];
struct tree{
	ll tag,sum,val;//乘法懒标，方案数，总和 
}tr[N<<2];
void mul(ll p,ll z){
	tr[p].sum=tr[p].sum*z%mod; 
	tr[p].tag=tr[p].tag*z%mod;
	tr[p].val=tr[p].val*z%mod;
}
void pushup(ll p){
	tr[p].sum=(tr[L].sum+tr[R].sum)%mod;
	tr[p].val=(tr[L].val+tr[R].val)%mod;
}
void pushdown(ll p){
	if(tr[p].tag!=1){
		mul(L,tr[p].tag);
		mul(R,tr[p].tag);
		tr[p].tag=1;
	}
}
void build(ll l,ll r,ll p){
	tr[p].tag=1,tr[p].sum=tr[p].val=0;
	if(l==r) return ;
	ll mid=l+r>>1;
	build(l,mid,L),build(mid+1,r,R);
	return ;
}
void qmul(ll l,ll r,ll x,ll y,ll z,ll p){
	if(x>y) return ;
	if(x<=l&&r<=y){
		mul(p,z);
		return ;
	}
	pushdown(p);
	ll mid=l+r>>1;
	if(mid>=x) qmul(l,mid,x,y,z,L);
	if(mid<y) qmul(mid+1,r,x,y,z,R);
	pushup(p);
	return ;
}
void add(ll l,ll r,ll x,ll z,ll p){
	if(l==r){
		tr[p].val=(tr[p].val+z*t[l])%mod;
		tr[p].sum=(tr[p].sum+z)%mod;
		return ;
	}
	pushdown(p);
	ll mid=l+r>>1;
	if(mid>=x) add(l,mid,x,z,L);
	else add(mid+1,r,x,z,R);
	pushup(p);
	return ;
}
ll query(ll l,ll r,ll x,ll y,ll p){
	if(x>y) return 0;
	if(x<=l&&r<=y) return tr[p].sum;
	pushdown(p);
	ll mid=l+r>>1,res=0;
	if(mid>=x) res=(res+query(l,mid,x,y,L))%mod;
	if(mid<y) res=(res+query(mid+1,r,x,y,R))%mod;
	pushup(p);
	return res;
}
int main(){
//	freopen("wall.in","r",stdin);
//	freopen("wall.out","w",stdout);
	read(n);
	_2[0]=1;
	for(int i=1;i<=n;i++) _2[i]=_2[i-1]*2ll%mod;
	for(int i=1;i<=n;i++) read(a[i]),t[++cnt]=a[i];
	for(int i=1;i<=n;i++) read(b[i]),t[++cnt]=b[i];
	sort(t+1,t+cnt+1);
	cnt=unique(t+1,t+cnt+1)-t-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(t+1,t+cnt+1,a[i])-t;
		b[i]=lower_bound(t+1,t+cnt+1,b[i])-t;
		if(a[i]>b[i]) swap(a[i],b[i]);
	}
	build(1,cnt,1);
	add(1,cnt,a[1],1,1);
	add(1,cnt,b[1],1,1);
	ll pre=0;
	pre=_2[n-1]*(t[a[1]]+t[b[1]])%mod;
	for(int i=2;i<=n;i++){
		ll sa=query(1,cnt,1,a[i],1),sb=query(1,cnt,1,b[i],1);
		qmul(1,cnt,1,a[i],0,1);
		qmul(1,cnt,b[i]+1,cnt,2,1);
		add(1,cnt,a[i],sa,1);
		add(1,cnt,b[i],sb,1);
		pre=(pre+tr[1].val*_2[n-i])%mod;
	}
	ll qz=tr[1].val;
	build(1,cnt,1);
	add(1,cnt,a[n],1,1);
	add(1,cnt,b[n],1,1);
	ll suc=0;
	suc=_2[n-1]*(t[a[1]]+t[b[1]])%mod;
	for(int i=n-1;i>=1;i--){
		ll sa=query(1,cnt,1,a[i],1),sb=query(1,cnt,1,b[i],1);
		qmul(1,cnt,1,a[i],0,1);
		qmul(1,cnt,b[i]+1,cnt,2,1);
		add(1,cnt,a[i],sa,1);
		add(1,cnt,b[i],sb,1);
		suc=(suc+tr[1].val*_2[i-1])%mod;
	}
	ll sumh=0;
	for(int i=1;i<=n;i++){
		sumh=(sumh+(t[a[i]]+t[b[i]])*_2[n-1]%mod)%mod;
	}
	ll ans=((pre+suc-sumh-qz)%mod+mod)%mod;
	write(ans);
	return 0;
}
/*
设 f(i,j) 表示前i个数最大值为j的方案数

考虑第i个位置是否更新最大值

f(i,j)=f(i-1,j)*([ai<j]+[bi<j])
f(i,ai)+=Σf(i-1,1~ai)
f(i,bi)+=Σf(i-1,1~bi)

线段树硬搞即可 
*/

R34 T3

P9019 [USACO23JAN] Tractor Paths P

题意

给定 nn 个区间 [l,r][l,r]，并且有一些区间为特殊区间。保证 lil_i 单增，rir_i 单增。称两个区间是连同的当且仅当两个区间有交，对于连通的两个区间，可以走一步互相到达。
现在给定 qq 次询问，每次给定 x,yx,y，求从第 xx 到第 yy 个区间的最少步数，以及所有最少步数路径经过的特殊区间的并集的元素个数。
1≤n≤2×105,1≤li≤ri≤2n1\le n\le2\times10^5,1\le l_i\le r_i\le 2n。

思路

根据数据找性质，发现若能从第 ii 个区间跳到第 jj 个区间（i<ji<j），那么区间 i∼ji\sim j 都能够从 ii 跳到。同理 jj 反向跳到 ii 的情况也一样。
于是我们可以类似于CF983E NN country的手法做第一问，具体地，倍增维护 f(i,j),g(i,j)f(i,j),g(i,j) 表示从第 ii 个区间开始往后 // 往前跳 2j2^j 步能够到达的编号最大 // 最小的区间，直接跳即可。
记第一问的答案为 disdis，sum(l,r)sum(l,r) 表示区间 [l,r][l,r] 内特殊区间个数。那么第二问的答案为 ∑i=1dis−1sum(f(a,i),g(b,dis−i))\sum_{i=1}^{dis-1}sum(f(a,i),g(b,dis-i))，这两个区间一定是不交的，否则就不是最短路了。
转换成前缀和形式也用倍增维护即可。
复杂度 O(nlog⁡n+qlog⁡n)\Omicron(n\log n+q\log n)。

代码

CPP
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
//#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=2e5+10,inf=1e9;
struct data{
	int l,r;
}d[N];
int cnt,n,q;
char c[N<<1],t[N<<1];
bool tag[N<<1];
int f[N][21],g[N][21];
int tr[N<<1],tr1[N<<1];
int sum[N<<1];
int sumf[N][21],sumg[N][21];
vector<int>v;
void add(int i,int z){
	for(;i<=(n<<1);i+=i&-i) tr[i]=max(tr[i],z);
}
int ges(int i){
	int res=0;
	for(;i;i-=i&-i) res=max(res,tr[i]);
	return res;
}
void add1(int i,int z){
	for(;i<=(n<<1);i+=i&-i) tr1[i]=min(tr1[i],z);
}
int ges1(int i){
	int res=inf;
	for(;i;i-=i&-i) res=min(res,tr1[i]);
	return res;
}
int dis(int x,int y){
	if(x==y) return 0;
	int res=0;
	for(int i=20;i>=0;i--) if(f[x][i]!=0&&f[x][i]<y) res+=(1<<i),x=f[x][i];
	return res+1;
}
int main(){
	freopen("tractor.in","r",stdin);
	freopen("tractor.out","w",stdout);
	read(n),read(q);
	scanf("%s",c+1);
	int pos=0;
	for(int i=1;i<=(n<<1);i++){
		if(c[i]=='L') d[++cnt].l=i;
		else d[++pos].r=i;
		tr1[i]=inf;
	}
	scanf("%s",t+1);
	for(int i=1;i<=n;i++){
		tag[i]=(t[i]=='1');	
		if(tag[i]) v.push_back(i);
		sum[i]=sum[i-1]+tag[i];
	}
	for(int i=n;i>=1;i--){
		f[i][0]=max(i,ges(d[i].r));
		sumf[i][0]=sum[f[i][0]];
		for(int j=1;j<=20;j++) f[i][j]=f[f[i][j-1]][j-1],sumf[i][j]=sumf[i][j-1]+sumf[f[i][j-1]][j-1];
		add(d[i].l,i);
	}
	for(int i=1;i<=n;i++){
		g[i][0]=min(i,ges1((n<<1)-d[i].l+1));
		sumg[i][0]=sum[g[i][0]-1];
		for(int j=1;j<=20;j++) g[i][j]=g[g[i][j-1]][j-1],sumg[i][j]=sumg[i][j-1]+sumg[g[i][j-1]][j-1];
		add1((n<<1)-d[i].r+1,i);
	}
//	for(int i=1;i<=n;i++) cout<<f[i][0]<<" ";
//	cout<<"\n";
//	for(int i=1;i<=n;i++) cout<<g[i][0]<<" ";
//	cout<<"\n";
	while(q--){
		int x,y;
		read(x),read(y);
		int mi=dis(x,y),ans=tag[x]+tag[y];
		for(int i=20;i>=0;i--) if(mi-1&(1<<i)) ans+=sumf[x][i],x=f[x][i];
		for(int i=20;i>=0;i--) if(mi-1&(1<<i)) ans-=sumg[y][i],y=g[y][i];
		write(mi);
		putchar(' ');
		write(ans);
		putchar('\n');
	}
	return 0;
}
/*
先想qn

不是哥们是并集？

n^2预处理+q回答？？？？？？？？？？？？

考虑一个点是否有可能成为答案

8 1
LLLLRLLLLRRRRRRR
11011010
1 8

扫码线？ 
*/

R35 T3

P13078 [NOISG 2019] Rigged Roads

题意

给定一个 nn 个点 mm 条边的无向连通图，第 ii 条边编号为 ii，现在给定一个生成树边集 RR，求一个长度为 mm 的字典序最小的排列 WW，使得在第 ii 条边的边权为 WiW_i 时，最小生成树的边集恰好为 RR。
1≤n,m≤3×1051\le n,m\le3\times 10^5。

思路

考虑 kruskal 最小生成树的过程，那么一条边没有成为树边当且仅当它的两个端点在树上的路径上的任意一条边的边权都要比它小。
既然要求排列字典序最小，显然让编号更小的边在合法范围内获得更小的边权是最好的。
于是我们考虑按编号从小到大枚举边，若边 ii 在 RR 内，直接赋上当前最小的可行边权。若边 ii 不在 RR 中，为了给它赋上最小边权，显然我们要给它两个端点在树上的路径的所有边都赋上最小边权。若赋完后当前最小边权为 xx，则给它赋上 x+1x+1。
考虑如何维护这个过程。具体地，我们维护一个并查集，每一个并查集的祖先都是在树上深度最小的点。当一条边 fax→xfa_x\to x 被赋了边权，则合并 xx 和 xx 的父亲 faxfa_x 的并查集，这样在给树上路径赋边权的时候就可以直接跳并查集了。
注意，在给树上路径赋边权时，也要按照路径上还没赋边权的边的编号升序排序后赋权。
均摊复杂度 O(nlog⁡n)\Omicron(n\log n)，log⁡n\log n 时给树上路径赋权时给边按编号排序带的。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	x=0;
	T w=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=3e5+10;
int n,m;
struct edge{
	int u,v;
}e[N];
struct data{
	int v,id;
};
vector<data>v[N]; 
int fe[N],dfn[N],ip,dep[N],lg[N],st[21][N],F[N],fa[N];
int sum[N],cnt,pos,lu[N];
bool tag[N];
void dfs(int u,int ff,int ffe){
	dfn[u]=++ip;
	dep[u]=dep[ff]+1;
	st[0][dfn[u]]=u;
	fe[u]=ffe;
	fa[u]=ff;
	F[u]=u;
	for(auto p : v[u]){
		if(p.v==ff) continue;
		dfs(p.v,u,p.id);
	}
}
int Min(int x,int y){
	return dep[x]<dep[y] ? x : y;
}
void init(){
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=lg[n];i++){
		for(int j=1;j+(1<<i)-1<=n;j++) st[i][j]=Min(st[i-1][j],st[i-1][j+(1<<i-1)]);
	}
}
int lca(int x,int y){
	if(x==y) return x;
	x=dfn[x],y=dfn[y];
	if(x>y) swap(x,y);
	int k=lg[y-x];
	return fa[Min(st[k][x+1],st[k][y-(1<<k)+1])];
}
int fin(int x){
	return F[x]==x ? x : F[x]=fin(F[x]);
}
void mer(int u,int v){
	int x=fin(u),y=fin(v);
	if(x==y) return ;
	if(dep[x]<dep[y]) F[y]=x;
	else F[x]=y;
}
void sol(int x,int y){
	x=fin(x);
//	cout<<x<<" "<<y<<"\n";
	while(dep[x]>dep[y]){
		lu[++pos]=fe[x];
		mer(x,fa[x]);
		x=fin(fa[x]);
	}
} 
void solve(int u,int v){
	int l=lca(u,v);
	pos=0;
//	cout<<u<<" "<<v<<" "<<l<<"\n";
	sol(u,l),sol(v,l);
	sort(lu+1,lu+pos+1);
	for(int i=1;i<=pos;i++) sum[lu[i]]=++cnt;
//	cout<<"\n";
}
int main(){
//	freopen("road.in","r",stdin);
//	freopen("road.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=m;i++) read(e[i].u),read(e[i].v);
	for(int i=1;i<n;i++){
		int x;
		read(x);
		tag[x]=1;
		v[e[x].u].push_back({e[x].v,x});
		v[e[x].v].push_back({e[x].u,x});
	}
	dfs(1,0,0);
	init();
	for(int i=1;i<=m;i++){
		if(sum[i]) continue;
		else{
			if(tag[i]) sum[i]=++cnt,mer(e[i].u,e[i].v);
			else solve(e[i].u,e[i].v),sum[i]=++cnt;
		}
	}
	for(int i=1;i<=m;i++) write(sum[i]),putchar(' ');
	return 0;
}
/*
[?,!,!,!,?,?,?,?,!,!]

考虑逐条边加入，如果是非树边，那么要给它一条尽量小的坏边

对于一条非树边，它要满足它连上的路径上编号比它大的边都要比它小

考虑最优分配

最理想的状态显然是编号为x的边分配边权x 

显然分配一条最小边最好

那我tm直接打链覆盖标记不就行了？

树剖一下然后直接疯狂跳链

可以直接对树边取min

然后就可以知道有几条树边是延后边

还有自然分配边

考虑这个过程

首先我给没有无效覆盖的边标上号

考虑"暴力赋值"，均摊可行

然后考虑跳链，显然这可以用并查集/链表做

具体地，一个并查集的祖先一定是深度最小的 

若当前编号上限为x，路径上有p条未标边，那么标号区间为[x+1,x+p+1]

考虑存下来之后赋值

然后没了。 
*/

R35 T4

P11089 [ROI 2021] 手机游戏 (Day 1)

题意

给定一个 k×kk\times k 的 0101 矩阵 AA，若 Ai,j=1A_{i,j}=1 则表示当存在相邻两个字母 i,ji,j 时，可以删去 jj，反之则不行。
给定字符串 ss，求 ss 删除若干个字母后的最小字典序。
1≤k≤26,1≤n≤5×1051\le k\le26,1\le n\le 5\times 10^5。

思路

考虑dp。由于是确定字典序最小，需要倒序dp。设 fif_i 表示以 ii 开头时能够删出最小字典序的字符串的下一个位置。转移时考虑 j∈[i+1,n]j\in[i+1,n] 子序列 [i,j][i,j] 是否能被删除到只剩第 ii 为。
考虑如何判断一个连续子序列 [a1,a2…,am][a_1,a_2\dots,a_m] 是否可以删到只剩 a1a_1。我们可以倒序扫描区间，用一个栈维护，在加入 ll 时我们就可以一直删去栈顶可以被 ala_l 删去的元素，然后再加入 ll。区间 [l,r][l,r] 可行当且仅当在加入 ala_l 时栈中元素可以被删完。这个可行区间是可以 O(n2)\Omicron(n^2) 预处理。
然后我们发现，对于一个区间 [l,r][l,r]，若取其后缀，删除序列时一样的。于是我们直接对 [1,n][1,n] 进行这样的维护，并在维护过程中转移dp。那么对于每个点都只会被一个点删去，那么转移总复杂度是 O(n)\Omicron(n) 的。
考虑怎么判断两个位置 x,yx,y 在dp意义下的字典序更优。在暴力下，我们不断跳 fx,fyf_x,f_y，找到第一个不同的位置，判断 axa_x 是否小于 aya_y，或者 xx 是 yy 的严格前缀。在普通的比较中是可以使用二分+hash判断的。
发现这个转移实际上是将第 ii 位拼接到 fif_i 前，于是考虑倍增优化，可以优化到 O(nlog⁡n)\Omicron(n\log n)。
具体实现看代码。

代码

CPP
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	x=0;
	T w=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=5e5+10,K=35,base=998244353,mod=1e9+9;
char c[K][K];
bool vis[K][K];
int k,n,a[N];
char s[N];
int f[N][21];
ll pw[N<<2],g[N][21];
stack<int>st;
bool check(int x,int y){
	for(int i=20;i>=0;i--) if(g[x][i]==g[y][i]) x=f[x][i],y=f[y][i];
	if(x>n) return 1;
	if(y>n) return 0;
	return a[x]<a[y];
}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	read(k),read(n);
	pw[0]=1;
	for(int i=1;i<=1100000;i++) pw[i]=pw[i-1]*base%mod;
	for(int i=1;i<=k;i++){
		scanf("%s",c[i]+1);
		for(int j=1;j<=k;j++) vis[i][j]=c[i][j]-'0';
	}
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1;
	for(int i=n;i>=1;i--){
		f[i][0]=i+1;
		while(st.size()&&vis[a[i]][a[st.top()]]){
			int u=st.top();
			if(check(f[u][0],f[i][0])) f[i][0]=f[u][0]; 
			st.pop();
		}
		st.push(i);
		g[i][0]=a[i]+17ll;
		for(int j=1;j<=20;j++){
			f[i][j]=f[f[i][j-1]][j-1];
			g[i][j]=g[i][j-1]*pw[1<<j]+g[f[i][j-1]][j-1];
		}
	}
	for(int i=1;i<=n;i=f[i][0]) putchar('a'+a[i]-1);
	return 0;
}
/*
考虑如何快速判定一段是否能被删去或者说使用 "逐步拓展"

要倒着做dp 

设 fi 表示以i为起点的最小下一个位置 

如果前面一段都删不完，那么显然后面删不掉前面的

考虑若何从可删的n拓展到n+1

考虑多进来一个字母的影响

考虑这个字母能被谁删掉，如果那个字母能露头，显然可以 

显然露头字母越近越好

考虑前缀 "露头就秒" 位置

如果前缀的露头就秒位置的前面还有能消的，那就绝对可以 

证明：在同字母下越后的位置越好

正确性：取后面时我可以用前面的先删一段再删其他的 

bcaaacqqqqqq

a->c,q,a
c->a 

那么这种情况下取到b取到第二个位置是最好的。 

后面的位置比前面不优当且仅当起前面的位置能删得更多

但是这种情况下前面位置的那个字母要被删去，因此背叛了定义

所以后面的位置严格更优

于是我们可以做dp的时候每做一次就记录可行的最远的对于每个k的位置，直接dp

理论上nk log nk能做，但我不会。 
*/

R34 T4

P11516 [CCO 2024] Summer Driving

题意

给定一棵 nn 个节点的树，树根 rtrt，以及 A,BA,B。
现在玩家 aa 和 bb 要在树上轮流行动，aa 先行动。行动规则如下：
  • aa 行动时，必须恰好走 AA 条未走过的边。
  • bb 行动时，最多走 BB 条边（可以为 00）。
当 aa 无法行动时，bb 会最后走一次，这次行动 bb 最多走 BB 条未走过的边。
aa 想要让最后走到的点的编号最大，bb 想让最后走到的点的编号最小，求双方都进行最优策略下，最终走到的编号。
1≤n≤3×1051\le n\le3\times10^5。

思路

step 1

首先当 A≤BA\le B 时，答案一定是 11。这是因为这个时候的主动权掌握在 bb 手上，若 aa 跳远离 11，bb 可以重新跳回去。
接下来考虑 A>BA>B 的情况。由于 aa 每次不能走走过的边，因此每次走到的深度一定会更深，考虑 dp。
设 fif_i 表示 aa 在点 ii 先手时的最终能够到达的最大值，gig_i 表示 bb 在点 ii 先手时能够到达的最小值。转移时考虑 f,gf,g 在下一步能够到达的点。
但是这个状态不好继续优化下去，我们考虑使用01trick。
我们尝试二分一个 midmid，并考虑最终到达的点是否能够 ≤mid\le mid。于是状态转变为：
  • fif_i 表示 aa 先手从 ii 出发最终是否能够到达 ≤mid\le mid 的点。
  • gig_i 表示 bb 先手从 ii 出发最终是否能够到达 ≤mid\le mid 的点。
那么转移如下：
  • 对于 fif_i，我们考虑 ii 的所有 AA 级儿子 jj。由于 ff 要取最大，因此只要有最终会 >mid>mid 的点，那么 aa 一定会跳过去，所以有
    fi=⋀gjf_i=\bigwedge g_j
    假设没有 AA 级儿子，这个时候给 bb 走最后一步那么就是判断以 ii 为根的子树内深度最浅的 ≤mid\le mid 的点到 ii 的距离时候 ≤B\le B。
  • 那么对于 gig_i 的转移大致是一样的，就是寻找在 BB 邻域中是否有 fj=1f_j=1。但这里有一个非常重要的点，就是当寻找的 vv 在 ii 的祖先链上时，不能直接取 fjf_j，而是要去掉点 ii 方向子树的情况考虑。
    具体地，我们要去掉 gig_i 方向上所有对 fjf_j 造成影响的 gg，如果去掉这些 gg 后 fjf_j 还能跳并且剩下的能跳的 gg 都是 11，或者不能再跳，让 bb 走最后一步时可行，则“此时”的 fjf_j 贡献是 11，否则为 00。
实现时每次到一个 ii，就更新 fif_i，以及它的 AA 级儿子 jj 的 gjg_j（没有就不更新）。因为 A>BA>B，所以更新 gjg_j 时 BB 邻域的信息一定是已经更新完毕的。
于是，我们就获得了一个 O(n2log⁡n)\Omicron(n^2 \log n) 的 dp，可以拿到 3636 pts。
由于笔者写 3636 pts 也调了很久，因此特地将代码放了上来。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=3e5+10,inf=1e15;
struct edge{
	ll v,next;
}e[N<<1];
ll head[N],id;
void add(ll u,ll v){
	e[++id]=(edge){v,head[u]},head[u]=id;
}
ll n,rt,A,B;
ll a[N],cnt,cld[N],cld2[N],dep[N],dfn[N],top[N],ip;
ll f[N];
ll g[N];
vector<ll>sna[N];
void dfs1(ll u,ll fa){
	a[++cnt]=u;
	dep[u]=dep[fa]+1;
	if(cnt>A) sna[a[cnt-A]].push_back(u); 
	top[u]=dfn[u]=++ip;
//	if(cnt>B) snb[a[cnt-B]].push_back(u); 
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].v;
		if(v==fa) continue;
		dfs1(v,u);
		top[u]=max(top[u],top[v]);
	}
	a[cnt]=0;
	cnt--;
} 
void init(ll u,ll fa,ll sum){
//	if(u>sum) val[u]=0;
//	else val[u]=1;
	cld[u]=(u<=sum ? dep[u] : inf);
	cld2[u]=inf;
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].v;
		if(v==fa) continue;
		init(v,u,sum);
		if(cld[v]<cld[u]) cld2[u]=cld[u],cld[u]=cld[v];
		else if(cld[v]<cld2[u]) cld2[u]=cld[v];
	}
}
void sol(ll cen,ll u,ll fa,ll bs){//wrong : ??????????cld 
	//走了bs步后要到A走，然后再续上B步…(Bushi 
	if(dfn[u]<dfn[cen]&&top[cen]<=top[u]){
		ll c=0,pt=0;
		for(int i=0;i<sna[u].size();i++){
			ll v=sna[u][i];
			if(dfn[fa]<=dfn[v]&&dfn[v]<=top[fa]) c+=g[v],pt++;//判定v在fa的子树内 
		}
		if(sna[u].size()==0||sna[u].size()==pt){
			if(cld[u]==cld[fa]) g[cen]|=(cld2[u]-dep[u]<=B);
			else g[cen]|=(cld[u]-dep[u]<=B);
		}
		else g[cen]|=(f[u]-c==sna[u].size()-pt);
	} 
	else g[cen]|=(sna[u].size()==0 ? cld[u]-dep[u]<=B : f[u]==sna[u].size());
	if(bs==B) return ;
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].v;
		if(v==fa) continue;
		sol(cen,v,u,bs+1);
	}
}
void solve(ll u,ll fa){
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].v;
		if(v==fa) continue;
		solve(v,u);
	}
	if(!sna[u].size()){
		f[u]=(cld[u]-dep[u]<=B ? 1 : 0);
	}
	else{
		for(int i=0;i<sna[u].size();i++){
			ll v=sna[u][i];
			sol(v,v,0,0);
			f[u]+=(g[v]);
		}
	}
}
bool check(ll sum){
	init(rt,0,sum);
	for(int i=1;i<=n;i++) g[i]=0,f[i]=0;
	solve(rt,0);
//	write(sum),putchar(' '),write(f[rt]),putchar('\n');
//	for(int i=1;i<=n;i++) cout<<f[i]<<" "<<g[i]<<"\n";
//	cout<<"\n";
	return (sna[rt].size() ? f[rt]==sna[rt].size() : cld[rt]-dep[rt]<=B);
}
int main(){
//	freopen("drive.in","r",stdin);
//	freopen("drive.out","w",stdout);
	read(n),read(rt),read(A),read(B);
//	if(n>4000) return 0;
	if(A==0||B==0) return 0; 
	for(int i=1;i<n;i++){
		ll x,y;
		read(x),read(y);
		add(x,y),add(y,x);
	}
	if(B>=A){
		write(1); 
		return 0;
	}
	dfs1(rt,0); 
	ll l=1,r=n;
	while(l<r){
		ll mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1; 
	}
	write(r);
//	putchar('\n');
//	for(int i=1;i<=n;i++){
//		cout<<i<<" ";
//		for(int j=0;j<sna[i].size();j++) cout<<sna[i][j]<<" ";
//		cout<<"\n";
//	}
//	cout<<dfn[rt]<<" "<<top[rt];
	return 0;
}
/*
9 6 2 1
1 3
1 6
2 4
2 5
2 7
3 9
4 6
4 8

3


*/

step 2

接下来考虑优化。
我们发现对 ff 的更新均摊后复杂度时 O(n)\Omicron(n) 的，瓶颈在于更新 gjg_j 时对 BB 邻域的搜索，我们考虑优化这个过程。
我们将 gjg_j 的更新换一下表达方式。
  • 对于所有不在 jj 祖先链上的点 kk，判断离 jj 最近的 fk=1f_k=1 的 kk 是否距离 jj 不超过 BB。
  • 对于在祖先链上的 kk，每个 kk 单独考虑去掉 jj 方向上子树后的情况，即不允许往回走。
于是通过这样的表达，我们就去掉了“BB 邻域”这个概念，扩展成了“所有点最优”的表达。接下来的处理都不会再跟 BB 邻域有关系。
我们考虑换种方式转移：我们不要更新 gg 时去找需要的 ff，而是在更新完 ff 后去更新能够被它影响的 gg。
注意到每次更新一个深度为 dd 的 ii 的 fif_i 时能过影响到需要的 gjg_j 的点的深度不小于 d+A−Bd+A-B，于是考虑将点按深度从深到浅加入与更新。每次到了一个深度 dd，就将所有深度为 d+A−Bd+A-B 的点纳入考虑范围。
现在考虑如何处理新加入的这些点。考虑现在新加入一个 jj。
我们要记住，更新 gjg_j 的目的是为了能够更新 fif_i。
为了方便，设 tjt_j 表示点 jj 的子树内深度最浅的满足 fk=1f_k=1 的 kk 的深度。
tjt_j 可以在这个过程中更新。
  • 第一种更新：对于在 ii 子树内的情况，我们可以直接取 tit_i，那么现在我们只需要考虑跨子树的情况。
    对于一个 tjt_j，显然它可以更新它的兄弟子树内的信息。具体地，它可以更新它兄弟子树中的点的值为 tj−depfaj×2t_j-dep_{fa_j}\times 2，在需要更新一个 gjg_j 时它的值加上 depjdep_j 就是它的贡献，实际上这个式子是求树上距离。
    可以用一棵区间取 min⁡\min，单点查询的线段树结合 dfndfn 序，加上标记永久化解决。
  • 第二种更新：这种情况是 aa 走进了 jj 的某棵子树内部，然后 bb 又从这棵子树走了出来恰好走到 jj。于是我们考虑枚举它从哪棵子树走出来，如果它能够满足以下两个条件之一，那么这颗子树内的所有点的值都变为 −∞-\infty，即将未确定 gg 全部变为 11。
最后计算 gig_i 的时候直接比较 ti−depit_i-dep_i 和线段树中 dfnidfn_i 的位置的值加上 depidep_i 即可，看它们是否 ≤B\le B。
复杂度 O(nlog⁡2n)\Omicron(n\log^2 n)。

代码

CPP
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=6e5+10,inf=1e9;
int n,rt,a,b;
struct edge{
	int v,next;
}e[N<<1];
int head[N],id;
void add(int u,int v){
	e[++id]=(edge){v,head[u]},head[u]=id;
}
int f[N],g[N],t[N];
int lg[N],st[21][N],fa[N],dfn[N],top[N],ip,dep[N];
int mad;
vector<int>son_a[N],dep_pt[N];
int lu[N];
int max_suma[N],cmax_suma[N],acp_suma[N],cacp_suma[N];
int min_sumb[N],cmin_sumb[N];
void dfs(int u,int ff){
	fa[u]=ff;
	dep[u]=dep[ff]+1;
	mad=max(mad,dep[u]);
	dfn[u]=top[u]=++ip;
	st[0][dfn[u]]=u;
	lu[dep[u]]=u;
	if(dep[u]>a) son_a[lu[dep[u]-a]].emplace_back(u);
	dep_pt[dep[u]].emplace_back(u);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==ff) continue;
		dfs(v,u);
		top[u]=max(top[u],top[v]);
	}
}
int Min(int x,int y){
	return dep[x]<dep[y] ? x : y;
}
void init1(){
	for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<=lg[n];i++){
		for(int j=1;j+(1<<i)-1<=n;j++) st[i][j]=Min(st[i-1][j],st[i-1][j+(1<<i-1)]);
	}
}
int lca(int x,int y){
	if(x==y) return x;
	x=dfn[x],y=dfn[y];
	if(x>y) swap(x,y);
	int k=lg[y-x];
	return fa[Min(st[k][x+1],st[k][y-(1<<k)+1])];
}
struct SGT{
	int sum[N<<2];
	#define L (p<<1)
	#define R (p<<1|1)
	void build(int l,int r,int p){
		sum[p]=inf;
		if(l==r) return ;
		int mid=l+r>>1;
		build(l,mid,L),build(mid+1,r,R);
		return ;
	}
	void modify(int l,int r,int x,int y,int z,int p){
//		cout<<x<<" "<<y<<" kkksc03\n";
		if(x>y) return ;
		if(x<=l&&r<=y){
			sum[p]=min(sum[p],z);
			return ;
		}
		int mid=l+r>>1;
		if(mid>=x) modify(l,mid,x,y,z,L);
		if(mid<y) modify(mid+1,r,x,y,z,R);
		return ;
	}
	int query(int l,int r,int x,int p){
		if(l==r) return sum[p];
		int mid=l+r>>1,res=sum[p];
		if(mid>=x) return min(res,query(l,mid,x,L));
		else return min(res,query(mid+1,r,x,R));
	}
}T;
void init(int u,int mid){
	f[u]=g[u]=0;
	t[u]=inf;
	min_sumb[u]=(u<=mid ? u : n+1);
	cmin_sumb[u]=n+1;
	max_suma[u]=cmax_suma[u]=acp_suma[u]=cacp_suma[u]=0;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa[u]) continue;
		init(v,mid);
		if(Min(min_sumb[u],min_sumb[v])==min_sumb[v]) cmin_sumb[u]=min_sumb[u],min_sumb[u]=min_sumb[v];
		else if(Min(cmin_sumb[u],min_sumb[v])==min_sumb[v]) cmin_sumb[u]=min_sumb[v];
	}
}
bool check(int mid){
	init(rt,mid); 
	T.build(1,n,1);
	for(int d=mad;d>=1;d--){
		for(auto p : dep_pt[d+a-b]){
//			cout<<p<<" ";
			if(f[p]) t[p]=dep[p];
			else{
				t[p]=inf;
				for(int i=head[p];i;i=e[i].next){
					int v=e[i].v;
					if(v==fa[p]) continue;
					t[p]=min(t[p],t[v]);
				}
			}
			T.modify(1,n,dfn[fa[p]]+1,dfn[p]-1,t[p]-(dep[fa[p]]<<1),1);
			T.modify(1,n,top[p]+1,top[fa[p]],t[p]-(dep[fa[p]]<<1),1);
			for(int i=head[p];i;i=e[i].next){
				int v=e[i].v;
				if(v==fa[p]) continue;
				int s=(dfn[v]<=dfn[max_suma[p]]&&dfn[max_suma[p]]<=top[v] ? cmax_suma[p] : max_suma[p]);
				int zs=(dfn[v]<=dfn[min_sumb[p]]&&dfn[min_sumb[p]]<=top[v] ? cmin_sumb[p] : min_sumb[p]);
				int ac=(dfn[v]<=dfn[acp_suma[p]]&&dfn[acp_suma[p]]<=top[v] ? cacp_suma[p] : acp_suma[p]);
				if(!s&&(ac||dep[zs]-dep[p]<=b)){
					T.modify(1,n,dfn[v],top[v],-inf,1);
				}
			}
		}
//		cout<<"over \n";
		for(auto p : dep_pt[d]){
			if(!son_a[p].size()){
				f[p]=(dep[min_sumb[p]]-dep[p]<=b);
			}
			else{
				f[p]=1;
				for(auto v : son_a[p]){
					int gs=0;
					gs=min(t[v]-dep[v],T.query(1,n,dfn[v],1)+dep[v]); 
					if(gs<=b){
						g[v]=1;
						if(!acp_suma[p]) acp_suma[p]=v;
						else if(lca(acp_suma[p],v)==p) cacp_suma[p]=v; 
					}
					else{
						if(!max_suma[p]) max_suma[p]=v;
						else if(lca(max_suma[p],v)==p) cmax_suma[p]=v; 
						g[v]=0,f[p]=0;
					} 
				}
			} 
		}
//		printf("step\n");
	}
	return f[rt];
}
signed main(){
	freopen("drive.in","r",stdin);
	freopen("drive.out","w",stdout);
	read(n),read(rt),read(a),read(b);
	for(int i=1;i<n;i++){
		int x,y;
		read(x),read(y);
		add(x,y),add(y,x);
	}
	if(a<=b){
		write(1);
		return 0;
	}
	dfs(rt,0);
	init1();
	dep[n+1]=inf;
	int l=1,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
//		printf("kkksc03\n");
	}
	write(r);
//	cout<<"\n";
//	check(1);	
//	for(int d=1;d<=mad;d++){
//		for(auto p : dep_pt[d]){
//			cout<<f[p]<<" "<<g[p]<<" "<<t[p]<<"\n";
//		}
//	}
	return 0;
}

R36 T2

P12966 [CCO 2025] Asteroid Mining

题意

给定 nn 个物品，每个物品有 viv_i 的价值和 wiw_i 的体积，背包容量为 WW。任意两个物品满足体积有倍数关系。
1≤n≤5×1051\le n\le 5\times 10^5。

思路

既然有倍数关系，那么将物品按 ww 升序排序后，必有 wi∣wi+1w_i\mid w_{i+1}。
贪心地想，最后的取到的物品一定是同类体积物品中最大的一段前缀，并且最后的序列一定满足对于一种 wiw_i，经过“合并”后除了重量最大的，一定不超过 wi+1wi\frac{w_{i+1}}{w_i} 个，于是根据这个贪心，我们就有了这样一个做法：
从小到大枚举 wiw_i，每次取 W mod wi+1/wiW\bmod w_{i+1} / w_i 个，这些是对后面的取的方案没有影响的，然后剩下的每 wi+1wi\frac{w_{i+1}}{w_i} 个合并成一个，拍到下一个优先队列里面，到最大体积时取到没有容量即可。
复杂度 O(nlog⁡V+nlog⁡n)\Omicron(n\log V+n\log n)。

代码

CPP
//#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=5e5+10;
struct rock{
	ll v,w;
}d[N];
bool cmp(rock a,rock b){
	return a.w<b.w||a.w==b.w&&a.v>b.v;
}
ll n,m;
priority_queue<ll,vector<ll>,less<ll> >q[50];
vector<ll>v[N];
ll w[N],cnt;
int main(){
//	freopen("mining.in","r",stdin);
//	freopen("mining.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=n;i++) read(d[i].v),read(d[i].w);
	sort(d+1,d+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(d[i].w!=d[i-1].w){
			if(d[i].w>m) break;
			w[++cnt]=d[i].w;
		}
		v[cnt].emplace_back(d[i].v);
	}
	ll ans=0;
	for(int i=1;i<=cnt;i++){
//		cout<<w[i]<<"\n";
		for(auto p : v[i]) q[i].push(p);
		if(i==cnt){
			while(q[i].size()&&m>=w[i]) ans+=q[i].top(),q[i].pop(),m-=w[i];
		}
		else{
			ll sum=(m%w[i+1])/w[i];
			while(q[i].size()&&sum) ans+=q[i].top(),q[i].pop(),sum--,m-=w[i];
			ll js=0,nxt=0;
			while(q[i].size()){
				nxt+=q[i].top();
				js+=w[i];
				if(js==w[i+1]) q[i+1].push(nxt),nxt=0,js=0;
				q[i].pop();
			}
			if(js!=0) q[i+1].push(nxt);
		}
	}
	write(ans);
	return 0; 
}
/*
按 w 排序后，w(i) 一定是 w(i-1) 的倍数

除了连续段的相同w外，重量的增进是2^级别的

对于一段相同的，一定是取一段最大前缀

怎么维护前面的？

所以总记段数有 log_2 (1e12) 段

从这个方向考虑

so？ 
 
取模？ 

40 n ?

最后合并后的形式是每段不超过相邻比值的


[_____]
[_]
[________]
[____]

how T2??????

怎么处理散块

 
*/

R39 T3

没有原题，扫码了。

题意

给定 n,mn,m，现在随机取 2n2n 个整数，每个整数会等概率在 [0,m][0,m] 内取，求前 nn 个整数的和比后 nn 个整数严格大的概率。
需要在至多 O(nlog⁡n)\Omicron(n\log n) 的时间内求出。

思路

设 P(x)P(x) 为 nn 个数和为 xx 的概率。
左边和右边总和取值的概率显然是相互独立的，因此对于一个和 xx，左边的 P(x)P(x) 和右边的 P(x)P(x) 是相等的。那么设左边的和最终为 xx，右边的和最终为 yy，那么有 P(x>y)=P(x<y)P(x>y)=P(x<y)，于是题目转换成求 P(x=y)P(x=y)。答案为 1−P(x=y)2\frac{1-P(x=y)}{2}
首先由于每取一次数就要乘上 1m+1\frac{1}{m+1}，因此我们整体把这个东西提出来，最后再乘上 (1m+1)2n(\frac{1}{m+1})^{2n}。那么现在需要考虑求 x=yx=y 的方案数。
我们将右边的取值变为其相反数，那么需要求的就是左边 nn 个数取值范围为 [0,m][0,m]，右边为 [−m,0][-m,0]，最终和为 00 的方案数。这样依旧很麻烦，因为在值域上不相等，于是我们考虑给左边的 nn 个数都加上 mm，于是问题就变成了有 2n2n 个数，取值范围为 [0,m][0,m]，最终和为 nmnm 的方案数。
假设没有取值值域限制的话，显然可以用插板法做，但是既然有限制，我们考虑容斥。
设钦定插板时有 ii 段违法（>m>m），我们考虑怎样让这 ii 段在式子中表达出来。
由于这 ii 段的大小至少为 m+1m+1，我们先提前取出 ii 个 m+1m+1 出来，那么剩下的 nm−i×(m+1)nm-i\times(m+1) 用插板法即可。这个时候我们再从中选择 ii 段不合法，并分别给它们加上 m+1m+1，于是我们就在式子中将这个不合法的东西表达了出来，于是我们有容斥式
∑i=02n(−1)i×C2ni×Cnm−i×m+(2n−1)2n−1\sum_{i=0}^{2n}(-1)^i\times C_{2n}^{i}\times C_{nm-i\times m+(2n-1)}^{2n-1}
复杂度 O(n)\Omicron(n)。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=2e3+10;
ll n,m,mod;
ll fac[N*N],inv[N*N];
void init(){
	fac[0]=inv[0]=fac[1]=inv[1]=1;
	for(int i=2;i<=4e6;i++) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=4e6;i++) inv[i]=inv[i]*inv[i-1]%mod;
}
ll C(ll x,ll y){
	if(x<y||x<0||y<0) return 0;
	return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
ll ksm(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1) res=res*x%mod;
		x=x*x%mod,y>>=1;
	}
	return res;
}
void solve(){
	read(n),read(m);
	ll p=ksm((m+1),mod-2),ans=0;
	for(int i=0;i<=(n<<1);i++){
		ans=(ans+(i&1 ? -1 : 1)*C((n<<1),i)%mod*C(n*m+(n<<1)-1-i*(m+1),(n<<1)-1)%mod)%mod;
	}
	ans=ans*ksm(p,(n<<1))%mod;
	write((1-ans+mod)%mod*ksm(2,mod-2)%mod);
	putchar('\n');
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T;
	read(mod);
	init();
	read(T);
	while(T--) solve();
	return 0;
}
/*
设 f(x) 为最终和为 x 的概率 

则

ans = sum of ( f(x) * sum of ( f(y) (y<x) ) )

但是显然这样是前缀和优化都有 O (n (nm) ) 的，瓶颈在于dp计算

f(i,x)=sum of f(i-1,x~x-(m)) * (1/(m+1)) 

由于这样的状态无法再优化下去，考虑一个更加好的状态

或者说优化转移？ 

等等你 tm T 2000？？？？？？？？？？？？？？？？？ 

O(nlogn) \ O(n)?

考虑一个东西的转移路径？

还是说式子？

总概率为 1 ，并且具有对称性

推式子

m+1 ？ ？

插板法后考虑有几步超限

考虑转换一下，变成相等的概率

ans= P(x>y) + P(x=y) 

其中 P(x>y) = P(x<y)

于是考虑计算 P(x=y)

考虑前 n 个数取 [0,m] 后 n 个数取 [-m,0]

然后给后面的数全部加上 m 

计算 2n 个数 和为 nm 的概率

考虑容斥

 
*/

R41 T2

P10883 [COCI 2017/2018 #2] Doktor

题意

给定一个排列 pp，这个序列的权值为满足 pi=ip_i=i 的 ii 的数量。
求进行一次将某个区间 [l,r][l,r] 翻转的操作后最大的权值增值。
1≤n≤5×1051\le n\le5\times 10^5。

思路

这里只说翻转数对区间长度为奇数的情况。
设数 ii 的位置为 tit_i，那么显然它能贡献的区间的翻转中心为 ⌊i+ti2⌋\lfloor\frac{i+t_i}{2}\rfloor。
于是我们对每一个区间中心开一个 vector，用于管理能够给它贡献的 ii 的 max⁡(i,ti)\max(i,t_i)。
同时我们发现如果有 i=tii=t_i，那么只要翻转区间包含它，那么贡献就会减 11，于是我们拿一个前缀和数组 prexpre_x 来统计前 xx 个位置中有多少个这样的 ii。
在统计答案时，我们将每一个区间中心 ii 的 vector 升序排序，假设当前枚举到的位置 xx 是这个 vector 的第 ss 个，那么显然它的贡献就是翻转对数量减去区间内满足 i=tii=t_i 的数量，即 s+prex−prei∗2−x−1s+pre_x-pre_{i*2-x-1}。
每次拿 ansans 和这个东西取 min⁡\min 即可。
翻转数对区间长度为偶数的情况雷同，这里不再赘述。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=5e5+10;
int n,a[N],pos[N];
int pre[N];
vector<int>v[2][N];
int main(){
//	freopen("doktor.in.5a","r",stdin);
//	freopen("a.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(a[i]),pos[a[i]]=i;
	for(int i=1;i<=n;i++){
		ll l=min(i,pos[i]),r=max(i,pos[i]);
		ll t=l+r>>1,type=(r-l+1)&1;
		v[type][t].push_back(r);
		pre[i]=pre[i-1]+(i==pos[i]);
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(v[0][i].size()){
			sort(v[0][i].begin(),v[0][i].end());
			ll cnt=0;
			for(auto p : v[0][i]){
				cnt++;
				ll lst=i*2-p+1;
				ans=max(ans,cnt-(pre[p]-pre[lst-1]));
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(v[1][i].size()){
			sort(v[1][i].begin(),v[1][i].end());
			ll cnt=0;
			for(auto p : v[1][i]){
				cnt++;
				ll lst=i*2-p;
				ans=max(ans,cnt-(pre[p]-pre[lst-1]));
			}
		}
	}
	write(ans);
	return 0;
}

R41 T3

题意

给定一棵 nn 个节点的树与 mm 个条件，树的根为 11，每个条件的形式为 x,k,vx,k,v，表示花费 vv 的代价可以把从 xx 起出发向根方向走 kk 步的路径上的边变为可行走状态。
初始时每条边的状态都为不可行走状态。
现在给定 qq 次询问，每次询问给定一个 pp，求从 pp 出发只走可行走的边到 11 的最小代价。
1≤n≤2×1051\le n\le 2\times10^5。

思路

因为是不断往上走，所以深度是不断减少的，考虑 dp。
设 dpudp_u 表示 uu 的最小价值，设 vv 为这个条件能够走到的且不为 uu 的点，那么对于一个 uu 的条件显然有转移
dpi=min⁡(dpi,min⁡{dpv}+v)dp_i=\min(dp_i,\min\{dp_v\}+v)
发现实际上这个转移式只需要对 kk 级祖先链上的 dp 值取 min⁡\min，倍增优化即可。
复杂度 O(nlog⁡n)\Omicron(n\log n)。

代码

CPP
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=2e5+10,inf=1e17;
struct edge{
	ll v,next;
}e[N<<1];
ll head[N],id;
void add(ll u,ll v){
	e[++id]=(edge){v,head[u]},head[u]=id;
}
ll n,m,q,f[N][21],g[N][21],dep[N];
ll sum[N];
vector<pll>v[N];
void dfs(ll u,ll fa){
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].v;
		if(v==fa) continue;
		dfs(v,u);
	}
}
ll fin(ll x,ll gd){
	ll res=inf;
	for(int i=20;i>=0;i--) if(dep[f[x][i]]>=gd) res=min(res,g[x][i]),x=f[x][i];
	return res;
}
void dfs2(ll u,ll fa){
	if(u!=1){
		g[u][0]=sum[fa];
//		cout<<g[u][0]<<"\n";
		for(int i=1;i<=20;i++) g[u][i]=min(g[u][i-1],g[f[u][i-1]][i-1]);
		for(auto p : v[u]){
//			cout<<"("<<p.fi<<","<<p.se<<") ";
			p.fi=min(p.fi,dep[u]-1);
			sum[u]=min(sum[u],fin(u,dep[u]-p.fi)+p.se);
		}
//		cout<<fin(u,dep[u]-1)<<"\n";
	}
//	cout<<u<<" "<<sum[u]<<"\n";
	for(int i=head[u];i;i=e[i].next){
		ll v=e[i].v;
		if(v==fa) continue;
		dfs2(v,u);
	}
}
int main(){
//	freopen("match.in","r",stdin);
//	freopen("match.out","w",stdout);
	read(n),read(m),read(q);
	for(int i=1;i<n;i++){
		ll x,y;
		read(x),read(y);
		add(x,y),add(y,x);
	}
	for(int i=1;i<=m;i++){
		ll x,k,val;
		read(x),read(k),read(val);
		v[x].push_back({k,val});
	}
	for(int i=2;i<=n;i++){
		sum[i]=inf;
		for(int j=0;j<=20;j++) g[i][j]=inf;
	}
	dfs(1,0);
	dfs2(1,0);
	while(q--){
		ll x;
		read(x);
		write(sum[x]);
		putchar('\n');
	}
	return 0;
}
/*
7 7 3
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
5
6
7
*/

R41 T4

P3665 [USACO17OPEN] Switch Grass P

题意

给定一个 nn 个点 mm 条边的无向连通图，边有边权。每个点有初始颜色 cic_i。设 dis(i,j)dis(i,j) 表示点 ii 到 jj 的最短距离，现在给定 qq 次操作，每次操作更改一个点的颜色，操作是永久性的，求每次操作后满足 i,ji,j 颜色不同的 dis(i,j)dis(i,j) 的最小值。
1≤n,q≤2×105,1≤m≤4×1051\le n,q\le 2\times10^5,1\le m\le4\times10^5。

思路

数据结构硬搞。
首先注意到最终的答案一定是一条边，并且是最小生成树上的边。
如果不是最小生成树上的边，那么应该是一条非树边。而最小生成树上非树边两个端点的路径上任何一条边都不劣于这条非树边。如果这些树边都不能用，显然这个路径的点颜色都相同，那么这条非树边也是不可用的。
有了这个结论之后，我们考虑对每个点 xx 维护 xx 到它的直接儿子的边。具体地，我们对每个点都开一棵动态开点线段树，每个节点管理区间内的儿子的边的最小值 mimi、这个最小值对应的儿子的颜色 sese、以及和 sese 异色儿子的边的最小值 cmicmi、这个儿子的颜色 csecse。
对于一个点 uu，只需要判断它的颜色是否和整个区间的 sese 是否相同即可，如果相同它的贡献就是 cmicmi，否则就是 mimi。
那么在更改一个点的颜色时，只需要更新它的父亲的线段树、它的父亲的贡献以及它的贡献即可。两个单点修。
对于所有点的贡献的最小值，我们可以再开一棵线段树管理，那么每次更新贡献时直接在这棵线段树上单点修改即可。
复杂度 O((n+q)log⁡n)\Omicron((n+q)\log n)。

代码

CPP
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
#define L (p<<1)
#define R (p<<1|1)
#define ls (tr[p].Ls)
#define rs (tr[p].Rs)
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=2e5+10,inf=1e16;
ll n,m,K,f[N],fa[N],q,k[N],son[N],siz[N],esum[N];
struct edge{
	ll u,v,w;
}e[N];
bool cmp(edge a,edge b){
	return a.w<b.w;
}
vector<pll>v[N];
ll fin(ll x){
	return f[x]==x ? x : f[x]=fin(f[x]);
}
void krus(){
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		ll x=fin(e[i].u),y=fin(e[i].v);
		if(x!=y){
			f[x]=y;
			v[e[i].u].push_back({e[i].v,e[i].w});
			v[e[i].v].push_back({e[i].u,e[i].w});
		}
	}
}
ll sum[N<<2];
void pushup(ll p){
	sum[p]=min(sum[L],sum[R]);
}
void build(ll l,ll r,ll p){
	sum[p]=inf;
	if(l==r) return ;
	ll mid=l+r>>1;
	build(l,mid,L),build(mid+1,r,R);
	return ;
}
void admin(ll l,ll r,ll x,ll z,ll p){
	if(l==r){
		sum[p]=z;
		return ;
	}
	ll mid=l+r>>1;
	if(mid>=x) admin(l,mid,x,z,L);
	else admin(mid+1,r,x,z,R);
	pushup(p);
	return ;
}
struct tree{
	ll mi,se;
	ll cmi,cse;
	ll Ls,Rs;
}tr[N*20];
ll rt[N];
ll ip;
tree newnode(){
	return (tree){inf,0,inf,0,0,0};
}
void pup(ll p){
	if(tr[ls].mi<tr[rs].mi){
		tr[p].mi=tr[ls].mi,tr[p].se=tr[ls].se;
		tr[p].cmi=tr[ls].cmi,tr[p].cse=tr[ls].cse;
		if(tr[rs].se!=tr[p].se){
			if(tr[rs].mi<tr[p].cmi) tr[p].cmi=tr[rs].mi,tr[p].cse=tr[rs].se;
		}
		else if(tr[rs].cmi<tr[p].cmi) tr[p].cmi=tr[rs].cmi,tr[p].cse=tr[rs].cse;
	}
	else{
		tr[p].mi=tr[rs].mi,tr[p].se=tr[rs].se;
		tr[p].cmi=tr[rs].cmi,tr[p].cse=tr[rs].cse;
		if(tr[ls].se!=tr[p].se){
			if(tr[ls].mi<tr[p].cmi) tr[p].cmi=tr[ls].mi,tr[p].cse=tr[ls].se;
		}
		else if(tr[ls].cmi<tr[p].cmi) tr[p].cmi=tr[ls].cmi,tr[p].cse=tr[ls].cse;
	}
}
void add(ll l,ll r,ll x,ll z,ll s,ll &p){
	if(!p) p=++ip,tr[p]=newnode();
	if(l==r){
		tr[p].mi=z,tr[p].se=s;
		return ;
	}
	ll mid=l+r>>1;
	if(mid>=x) add(l,mid,x,z,s,ls);
	else add(mid+1,r,x,z,s,rs);
	pup(p);
	return ;
}
ll query(ll u){
	if(!rt[u]) return inf;
	return tr[rt[u]].se==k[u] ? tr[rt[u]].cmi : tr[rt[u]].mi;
}
void dfs(ll u,ll ff){
	fa[u]=ff;
	for(auto p : v[u]){
		if(p.fi==ff) continue;
		siz[u]++;
		son[p.fi]=siz[u];
		esum[p.fi]=p.se;
		dfs(p.fi,u);
	}
	for(auto p : v[u]){
		if(p.fi==ff) continue;
		add(1,siz[u],son[p.fi],p.se,k[p.fi],rt[u]);
	}
	ll val=query(u);
//	cout<<u<<" "<<val<<"\n";
	admin(1,n,u,val,1);
}
int main(){
//	freopen("war.in","r",stdin);
//	freopen("war.out","w",stdout);
	read(n),read(m),read(K),read(q);
	for(int i=1;i<=m;i++) read(e[i].u),read(e[i].v),read(e[i].w);
	for(int i=1;i<=n;i++) read(k[i]),f[i]=i;
//	cout<<"\n";
	krus();
	build(1,n,1);
	dfs(1,0);
	while(q--){
		ll x,c;
		read(x),read(c);
		if(k[x]==c){
			write(sum[1]);
			putchar('\n');
			continue;
		}
		k[x]=c;
		if(fa[x]){
			add(1,siz[fa[x]],son[x],esum[x],k[x],rt[fa[x]]);
			admin(1,n,fa[x],query(fa[x]),1);
		}
		admin(1,n,x,query(x),1);
		write(sum[1]);
		putchar('\n');
	}
	return 0;
}
/*
3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2

更新后的情况一定是有两个点经过一条边搞定 

建一棵最小生成树

考虑边上更新

那么我们就有了 O(qn) 暴力

接着我们发现这无法优化

考虑更新 "点"

那么每个点维护一个边集

同色不管。 

假设更新 u，考虑 u<->v 

u 更新所有与其相连的同色 v 

维护一个可删堆，可以用 multiset 做 

这样是 O(qn\log n) 的卡不满，有40 

然后我们发现实际上是更新 "1" 邻域的点

考虑更新父亲与直接儿子

父亲的更新是 O(1*logn) 的，可以直接做

然后我们考虑用 bfs 序做

考虑管理覆盖段

考虑维护两个值，一个是 x->fa(x) 的总最小值，一个是 x->son(x) 的总最小值

额好像有点难搞，好像要线段树？

考虑色变化时的影响

考虑维护一个祖先树和一个儿子树

对于儿子树，我们考虑对每个节点维护一个最小值和异色最小值，修改 x 时有一个单点修改和直接查询 

对于父亲树，我们考虑 bfs 序的线段树

怎么维护呢？

哎等等真的要用父亲树吗

实则不然哎

好像直接更新就行了

那么我们不维护父亲的值？

可以的，我们对每个点开一个动态开点线段树，用于更新这个点的值

再开一棵线段树用于管理整体值

于是我们每次的操作就变为了一次单点修改，一次直接查询，一次单点修改，一次直接查询答案

然后没了 
*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...