由于NOI2016考前刷题记（上）写太多了，重新开了个blog。

UNR1滚粗记

就要NOI了，在挂NOI之前先挂一场模拟赛以作心理准备。

7月16日

晚上笔试。

由于之前没背笔试，于是喜闻乐见地爆成了97分……

看了下名次，居然掉出了前100名。这是Fe滚粗的节奏啊……

就这么挂了。坐等UNR考跪。

7月17日

早上以为是8:00开始比赛后来看了一下是8:30……于是去BZOJ上研究了一些题【然而并没有研究出来

8:30。

开场看第1题，一眼这不就是笛卡尔树吗= =（前两天在学校还讲过笛卡尔树的线性构造）

然后迅速写完一查样例1，WA

发现题目理解错了2333

改了一下终于过了样例1

一交，样例全过了【也许样例弱？不知道反正我不管了

这时候9点多了。

看第二题看了好久才明白，然后没思路!0=0!

把期望转成概率来算？然而是个无穷级数而题目要求精确值我就放弃了。【我真是SB

$n=m$ 貌似可以直接算？

写了下发现不对

原来我把 $\sum_{i=1}^n|t_i|$ 和 $m$ 混了。改。

改完后过了

又敲了个 $O(2^{\sum_{i=1}^n|t_i|}\cdot \sum_{i=1}^n|t_i|)$ 的暴力，好虚不知道会不会挂

然后去做第3题提交答案题，一道搜索题啊我去

搜索不会写……先手玩前面的点……

第1个点玩了个9步的解= =

第2个点玩了个11步的解= =

第3个点……玩不动了

那好我还是写个暴搜

题目给的checker是cpp？那我直接用咯【雾

把checker改写成了个暴搜程序搜1、2，发现1也只能搜出9步，2也只能搜出11步

然而还是感觉有错

不管了有分就行

跑后面的点结果一个也没跑出来【尴尬

加了个简单的剪枝写成了IDA*

一开始想把估价函数 $h(x)$ 定义为局面 $x$ 的连通块个数，想了一下觉得不满足对任意当前已操作步数为 $d(x)$ 的局面 $x$，有答案 $ans\ge d(x)+h(x)$ 了。【我比较SB，事实证明即使不用满足这个条件也能搜出接近最优解】

于是就把 $h(x)$ 定义成最大的 $f(c)$，其中 $f(c)$ 表示颜色为 $c$ 的所有位置在地面上的投影的间距之和。实际上这个估价函数差极了。

加了估价以后，依旧跑了几十分钟没跑出来

什么鬼啊一定是我姿势不对

发现块的个数不多，也就是总状态数不多

加个记忆化，居然跑出了好几个点，爽！

“记忆化IDA*”……interesting

就这样一个个点跑到比赛快结束了还有两个点跑不出

（也想把程序改成BFS，觉得会更快，结果BFS队列内存开不下最后只好放弃）

没空检查前面的题，就结束了

13:30。开测。

第一题几乎全场都过了。我也过了。

第二题……好虚……

测出来了，60分，没挂。

然而大家都是80分……就我60……

我好弱。

第三题，等了好久。

第一发测出来了。71。

第二发测出来了。81。

第三发测出来了。86。

最后一发……电脑卡了……

90。

和预期一样。

100+60+90=250。

一看居然是rank1？？？！！！

似乎把笔试的分数都捞回来了……

不过明天Day2感觉挂的可能性更大（如果今天只看第2题的话我就跪了）。坐等Day2爆炸。

7月18日

今天真的挂啦2333

第一题一开始没啥思路，想了挺久

打表找规律看下什么情况有解

发现 $c\le\max\{a,b\}$ 且 $(a,b)|c$ 时有解

然后觉得应该能构造

思考了很久得出的结果是：先用奇（zhan）技（zhuan）淫（xiang）巧（chu）搞出 $(a,b)$，然后在用倍增得到 $c$

写完一测，结果连 $10^9$ 都过不了- -

卧槽

这是要爆10分的节奏啊2333

先交了一发不管了= =

第二题想了一会儿，没思路，决定暴力弃疗- -30分滚粗

没检查，感觉是错的

第三题只会 $O(n\log^2 n)$ 的线段树套可持久化Treap【然而我从没写过可持久化Treap啊怎么办

不管了硬着头皮写

又写了好久，终于写完了

发现WA了2333

强行对拍找错

找出来了6666

测一发大数据不仅TLE还MLE，感觉整个人被掏空- -估计只剩暴力分了

感觉今天要10+0+30=40滚粗了。。。

最后几分钟。决定检查下第一题。

看第一题发现可以加个优化，这样步数会少一些。然后自己手写的checker过不了- -

发现有些地方没改清楚。

改好以后自己倒是没把它卡掉了然而由于是子任务制应该没什么卵用吧= =

最后3min把修改后的第一题交上去了，不过希望不大。

【不知测评系统中途为啥跪了

看了下，第1题20分，第一个subtask WA了……

回去看了下代码

有个地方似乎写错了

靠！

靠！！

靠！！！

看了下大家都A了第一题，虚炸了

完了今天真的要被吊打成dog了

……T T

第2题暴力居然没挂，30分拿到了呵呵，爽

第3题……最好多拿点分……

……

暴力30分测出来了……

第一版0分……

第二版0分……

最后一版……

50分。居然比暴力多过了两个点。

然而还是20+30+50=100，要滚粗的节奏。。。【排名掉到37了垫到不知道多后面去了

唉我好弱居然写炸第一题

唉我好弱居然写炸第一题【我是SB我是SB我是SB

唉我好弱居然写炸第一题【你看这就是平时不做题考场上懵逼的后果

完了

要完了

真要完了

……

不过第1题最后还有一次提交。

测了……

……（估计还是20分）

……（我又没改那个地方）

……（没戏了没戏了）

……（至此Day2 100分滚粗）

……

……（刷新出来往下拉）

……

……100！！！

……卧槽居然A了！！！

RP超好【之前程序的bug因为加了优化以后就没了？】

原本觉得最好也只能拿大概70分的第1题居然就这么rush过了！！！！！

最后排名定在了rank10，和UR14的名次一样 如果我最后3分钟没改第1题那真的是废了

不过这样的事情在NOI基本上不会发生吧

最后总分：97 + 100+60+90 + 100+30+50 = 527。这个分数在NOI2015是要滚粗的啊。。。

UPDATE：总分居然拿了rank3……D2T1真是RP大爆发给我rush A了不然就没戏了

然后就去看题解了

Day1第1题，正解居然不用构笛卡尔树6666

不过反正我可以线性构笛卡尔树复杂度也是 $O(n)$ 的= =

Day1第2题……尼玛我容斥都想到了就是因为算的是一个无穷级数然而题目要求精确值而我不知道 $\sum_{i=0}^\infty x^i=\frac{1}{1-x}$ 在模意义下也是成立的然后我就放弃了！

早知道就打表验证一下了- -我好弱

Day1第3题果然是搜索题……而且出题人就是故意让我们改checker的

引用了immortalCO的题解，immortalCO%%%

Day2第1题我写的应该是正解吧，辗转相除+倍增

问题是考场上并不会证复杂度233【所以AC也是挺意外的

qmqmqm的题好神！

Day2第2题……网络流？？完全分析不动

jiry_2的题太神啦！

Day2第3题……线段树套可持久化Treap的得分是30分~100分？也就是说我的做法有希望优化到100分？

然后看了下正解- -卧槽这是我最开始的思路然而由于不会区间弹数被我直接否定了！我该是有多么SB啊。

我毕竟还是太弱了。拿rank3完全是运气，然而NOI基本上就不会有这样的运气了……

坐等NOI滚粗。

[UPDATE 7/19] 早上一早起来头晕……休息了一会儿

去想昨天T2依旧没想出来

浑浑噩噩过了一上午

下午继续想不出题。。。回去刷水题算了

[UPDATE 7/20] 昨天晚上打了场CF，虽然没FST，但还是炸到113名……

CF 363 Div.2 爆炸记

我很弱，现在还只能打Div.2。

开场的时候网络卡得要命，根本进不去，过了十几分钟才进到网页里面去看题。

开始看C（就是Div1.A），想了下觉得是个线性复杂度的DP。

然而数据范围为何是 $n\le 100$？难道我理解错题目了？

想了好久觉得没问题，最后交了个很可能会FST的 $O(n)$ 程序上去

22分钟了。

然后再去看D（Div1.B），是求把基环外向树改成树至少要动几条边？

好像有几个基环外向树就要动几条边吧……哦不，如果已经有一个是自环就要减1。

这样结论似乎挺资兹的？写了一发过样例交上去。

39分钟了。

然后去看E（Div1.C）。

首先搞明白LRU就花了我老半天。我不会说我参考了百度百科

然后开始推，发现暴力DP复杂度会炸。

怎么优化？

没什么好的思路。

再去看F（Div1.D）。

感觉题目太坑爹简直不可做。算了，直接放弃。

回来看E。

我可是研究了两年的奥拉星的怎么现在连频率这一基本概念都忘了

开始推个频率的式子……

$t$ 时刻 $i$ 不在 cache 里的条件是 $t$ 之前第一次访问 $i$ 到现在出现了至少 $k$ 个不同的元素

然后SB历程开始——枚举上次 $i$ 到现在多少时间，然后用个式子去算？

复杂度会炸。不行。

1个小时了。感觉这样下去吃枣药丸。

去做B，一个大裸题我居然写了2遍才对……

65分钟了。

再去做A，理解题意花了一段时间……写的话真的很快……

78分钟了。

回来全力搞E（Div1.C）。

一开始想用个DP来容斥，发现推不出有用的东西。

快2个小时过去了。

最后……

我特么为何要去枚举时间 $t$ ？

直接DP求出每个子集出现的概率不就好了吗？

于是开始DP求从空集开始每次放一个东西进来直到出现 $i$，最后得到的每一种集合的概率。

好不容易写完了，剩1分钟。

交一发……

Wrong answer on pretest 2

卧槽！！

自己测了一发样例，发现样例二挂了。

没特判0。然后程序就跪了，输出了nan。

赶紧改了一发，准备交的时候就结束了。

悲剧。

于是最后就只有rank 113……被暴踩……

后来把改后的程序交上了CF，就AC了。

算下如果我昨天能交上去，就能排到rank 2了。

rank 2 → rank 113

论如何从rank2掉到rank113。

我好弱。

于是现在rating依旧没上1900。我就是传说中的打了两场CF依旧是Div.2的逗比。

下一次打CF就是NOI滚粗以后的事情了。估计下一次打CF就是我第一次掉rating了。希望第4场CF带我上Div.1。

CF698C 口胡

http://www.codeforces.com/contest/698/problem/C

有 $n$ 个元素 $1,2,...,n$，$i$ 的访问概率为 $p_i$，其中 $\sum_{i=1}^np_i=1$。

有一个初始为空的序列 $S$，以及一个限制 $k$。

每次随机从 $1,2,...,n$ 中访问一个元素，访问的元素为 $i$ 的概率为 $p_i$，访问 $i$ 时，若 $i$ 不在序列中，则将 $i$ 加入 $S$ 的头部（若加入前 $S$ 中已满 $k$ 个元素，则去掉 $S$ 末尾的元素），若 $i$ 在序列中，则将 $i$ 移到 $S$ 的头部。

不断这样操作下去，求每个元素在 $S$ 中的时间占总时间的比例。

这就是我早期研究游戏攻略时常用的频率分析法

然而这题我单纯这样想就掉坑了2333

考虑计算 $i$ 在 $S$ 中的时间比例。

随机取一个时刻 $t$，则 $i$ 不在 $S$ 中当且仅当 $i$ 从上次加入 $S$ 到现在，头部被插入至少 $k$ 个元素。

我们取出从时刻 $t$ 往前直到第一次出现 $i$ 的操作序列 $L$。

$L$ 是随机生成的，可以这样理解：一开始 $L$ 为空，每次从 $1,2,...,n$ 中随机取一个元素 $j$ 加入 $L$，$j=x$ 的概率为 $p_x$，直到 $j=i$ 时停止。

用 $P(A)$ 表示存在一个时刻 $L$ 中元素组成的集合为 $A$ 的概率，容易得到

$$P(A)=\sum_{x\in A}P(A-\{x\})\frac{p_x}{1-\mathrm{sum}(A-\{x\})}$$

其中 $\mathrm{sum}(A)$ 表示 $A$ 中元素的和。

这样就能得到最终得到 $L$ 的元素集合为 $A$ 的概率为 $P(A)\frac{p_i}{1-\mathrm{sum}(A)}$。

最后枚举所有满足 $|A|\ge k$ 且 $i\not\in A$ 的集合 $A$ 统计答案，答案就是 $\mathrm{ans}_i=1-\sum_{|A|\ge k,i\not\in A}P(A)\frac{p_i}{1-\mathrm{sum}(A)}$。

UPD：其实可以更简单：$\mathrm{ans}_i=\sum_{|A| < k,i\not\in A}P(A)\frac{p_i}{1-\mathrm{sum}(A)}$（orz qmqmqm）

该算法复杂度为 $O(2^nn)$。

显然当 $p_i>0$ 时，对任意 $i\not\in A$ 有 $\mathrm{sum}(A)< 1$。然而当 $p_i=0$ 时，可能出现 $\mathrm{sum}(A)=1$ 于是分母为 $0$，出现错误。注意到 $p_i=0$ 时显然有 $\mathrm{ans}_i=0$，特判输出即可。

另外CF貌似计算inf/nan特别慢？

然后发现好多神犇昨晚也打挂了？

不过还是要膜一下IOI大爷kfdong，不到1小时把Div1.C给A了。