• 周二. 7 月 16th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

ST03模拟赛#1 比赛记录

admin

11 月 28, 2021

ST03模拟赛#1 比赛记录

终于不是vp了

比赛情况

赛时:(0)

赛后:T1

题解

T1

点分治垃圾题,然而我想了一个傻逼做法,所以应该我是傻逼

首先是人都能看出来点分治,然后每个点处理一个 pair<int,int> 表示它到根的最大,严格次大。

然后是计算子树里经过根的答案。

如果暴力维护当前选好的点,然后加入一个子树合并一下,这样写,保准他妈写死你。

然而我只会这一种做法,是我太simple了。于是我就写了怎么想都不太能写出来的,点分+BIT+SGT。

这题的话,我们用瞎几把算+去重的写法,更加合适。对于瞎几把算的部分,我们不妨排个序。维护尼玛的线段树啊先排个序啊喂

然后就是枚举一个位置算一下它跟前面组合一下的答案。设当前是 ((A_1,A_2)),表示这个pair。

对于前面的一个 ((B_1,B_2)),如果:

(B_1le A_2),这一部分的pair显然是 ((A_1,A_2))。对答案的贡献是 (A_1 imes A_2 imes #)

(A_2<B_1< A_1),这一部分的pair是 ((A_1,B_1))。对答案的贡献是 (A_1 imessum B_1)

(B_1=A_1),这一部分我们讨论一下 (B_2) 的大小,用树状数组维护

然后,加子树,加子树,去重,诶,做完了,简单吧,除了我应该都会qaq

实况

上来先把3题都看了一遍。T3是神秘题,不会;T2是一个我怎么也看不出来是分块的分块;T1是我一眼就看出来的点分治。

然后我就去主攻T1。

做一做发现要讨论4个情况。啪啪啪打完发现不对,因为要讨论6个情况。

我接着搞,发现了剩下两个情况。原来的 (4) 个用树状数组写一下就行,新来了俩我还不会做了还。仔细的想一想,我得到了一个动态开点线段树做法。虽然怎么想它好像都不太对,不应该有这么大码量;但是我没有办法,只能这么写了

然后我就硬是写+调了这么一个点分治+大讨论+BIT+动态开点线段树。码长7.7KB,我靠我 高 超 的码力,终于,在距离比赛结束40s的时候,调过了样例。

删掉调试输出,剩2s

ctrl+c,进入提交界面,ctrl+v,剩1s

划鼠标到“提交”键,剩0s

于是我没交上去,比赛就结束了,我喜提0分的好成绩,rating有了200多的变化量,当然,是负的

总结

  • 对于这种难度很大,时间很短的比赛,先去打部分分
  • 对于码量明显很大的题,适当放弃

发表回复