专栏文章

题解：P13276 [NOI2025] 绝对防御

sstrapplE
P13276题解参与者 18已保存评论 20

文章操作

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

当前评论
20 条
当前快照
1 份
快照标识符
@miou6ssq
此快照首次捕获于
2025/12/03 01:13
3 个月前
此快照最后确认于
2025/12/03 01:13
3 个月前
查看原文
题解文字部分很长，知道大家不喜欢看，因此每一段我都会写下省流，有些部分你可以略读。
给一个（我场上胡的）单点修改线段树二分做法。时间复杂度与题目中的参数 33 无关（即改成任何数都一样），预处理线性，修改单 log⁡\log，求答案单 log⁡\log，因此总复杂度 O(n+qlog⁡n)O(n+q\log n)。
省流：给个比较优秀的做法，让大家见笑了。
先考虑一些暴力的做法。大部分人第一个想到的正确做法应该是二分答案再暴力 dp check。直接做是 O(qn2log⁡n)O(qn^2\log n) 的，可以 bitset 优化但对正解没啥意义。有不少选手注意到了存在的连续段这个性质，可以获得 35∼4035\sim 40 pts。再往下就没有前途了，而我赛时可能代码能力不太够没写明白，干脆放弃了这个做法，去想下面的内容了。
省流：有一些暴力做法，不一定都对正解有帮助，所以我们接下来要取其精华。
首先保留刚才的二分结构，现在你二分到了 kk，要判断其是否合法。我们先刻画出抽卡的结构。初始有 $$每一轮你可以摸 1∼21\sim 2 张牌，并打出一场攻击牌，一张防御牌或两张攻击牌。只有最后一次可能只摸 11 张，所以在每次摸牌前，你手里都必然有 kk 张牌。
我们称每轮摸牌为一个回合，你需要挺过 tt 个回合，其中前至少 t−1t-1 个回合都是摸两牌。
省流：避免题目太玄幻，我们要用数学语言刻画下。
接下来，我们来定义几个数组变量：
ai,bia_i,b_i 分别表示第 ii 回合将摸到多少张攻击牌/防御牌，di=ai+bi,li=1−bi,ri=ai−1d_i=a_i+b_i,l_i=1-b_i,r_i=a_i-1。Li,RiL_i,R_i 分别为 li,ril_i,r_i 的前缀和。根据这些定义你应该能看出，∀i<t,di=2,li=ri,Li=Ri\forall i<t,d_i=2,l_i=r_i,L_i=R_i。以及为了体现做法对于技能冷却时间的普遍性，设 z=3z=3。
设初始时的 kk 张牌中有 hh 张防御牌，则你能活下来，当且仅当存在一个序列 c1∼tc_{1\sim t} 表示每回合是否发动技能，满足：
  • ∀1≤i≤t,ci∈{0,1}\forall 1\leq i\leq t,c_i\in \{0,1\}
  • ∀1≤i≤t,h+(b1−1+c1)+(b2−1+c2)+⋯+(bi−1+ci)≥0\forall 1\leq i\leq t,h+(b_1-1+c_1)+(b_2-1+c_2)+\dots+(b_i-1+c_i)\geq 0
  • ∀1≤i≤t,k−h+(a1−1−c1)+(a2−1−c2)+⋯+(ai−1−ci)≥0\forall 1\leq i\leq t,k-h+(a_1-1-c_1)+(a_2-1-c_2)+\dots+(a_i-1-c_i)\geq 0
  • ∀1≤x≤y≤t,y−x<z,cx+⋯+cy≤1\forall 1\leq x\leq y\leq t,y-x<z,c_x+\dots+c_y\leq 1
省流：刻画完毕。
接下来我们稍微做做变形，设 si=c1+⋯+cis_i=c_1+\dots+c_i。不难证明，cic_i 不会取到浮点数，下面我们只去刻画其上下界。四个条件可以分别这样改写：
  • ∀1≤i≤t,0≤si−si−1≤1\forall 1\leq i\leq t,0\leq s_i-s_{i-1}\leq 1
  • ∀1≤i≤t,h−l1−⋯−li+si−s0≥0\forall 1\leq i\leq t,h-l_1-\dots-l_i+s_i-s_0\geq 0
  • ∀1≤i≤t,k−h+r1+⋯+ri−si+s0≥0\forall 1\leq i\leq t,k-h+r_1+\dots+r_i-s_i+s_0\geq 0
  • ∀0≤x<y≤t,y−x≤z,sy−sx≤1\forall 0\leq x<y\leq t,y-x\leq z,s_y-s_x\leq 1
省流：我们已经可以转成前缀和的差分约束限制了，因为只要判无解，所以找负环即可。
建出 t+1t+1 个结点的图，则去除第一条和第四条限制的重复部分后，只剩了如下几种边：
  • ∀1≤i≤t,i→0i−1\forall 1\leq i\leq t,i\xrightarrow{0}i-1
  • ∀1≤i≤t,i→h−Li0\forall 1\leq i\leq t,i\xrightarrow{h-L_i}0
  • ∀1≤i≤t,0→k−h+Rii\forall 1\leq i\leq t,0\xrightarrow{k-h+R_i}i
  • ∀0≤x<y≤t,y−x≤z,x→1y\forall 0\leq x<y\leq t,y-x\leq z,x\xrightarrow{1}y
称这四种边分别为一二三四类边。那么因为一四类边一定非负，不能只通过这类边搞出负环，所以一定要经过一次二三类边，因此一定要经过至少一次 00 号点。而我们只在意简单负环，也就是经过 00 号点恰好一次的环。
把二三类边经过的点记作关键点，则一四类边的作用是连接关键点，具体地，我们设 dist⁡(x,y)\operatorname{dist}(x,y) 表示从 xx 只经过一四类边到达 yy 的最短路，则有： dist⁡(x,y)=max⁡(0,⌈y−xz⌉)\operatorname{dist}(x,y)=\max(0,\lceil\dfrac{y-x}{z}\rceil)
接下来我们根据是否经过二三类边，把环分为三类，则限制有如下几类：
  • 只经过二类边：dist⁡(0,x)+h−Lx≥0\operatorname{dist}(0,x)+h-L_x\geq 0
  • 只经过三类边：k−h+Ry+dist⁡(y,0)≥0k-h+R_y+\operatorname{dist}(y,0)\geq 0
  • 都经过：k−h+Ry+dist⁡(y,x)+h−Lx≥0k-h+R_y+\operatorname{dist}(y,x)+h-L_x\geq 0
省流：成功得到极其好写的 O(qn2log⁡n)O(qn^2\log n) 做法，前缀和优化就能得到小常数 O(qnlog⁡n)O(qn\log n) 的 40pts 了，而且很有前途！
再做变形，dist⁡(x,y)=⌊max⁡(0,y−x+z−1)z⌋\operatorname{dist}(x,y)=\lfloor\dfrac{\max(0,y-x+z-1)}{z}\rfloor，于是又能改写：
  • ∀1≤x≤t,x+z−1+z(h−Lx)≥0\forall 1\leq x\leq t,x+z-1+z(h-L_x)\geq 0
  • ∀1≤y≤t,k−h+Ry≥0\forall 1\leq y\leq t,k-h+R_y\geq 0
  • ∀1≤x<y≤t,k+Ry−Lx≥0\forall 1\leq x<y\leq t,k+R_y-L_x\geq 0
  • ∀1≤y<x≤t,z(k+Ry−Lx)+x−y+z−1≥0\forall 1\leq y<x\leq t,z(k+R_y-L_x)+x-y+z-1\geq 0
到这里已经很接近正解了，不过我们还有一些遗留问题。也就是说，我们每次二分一个 kk 都要重新分回合，要维护的回合数量（也就是 tt 的总和）是 O(n2)O(n^2) 的，不就爆炸了吗？
此时你会注意到，阶段（即回合）本质不同只可能 kk 的奇偶性不同，因此你只需要分两类，奇数开头还是偶数开头。
具体地，如果 nn 是偶数，那么奇数开头的 dd 序列为 122…221122\dots221，偶数为 22…2222\dots22。nn 是奇数的话，奇数开头为 122…22122\dots22，偶数开头为 22…22122\dots221。
则二分的一个 kk 代表的是，已经完成了前面的一些阶段，你要用线段树维护一段后缀的信息。
省流：你要根据 kk 的奇偶性开两棵线段树，里面完全一样，所以只需要用结构体实现其中一个。下面讲线段树维护的具体细节，然后这个题就被成功解决了。
如果一起维护的话，开头位置就不是 00 了，设为 mm 吧，则限制条件等价于。
  • ∀m<x≤t,z⋅h≥−z+1+∑i=m+1x(z⋅li−1)\forall m<x\leq t,z\cdot h\geq -z+1+\sum\limits_{i=m+1}^{x}(z\cdot l_i-1)
  • ∀m<y≤t,z⋅(k−h)≥−z+1+∑i=y+1m(−z⋅ri)\forall m<y\leq t,z\cdot(k-h)\geq -z+1+\sum\limits_{i=y+1}^{m}(-z\cdot r_i)
  • ∀m<x<y≤t,z(k+(Ry−Rm)−(Lx−Lm))≥−z+1\forall m<x<y\leq t,z(k+(R_y-R_m)-(L_x-L_m))\geq -z+1
  • ∀m<y<x≤t,z(k+(Ry−Rm)−(Lx−Lm))+x−y≥−z+1\forall m<y<x\leq t,z(k+(R_y-R_m)-(L_x-L_m))+x-y\geq -z+1
第三四条，根据我们很早就提到的性质分别有：
  • Lx−Lm=Rx−RmL_x-L_m=R_x-R_m
  • Ry−Rm=Ly−LmR_y-R_m=L_y-L_m
因此可以分别改写为：
  • ∀m<x<y≤t,z(k+Ry−Rx)≥−z+1\forall m<x<y\leq t,z(k+R_y-R_x)\geq -z+1
  • ∀m<y<x≤t,z(k+Ly−Lx)+x−y≥−z+1\forall m<y<x\leq t,z(k+L_y-L_x)+x-y\geq -z+1
因此四个条件也就是：
  • ∀m<x≤t,z⋅h≥−z+1+∑i=m+1x(z⋅li−1)\forall m<x\leq t,z\cdot h\geq -z+1+\sum\limits_{i=m+1}^{x}(z\cdot l_i-1)
  • ∀m<x≤t,z⋅(k−h)≥−z+1+∑i=x+1m(−z⋅ri)\forall m<x\leq t,z\cdot(k-h)\geq -z+1+\sum\limits_{i=x+1}^{m}(-z\cdot r_i)
  • ∀m<x<y≤t,z⋅k≥−z+1+∑i=x+1y(−z⋅ri)\forall m<x<y\leq t,z\cdot k\geq -z+1+\sum\limits_{i=x+1}^{y}(-z\cdot r_i)
  • ∀m<x<y≤t,z⋅k≥−z+1+∑i=x+1y(z⋅li−1)\forall m<x<y\leq t,z\cdot k\geq -z+1+\sum\limits_{i=x+1}^{y}(z\cdot l_i-1)
省流：发现这个条件很像最大子段和状物，因此你类似小白逛公园地，单点修改并分别维护每个节点 (z⋅li−1)(z\cdot l_i-1) 和 (−z⋅ri)(-z\cdot r_i) 的和、最大前后缀和、最大子段和共八个变量即可。
每次二分 kk，用树状数组算出 hh，线段树查询后缀可以做到 O(n+qlog⁡2n)O(n+q\log^2 n)。我考场就写的这玩意，在 selfEval 上最大点 1.6s1.6s，感觉稳了，没再优化下去。
赛后重新写了一遍，发现其实可以直接线段树二分，因为信息的可加性很强，也显然有二分性。树状数组省去了，代码极短，加上我的快读板子也只有 2.7K2.7K，下面是我的代码：
CPP
#include<bits/stdc++.h>
using namespace std;
namespace file_read{
	char ib[1<<25],*ip1=ib,*ip2=ib;
	inline char gc(){
		return ((ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin))),ip1==ip2?EOF:*ip1++);
	}
	inline int read(){
		int x=0;char c=gc();
		while(c<'0'||c>'9')c=gc();
		while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^'0'),c=gc();
		return x;
	}
	char ob[1<<25],*op=ob;
	inline void pc(char c){
		*op++=c;
	}
	void write(int x){
		if(x>=10)write(x/10);
		pc(x%10+'0');
	}
	void final_write(){
		fwrite(ob,op-ob,1,stdout);
	}
}
using namespace file_read;
int cc,T,n,q,s[400005];
struct pear{
	int hl,hr,h;
	int qdr,hdr;
	int mx1,mx2;
	int qdl,hdl;
}pp;
pear operator+(pear a,pear b){
	pear c;
	c.hl=a.hl+b.hl,c.hr=a.hr+b.hr,c.h=a.h+b.h;
	c.hdr=max(b.hdr,a.hdr+b.hr);c.qdr=max(a.qdr,a.hr+b.qdr);
	c.mx2=max(max(a.mx2,b.mx2),a.hdr+b.qdr);
	c.hdl=max(b.hdl,a.hdl+b.hl);c.qdl=max(a.qdl,a.hl+b.qdl);
	c.mx1=max(max(a.mx1,b.mx1),a.hdl+b.qdl);
	return c;
}
struct apple{
	int t,L[100005],R[100005],K[100005];
	void jjj(int l,int r){
		int b=s[l]+(l<r&&s[r]),a=r-l+1-b;
		++t;L[t]=1-b,R[t]=a-1;K[t]=r;
	}
	pear sm[400005];
	void build(int l,int r,int o){
		if(l==r){
			sm[o].hl=3*L[l]-1,sm[o].hr=-3*R[l],sm[o].h=1-L[l];
			sm[o].qdr=sm[o].hr,sm[o].qdl=sm[o].hl;
			sm[o].hdr=max(0,sm[o].hr),sm[o].hdl=max(0,sm[o].hl);
			sm[o].mx1=sm[o].mx2=-1e9;
			return;
		}
		int mid=(l+r)>>1;
		build(l,mid,o<<1);build(mid+1,r,o<<1|1);
		sm[o]=sm[o<<1]+sm[o<<1|1];
	}
	void add(int l,int r,int o,int x){
		if(l==r){
			sm[o].hl=3*L[l]-1,sm[o].hr=-3*R[l],sm[o].h=1-L[l];
			sm[o].qdr=sm[o].hr,sm[o].qdl=sm[o].hl;
			sm[o].hdr=max(0,sm[o].hr),sm[o].hdl=max(0,sm[o].hl);
			return;
		}
		int mid=(l+r)>>1;
		if(x<=mid)add(l,mid,o<<1,x);
		else add(mid+1,r,o<<1|1,x);
		sm[o]=sm[o<<1]+sm[o<<1|1];
	}
	void jia(int x,int y){
		L[x]-=y;R[x]-=y;add(1,t,1,x);
	}
	void init(int a){
		t=0;jjj(1,a);
		for(int i=a+1,j;i<=n;j=min(n,i+1),jjj(i,j),i=j+1);
		build(1,t,1);
	}
	int query(int l,int r,int o){
		if(l==r)return K[l];
		pear qq=sm[o<<1|1]+pp;
		int mid=(l+r)>>1,k=K[mid],h=sm[1].h-qq.h;
		if(3*k<max(qq.mx1,qq.mx2)-2||3*h<qq.qdl-2||3*(k-h)<qq.qdr-2)
			return query(mid+1,r,o<<1|1);
		pp=qq;return query(l,mid,o<<1);
	}
	int suan(){
		pp.mx1=pp.mx2=-1e9;
		pp.hdl=pp.hdr=0;pp.qdl=pp.qdr=-1e9;
		pp.hl=pp.hr=pp.h=0;
		return query(1,t,1);
	}
}e0,e1;
void solve(){
	write(min(e0.suan(),e1.suan()));
}
int main(){
	cc=read(),T=read();
	while(T--){
		n=read(),q=read();
		for(int i=1;i<=n;++i){
			char c2=gc();
			while(c2<'0'||c2>'9')c2=gc();
			s[i]=c2-'0';
		}
		e0.init(2);e1.init(1);solve();
		while(q--){
			int x=read(),aa=(s[x]^1)-s[x];s[x]^=1;
			e0.jia((x+1)/2,aa);e1.jia(x/2+1,aa);
			pc(' ');solve();
		}
		pc('\n');
	}
	final_write();
	return 0;
}
省流：这题做完了。
接下来考虑加强，从几个方向考虑：
  • 33 显然可以改成任何数，一点区别都没有。
  • 复杂度是单 log⁡\log 的，因此可以加强到 ∑n≤5×106,∑q≤1×106\sum n\leq 5\times 10^6,\sum q\leq 1\times 10^6。
  • 单点修改改为区间修改，应该存在一些分块做法。
作者码字不易，花费很多心血，留个赞再走吧，谢谢！有错误请尽情指出，感激不尽！

评论

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

正在加载评论...