UOJ Logo matthew99的博客

博客

HNOI D1T1 hunt

2018-04-15 13:32:46 By matthew99

第一次给HNOI出题(其实也是第一次给NOI赛事出题)。

题目链接

稍微了解一点MIT的人(比如知道Infinite Corridor不是真的无限长)可能看完题就知道出题人是谁了(然而好像因为奇怪的原因不能把学校名写在题目里,不过大家看到“某大学”,而不是“T大”或者“P大”可能也知道是怎么回事了?)。

简易题解:

如果第i个数之前的运算符是and,则这一位设为1,否则为0,得到的二进制数记为$x$。

对每一位分别考虑,对于第i位,如果第j个数是1,那么这一位设为1,否则为0,得到的二进制数记为$b_i$。

以左边为最低位,按前缀归纳容易证明,第i位的结果为1,当且仅当$x < b_i$。

我们将b从大到小排序,结果设为c,那么答案不为零仅当在c的顺序下,r中没有任何0在1的前面。找到r中第一个0的位置,假设是k,那么解x要满足$c_k \le x < c_{k – 1}$,于是答案是$c_{k – 1} – c_k$。

题外话:

当时出题的时候很紧张,是真的紧张,因为觉得实在是太水了。我当时的70分做法是猜结论,大概就是猜到有用的DP状态有$O(nm)$个再bitset。然后觉得这实在好猜了,其实根本不用猜,只要你注意到DP状态可能不满这个事实,然后直接记录有用状态就行了。

我当时很怕结果出来十几个AC,全场70。然后就再也没人找我出题了。

当时就不停的想HNOI有什么水题,是不是比我这个更水来安慰自己。

后面想想给大家送送分也好,至少这个题不是原题或者错题,能让自己成为大众喜闻乐见的出题人也不错。

结果分数分布大家都懂的。我至今不知道拿50分的是怎么回事($n$只开了$500$?拿50分的人能不能在下面评论区说一下怎么拿的)。于是我的顾虑成了多余的。

不过这也不错,一来我的题终于不是HNOI最水的题了,二来我的题很可能送人进队(比如你A了或者高分暴力),不太可能送人退役(最多就是你30分暴力分挂成10分或者0分)。Still,如果有人因为我的题暴力写错退役我只能抱歉了,对不起我给了30分暴力分

至于重测,那是因为我在Windows下造的数据,然后由于跨操作系统,换行符出了点问题-.-

考场上被各种倒推做法虐了。

其实倒推本质就是动态维护字典序。我很高兴大家因为我的题发明了一种新的排序算法。我可以把这个题改成每次模一个不同的数,然而似乎还是有基于倒推的奇技淫巧可以做。我也可以出成二进制高精度什么的,但是感觉它们还是可以过,也就是说在不懂正解只会倒推的(也就是大多数)人眼里,我把这个题目弄得更毒瘤而不是更神了。

说起来$O(\frac{nmq}{w})$可能是能过的(UOJ上能过TAT),解决方法大概是把$q$弄大,比如$10,000$。但是读入就很tricky了,可以压字符读入但是这样也很毒瘤。

所以大概这个题也只能放了吧,虽然不得不说我不是很喜欢这种倒推的做法,太直接了,个人感觉和标算没法比。但是也没办法,就像一个优美的题,结论就是输出a+b,也会有不明真相的群众写出一种和按位模拟加法等价的做法,你还没什么办法卡。

快乐游戏鸡LCT做法

2017-01-26 19:40:17 By matthew99

首先你得看了题和题解至少算法二之前的部分。

题解地址:http://vfleaking.blog.uoj.ac/blog/2292

我们把每个询问转化为总和减去大于等于最大权值的部分的后缀和。

接着我们按w从大到小加入点,考虑维护每个点的子树中的最小深度

这个怎么维护呢,考虑一个点肯定是更新它到根的路径,所以我们用类似LCT的access的方法更新,我们可以保证随时每个链的最小深度都相同,如果当前的链的最小深度小于用来更新的值就直接退出,否则的话我们就更新,最后再把这些更新了的链连起来。

复杂度显然是$O((n + m)\log{n})$的,用类似证明LCT复杂度的方法证明即可。

答案也很好算,记录一个后缀和即可,你会发现更新的时候也很好打标记,询问也很好处理。

怎样,是不是只要有模板就好写又好调?而且时间效率还不错呢。

代码:http://uoj.ac/submission/123579

UOJ Easy Round #7 题解

2016-10-15 20:15:21 By matthew99

短路

By matthew99

算法一

直接暴力 dfs,复杂度指数级,期望得分 10 分。

算法二

用最短路算法,复杂度 $O(n ^ 2 \log n)$,根据实现情况可以获得 10 至 30 分。

算法三

猜想只能往右或者往下走,然后做一个 $O(n ^ 2)$ 的 DP,可以获得 30 分。正确性证明参见算法五。

算法四

在算法三的基础上进行对称性优化或者使用滚动数组,可以获得 50 分。

算法五

我们考虑假设我们要从左上角走到从外到内第 $i$ 层任意一个中继器上,那么我们最少需要多少代价呢?显然我们一共最少走 $2i - 2$ 步走到 $(i, i)$ 上。其中,第 $1$ 层到第 $i - 1$ 层每层都必须经过至少一个中继器,除了这 $i - 1$ 步,还要再走恰好 $i - 1$ 步。

我们发现剩下来的 $i - 1$ 步至少要走的是 $1$ 到 $i - 1$ 层的前缀最小值之和,为什么呢?考虑一条走到第 $x$ 层某个给定位置且只到过前 $x$ 层的最短路径,那么该路径的最后一步要么是从第 $x - 1$ 层走下来,要么是在第 $x$ 层又逗留了一次。如果是后者,我们总是可以把这最后一步挪到前面去走,相当于对于某个 $k$ 在第 $k$ 层先走了这一步,然后把这一步之后的路径平移一下而不影响平移的这段路径的总时间,这样代价变化就是第 $x$ 层的 $a$ 与第 $k$ 层的 $a$ 的差值。这样我们就推出,如果第 $x$ 层的 $a$ 不是前缀最小值,那么肯定不是最短路径。因此,最短路径肯定不会在不是前缀最小值的层停留超过 $1$ 次,于是这条最短路就是把所有的前缀最小值所在的层的最左上角的点用 L 型的曲线连起来的路径。

那么假设我们走到的最深的一层是第 $x$ 层,首先第 $x$ 层不是前缀最小值的话那么一定不是最短的。如果是前缀最小值,那么最短路径就是先走到第 $x$ 层左上角,再绕一圈绕到第 $x$ 层右下角,再走出去(代价和走过来是一样的)。

这样,我们暴力枚举 $x$,走到第 $x$ 层的代价可以在线计算,然后每次更新答案即可。

时间复杂度 $O(n)$,期望得分 100 分。

同样的我们也证明了算法三的正确性。

怎样,是不是一个超级送分大水题呢?

天路

By zhj, vfleaking,题解 By vfleaking

什么鬼?

嘿嘿嘿……vfk 又来出题玩玩了。事情是这样的,我和 zhj 发现了一个好玩的 idea,然而我并不知道怎么套个优雅的模型。这时 zhj 拯救了世界,于是就出出来了。

哎说实在的过去的一年给 CCF 出题有点心累,在自家 UOJ 上出题各方面还是爽多了2333……

依稀记得 NOI2016 讲题时我兀自地讲讲讲,台下纠结分数线的梦想们并没有多少热情听。后来当我看到分数线公布以及签约的现场有点百感交集,感觉给 CCF 出一次题的事情多,责任也好重……在 UOJ 上自己随便出出出题至少不会直接影响选手痛失金牌。

但愿我出的萌萌哒题目们都能让大家有所启发吧。

谜之声:怎么近似算法都出到 OI 里啊?这真 NOIP 难度?

咳咳客官别急,往下看。敢承诺这个近似算法非常 NOIP 向,并不是那种数学大不等式乱搞证 bound 型。

算法一

对于 1 号测试点,$n \le 100, a_i \le 100$。

大暴力!

你会使用 for 循环吗?

时间复杂度 $O(nV^2)$,可以获得 10 分。(其中 $V$ 为权值范围)

算法二

对于 1,2,3 号测试点,$n \le 100$。

权值范围好大啊……

不要慌,你可以先枚举 $k$,然后枚举 Nokia1050 是在哪一段时间连续拦截了 $k$ 次攻击嘛……该区间中高度的最小值和最大值作为高度区间。

你会使用 for 循环吗?

时间复杂度 $O(n^3)$,可以获得 30 分。

算法三

对于 4,5 号测试点,$n \le 1000$。

在算法二基础上,把每次扫一遍求最小值最大值改为 for 的时候乱维护维护就行了……

(而且 $O(n^3)$ 常数好就过了呢)

(感觉在 CCF 系列比赛这样送分会被选手喷的……hhh)

时间复杂度 $O(n^2)$,可以获得 50 分。

算法四

对于 6,7 号测试点,$n \le 10^5$。

诶数据随机?

同学们你想到了什么!随机数据的前缀最小值只会变化 $O(\log n)$ 次对吧!

所以当我们固定左端点移动右端点时,区间内最大值与最小值至多只会变化 $O(\log n)$ 次。

拿个单调栈维护一下……每次给对应的长度区间更新答案。

脑抽选手可以使用线段树,但其实由于答案单调,所以可以变成给一个长度的后缀更新更新,于是就能 $O(n \log n)$ 的复杂度了。

可以获得 70 分。

算法五

还是数据随机的情况,观察数据我们注意到如果区间长度够长,那么答案就非常接近$10 ^ 6$。

所以我们设一个几百左右的值 $l$,然后处理小于 $l$ 时的答案,剩下来的输出 $10 ^ 6$ 即可。

同样可以获得 70 分。

算法六

好了好了所以之前的部分分跟近似算法都没什么关系……

这题应该怎么近似呢?你想,要是直接把权值除以一个大常数,做完之后再乘回来,看上去好像很近似!但是冷静冷静就会发现这样做出来是个绝对误差的,如果碰到 \begin{equation} 233333 - 233332 = 1 \end{equation} 这种就 GG 了。

所以……相对误差,看上去很没头绪。

来来来先把近似算法扔进垃圾桶,来想想如果要你求出准确解,你可以怎么做。

一个思路是,我们应该是枚举一个 $k$ 然后某种方式维护一下,但这个看上去就很没办法改造为近似算法。

诶,那如果告诉你一个常数 $c$,我们来把答案 $c_k$ 划一划范围好像很兹瓷啊……那 $c_k \ge c$ 可做吗?

……好像是可做的诶,因为最终的答案肯定是单调递增的,所以范围肯定是一段连续的 $k$。我们可以两个指针再开两个栈乱扫扫,左端点往后挪一挪,右端点也往后挪一挪……就能把 $k$ 的范围求出来了。

嗯很好,于是我们就可以每次找找 $c$,划分 $k$ 的范围。当范围足够小的时候,就可以把这一段的 $k$ 都用同一个数近似了。

事实上,你只需要取: \begin{equation} 1.05^0, 1.05^1, 1.05^2, 1.05^3, \dots \end{equation} 就可以啦!每一段里面随便找个数当答案一定不会超过相对误差的容许范围。

现在还差一个想题时的直觉 —— 就是需要划分的段很少……只要注意到其实段数是 $O(\log V)$ 级别的……23333333……别看人家 $1.05$ 小,但人家也是个指数函数。

中间找到 $k$ 的范围只需要 $O(n)$ 时间乱扫,所以总时间复杂度是 $O(n \log V)$。如果把 $5\%$ 当做变量 $\epsilon$,那么时间复杂度就可以写为 \begin{equation} O(n \log_{1+\epsilon} V) = O(n \log V / \log(1 + \epsilon)) = O(\epsilon^{-1} n \log V). \end{equation}

这个算法其实说明,所有 $f(i)$ 随 $i$ 递增且有个算法告诉我 $f(i) \ge k$ 的第一个 $i$ 在哪里的话,都可以套这个近似算法!(然并卵)

噔噔!这题就做完了!相信比赛时很多选手都轻松 AC 啦~

(为什么一道水题的题解我能写这么长)

套路

By matthew99

算法一

枚举区间,再枚举区间内两个数统计这个区间的答案,再求出整个问题的答案。时间复杂度 $O(n ^ 4)$,期望得分 7 分。

算法二

用 $\mathrm{ans}[l, r]$ 表示区间 $[l, r]$ 的答案,很容易发现 $\mathrm{ans}$ 可以由如下递推式算出: \begin{equation} \mathrm{ans}[l, r] = \begin{cases} |a_l - a_{l + 1}| & \qquad r - l = 1, \\ \min\{\lvert a_l - a_r \rvert, \mathrm{ans}[l + 1, r]\,, \mathrm{ans}[l, r - 1]\} & \qquad r - l > 1. \end{cases} \end{equation}

时间复杂度降为$O(n ^ 2)$,期望得分20分。

算法三:

注意到如果 $m \le 1000$,那么根据鸽巢原理,长度超过 $m$ 的区间肯定有两个相同特征值相同的跳蚤,因此答案是 $0$,所以我们处理长度小于 $m$ 的区间即可。

时间复杂度为 $O(nm)$,期望得分 27 分,结合算法二可以获得 40 分。

算法四:

使用任何一种时间复杂度为 $O(n \sqrt{m + n} (\log m + \log n))$ 的算法(请注意大O符号的意思),即可获得至少 $70$ 分。由于这些算法过于复杂且与标算没有太大关系(或者是标算强行多写了一个 $\log$),故不再赘述。

算法五:

我们考虑如果区间长度是 $x$,那么最小差不超过 $\frac{m}{x - 1}$。

设一个常数 $S$。

如果 $x \le S$,则用类似算法三的方法,可以做到 $O(nS)$。

如果 $x > S$,那么最小差不会超过 $\frac{m}{S - 1}$。我们扫描一遍序列,考虑当前位置作为右端点,用 $r_x$ 表示权值为 $x$ 的数最后出现的位置,然后每次新加入一个数 $z$ 之后,对于所有 $\lvert z - y \rvert \le \frac{m}{S - 1}$,利用 $r_y$ 进行计算更新答案,然后 $r_z$ 即可。时间复杂度为 $O(n\frac{m}{S})$。

设 $S = O(\sqrt{m})$,则总时间复杂度为 $O(n\sqrt{m})$,可以获得 100 分。

这是不是 UOJ 历史上最水的C呢,相信大家 AK 得非常的爽,作为出题人之一看到大家 AK 我也感到非常荣幸。

UPD:好像打脸了。

NOI2016及赛前的故事

2016-07-10 22:23:24 By matthew99

退役前最后一次NOI,如果不写点什么感觉太遗憾了。

明天是湖南省队集训的第一天,地点是师大附中。基本上是上午8点到下午1点考试,下午2:30到5:00讲题改题。

记录一下每天干的事情吧。

随之而来的15号凌晨有一场CF,19号晚上有一场SRM。我当然希望能打好,但是我也知道这往往可遇不可求。UPD:19号新增一场CF紧接着SRM UPD:决定还是不打CF了

2016年7月11日

省队集训第一天。

早上去报到,接下来去机房开始考试。

这一场前两题都非常简单,第三题是一个稍有难度的数据结构题,我在考场上很快写完了前两题,第三题却做了很久,而且做法也过于复杂。

中午发盒饭在机房吃。

下午发现包括我以内的很多人都挂了第一题。

第一题的题意是这样:

定义一个置换的平方为对1~n的序列做两次该置换得到的序列。已知一个置换的平方,并且这个结果是一个排列,求该置换。

输入第一行一个数n表示排列长度,接下来一行n个数描述排列。

有解则输出一行n个数表示原排列。否则输出一行一个-1。

这个题,几乎绝大部分同学都写了一个checker检查。

大概流程是这样:

  1. 读入排列a。

  2. 用某种途径得到输出b。

  3. 检查是否有对所有i有b[b[i]] = a[i]。

这样的检查方式以及检查通过的程序都是有问题的,你们能看出为什么吗?此外,你们能否不利用a只通过对b进行简单处理使得这个checker正确?

祝贺ppfish前两题都没有挂,第三题打满了暴力并成功获得了第一名。

此外今天才知道,g++在不开O2的情况下,开了-pg选项会变慢很多。

晚上看了一些黑(xiao)科(chang)技(shi)。

7月12日

省队集训第二天。

上午考试,去的时候发现每天中午的盒饭20元,感觉可以和火车上买饭的价格比比了。三道题做法都不难,但是我却在后两题都卡了一阵子。三题都有大样例,虽然第三题大样例过了之后我依然发现我犯了一个非常厉害的错误(虽然听说数据强度和样例差不多)

最后没挂分。然后发现第三题暴力可以过85分,因为不仅树都是随机的,而且每个点的父亲编号都小于它自己的编号= =b

共价大爷第三题被卡常数了,7s时限,链的点全部TLE了,不是链的点零点几秒,虽然为什么会这样上面已经解释了233

今天早上把公交卡塞进了手机上,考完之后才发现来的时候手机掉在了车上,但是幸亏早上坐是我们家的车而不是公交车23333。

今天的第二题是,给定$n$个点,每个点的度数都有一定的限制,现在要你选择一些点构成一棵树并满足度数限制,问你总共有多少种方法构成大小分别为$1$到$n$的树。$n \le 100$。

这道题目需要一些计数能力,你们会做吗?

下午带着自己电脑过来到隔壁机房蹭网,开了一下SRM639的hard,然后发现自己最不擅长做的就是这种类型的数学题,需要分一些情况并且要考虑的很多,我发现仔细想出了很多贪心算法却一个也不会hack,后来只好看杜爷代码发现却很简单,然后发现过不了样例,接着便沦为了人眼diff选手,一阵子之后发现居然五点了!我要和tty他们一起坐车回去,赶快收好东西到原来的机房去却发现他们早就走了,感人肺腑。

晚上做了SRM640的hard。

看到几篇和本日志风格类似的日志:

http://wronganswer.blog.uoj.ac/blog/1831

http://yjqqqaq.blog.uoj.ac/blog/1827

我写这个日志,意义在哪里呢?大概也想体验一下写日记的感觉吧。而且如果NOI出现不可理喻的低级失误,这大概就是OI生涯最后一段训练和除了NOIP之外最后一场比赛,不留下点文字太遗憾了。假如进队了,那也是最后一次作为正式选手参加NOI。

关于昨天的第一题,坑点就在于题目中给出的是一个排列。

置换对排列的作用就是交换这些数的位置,也就是说比如置换的第1个数是3,那么就将第一个数换到第三个数的位置上,而不是将排列的每个值变化成另一个值,比如说把值是1的数变成值是3的数。

所以在读入排列a之后,结果是排列a的置换应该是排列a对应的置换的逆。只需要一开始对a取逆就可以了。

那么如何不利用a只通过对b进行简单处理使得这个checker正确呢?我们可以不对a先取逆,而是得到输出b之后再对b取逆,两者对应的答案是一样的,正确性留给读者思考。

7月13日

省队集训第三天。

上午看三道题,发现第二道题居然是三年前省队集训考过的题,另外两题也不难。

开始的时候做第三题,一开始一直想用单调队列+multiset但是没注意到单调性,然后想写线段树,后来才发现居然是有单调性的,于是顺利开始写了个multiset,每次取最小值并支持插入删除。

考完之后德霸哥提醒我,我突然感觉发现了世界的奥秘。

你 大 爷 , 这 他 妈 就 是 个 堆 啊

由于这是一道考察stl基础应用的好题,一开始用专业卡stl的cena测搞得我虚的要死,后来发现改成lemon了,不虚不虚。

第一题我复杂度比标算优,不过这套题年代久远,在当时标算的复杂度就已经很不错了。

noname说HNOI也出现过同一道题出现两次的现象。省选重题,省队集训重题,接下来是什么了?现在终于知道为什么去年老师要我们把历年的NOI题都做一次了23333。

下午看到成绩,第一题数据有问题,但是实测如果数据正确应该能AC,另外两题都AC了。

第一题题意是,给定一张点数$n$不超过10000,边数$m$不超过200000的图。每条边有一个权值和长度,每种长度的边都不超过30,求最小生成树的边权和的期望(注意权值和长度不是同一个东西)。

一个经典的思路是,考虑相同权值的边,将权值比它小的边缩起来,然后考虑这种权值的边连成的每个连通块,于是问题转换成生成树计数。

用$s$表示相同权值的边的数目的最大值。考虑用矩阵树定理计算出不包括每条边的生成树个数和总的生成树个数,复杂度是每次$O(s ^ 4)$,但是考虑到如果当前图中有$x$个点,那么必有$x - 1$个点被缩起来,因此很容易证明复杂度实际上是$O(ns ^ 3)$。此外,为了避免精度误差,可以找一个大于$2 ^ s$的质数(如1073741827)并在模意义下做。

由于常数小实际上上述算法已经可以AC了,但是你们能不能做到$O(ns ^ 2)$呢?

晚上颓了很久QAQAQAQAQ,最后做了个SRM642hard,是个傻逼800分,然后网络不好,交题交了很久。交题花的时间比做题长,颓的时间比交题长,令人感动。

昨天晚上做了个噩梦,梦见我打游戏被老师抓个正着,结果就醒过来了。我现实中却很久没被抓,结果果然看别人打游戏还被老师抓了。我最近整个就没效率啊。还号称可能是最后一场OI比赛,我却用这点时间在颓,表里不一不是我想要的啊。知道自己不应该颓却像戒毒一样难以停下来,简直感觉身体被掏空。

CTSC之后去准备水考,准备好好认真搞搞文化看能不能恢复到班上前几名,却也落得个半颓半学习的下场,最后成绩也不太尽人意。平时不注意就一直颓,曾经自诩“我的下午从五点开始”,颓的时间还有一辈子,搞OI的时间却只有这么一点,还是希望明天开始能少颓一点。

想起来我做过的梦,一半准一半不准,去年HNOI之前梦见自己滚大粗但是还是踩线进队,结果果然滚大粗但还是踩线进队,CTSC之前梦中进了两次队,结果梦里把两年的队进完了,NOI之前觉得NOI滚粗了也没多大事,结果就做了个梦,梦见自己NOI 500分都没上,最后被金牌线卡(当时还是认为金牌线是集训队线),希望这是把粗在梦里滚完了吧233。

我曾经天真的想在NOI之前刷完500以后所有SRM(因为从670左右的地方开始后面的场我都做过),现在看来不太现实了,要是NOI真的滚粗了,感觉整个人还是会浑身难受啊,虽然保送了我也觉得不管怎么样也还是要继续搞算法竞赛,但是那时候再做SRM心境也不同了吧。

明天晚上(准确来说是后天凌晨,但是我还是习惯说明天晚上)有一场CF,我知道只要涨rating就能LGM,但是涨rating也不是见容易事,大概不打出一个能过WC的名次还是很危险的吧。但是如果我今年(或者今年和明年)的OI想要走的更远,就应该做到每一场比赛都打好,毕竟想想最近也没打过什么比较差的名次。如果明天真的滚大粗就会成为我NOI也可能滚粗的信号弹,所以除非出现不可理喻的低级错误我绝对不会滚粗。因此还是希望我能把最近CF名次至少都不差的现状持续下去或者争取做得更好。当然光说不做假把戏,明天至少要记住我心态不要崩盘,题目看清想清再下手,争取一遍过。总之祝我好运吧!

昨天的第二题做法是,我们容易用prüfer序列证明每个点度数分别是$d_1, d_2, \cdots, d_n$的树的个数是$\frac{(n - 2)!}{\prod{(d_i - 1)!}}$,因此,我们考虑枚举每个点选不选和每个点的度数,用$\mathrm{dp}[i][j][k]$表示前i个点,选了j个点,度数减一的和为k的所有方案的$\frac{1}{\prod{(d_i - 1)!}}$之和,容易实现转移,特判大小为1的情况(答案就是点数$n$)之后最后答案就是$\mathrm{dp}[n][\mathrm{size}][\mathrm{size} - 2] \times (\mathrm{size} - 1)!$,复杂度是$O(n ^ 4)$,常数较小可以通过。

此外可以用FFT优化,但是这仅限于理论复杂度的优化,实际上速度尚不及直接暴力。另外APIO2016的第一题也可以用FFT优化,同样暴力也可以通过,只是暴力速度不如FFT优化。

7月14日

省队集训第四天。

上午三题都挺简单。第一题强行三个subtask,前两个n是$10 ^ 6$,最后一个$k$是$10 ^ 9$而$n$只有2000。第二题KMP傻逼题我不会KMP只好强行用hash上。

接着发现我、共价大爷、owaski都能AK。

最后成绩出来我们三个都喜闻乐见的自爆了。我第一题第一个subtask一个地方没取模爆了int。共价大爷第三题答案是0就会错,owaski第一题没看到$n$有$10 ^ 6$。于是挂成了295,280,260,令人感动。

我怎么又爆int了?再爆int我真的不能忍了,为什么一个取模我就是做不到。还有读入优化快速幂也是每天错一次,简直不知道在干嘛。

所以怎么避免呢,认真写当然是最好的,我最近写程序都极为不认真,这样什么错都容易犯。

还有一些人可能会想出建一个类或者加数之后取模的函数什么的办法,让程序自动取模,但是首先这样太麻烦,其次你怎么知道你哪天就忘记用类或者是函数呢?再者这也是一个治标不治本的方法,解决了这个错还有那个错,错是犯不完的。我曾经天真的觉得错误就那么多,最后每次一到大考却出现了新的错误,改完一个又一个,时间一久老的错误又卷土重来,最后什么都解决不了。

昨天我提到过第一题存在复杂度为$O(ns ^ 2)$的做法,怎么做呢?

考虑如何快速求删掉一条边的生成树个数。我们发现删掉一条边,要求行列式的那个矩阵中最多只有两行发生了变化。

那么我们可以参考策爷去年的集训队互测题《最大异或和》的做法,考虑维护消元之后每一行是由原来的矩阵的哪几行分别乘上多少组成的,假如我们要修改某一行,我们就看看这一行对消元之后的矩阵的哪几行有贡献,找到有贡献的最后一行,让后用它消去所有行,注意这样不会导致主元发生变化。

接下来对这一行做对应的改变之后,再对这一行消一次元即可。这样每次的时间复杂度降为$O(s ^ 3)$,因此省去了一个$s$,复杂度变为$O(ns ^ 2)$。

另外要注意改变其中一行之后可能不满秩,改变另一行之后却满秩的特殊情况,以及行列式交换两行值要取反,这些都比较容易处理所以不再赘述。

晚上就是CF了,一定要沉住气啊。而且明天考我的题,上午太困也没关系咯23333

7月15日

马上就开始CF了。听说19号还一场那么这一场其实只要不暴跌,问题也不大?重点是这种比赛我本来就不应该有太大的压力。

如果LGM了,终究下一场还是不太想打了,毕竟马上NOI了真的不太想最后又把这个LGM丢了,虽然我知道我很看重rating......但是还是不太放得下。毕竟自己还是有以LGM身份参加NOI的梦想,还是不希望他在自己手上这样破灭。

即使我滚粗了,只要不太厉害下一场也完全有翻回来的机会。已经没有什么好怕的了。

虽然你们可能说我立了很多flag,以及压线从来没人涨过这种奇怪的debuff,但是看看欧洲杯这次最后两场,以前某两队之间的比赛基本都是某一边赢,这次偏偏成了另一边,一切皆有可能。

考完了,不FST是可以上LGM的。F题状态不好只会三方log,最后没敢写。

考前觉得自己A不能一遍过,很认真的写完,很晚才交结果一次过pp了,觉得果然自己的感觉不一定对。

结果快下考的时候,A被hack了= =b

不过估计这场FST的人很多,我估计也有可能FST,甚至FST多题,成事在天。

A不太可能再挂了。B挂了应该还是能LGM,C挂了不知道,D和E挂了肯定不太行了。不过还是挺充裕的,但是真的虚的很啊,这场pretest太弱了。

最后没有FST,rank4,顺利LGM。难得的国家队名次,我已经拿了不知道多少次rank5了23333。claris也拿到了面试名次,rank6。(CTSC英文面试那这个如果真的有面试是不是中文面试呢?歪果仁不会说中文岂不是大家都稳了啊)

这次上LGM,喜悦当然是有,然而我也再一次知道,所谓flag都是假的。

AC五道题rank5一定会FST吗?不一定,我最近多次证明了这一点。

压线一定会暴跌吗,不一定。

对拍过的题一定会FST吗,不一定,这次我的E题对拍了也没有FST。虽然之前的对拍过的题都FST了= =b

想起了不久之前的CF345,当时我2775的rating,第一次在div1 pretest AK,心想终于要LGM了,却没想到刚下考就被人指出B是错的,我便想估计2800+还是有的。

最后的结果令人吃惊,FST了三道题,目前我听说别人CF上FST的最多几次的也就只有某一次有人FST四道题以及某几次有人FST三道题,掉了一百多的rating,那一次之后我还是收到了不少打击。

之后的VK cup,我再一次FST了一道题,从大约四十多名变成了一百多名(也就是从集训队变成了前一百的约都拿不到23333)。

上IGM之后我的rating跌宕起伏,虽然一直没有掉下过2600,但是也足够让人胆战心惊。大概人生也可能就是这样吧。

省队集训第五天,考的是我的题。

我出的模拟题,没有一套不出事故的,这一次也做好了出事故的准备,主要还是怎样应对。上次我应对得很不好——题面出现与数据不合的地方,应当改数据而不是题面,因为改数据只要我知道就行,改题面要重新通知所有人。

23333333果然出事故了。

上午他们在考试,我在这边造数据,结果发现卡了A算法卡不掉B算法,卡了B算法A算法又轻松AC了,十分感动,最后决定大赦天下各送一半分,感觉我这么良心的出题人很难见啊。

最后还是被水过去了,肝败吓疯。

讲题的时候听说我的提答题是addition chain的特殊情况,并不是NPH的,身败名裂......

下午外面风雨大作、电闪雷鸣。

7月16日

省队集训第六天。

今天的题不太可能全部考场上写完,然而我第二题被卡常数,第一题写错,第三题暴力骗了50分。

今天的题原来是给省选模拟赛准备的,仔细想想要是真的是省选模拟赛应该还是非常贴近真正的满是瘠薄题的HNOI啊(雾)

第二题是一个裸轮廓线DP,我因为被卡常数鏼了三个小时无果,因为我没有预处理转移,仔细想想这类题目,能预处理就先预处理,因为预处理不仅复杂度是稳定的,而且即使要矩阵乘法加速也很容易,可移植性强。

第一题是一个数论七合一,虽然都没什么难度,我却犯了一个傻逼错误,我以为无根树计数双重心不用处理,结果就错了,主要是当时第二题卡了三个小时没时间太急了,唉。

第三题是一个大字符串,标算代码量差不多是我前两题的代码长度的总和(也是昨天模拟赛我标程的代码长度总和的几倍233333),由于事先知道一点信息所以果断知道要跳过把题目留给另外两题了。

不得不说第二题写错真是败笔,第一题其实也很容易多过一些点的。

今天第一题的一个子问题是,求n个点的带标号二分图个数,原题$n$是1000但是实际上可以做到$O(n \log n)$,你们会做吗?

7月17日

省队集训第七天。

今天的第二题很简单,第三题是一个送分送的和水考差不多的提答题。第一题较难得分,我最后一个多小时一直在鏼第一题,写了8K代码成功拿到0分,感人肺腑。

第二题大概是一个障碍多边形在绕着地球公转,本身在自转,自转是绕着重心,太阳是一个点地球是一个圆,求某个时刻太阳照射到地球上的弧长。

有一种的做法是,算出自转角度和公转角度,将每个点绕着重心将算出的旋转角度代入旋转矩阵算出自转后的位置,接着将每个点绕着太阳将算出的旋转角度代入旋转矩阵算出公转后的位置。这个算法对吗?

第一题题意大概是要我们维护一个亲戚关系,考场上时间不够导致写代码BUG很多所以零分是必然的了,其中一个BUG特别有趣。

父亲的因为是father,母亲的英语是mother,我用fa表示父亲,mo表示母亲,写着写着就成了ma了,然后我就发现,怎么一堆的mo啊,mo不是模数的意思吗,惨啊赶快都改成ma,然后喜闻乐见,mother我判断前两个字符是否分别是m和a而不是m和o,于是我的程序重男轻女,只认父不认母。顿时感觉自己多年的英语白学了2333333

下午听说第二题没过样例都能AC,论做UR特判样例的重要性,多拿三分啊233333,事实是第二题好像,不管障碍多边形就AC咯,结果这样都没多少人AC,人没有梦想就是咸鱼咯。

以及这么多个人连重心都不会求是怎么回事啊!感觉这不是,计算几何基础知识么,应该和求面积一起学的(雾)。论看完黑书白书的重要性。

祝贺共价大爷采取了直接不做第一题的正确策略,在第二题AC之后把时间全部留给提答题,最后成功获得第一名。

昨天我提到了$n$个点的带标号二分图个数怎的统计问题。这个问题怎么做呢。我们先看看$O(n ^ 2)$的做法吧。

对于一个图,考虑它的黑白染色方案数,那么当它不是二分图时,个数是0,是二分图时,个数是二的连通块数目次幂。

考虑对所有图求方案数之和。可以考虑枚举黑点个数,那么容易得到公式$g_n = \sum_{k = 0}^{n}{\binom{n}{k}2^{k(n - k)}}$。

接着,我们用容斥求出连通图的贡献,也就是枚举一号点所在的连通块的大小。于是有公式$f_n = g_n - \sum_{k = 1}^{n - 1}{\binom{n - 1}{k - 1}f_kg_{n - k}}$。

最后考虑求非连通图,无非也是枚举一号点所在连通块的大小。于是有公式$\mathrm{ans}_i = \sum_{k = 1}^{n}{\binom{n - 1}{k - 1}\frac{f_k}{2}\mathrm{ans}_{n - k}}$。

接着考虑如何做到更优。

首先$g_n = \sum_{k = 0}^{n}{\binom{n}{k}2^{k(n - k)}}$怎么优化呢,考虑参考CZT的思路,$2 ^ {k(n - k)}$容易拆成$-2k ^ 2 + \frac{k ^ 2}{2} + \frac{(n - k) ^ 2}{2}$,于是容易展开成FFT的形式。

接下来的两个公式容易用分治FFT做到$O(n \log ^ 2 n)$。

怎样做到$O(n \log n)$呢,可以参考策爷2015年的集训队论文,一张图是由若干个连通分量组成的,因此任意图的指数生成函数可以看做连通图的指数生成函数的$\exp$,相反连通图就是任意图的$\ln$了,所以$f_n$的生成函数就是$g_n$的生成函数的$\ln$,而$\mathrm{ans}_n$的生成函数就是$\frac{f_n}{2}$的生成函数的$\exp$,只需要用多项式$\exp$和$\ln$即可在$O(n \log n)$时间内解决该问题,而二者的做法均可以在该集训队论文中找到。

7月18日

省队集训第八天。

三道傻逼题+挂了10分=爆炸。第二题加了往点数组里加了一个终点但是离散化数组没加,挂成90分。考挂自己弱没什么好说的。

祝贺共价大爷,CyanHJWJBSRFuxeyZZD五位AK爷。

明天的CF仔细想想还是不参加了吧。不管是谁都不敢确保自己下场比赛能在2986的rating守住lgm,即使是tourist也有可能失误,一旦下场比赛滚大粗,我怕在现在还是很可能对我整个人的心态产生影响,从而影响NOI。虽然下场比赛有可能打得好,但是我感觉也不能操之过急,如果水平在那里,什么时候涨rating都一样。而且那天晚上还是TC接着CF,两场比赛连着打第二场可能会受影响,再说我也想NOI之前好好休息一下。CF打完11点而且打完CF一般比较兴奋有点难入眠。所以还是NOI之前不打CF了。

明天是省队集训的最后一天,仔细想想这次省队集训大的失误除了第一天一个基本上所有人都犯了的错误之外,还是没有别的错误的,希望这次能够完美收尾吧,不要最后一天滚个大粗。

昨天提到一个求自转公转一定时间后的位置的做法,这个算法是错误的,原因很简单,如果你用旋转公式给整个多边形进行公转,那么同时整个多边形实际上也自转了一定角度,其实理解起来和地球日太阳日的区别差不多。论地理在OI中的重要性。

正确做法很多,最简单的做法之一是先把重心公转后的位置算出来,再按照相对重心的位移恢复其他点,再进行自转即可。

7月19日

省队集训第九天也是最后一天。

今天三道题都比较有意思,第二题很快做完,第三题想了个错误算法然后很快写完,接着很快做完了第一题。然后就开始浪了。

结果喜闻乐见的第三题就挂了。

今天第三题题意是,给你一个带权完全无向图要求把点集分成两部分使得两部分的点之间的边权的最大值之和最大,这是一道原题但是我没做过。

我的做法是,一开始点集只有1号点,接着选一个与当前点集之间的点连边最大值最小的点加入点集,每次将点集和点集的补集的集合内的最大边加起来更新答案。

这个算法你能具体解释一下为什么会错吗?

今天晚上是SRM 695和CF 363,后者已经决定不打了,前者我还是要打的,希望不要考挂。

300慢慢的认真写,写完认真检查了好久。分比别人低很多。

接着看到群里都说500不会做,于是开了800。

800想了一会儿写了一个发现萎掉了,然后就一直以为有然后,然而并没有然后......当时就意识到肯定要滚粗了。还剩20+min的时候灰溜溜的开了500

500不会,800也不会。

500问策爷说考虑前21条边就够了,我为了保险考虑了30条。

结果杜爷说500要考虑31条,成为CTSC rank5和CF 2899之后又一次只差1。

结果challeng环节发现300被hack了。写这么认真+这么久,你还给我错,其他人比我快还对。最后发现我犯的错,简直不能说是错,简直可以说是我没做出来,算法核心部分我都没有实现。

naive的以为学习petr写的时候认真一点交完再认真检查就能对,结果是真正的petr以比我快很多倍的速度写完并且对了,而我还是错了。果然是水平差距太大已经无法模仿了。

hack本来还失败了一次,结果后来hack回去了,hack回去之后知道要只有25分了急了随便hack了一个又失败了。结果最后爆零了。

我还naive的觉得我能一举target,结果居然掉到了2743。这个结果,我真的完全没有想到。

NOI要是这种名次我就铜牌了。

真的很想和鏼老师还有杜老师同台竞技,最后却发现自己实力远远落后于他们,所谓同台竞技,成了不断的喊“救命”和不断的求程序对拍。

不想传播什么负能量了,NOI之前最后一次TC爆零滚粗了,如果NOI再滚粗就可以向最后一场CF、TC和OI比赛都考跪的吉司机致敬然后看吉司机吃*了(逃)

7月20日

省......不,省队集训已经结束了。

早上看了看CF发现策爷CF掉的比我TC掉的还多......同是天涯沦落人咯。杜爷rank3帅气掉rating。petr帅气TC、CF两个一起AK+win+超过tourist。

非常佩服petr啊,两场比赛连续考还能一场不挂而且都是AK+win,换做是我考完第一场第二场一般都太兴奋就挂了。

明天一早就出发了,这次NOI是我最后一场NOI,我的前三场NOI结果都算好的,这次当然希望能考好。不过这次完全没有任何压力了,毕竟已经保送,当然如果滚粗了我肯定还是很伤心啦。

昨天提到一个错误算法,那个算法为什么会错呢,可以这样想,你加入一个新点到点集,可能导致其他点到这个点集的距离都变大了很多,这样就错了。

比如假设图权值只有0和1,且权值为1的是个二分图,那么答案显然是0,但是当且仅当我集合扩展到了图的X部分或者Y部分的时候答案才会是0,而我的算法就等价于——找与当前点集没有任何边相连的顶点扩展,所以很容易就从X部扩展到了Y部,随机一个二分图我的算法就很容易出错,因为一旦扩展到了Y部,基本上就不太可能还能算出正确的答案了(比如我们可以假设Y部的点度数都不为0)。

7月21日

出了些状况......

早上七点出发到成都再转车去绵阳,然后火车路上遇到状况晚点了,于是就没赶上第二趟火车。然后我们在外面转了好久才找到宾馆在火车站附近住下来。蜀道之难,难于上青天!

看了下上场SRM的800,发现我突然一下子怎么就什么题都不会了啊QAQ

成都东站我来过很多次了,比如WC的时候我就来过一次,最早来还是2013年第一次参加NOI的时候,那年是在电子科大。

而我后面还要去百度之星,打算玩几天再从成都出发到北京。

于是乎,不论是这次NOI,还是我参加过的所有NOI,都是从成都开始,到成都结束了。

不管是什么结果,都当做是命运给我的一份礼物吧。

7月22日

报到日。

上午差点又没赶上火车。

开了下上场CF的F,发现我最近debuff好像有点严重。

7月23日

开幕式上看了很多节目,比如变脸,完全不懂京剧那一套理论。

听到了CCF和教育部抗争10年,终于取消了NOIP保送的事。其实讲道理NOIP保送也挺不公平的,首先我们都觉得NOIP一等奖很容易,比直接高考考上那些学习容易很多,其次在NOIP作弊比在高考作弊容易多了,所以我个人还是持支持态度的。

下午笔试,感觉是四年来最水的一次笔试,三分钟提交满分无压力,虽然后面还是检查了一阵子。

明天就是day1了,希望自己能不留遗憾吧。

7月24日

NOI第一天。

看完三个题发现好像都比较可做的样子,第二题一眼以为是转化为八连通之后搞搞,结果发现答案只有四种可能。

感受一下感觉第二题比较恶心,于是就决定先做第一题再做第三题再做第二题。

第一题做到一半发现暴力有95,瞬间感觉自己在做无谓的努力,然后搞到九点多,感觉非常虚,过了样例就不管了。

第三题猜想互质就行了,结果写了个暴力发现大样例跑不出,然后开始加两句优化跑两下,终于加到能跑出的时候发现答案错了,然后写个大暴力好像排上了顿时慌了。接着发现我有个地方爆int了= =b

于是愉快地开始瞎做,做到一半发现我的方法好像有点萎,接着发现好像要用杜教筛,顿时感觉我走上了不归路。思考了一会儿人生发现好像没有什么救只好强上杜教筛了。

接着到了十点半宣布考试过了一半了。我开始刚T2。

结果发现果然T2才是最难刚的,一开始觉得把每个点周围曼哈顿距离不超过2的弄出来求下tarjan是不是行了,后面发现好像要用set或者map,估计不改成hash很虚要超时。

然后开始想别的做法,发现好像可以枚举一个点判断周围八个方向的情况,然后正要开始写的时候发现不会判不连通。然后发现前面那个tarjan的方法好像也不太好做了。

接着发现好像可以扫描线,每个连通块用最下边的最右边的点统计答案就可以了。

于是开始写写写,发现各种错,过了样例发现判八个方向好像没那么容易,然后瞎几把猜了个结论过了1000个数据的对拍。

于是我在1000后面加个零,拍10000组数据,发现WA得七七八八的= =b

于是令人感动的又改了几下,瞬间面目全非,感觉一副AC不了的样子,瞬间想起了WC拍100000组数据怒挂T2的故事,觉得很慌。然后开始狂对拍狂看代码。

后来觉得还是看看另外两题比较好,然后发现第一题好像三个样例拼起来就挂了,接着发现样例里面n递增于是我一个地方没清空没发现,令人感动......

下午过去看好像AK了,非常感动。

最后说下我对题目的看法吧,我觉得这次NOI的题目还算比较科学,部分分也较为合理,送的比较多,基本属于挂分大于没写正解少的分,这也正是ACM、CF、TC这些比赛的情况。没有码农题,有一定思维难度。而且这是NOI第一次引入杜教筛,感觉科技在进步。

我的第二题判断是否有割点的方法是。考虑每个蝈蝈周围8个方向的跳蚤,按顺时针或者逆时针考虑周围八个方向,如果一个对角线(比如上面和右边)都有蝈蝈那么就在右上角加一个蝈蝈,连通性和这两个相同(因为显然这个对角线上的两个蝈蝈属于同一个连通块)。

接着我们发现,如果按逆时针或者顺时针方向,某一个连通块的两个格子中间和外面都有跳蚤,那么这个跳蚤肯定是割点。

这个做法我不会证明或者证伪,如果有人会证明或者会证伪欢迎在博客下面评论。

7月25日

社会活动日,看了核武器以及很多其他炫酷的武器,接着去了一个公园,然后到了一个阁,听tty介绍了一些建筑学知识。

中午吃饭的时候听到有人说:“你怎么一颗原子弹都没偷出来”233333333

下午和大家颓。晚上开了一个CF题,发现自己一个思路完全不会变通,而且几年前学的huffman编码怎么用两个队列维护都想不起来了。

密码条上有我day2滚粗的flag啊。虽然我并不信还是希望第二天不要考挂了。这还守不住集训队我就把脑袋留在南山。

7月26日

NOI第二天。

当了一发咸鱼,第一题写完第二题写个85分第三题写个84分之后发现分好像比day1的第二名高了就开始守,然后发现第二题居然有部分分,然后提到了91分,然后开始不断检查,最后瞎猜了第二题的几个结论发现都是错的,然后就下考了。

下考的时候很慌很怕第二题是个上百人A的傻逼题。

结果发现我周围距离不超过2的地方就有人AC第二题,令人感动。不过反正我也有91分。

下午去看一分没挂,275分。

感觉今天题目分差比较小啊,第一题还算有点意思,two pointers套线段树,第二题结论还是挺有趣的,只是我太咸鱼了就没去猜了,其实好像去猜也猜不到,我本来想给样例打个表,后来构造了一个极端例子觉得好像分段可以很随机应该不会有啥规律就不管了,事实上好像是有规律的,那我考场上肯定想错了QAQ。

第三题拿到84分之后就不敢往下做了,实际上当时还是觉得第二题不会做放不下,放下了可(gu)能(ji)会(ye)高(shi)点(yi)吧(yang)。

晚上和vfk聊了很多关于他在英国的故事,感觉非常有趣啊。比如英国松鼠很常见,街道很干净,污染很小,天空很蓝。人们喜欢说thank you,餐厅里别人来为你服务也会说一句thank you。还有就是由于版权问题网易云音乐用不了233333

7月27日

上午趣味运动会,发现节目比较高能就逃出来了233333

然后下午闭幕式颁奖领到了金杯。节目也非常厉害,健美操四女一男比例有点鬼畜啊。

感觉这篇文章到这里也要结束了,总要说些什么吧。

首先当然是感谢了。这次NOI的成功,我必须感谢我的父母和老师对我的培养,感谢机房里的同学与我的交流以及对我的支持和鼓励,还要感谢CCF以及各位出题人们和南山中学等提供了这样一个平台,当然还要感谢命运女神的眷顾。

这是我第四次拿到NOI金牌了,当然这次还带有金杯,虽然在六块IOI金牌的tourist面前还是不值一提。

不得不说这四年NOI,最好的当然还是今年和2013年。今年就不用说了,13年的时候我水平比现在差很多却混到了金牌,其实最主要还是树的计数拿到了90分以及低的令人感动的金牌线。这两年都是在四川,或许四川是我的福地吧。

当然实际上我也大概知道原因,13年的时候,我什么负担都没有,觉得就是来玩玩,因此心态很好莫名其妙的拿了金牌。14年想13年我拿了金牌,于是当然便冲着金牌去,15年高一当然想进队,这两年都有一定的负担,反而就滚粗了。今年反正保送了,负担比前两年小,所以心态也好一些。所以感觉我还是这些负担比较小的比赛反而考的好啊,所以为什么那么多人(包括我)都经常CF、TC什么的贴线暴跌。

喜悦之余当然也有忧伤,作为退役的季节,不少厉害的人都没进队。共价大爷、稳爷爷kpm的滚粗完全出于我的意料之外。我们学校的tty也失误了。absi2011也没有进队。noname由于是D类,以集训队分数忧伤的退役了,有时候进队分数都达到过却不在同一年,也是挺悲惨啊(想想我CTSC2015的分数是不是能进队呢?不过仔细想想好像dls也也经历过一样的悲剧?)。而湖南省选的第二名yml和女生A队Cyan都没有进队。

作为UOJ的管理员,以后很难在榜上看到某些人的名字,看到这些人FST而叹息,看到这些人终于有人AC了某道题而欢呼,也不能在CF、TC上看到这些人的名字了。当我看到UNR上wyy怒虐第二名68分的时候,感觉十分佩服他,却在NOI之后惊闻wyy银牌滚粗。NOI之前的那场SRM,爆零之后kpm还特意安慰过我,然而他也无缘集训队,感觉真是十分忧伤。

在闭幕式结束后,lzz和wyy还和CCF的一些人讨论过NOI的出题问题,大概就是暴力和暴力之间分差过大,而暴力和正解之间分差过小。这一点我也深深的感觉到它对某些人命运的作用。共价爷第一天写了第一题正解,第三题由于没时间只写了一个40分的暴力。然而别人第一题不会正解有95分,第三题可以写个84分的暴力。共价爷分固然比他们低,但是他就真的比这些人弱吗?并不是!他们并不会第一题正解少了5分,然而却因为第三题会一个不那么暴力的暴力,就多了整整44分,连用杜教筛优化成正解都只值16分。实际上无论是CF还是TC这些较为权威的国际网赛,都是尽量使得难题分值大,简单题分值小,而NOI似乎是反过来的,这也是共价爷为什么进不了队的原因之一。

怎么说我UR出的Yist什么的题目顿时被D啦,不过UR毕竟不是选拔性质,这样出后果并不大,而且那题做UR的A只能这样,做B又太水。

然而OI比赛,真正应该出成怎样,并不是说大家希望怎样就是对的,也没有什么依据说一定要难题分值大,简单题分值小,相反有时候做好每一件简单事,不是比做好一件大事情要重要吗?OI比赛真正的最佳形式,或许只有历史的行程能告诉我们答案。

总之NOI已经告一段落,无论结果如何,都应该当做上天给自己的礼物,无论是进队或是回去高考,前途都是广阔的,清华北大不必说,就算是北航北邮这些学校,也是许多学生心中遥不可及的目标,希望集训队员能向着国家队前进,没进队的也能通过高考考进心仪的学校。

完结撒花。

《UOIP十合一》标程已经放出

2016-07-07 16:14:38 By matthew99

《UOIP十合一》解题报告

2016-06-26 19:48:35 By matthew99

题目地址

http://uoj.ac/problem/208

Q&A

羊芳斐、牛芳斐、马芳斐、欧阳芳斐,黄瓜条以及共价大爷是谁?

羊芳斐、牛芳斐、马芳斐、欧阳芳斐,黄瓜条他们都是WC2015小品《时光2》中的角色,黄瓜条当时是由UOJ创始人之一vfleaking扮演的。

共价大爷的ID是zhangzj,是目前雅礼机房的红太阳,神通广大,无所不能,切题如麻,所向披靡。

“中国国家队以7分钟的罚时之差惜败给俄罗斯国家队”是什么典故?

这里影射WF2016上上海交通大学队以7分钟只差败给圣彼得堡州立大学队,作者出此题时WF2016刚结束不久。

每个点的做法

测试点1

容易发现,对于所有$x \rightarrow y$的边,都有$x \le y$,去掉自环后无论怎么选都不会有环,因此答案显然是2的非自环边数次幂。

测试点2

容易发现这张图是由若干个边数很少的连通块组成的,而连通块之间显然是独立的,因此答案就是每个连通块的答案乘起来,而每个连通块的答案显然可以直接暴力算。

测试点3

容易发现这张图每个连通块都只有一个环,而对于一个大小为$x$的环,答案是$2 ^ x - 1$,答案就是所有环的答案乘起来再乘上2的不在环上的点数次幂。

测试点4

容易发现这张图是由很多层组成的,每层最多4个点,且只有相邻两层之间有连边,因此我们直接状压连通性,对于两层之间的转移,可以枚举边的子集之后用Floyd或者是BFS。

测试点5

这个点如果不进行一些猜测,是很难做出来的,我们可以发现这张图每个强连通分量边数都很少,而连接两个属于不同强连通分量的点的边选和不选是没有影响的,因此可以直接将答案乘2,对于每个强连通分量我们直接暴力然后将答案乘起来即可。

什么你不会求强连通分量?因为点数少的令人感动所以直接按定义用Floyd就行了。

测试点6

这个点是一个有向完全图,对于有向完全图,我们考虑枚举最终DAG中入度为0的点是哪一些,令$a_n$表示$n$个点的有向完全图的生成DAG个数,很容易得到递推式:

$a_n = \sum_{k = 1}^{n}{\binom{n}{k}{(-1)}^{k + 1}2^{k(n - k)}a_{n - k}}$。

设$a_0 = 1$,通过递推容易求出答案。

测试点7、测试点8

这个两个点$n$都非常小,且没有重边和自环,同测试点6的思路,设$\mathrm{dp}_S$表示$S$这个子集中的生成DAG个数,那么有递推式。

$\mathrm{dp}_S = \sum_{S\prime \subset S, S\prime \ne S}{{(-1)}^{|S| - |S\prime| + 1}2^{E_{S\prime, S - S\prime}}\mathrm{dp}_{S\prime}}$。

其中$E_{S_1, S_2}(S_1 \bigcap S_2 = \emptyset)$ 表示从$S_1$中某个点连向$S_2$中某个点的边的条数。

设$\mathrm{dp}_{\emptyset} = 1$,通过递推容易求出答案。然而直接做的话时间复杂度是$O(3 ^ n n)$ 的,瓶颈在于$E$的计算。我们考虑倒过来DP,从枚举子集改成枚举超集,也就是我们用$\mathrm{dp}_{S\prime}$来反过来更新$\mathrm{dp}_S$,这样的话对应的$E$的值就很好计算了。时间复杂度降为$O(3 ^ n)$。8号点最多几分钟就可以出解。

如果时间复杂度过高或者剩余时间不够的话,可能只能做出测试点7。

测试点9、测试点10

这两个点的特点是,一开始有一个大小为$k + 1$的竞赛图,接下来所有点都与前面$k$个两两之间存在边(即要么从$a$连向$b$要么从$b$连向$a$)的点连一条方向任意的边(即要么由这个点连去要么由那个点连过来)。

容易发现进行树分解后的树宽度是$k$,且$k$很小(9号点是2,10号点是3)。

我们容易将图树分解成这样:除了根之外,每个点的集合都与父亲之差了一个点。

根据树分解的性质,我们容易设计状压DP,同测试点4,我们状压两两之间的连通性。两个子树之间的合并就是直接合并连通性。对于非根的节点我们枚举那个不在父亲的集合中的点向其他点连的边的子集然后转移,对于根我们直接枚举边的子集转移。这样就可以做出这两个点了。

如果不熟悉图树分解,直接进行一系列的思考也可以想出这两个点的做法。

程序

测试点1

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int ans = 1;
    REP(i, 0, m)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x != y) (ans <<= 1) %= Mod;
    }
    printf("%d\n", ans);
    return 0;
}

测试点2

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 5;

int n, m;

int main()
{
    scanf("%d%d", &n, &m), n /= 10, m /= 10;
    int ans = 1;
    REP(i, 0, 10)
    {
        vector<pair<int, int> > ed;
        REP(j, 0, m)
        {
            int u, v;
            scanf("%d%d", &u, &v), --u, --v, u -= i * n, v -= i * n;
            if (u != v) ed.pb(mp(u, v));
        }
        int tmp = 0;
        REP(j, 0, 1 << SZ(ed))
        {
            static bool f[maxn + 5][maxn + 5];
            memset(f, 0, sizeof f);
            REP(k, 0, SZ(ed)) if (j >> k & 1) f[ed[k].x][ed[k].y] = 1;
            REP(k, 0, n) REP(i, 0, n) if (f[i][k]) REP(j, 0, n) if (f[k][j]) f[i][j] = 1;
            bool failed = 0;
            REP(i, 0, n) REP(j, 0, i) if (f[i][j] && f[j][i]) { failed = 1; break; }
            if (!failed) ++tmp;
        }
        ans = (LL)ans * tmp % Mod;
    }
    printf("%d\n", ans);
    return 0;
}

测试点3

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 100000;

int n;
int fa[maxn + 5];

int lst[maxn + 5];
int pw[maxn + 5];

int main()
{
    scanf("%d%*d", &n);
    REP(i, 0, n) scanf("%*d%d", fa + i), --fa[i];
    pw[0] = 1;
    REP(i, 0, n) pw[i + 1] = (pw[i] << 1) % Mod;
    memset(lst, -1, sizeof lst);
    int cur = 0;
    int ans = 1;
    int cnt = 0;
    REP(i, 0, n) if (!~lst[i])
    {
        int u = i;
        while (1)
        {
            lst[u] = cur++;
            u = fa[u];
            if (~lst[u])
            {
                if (lst[u] >= lst[i])
                {
                    cnt += cur - lst[u];
                    ans = (LL)ans * (pw[cur - lst[u]] - 1) % Mod;
                }
                break;
            }
        }
    }
    ans = (LL)ans * pw[n - cnt] % Mod;
    printf("%d\n", ans);
    return 0;
}

测试点4

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 1000, maxk = 4;

int n, m, K = maxk;
int dp[maxn + 5][(1 << ((maxk * (maxk - 1)))) + 5];

int main()
{
    scanf("%d%d", &n, &m);
    n /= maxk, m /= n - 1;
    dp[0][0] = 1;
    REP(i, 0, n - 1)
    {
        vector<pair<int, int> > ed;
        REP(j, 0, m)
        {
            int u, v;
            scanf("%d%d", &u, &v), --u, --v;
            u -= i * K;
            v -= i * K;
            ed.pb(mp(u, v));
        }
        REP(j, 0, 1 << (K * (K - 1)))
            if (dp[i][j])
            {
                static bool f[(maxk << 1) + 5][(maxk << 1) + 5];
                REP(k, 0, 1 << SZ(ed))
                {
                    memset(f, 0, sizeof f);
                    int cur = 0;
                    REP(u, 0, K) REP(v, 0, K) if (u != v) f[u][v] = (j >> (cur++) & 1);
                    REP(u, 0, SZ(ed)) if (k >> u & 1) f[ed[u].x][ed[u].y] = 1;
                    REP(w, 0, K << 1) REP(u, 0, K << 1) if (f[u][w]) REP(v, 0, K << 1) if (f[w][v]) f[u][v] = 1;
                    bool failed = 0;
                    REP(u, 0, K << 1) REP(v, 0, u) if (f[u][v] && f[v][u]) { failed = 1; break; }
                    if (failed) continue;
                    int nxt = 0;
                    cur = 0;
                    REP(u, 0, K) REP(v, 0, K) if (u != v) nxt |= f[u + K][v + K] << (cur++);
                    (dp[i + 1][nxt] += dp[i][j]) %= Mod;
                }
            }
    }
    int ans = 0;
    REP(i, 0, 1 << (K * (K - 1))) (ans += dp[n - 1][i]) %= Mod;
    printf("%d\n", ans);
    return 0;
}

测试点5

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 110;

int n, m;

bool f[maxn + 5][maxn + 5];
int ori[maxn + 5][maxn + 5];

int N = 0;
int bel[maxn + 5];

int main()
{
    scanf("%d%d", &n, &m);
    REP(i, 0, m)
    {
        int u, v;
        scanf("%d%d", &u, &v), --u, --v;
        f[u][v] = 1;
        ++ori[u][v];
    }
    REP(i, 0, n) f[i][i] = 1;
    REP(k, 0, n) REP(i, 0, n) if (f[i][k]) REP(j, 0, n) if (f[k][j]) f[i][j] = 1;
    int ans = 1;
    memset(bel, -1, sizeof bel);
    REP(i, 0, n) if (!~bel[i])
    {
        vector<int> all;
        REP(j, 0, n) if (f[j][i] && f[i][j]) all.pb(j), bel[j] = N;
        ++N;
        vector<pair<int, int> > ed;
        for (auto x : all) for (auto y : all) if (x != y) REP(j, 0, ori[x][y]) ed.pb(mp(x, y));
        int tmp = 0;
        REP(j, 0, 1 << SZ(ed))
        {
            static bool g[maxn + 5][maxn + 5];
            memset(g, 0, sizeof g);
            REP(k, 0, SZ(ed)) if (j >> k & 1) g[ed[k].x][ed[k].y] = 1;
            for (auto w : all) for (auto u : all) if (g[u][w]) for (auto v : all) if (g[w][v]) g[u][v] = 1;
            bool failed = 0;
            for (auto u : all) for (auto v : all) if (u != v && g[u][v] && g[v][u]) { failed = 1; break; }
            if (!failed) ++tmp;
        }
        ans = (LL)ans * tmp % Mod;
    }
    REP(i, 0, n) REP(j, 0, n) if (bel[i] != bel[j]) REP(k, 0, ori[i][j]) (ans <<= 1) %= Mod;
    printf("%d\n", ans);
    return 0;
}

测试点6

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 110;

int n;

int C[maxn + 5][maxn + 5];
int pw[maxn * maxn + 5];

int a[maxn + 5];

int ans;

int main()
{
    REP(i, 0, maxn + 1)
    {
        C[i][0] = 1;
        REP(j, 1, i + 1) (C[i][j] = C[i - 1][j - 1] + C[i - 1][j]) %= Mod;
    }
    pw[0] = 1;
    REP(i, 0, maxn * maxn) pw[i + 1] = (pw[i] << 1) % Mod;
    a[0] = 1;
    REP(i, 1, maxn + 1)
    {
        a[i] = 0;
        REP(j, 1, i + 1)
        {
            int tmp = (LL)a[i - j] * pw[j * (i - j)] % Mod * C[i][j] % Mod;
            if (j & 1) (a[i] += tmp) %= Mod;
            else (a[i] -= tmp) %= Mod;
        }
    }
    scanf("%d", &n);
    ans = (a[n] + Mod) % Mod;
    printf("%d\n", ans);
    return 0;
}

测试点7、测试点8

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

#define clz __builtin_clz
#define ctz __builtin_ctz
#define bcnt __builtin_popcount
#define bpar __builtin_parity  

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 20;

int n, m;
int from[maxn + 5], to[maxn + 5];
int dp[(1 << maxn) + 5];

int ans = 0;

int nxt[maxn + 5];

int bc[(1 << maxn) + 5];

int oriS;

void dfs(int x, int S, int mul)
{
    if (x == n)
    {
        if (S != oriS) (dp[S] += mul) %= Mod;
        return;
    }
    dfs(nxt[x], S, mul);
    dfs(nxt[x], S | (1 << x), ((LL)-mul << (bc[to[x] & oriS])) % Mod);
}

int main()
{
    scanf("%d%d", &n, &m);
    REP(i, 0, 1 << n) bc[i] = bcnt(i);
    REP(i, 0, m)
    {
        int u, v;
        scanf("%d%d", &u, &v), --u, --v;
        from[u] |= 1 << v;
        to[v] |= 1 << u;
    }
    dp[0] = 1;
    REP(i, 0, 1 << n) if (dp[i])
    {
        oriS = i;
        int now = n;
        for (int j = n - 1; j >= 0; --j) 
        {
            nxt[j] = now;
            if (~i >> j & 1) now = j;
        }
        dfs(now, i, -dp[i]);
    }
    ans = dp[(1 << n) - 1];
    (ans += Mod) %= Mod;
    printf("%d\n", ans);
    return 0;
}

测试点9、测试点10

以下是测试点10的程序,测试点9的程序和测试点10的程序的区别参见代码注释。

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

const int maxn = 1100;

const int per = 3;//测试点9中per = 2
const int maxmask = 1 << (per * (per + 1));

int n, m;
int N;

vector<int> chd[maxn + 5];

vector<int> belong[maxn + 5];

int fa[maxn + 5];
map<int, int> rk[maxn + 5];
vector<int> what[maxn + 5];
int w[maxn + 5];

int dp[maxn + 5][maxmask + 5];
int tr[maxmask + 5];
bool ok[maxmask + 5];

vector<pair<int, int> > rt_ed;

int id[per + 5][per + 5];

inline void deal(int *f)
{
    REP(w, 0, per + 1) REP(u, 0, per + 1) if (f[u] >> w & 1) f[u] |= f[w];
}

inline void masktoa(int x, int *f)
{
    REP(u, 0, per + 1) f[u] = 0;
    REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v && (x >> id[u][v] & 1)) f[u] |= 1 << v;
}

inline int atomask(int *f)
{
    int ret = 0;
    REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v && (f[u] >> v & 1)) ret |= 1 << id[u][v];
    return ret;
}

void dfs(int x)
{
    memset(dp[x], 0, sizeof dp[x]);
    dp[x][0] = 1;
    for (auto y : chd[x]) dfs(y);
    static int sum[maxmask + 5];
    memset(sum, 0, sizeof sum);
    if (~fa[x])
    {
        REP(i, 0, maxmask) if (dp[x][i])
        {
            REP(j, 0, 1 << per)
            {
                static int f[per + 5];
                masktoa(i, f);
                REP(u, 0, per) if (j >> u & 1)
                {
                    if (w[x] >> u & 1) f[per] |= 1 << u;
                    else f[u] |= 1 << per;
                }
                deal(f);
                if (!ok[atomask(f)]) continue;
                int mask = 0;
                REP(u, 0, per) REP(v, 0, per) if (u != v && (f[u] >> v & 1)) mask |= 1 << id[what[x][u]][what[x][v]];
                if (ok[mask]) (sum[mask] += dp[x][i]) %= Mod;
            }
        }
        static int nxt[maxmask + 5];
        memset(nxt, 0, sizeof nxt);
        REP(i, 0, maxmask) if (dp[fa[x]][i]) REP(j, 0, maxmask) if (sum[j] && ok[tr[i | j]]) (nxt[tr[i | j]] += (LL)dp[fa[x]][i] * sum[j] % Mod) %= Mod;
        memcpy(dp[fa[x]], nxt, sizeof dp[fa[x]]);
    }
    else
    {
        REP(i, 0, maxmask) if (dp[x][i])
        {
            REP(j, 0, 1 << SZ(rt_ed))
            {
                static int f[per + 5];
                masktoa(i, f);
                REP(k, 0, SZ(rt_ed)) if (j >> k & 1) f[rt_ed[k].x] |= 1 << rt_ed[k].y;
                int mask = atomask(f);
                mask = tr[mask];
                if (ok[mask]) (sum[mask] += dp[x][i]) %= Mod;
            }
        }
        memcpy(dp[x], sum, sizeof dp[x]);
    }
}

int main()
{
    int cnt = 0;
    REP(u, 0, per + 1) REP(v, 0, per + 1) if (u != v) id[u][v] = cnt++;
    REP(i, 0, maxmask)
    {
        ok[i] = 1;
        REP(u, 0, per + 1) REP(v, 0, u) if ((i >> id[u][v] & 1) && (i >> id[v][u] & 1)) ok[i] = 0;
        static int f[per + 5];
        masktoa(i, f);
        deal(f);
        tr[i] = atomask(f);
    }
    scanf("%d%d", &n, &m);
    memset(dp, 0, sizeof dp);
    REP(i, 0, per * (per + 1) >> 1)
    {
        int u, v;
        scanf("%d%d", &u, &v), --u, --v;
        rt_ed.pb(mp(u, v));
    }
    REP(i, 0, per + 1) belong[i].pb(0), rk[i][0] = i;
    fa[0] = -1;
    N = 1;
    REP(i, per + 1, n)
    {
        w[N] = 0;
        what[N].clear();
        REP(j, 0, per)
        {
            int u, v;
            scanf("%d%d", &u, &v), --u, --v;
            if (u == i) w[N] |= 1 << j, what[N].pb(v);
            else what[N].pb(u);
        }
        vector<int> &all(what[N]);
        assert(!all.empty());
        vector<int> now(belong[all[0]]);
        REP(j, 1, SZ(all))
        {
            vector<int> nxt;
            set_intersection(ALL(now), ALL(belong[all[j]]), back_inserter(nxt));
            now = nxt;
        }
        assert(!now.empty());
        fa[N] = *now.begin();
        chd[fa[N]].pb(N);
        belong[i].pb(N);
        rk[i][N] = SZ(all);
        REP(j, 0, SZ(all)) 
        {
            int &u = all[j];
            belong[u].pb(N);
            rk[u][N] = j;
            u = rk[u][fa[N]];
        }
        ++N;
    }
    dfs(0);
    int ans = 0;
    REP(i, 0, maxmask) (ans += dp[0][i]) %= Mod;
    (ans += Mod) %= Mod;
    printf("%d\n", ans);
    return 0;
}

《共价大爷游长沙》解题报告

2016-06-26 19:37:35 By matthew99

题目地址

http://uoj.ac/problem/207

Q&A

题目名称怎么来的?

本题题名是跟风另外两道题目的,另外两道题目的题目名见题面第一句话。

共价大爷和小L是谁?

共价大爷的ID是zhangzj,是目前雅礼机房的红太阳,神通广大,无所不能,切题如麻,所向披靡。

小L的ID是luoyuchu,他是共价大爷的忠实粉丝。

长沙市真的总是在不断的施工吗?

的确是的,比如说从雅礼到我现在住的地方就有多处施工点。雅礼操场目前在施工,已经挖出了多座古墓,甚至曾经被以为是太守坟。

算法一

直接上暴力,每次对于所有路径将它经过的边边权加一,然后看看询问的路径边权是否为$|S|$,时间复杂度$O(n ^ 2m)$,期望得分10分。

算法二

如果没有加边删边操作和删除点对操作,那么我们可以维护当前的可行路径,每次可以用$O(\log n)$或者$O(1)$时间进行树上路径求交以及判断一条边是否在路径上,如果使用倍增,则时间复杂度为$O((n + m)\log n)$,期望得分20分,结合算法一可以获得30分。

算法三

如果没有加边删边操作,那么我们可以用动态树或者树链剖分等支持链修改单点询问的结构,维护每个点被路径经过的次数,每次看看询问边的两个端点是否都被经过了$|S|$次。如果使用LCT那么时间复杂度$为O((n + m) \log n)$,期望得分40分,结合算法一可以获得50分。

算法四

对于没有加边删边操作的数据,我们还有一种做法,我们对所有点对建一棵线段树,每个节点存子树中所有路径的交,每次操作的时候都很容易在线段树上update解决,如果用ett序或者dfs序加ST表,那么每次可以在$O(1)$的时间内update,总时间复杂度为$O(n \log n + m \log m)$,期望得分40分,结合算法一可以获得50分。

算法五

对于$|S| \le 10$的数据,我们可以每次询问的时候进行和算法三类似的操作,每次暴力加入所有路径维护每个点被经过的次数再用同样的方法询问,期望得分20分,结合前面的算法可以获得70分。

算法六

我们注意到,一条$x$到$y$路径被所有路径经过,当前仅当以$x$为根时,所有路径的端点都恰好有一个在$y$的子树中。这样,我们对每一个路径随机一个权值,然后每次加入删除路径时,将两个段点的点权异或上这个权值,然后用动态树维护子树权值异或和,每次询问对应子树内的权值异或和是否是当前所有路径的权值异或和,权值如果设为$10 ^ 9$级别,就基本不可能出错了。时间复杂度$O((n + m) \log n)$,空间复杂度$O(n)$,可以通过全部数据。

算法七

这题罗哲正同学提出了另外一种做法,我们可以将权值异或在一条链上,新加入一条边的时候,新形成的环上必然有一条边会被删除,假设这条边是$u$和$v$之间的边。我们发现,将这条被删除的边的权值异或到删除这条边后$u$和$v$之间的路径上,就可以更新新树上对应的权值了。时空复杂度均和算法六一样,也可以通过全部数据。

关于“鏖战表达式”错误复杂度算法水过现象的看法

2016-02-27 21:42:39 By matthew99

WC2016鏖战表达式一题,松爷(王逸松,鏖战表达式出题人)在WC上讲了复杂度为每次操作$O(k + \log n)$的做法,即所谓的树(套树)$^*$。然而民间流行一种直接用treap维护的,并把优先级比较定为比较运算符,运算符相同则根据子树大小用概率比较的做法,复杂度为$O(k\log n)$,为什么呢,因为我们先加入一堆1,再加入一堆2,一直到一堆k,每一次新加入一堆运算符,不能改变前面运算符的形态,因此复杂度是$O(k \log n)$,直接提交会得到七十到八十的分数,由于此题数据强度不大,因此稍微根据数据进行修改一些实现细节即可水过。

松爷与我曾多次提到过此事,我也认为此事十分不妥,作为一个很好的数据结构题,留下的却是一堆的水过,以及不断的有新人抱着以为这是正确的做法的心态去写,最后却死活过不去而只能跟着水过的事情。幸运的是考场上并没有人水过。

本题作为一道特殊的题,难以像现在大部分UOJ上的题一样支持hack和extra test,甚至考场数据和grader都使用了特殊的方法加密,因此想要阻止这种现象只要两条路,一是通过@vfleaking等管理员来手工添加一些extra tests强行卡掉复杂度错误的算法,二是靠大家的理解和自觉,理解这种算法的不正确性,并自觉不使用这种算法。

这里我提醒一下大家不要再陷入错误做法的泥潭中。

对于那个$O(k \log n)$的做法,本人也进行了一些改进,可以参见http://uoj.ac/submission/50137注意,提交统计里面显示的我的提交是我之前跟着大家水过的程序,并不是这份代码。

我大概是在merge和split的时候进行了一些rotate,具体复杂度无法给出详细证明,但是感觉是$O(k + \log n)$的可能性还是比较大的(当然也有可能是$O(k\log n)$,或者甚至$O(\sqrt{k}\log n)$, $O(k \log k + \log n)$, $O(k \log \log n + \log n)$这些鬼畜的复杂度233,大家还可以继续脑洞),大家可以感受一下我改动的地方。如果觉得我的做法也不靠谱可以学习松爷std程序的做法。如果有谁卡掉了我的做法或者是证明了我的做法的复杂度的确是$O(k + \log n)$,欢迎与我讨论。

清华集训总结

2015-12-11 14:08:29 By matthew99

这是集训队作业的一部分。

我从主观条件和客观条件上来总结一下这次清华集训吧。

首先主观上,我有很多该拿到的分没有拿到。

第一天第二题完全可以注意到精度问题,只要注意到了精度问题,很容易发现精度误差会不断变大,然而我当时只是简简单单的把double改成long double看差异,这是十分naive的做法,看着数从整数掉下去又突变回来而我却习以为常,作为集训队员连简单的精度一时都没有应该感到羞耻......充分的体现出我在考场上考虑的东西实际上有多么欠缺。

第二天的第二题,我势能公式推对了,但是由于我用叉积算面积,没有除以二,而后面推的时候我以为它就是面积。物理功底不行的我在考场上更倾向于怀疑自己的物理水平而不是代码能力,最终否定了自己已经推出来的正确结论,这个时候我莫名其妙的以为提答题是全对才有一个点的分,这个错误我在ZJOI day2也犯过,不然应该能超过标准分。原因都是看到了评分规则,但是由于当时并不想做提答题就没管,等到想做的时候却把这个东西抛到脑后了。所以最后1h挣扎T2,当时很着急也不知道在搞什么,最后当然是只有前一个半小时有得分,最后两个半小时一分没得,由于大部分集训队员恰好这天都考挂了并且比我还惨,我意外的没有大崩盘,如果大家这天都发挥正常的话,我第二天结果应该比第四天更差。总之这一天不仅暴露出我写代码时的粗心,同时还暴露出我非常糟糕的物理能力。实际上我物理考出过100分拿40分的好成绩......

第三天前两题写完之后还有将近2h,觉得自己rank1定了,于是慢悠悠的检查前两题慢悠悠的做T3,而且我又!没!看!到!有!部!分!分!,这次很简单,看到“10个测试点,每个测试点1分”的时候,我想,不是每个测试点10分吗,不然这题满分不是10分?实际上这个指的是每个10分的点有1分的部分分,这说明我当时宁愿怀疑出题人也不怀疑自己的理解能力,这是很不对的,因为如果出题人错了肯定会更正,然而我过了一阵子就不记得有这回事了。T3做了很多分觉得自己肯定能标准分,所以最后都是一种做一个点是一个点的态度,慢慢的做,最后看到榜才如梦初醒,发现我T3基本上是全场花了很长时间的选手中做得最糟糕的,花了别人两倍的时间却比大家少十多分。而且提答题也因为自己的一个粗心大意丢了一个不该丢的1分,如果自己当时抱着一种要AC这道题的态度,以集训队选手的平均速度去做T3,应该完全有时间可以在考场上拿到100(99)分。

第四天是我发挥的十分糟糕的一天,然而导致我出问题的原因,却是我一直以来都犯了的错误。这一天我看T1,然后想了很久,想到一个错误算法开始写的时候就发现错了,然而影响了心情,后面时间过得越久人的思维能力就越差,而且对题目整体把握越糟糕,觉得这是一个很难的题,最后搞得只能写暴力,接近3h过去了却只有暴力分,相反其他人基本上都用了我一半的时间拿到了100分。看完T2我整个人急了,T2是整个清华集训中和第三天的第一题并列的最水的两题之一,然而我却2h多才开始看,就想赶快A掉,然而欲速则不达,最后还剩十多分钟的时候过了考场上的全部数据,这个时候我纠结于是否检查前两题,然而当时我觉得第一题拍过,虽然对拍不是很强但是至少还是拍过的,第二题大数据就是极限数据而且应该属于极限数据强度不错,而且当时由于不知道T3是什么题,就赶紧去看T3,生怕T3是一个所有人都会做的傻逼题,看完之后发现根本没时间做就交样例得了一份。接着还剩一分钟的时候发现第二题写错了,当时我完全被水淹没不知所措,完全属于一种GG的状态,考试便结束了,实际上当时只需要加上几个+1什么的就可以了,冷静下来还是有时间改对的。最后排名非常非常靠后,只能靠前三天的成绩保持一个微弱的优势。第四天最大的问题在于没有开场看三个题并稍微想一下,其实我四天都没有看三个题,但是前三题第一题都是我能很快想出90到100分算法的一个题,第四天我却由于失误没有想出来,这直接导致我后两题看的很晚,也导致了我T2做完不敢检查,因为我怕T3是傻逼题,实际上如果T3真是傻逼题,那么我可能这一天真的会把总名次一下子弄得很差了,而且T1在没看后两题的情况下,死磕那么长时间是非常不划算的,如果后两题都是需要很长时间但是花了时间却很好拿到满分或者高分的题,我这场基本上就没戏了,没有合理考试策略是我最大的问题,前三场完全只是运气,用这种高风险的方法恰好没有出很大问题。其次,第一题我想错了方向,整个人陷了进去,思维没有打开,而且由于紧张基本没法打开,如果第一题是在我平时做题的时候见到,那么想出来的概率还是很大的,考试紧张也是我这天的问题。第二题写错,是我没考虑周全,这也是我很大的一个问题,而且,写代码犯小错误的积累导致效率不高,想题的时候容易分心导致的效率不高,我现在无法具体想起来的许多小失误,也多多少少促进了我的滚粗。

因此,这次清华集训暴露了我许多能力的不足,做事太浮躁也是个主要问题,导致我代码写不对或者调太久,而且比较急的时候思维能力也大打折扣,可能也的确导致了一些simple的东西居然没有在考场上想出来。因此,一定要让自己做事更加冷静,更加沉下心来,每次犯错误,不管是多么小的错误,都要注意并且尽量下次避免,甚至具体到某个具体算法或者具体的常用代码的某个具体的地方,有时候一些无关紧要的习惯的积累,最后就是几十上百分的差距。

接着我再说说客观上我对整个清华集训的看法。

清华集训由于有四场考试,当然能很好的体现出每一位集训队员的水平,这次清华集训的分,当然分为没拿到的分和拿到的分,但是我所有拿到的分,却没有什么非常值得一提的,基本都是看完马上就知道怎么拿了,没拿到的分也基本上是自己的粗心大意或者时间的紧缺所致,如果时间允许,大部分的分应该都能拿到。清华集训的分,基本上要么是trivial的,要么就是会某个东西或者做过某个题就能轻轻松松获得,没做过要获得就难得多。清华集训有两个物理题,体现出了物理以及微积分水平的重要性,比如第三天第二题,会了微积分就是一个很trivial的DP,其实国内的DP题一般都是合成题,就是在DP之前还要用一些别的知识点,再比如NOI的最后一题,DP只是一个部分,网络流是另一个部分,难点往往在于你必须两个东西都会,相比之下Topcoder和Codeforces的DP题,一般都是经过一些转化才能DP,或者DP之后利用一些性质优化,或者需要设计一些特别的状态,总之难点在于有些题,可能你根本不会设状态或者转移,有些题可能方程列出来却效率太低,想AC需要一定的水平。其实不仅限于DP,这归根结底反映出一个国内OI和国际上其他赛事的差异,国内的难题,要么都是代码量特别大的,要么就是很多东西合成起来,或者需要对某个特定算法及其优化很深入的研究,而国际上的难题,很多都是代码短小,考点也只有一两项,最终算法可能非常简单并且不需要什么优化,但是却需要对问题很深入的分析,对于这个差异,个人认为两者各有所长,应该相互借鉴和促进。OI的赛制也与其他competitive programming的比赛有所不同,其他的要么就是必须AC一个题,要么就是分为若干个subtask,而国内通过一个测试点就有分,有时候一个无解就会有10分,一个样例就会有1分,而且其他的比赛,有些要求算法每一个地方都不能写错,不然就相当于什么都没做,而国内相对来说比较良心,比如第三天第二题,只要会势能公式,随便写一个三分就能有很多分,NOI的最后一题,只要算法在随机情况下效率不错,就算在极端情况下可能运行时间很长,也不至于只拿到暴力分,基本上花的时间不容易白白浪费,但是也并不意味着什么都不知道乱写一通就会有分。本次清华集训我也看到了很多新的东西,比如大量的交互题和提交答案题,都十分有趣,我也比较喜欢,突破了传统题太多的枷锁,这一方面得益于UOJ的通用性,另一方面也顺应了IOI等国际赛事上非传统题题多的潮流。

分金币问题

2015-10-26 15:56:32 By matthew99

今天的模拟题给了我们一次刻骨铭心的经历。

题目是这样的,n个人分m个金币,每个金币完整不可分。从第一个人开始,每个人提出一个分金币方案,如果投票同意的人超过半数,那么这个方案就通过,否则这个人将被杀掉。

现在假设每个人都很聪明。每个人尽可能的保证生命。如果可以保证生命,那么他希望自己分到的金币最多。如果不能过获得更多金币,就会希望别人死。如果一个人知道自己肯定要死,那么他对别人的方案会投反对票。

假设有6个人,100个金币。

对于一个人,显然分到所有金币。

对于两个人,显然第二个人必死,第一个人分到所有金币。

对于三个人,他会给自己留100个金币,其他人不分,第二个人想,自己不同意就会死,第一个人显然不会同意,而第三个人自己的方案显然会同意,所以有两个人同意,方案通过。第三个人获得100个金币,前两个人都没有金币。

对于四个人,他会给自己98个金币,第一个人和第二个人各1个金币,前两个人想,如果我不同意而给第三个人决定,那么自己就不会有金币了,因此会同意,而第四个人显然会同意,所以有三个人同意,第四个人获得98个金币,前两个人各1个金币,而第三个人得不到金币。

对于五个人,他会给自己97个金币,第三个人1个金币,第一个或者第二个人2个金币,这样第三个人肯定同意,给了2个金币的那个人也会同意,第五个人自己也同意,所以分金方案是第五个人97个金币,第三个人1个金币,第一个或者第二个人2个金币。

对于第六个人,矛盾就出现了。

考虑给自己留97个金币,第四个人1个金币,第一个和第二个人各1个金币。 自己和第四个人肯定会同意,而第一个和第二个人会不会同意呢。

第一个人和第二个人的想法是,如果自己不同意,那么自己可能一分钱没有,也可能会得到两块钱,如果他们都想保全这一块钱,那么就都会同意,反之如果有人想奋力一搏,觉得还不如不同意,说不定有两块钱,那么大家都不会同意,出现了矛盾。

如果第一个人和第二个人都清楚第五个人的选择,比如第一个人和第五个人关系特别好,他知道第五个人肯定会给他,而第二个人也清楚这一点,那么,如果是上面这样分,只会有第一个人同意,第六个人就会被杀死。

这个时候正确方案应该是自己留96,第二个人留1,第四个人留1,第三个人留2。 如果第六个人想:“唉我还这么年轻,真的不想死啊,钱是身外之物我不想要了!”,那么他就会做出这样的决策:

自己留94,第四个人留1,第三个人留3,第二个人或者第一个人留3,这样给3个金币的人肯定会同意,另外三个也会同意,自己肯定死不了。

五个人的情况似乎是小学奥数的经典内容?因为五个人的情况是没有争议的。

事实上,我考场上实现的,包括出题人的数据,都是第二个想法,就是大家都是先知,都可以预测别人的想法。然而也有相当一部分人写的是第一种想法,而第三种没听说有人写过。

实际上题面也什么也没说清楚,所以才会导致这么大的撕逼。

如果是CF或者TC遇到这种情况当然unrated咯。

但实际上大家为此撕逼了一中午和一下午233333333333333333333。各抒己见,感觉还是很好玩很刺激。

实际上如果大家都可以预测别人的想法,那两个人玩起石头剪刀布,究竟会怎么出呢,估计两个人的大脑都栈溢出咯......

事实上撕逼这种问题也不是第一次,CTSC day2的前夕和吉丽、松爷、猪猪侠和DZY也为此撕逼过。详见http://jiruyi910387714.is-programmer.com/posts/94162.html

公平分配中的争议还真是多。

共 17 篇博客