ZJOI2017 R1总结

先上了两天的课,主要以讲题为主。

考试大巴好像翻车了,我们学校的人\(7\)点半到考场,\(8\)点我们考场总共只来了\(4\)个人,其他人还都是走路/打车来的。\(8\)点\(45\)人才陆续到齐开考。

打开题面:

T1仙人掌什么鬼啊弃疗。。

T2好像可以搞一搞?

T3多项式+字符串好可怕啊不会做只会\(10\)分暴力

于是开始大力推导T2。

意会了一下写错的树状数组相当于前缀修改和两点查询,把他的代码蒯下来随便试了试感觉很对。看了下部分分有个\(30\)分\(n\le 50\),感觉很暴力呀。记录\(f_{i}\)为每个位置最终为\(1\)的概率直接算就可以了?

然后WA on 样例。

于是换了个想法。令\(a\)表示写对的树状数组的前缀和为\(1\)的概率,\(b\)表示写错的树状数组的前缀和为\(1\)的概率,比较两段似乎就不会有问题了。

算是过了样例。想测一发大样例。打开文件夹一看

cactus/cactus.in cactus.out
bit/
poly/poly.in poly.out

不会这题没大样例吧

于是手造了几组数据。。貌似又WA了

仔细想了想好像概率不独立?

于是直接考虑每次修改对于每种询问的影响:

令\(ans\)为两个树状数组查询结果的异或值,那么\(ans=0\)表示正确,否则为错误。

如果修改了位置\(p\),那么正确的树状数组中\([p,n]\)的值会异或\(1\),错误的树状数组中\([1,p]\)的值会异或\(1\)。

那么如果一个询问的端点不在\(p\)上\(ans\)是不会变的。

那么如果一个长度为\(len\)的修改包含了某个询问的一个端点,那么这个询问的\(ans\)就有\(\frac{1}{len}\)的概率变化。

如果一个长度为\(len\)的修改包含了某个询问的两个端点,那么这个询问的\(ans\)就有\(\frac{2}{len}\)的概率变化。

那么就是一些线段的问题了。统计每个修改对每个询问的贡献即可。

先写了个\(n^2\)暴力,手构的数据貌似跑得挺对。如果没错就拿到\(50\)分了?

看了看时间,妈呀怎么只有两个多小时了。

再去看一眼T3貌似还是只会\(10\)分,快速幂FFT似乎也过不了\(30\)。

T1没什么想法。。好像T2离正解也没差多少了接着写吧。

考虑一下用树状数组优化?发现需要减掉一些区间的答案,那么需要贡献的逆过程。

贡献:\(apply(x,y)=x(1-y)+y(1-x)=x+y-2xy\)

逆贡献:\(bpply(x,y)=\frac{x-y}{1-2y}\)

于是写了个cdq+树状数组。

写完拍一拍发现WA了。。发现\(apply\)完\(bpply\)回去居然值不一样了。。难道不能求逆。。那不是gg了。。

仔细看了一下,貌似\(y=\frac{1}{2}\)。。求逆的时候就挂了。。

于是再分析了一下这个\(apply\)的性质:

满足交换律
满足结合律
满足分配律
存在逆元
具有封闭性

好优美啊

不对我在做什么。。明明是要分析\(\frac{1}{2}\)

发现\(apply(x,\frac{1}{2})=x+\frac{1}{2}-x=\frac{1}{2}\)

并且由于交换律,只要有\(\frac{1}{2}\)对某个询问产生了贡献那么这个询问的答案就是\(\frac{1}{2}\)了

于是先把所有长度为\(2\)的修改提出来处理一下就好了

终于拍不WA之后看了看时间。。只有半个多小时了

赶快T3暴力写起。。\(10\)分还是不难写的。。测了点数据感觉不会T

接着赶快T1暴力写起

枚举完加的边发现还要判是不是个仙人掌。。只剩不到\(5\)分钟了感觉没什么戏弃疗了

出来问王队长:

“怎么T2没有大样例啊?”
“啊?有的啊。你需要再解压一遍。我第一次解压出来什么都没有。”

然后听说XPZ也是第一遍解压少了东西。。这个解压软件怎么这么鬼畜啊。。。

然后听说伦和YMD都会做T2。。开口就是

“二维线段树”
“当\(l=1\)时balabala,当\(l\ne 1\)时balabala”

都过了大样例。。感觉我的是个萎的啊。。那我要爆零了啊。。

上飞机之前听说有题解了赶快下下来看一下

看到这句话兴奋透了 我的做法可能是正解呀

但是没试大样例还是虚的一B啊

AC还是爆零就看脸了吧。。幸好不是浙江人,没有利益相关

 

upd:果然还是爆零了呀。。

又仔细想了一下

此处

那么如果一个询问的端点不在\(p\)上\(ans\)是不会变的。

还是有点问题

应该是

如果一个询问的端点同时在或同时不在\(0\)和\(p\)上\(ans\)是不会变的。

也就是说,如果一个询问有一个端点在\(0\)上,那么应将条件改成有\(1-\frac{1}{len}\)的概率变化。

听说他们都是大样例看出的这个问题。。

辣鸡解压软件毁我青春。。吃我大样例。。

 

不过还是挺开心的 毕竟是来学习的又不是来进队的

发现能在考场上想出一道ZJOI的题 还是挺愉快的

HNOI加油233

说点什么

1 评论 在 "ZJOI2017 R1总结"

提醒
排序:   最新 | 最旧 | 得票最多
成员

前排Orz

wpDiscuz