真的是最后一天了,反而没有之前向外离开的那么高兴……
新交的一个朋友 lcj ,有缘千里相见!
Part1. 游记
“最后一天了,今天的模拟赛一定要好好打!”因为是最后一天了,大清早起来就像打了鸡血……我也不知道为什么……
模拟赛上也拼尽全力,AC 了一道题,而且 $O(N)$ 踩标算(ヽ(=^・ω・^=)丿),这一点没留遗憾(tl 6666,比我多5分爆踩我)。打完这最后一场模拟赛,虽然打的不错,有一种快感,但是总有一种意犹未尽的感觉,似乎之后少了这么高强度的模拟赛训练会不习惯(似乎立了一个什么惊人的 flag)……
下午跟着家长去参观了孙中山纪念馆,竟然就在学校旁边,来纪中的时候注意到了旁边有一座特别大的园,但是不知道这就是孙中山纪念馆。
因为我们是中午去参观的,人不算多,每一件实物都有机会近距离观摩(???什么玩意,输入法自己跳出来的)。然后非常尴尬的是一开始并没有注意到“No photo”,拍了几张,后面 tly 注意到提醒了我,然后我就默默的把手机收了下去 (@w@)。但是更加尴尬的是,发现许多游客根本没有注意到禁止拍照的标志,一直在合影、拍照,或许博物馆应该把标识牌放到显眼一点的地方……
反正是各种参观,顺便对应一下历史书上学到的知识点(和其他同学一起 match 历史书上的图片还挺有意思的)。
参观完纪念馆就去参观故居,反差有一点大,纪念馆里红毯、石雕、锦旗装点,而故居里徒有灶台、没有任何雕刻的木桌(然后印象最深刻的)是一个非常小的浴盆(???)仿佛仍有当年简朴之地出贤才的灵气。
最后一点小插曲,出纪念馆的时候看到旁边一棵乔木,标识牌写着“芒果树”,一群人震惊了——
- “woc 这就是芒果树!!”
- “吃了这么多年芒果才知道芒果长树上的……”
- “这芒果树这么高怎么摘啊?”
没办法,身处内地见识太少了(改革开放的伟大决策,???反正重庆也正在走向开放进步嘛)
领略了一番民国历史,也不枉此行。
下午回去听课(好惨啊),上讲台上讲了一发 $O(n)$ 做法,非常开心的装了一逼(口吐莲花)结果第三题没有听懂,现在都还没改出来,之后估计也没有机会改了(大概意思就是今天的 T3 题解咕了)。然后下午就把 T1 改对了,然后一直弄 T3 没弄出来,一下午就没了 QwQ
下午放学后就放假了……我那个新疆远到而来的朋友准备去广州参加 B站 的漫展,我也好想去啊!!然而当然是没有机会的,明天清早就要走了。
- “有缘再见!”
- “这就真的是有缘再见了!bye~”
那么 罗传杰,一个看起来健硕高大乍一眼以为比我年级大结果实际上只有初二的 OIer,祝你漫展愉快~ 反正出外省游学的机会还很多,说不定哪一次又会在游学的时候碰到呢?剩下的就真的是“有缘千里相见”了……ヾ( ̄▽ ̄)Bye~Bye~
然后现在写游记的时候是晚上了,反正已经放假了,然后一群人在机房里颓废放松,然后我就捞了一套 CF Div3 的题刷水(好久没有做这么简单的题了好开心啊 ♪(^∀^●)ノ)今天晚上准备好“文娱节目”了,希望宿管能稍微宽松一点吧……
这篇游记写完了,不过不知道写完这篇游记之后会不会有一些值得写进去的东西……反正记得就写吧(然后就忘了)
Part2. Solution
少了一道 T3 写题解瞬间简单了好多
今天题目质量很高
T1. 投票(vote)
[Experience]
一开始真的犯蠢……想到一个后效性明显的 DP,然后以为想到了正解,写完过后测样例发现锅了……QwQ调试发现 DP 有后效性,还没法改正……
没办法,时间早就超过预期了,就把 T1 跳了看 T2……
最后只好骗了 50 的部分分(话说为什么实际上可以有 70 分啊???然而我真的就只判断了数据规模在 $50\%$ 内才计算,现在想好像不太 OK)
[Solution]
首先这是一道结论题,然后结论不知道怎么证明,似乎可以感性理解、打表证明一下。
结论就是:把所有人按 $p_i$ 从小到大排序,则选取的人一定是最前面和最后面的一些。比如将所有人排序后,每个人的编号为 $\{1,2,3,4,5,6,7,8\}$,我们可能选择 $\{1,2,3\}$ 、$\{5,6,7,8\}$,或是 $\{1,2,6,7,8\}$,但是不可能选择 $\{2,3,7\}$、$\{1,2,4\}$ 等等……
所以我们可以考虑 DP —— 先将所有人按 $p_i$ 排序f[i][j]
表示选择 1
到 i
的所有人,有 j
个人投“好”的概率;g[i][j]
表示选择 i
到 n
的所有人,有 j
个人投“好”的概率;
拿 f[i][j]
的状态转移举例(因为 g[i][j]
的转移是基本类似的):
考虑第 i
个人是否投了“好”,若是,则对概率的贡献为 p[i]*f[i-1][j-1]
;否则贡献为 (1-p[i])*f[i-1][j]
。所以 f[i][j]=p[i]*f[i-1][j-1]+(1-p[i])*f[i-1][j]
。
然后枚举选择了第 1
到 i
的所有人和 m-i+1
到 m
的所有人(加起来恰好 m 个人);再枚举第 1
到 i
的所有人中有 j
个投了“好”,则第 m-i+1
到 m
的所有人投了 m/2-j
个“好”。也就是说选择前 i
个人和后 m-i
个人,投了 m/2
个 “好” 的概率为:
对于每一个 i
取 max
即可。
[Source]
1 | /*Lucky_Glass*/ |
T2. 动态数点 (point)
A了A了(
“噫好了!我AC了!”)
[Experience]
因为决心最后一次要好好打,就决定一定要想出一道题的正解。
发现这道题的思路非常清晰,就试着写了一发,然后一测样例……(oh)又调试了二十几分钟,然后发现自己的标记数组没清空(没脸见人了)
改了之后,发现自己写了一个非常非常优秀的 $O(n)$ 算法,愉快 AC。
Tab. 赛后发现其实我写的是一个 $O(n\log n)$ 算法,因为我最后对答案排了一个序……其实主要是我偷懒,只要换种输出答案的方式就不必要排序了。
因为这是我自己想出来的做法,我一定要多写一点!
[Solution]
= 方法
考虑对每一个点 i
储存 lef[i]
和 rig[i]
,表示 lef[i]
到 rig[i]
的所有数都被 a[i]
整除。(In fact,并不是每个 i
都会计算 lef[i]
和 rig[i]
,这是一个优化,有了这个优化,算法能变为 $O(n)$,之后解释)
那么我们可以从左到右枚举 i
,计算 rig[i]
。从 rig[i]=i
开始暴力尝试向右扩展 rig[i]
—— 如果下一个数字仍然可以被 a[i]
整除,则将 rig[i]++
,并且把新扩展到的那一个点打上一个标记:vistag[rig[i]]=i
。
然后我们把 i++
。如果 vistag[i]
有值,则查看 a[i]
是否等于 a[vistag[i]]
,如果等于,则 rig[i]=rig[vistag[i]]
,然后 continue,否则直接 continue。
以上是 rig[]
的计算,lef[]
只是把 i
改成从右到左枚举而已。
求出 lef[],rig[]
后,我们枚举 i
,则对应的区间就是 lef[i]
到 rig[i]
,找到最长的几个区间,然后储存到答案里面即可(因为最长区间的长度都是一样的,只要从左到右找区间,储存的答案就是从左到右有序的)
= 举例
比如 a[]={2,4,2,8,6,3,9}
;
i=1
,扩展rig[i]
到4
,vistag[1~4]=1
;i=2
,vistag[2]
有值,且a[2]!=a[vistag[2]]
,直接 continue;i=3
,vistag[3]
有值,且a[3]==a[vistag[3]]
,rig[3]=rig[vistag[3]]
,即rig[3]=4
,然后 continue;i=4
,vistag[4]
有值,且a[4]!=a[vistag[4]]
,直接 continue;i=5
,发现rig[5]
不能扩展,rig[5]=5
,vistag[5]=5
;i=6
,rig[6]
扩展到7
,vistag[6~7]=6
;i=7
,vistag[7]
有值,且a[7]!=a[vistag[7]]
,直接 continue;- 清空
vistag[]
!!!(emm……)
那么我们最后得到的 rig[]={4,0,4,0,5,7,0}
。
那么 lef[]
就留给 reader 们试试计算了,如果你算出来 lef[]={1,0,1,4,0,5,7}
,那就 OK 了,你应该已经理解了这种做法。
= 证明
首先时间复杂度显然 $O(n)$,每个点只会被计算一次。
然后我们来证明 —— “vistag
有值的点不用再暴力计算(即continue掉)”,仍然拿 rig[]
来证明。
设
j=vistag[i]
,那么j
到rig[j]
的所有数都会被a[j]
整除,且a[rig[j]+1]
不会被a[j]
整除。那么可以证明,如果计算
rig[i]
,则有rig[i]<=rig[j]
,因为a[i]
是a[j]
倍数,则a[rig[j]+1]
也不会被a[i]
整除,所以rig[i]
最大也只能达到rig[j]
。以上证明了
rig[i]<=rig[j]
因为
a[i]
被a[j]
整除,则显然a[i]>=a[j]
。
- 当
a[i]>a[j]
时,则a[i]
不整除a[j]
,那么lef[i]>j
,而lef[j]<=j
,所以lef[j]<lef[i]
。此时存在lef[j]<lef[i]<=rig[i]<=rig[j]
,显然lef[i]
到rig[i]
这个区间并不优,所以不必要计算。- 当
a[i]==a[j]
时,不难证明lef[i]==lef[j]
且rig[i]==rig[j]
,所以直接让rig[i]=rig[j]
即可。
综上,这是一个正确的 $O(n)$ 算法。
[Source]
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com,欢迎提问!