社区讨论

O(n log^3 V) 做法卡常技巧

潘潘德理2010
P14522【MX-S11-T3】空之碎物参与者 19已保存回复 21

讨论操作

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

当前回复
21 条
当前快照
1 份
快照标识符
@mi8bape2
此快照首次捕获于
2025/11/21 11:39
3 个月前
此快照最后确认于
2025/11/21 13:34
3 个月前
查看原帖
加上这两行，实测快到飞起，最大点不超过 300ms，比同学写的少一只 log⁡\log 的做法还快。
含义：
  • 当前枚举第一个数 xx 时，答案最大为 axa_x。超过了就不用继续枚举。
  • 当前枚举区间 [i,j][i,j] 时，答案最大为 a[i...j]a[i...j] 的 max⁡\max。如果当前答案已经取到 max⁡\max 那么不用继续枚举。
简单想一下就知道这东西带来的优化作用是较大的且不太能被卡。反观双 log⁡\log 做法，需要写一大串较为复杂的东西（相当于以增大常数的代价）来优化掉一个 log⁡\log。
CPP
			for(int x=i;x<=j;x++){
				for(int y=i;y<=j;y++){
					if(res>=a[x]) break;
					if(x==y) continue;
					int w=a[x]&(~(a[y]&ca(h,x-i+1,y-i+1,j-i+1)));
					res=max(res,w);
				}
				if(res==mx) break;
			}

回复

共 21 条回复，欢迎继续交流。

正在加载回复...