UOJ Logo matthew99的博客

博客

清华集训总结

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

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

app管理器的乱搞经历

2015-08-11 09:06:46 By matthew99

昨天下午改完app管理器之后发现dwjshift的程序特别快,然而是个乱搞,便造了个数据hack了。之后觉得他的思路很有趣,便新建了一个dwjshift_fan的账号优化他的算法,代码风格都是我自己的然而并没有多少人认出那是我(大雾。

最后137ms过了那道题,我的hack数据也跑得很快,自己试了试好像也没能hack。算法大概就是每次用dfs实现的SPFA暴力找环然后确定方向之后缩起来,注意重边的处理。加了很多优化之后才跑到137ms。欢迎有兴趣的同学前来hack:http://uoj.ac/submission/24834

...妈妈我终于会做动态仙人掌IV了

2015-05-16 23:10:45 By matthew99

妈妈我终于会做动态仙人掌IV了!!

鼓掌熊

由于mx此时刚好正在滚粗搞文化课,为了战这道题,可谓历尽辛酸(大雾)。迟到缺交作业忘搞卫生已经把我罚得在班上没脸做人了。

傻逼mx还因为手算算错答案怀疑标程正确性制造了两个恶意hack。看来要被封号了QAQ

不能作为除出题人之外第一个AC的人真是太遗憾了,膜CHXER!

UPD:出了点奇怪的事情。

mx的仙人掌 题解

2015-03-27 11:59:14 By matthew99

题目地址

http://uoj.ac/problem/87

算法一

估计大家应该不会被仙人掌吓到而直接$\mathrm{gg}$了,至少先会考虑任意图的情况。

妈妈我不会处理图的问题怎么办?

有$5\%$的数据$n \le 7, \mathrm{tot} \le 7$,可以用各种方法(如枚举所有路径)水过去。

算法二

有$10\%$的数据$n, \mathrm{tot} \le 5000$。

最短路算法

由于时限和数据都很令人感动,这些数据其实用$\mathrm{dijkstra}$甚至$\mathrm{SPFA}$(我多良心没有卡哦!(大雾))都能跑得过去......

更好的做法

考虑仙人掌图的$\mathrm{dfs}$遍历树,有很多条前向边,每条前向边$x \rightarrow y$对应一个环,不妨设这个环的根为$y$,每当我们找到一条前向边$x \rightarrow y$时,通过从$x$不断回到$\mathrm{dfs}$树上的父亲直到到达$y$,我们可以取出这个环上所有点,并且容易得出环的长度,对所有点除了$y$以外的点都标记一下它所在的环编号。

$\mathrm{dfs}$完以后,对每个点考虑他到根的距离,如果他没有环标记那么距离就是父亲到根的距离加上自己到父亲的边的长度。否则就是他到环的根$y$的两条路径长度(一个是$\mathrm{dfs}$树上的距离(这个用两个点离根的距离减一减就求出来了),另一个是环的长度减去树上距离)中的较小值加上$y$到根的距离。

对每个询问的每个询问点,我们都遍历一遍,时间复杂度为$O(n\times \mathrm{tot})$。

算法三

有$10\%$的数据$Q \le 10$。我们考虑对每一次询问直接$\mathrm{dfs}$一遍求得答案。

用$\mathrm{maxlen}_x$表示从$x$出发到以$x$为根的子仙人掌(即在原图中删去$x$之后不与根相连的点和$x$的导出子图)的某个询问点的最短路的最大值(如果没有询问点可以设为-∞),对于$x$的某个$\mathrm{dfs}$树上的孩子$y$,如果从$x \rightarrow y$的边$e$是割边那么就直接用$\mathrm{maxlen}_y + w_e$更新$\mathrm{maxlen}_x$,$w_e$表示$e$的权值,否则如果$x$成为了边$e$所在环的根那么我们要把环取出来,直接枚举换上的点然后用他的$\mathrm{maxlen}$加上他到$x$的两条路径长度的最小值更新$\mathrm{maxlen}$即可。

考虑更新答案,所有询问点的$\mathrm{maxlen}$显然可以用来更新答案,对一个点的两个不同的子仙人掌(即在原图中删去$x$之后不与根相连的点的一个连通块和$x$的导出子图),他们的$\mathrm{maxlen}$之和加显然也可以用来更新答案(求出一个子仙人掌$y$的$\mathrm{maxlen}_y$之后,先用$\mathrm{maxlen}_y + \mathrm{maxlen}_x$更新答案,再用$\mathrm{maxlen}_y$更新$\mathrm{maxlen}_x$即可)。现在还需要考虑经过一个环的路径的情况。

经过一个环的最短路径一定是由两条环以外的路径(可以长度为0)和一条环上的路径组成,我们按顺序取出环上的边,并且复制一份接在后面,形成一条链。对于链上的点$i$,记$mathrm{len}_i$为链的头部到它的路径的长度,$\mathrm{val}_i$为它对应的点的$\mathrm{maxlen}$,那么经过这个环的最长的最短路径即为$\mathrm{max}\{\mathrm{val}_i + \mathrm{val}_j + \mathrm{len}_i - \mathrm{len}_j\}(0 \le \mathrm{len}_i - \mathrm{len}_j \le \frac{\mathrm{cirlen}}{2})$,其中$cirlen$表示该环的长度,容易用单调队列维护,时间复杂度为$O(Qn)$,如果用线段树时间复杂度为$O(Qn\log n)$。

算法四

对于树的情况,可以使用虚树。

虚树的建立方法之一是,对询问点按$\mathrm{dfs}$序排序,然后取出他们相邻节点间的$\mathrm{lca}$,接着再按$\mathrm{dfs}$序排序,接着扫一遍,维护一个栈,如果当前栈顶的节点是当前节点的祖先那么就连一条边,边权为它们之间的距离,否则将栈顶的节点弹出栈。这只是一种建立方法。

然后在虚树上$\mathrm{DP}$即可。

时空复杂度均为$O(n\log n)$(今后视tot = $O(n)$)

此外时间复杂度可以通过更大的代码复杂度降为$O(n\alpha(n))$或者$O(n)$,具体不再赘述,我多良心没有要求大家写这些算法哦!(大雾)。

算法五

对于树的情况,还可以用树分治解决。

一种较方便的树分治的做法是,先建立好树分治结构,然后对每一个询问,先将点去重。接着对于每一个树分治结构中的节点(对应一棵子树$T$),我们只考虑该询问中所有在$T$中的点。直接用两个属于不同子树的点到根的距离和的最大值更新答案即可(要注意判一下询问点是根的情况)。接着对于它的每一个孩子节点,递归处理下去,注意我们只要保留该询问中在这个孩子节点中的点。

但是这个做法由于要预先存储结构,时间空间常数都比较大。

还有一种做法是,询问和树一起分治,这个很好理解,无非就是把两个过程合并了,每一次要处理的是一棵子树和一个询问序列,这个序列只保留所有存在询问点在该子树中的询问,并且每个询问只保留在该子树中的询问点,然后处理询问的方法如同前面所述。

时空复杂度均为$O(n\log n)$。

UPD:树上迭代两次求最远点即可,最远点可以直接枚举然后$\mathrm{lca}$,呜呜呜我出题的时候怎么就脑抽了,30分送大家吧,前面的算法就当做口胡......

算法六

对于树的情况,如果你只会虚树或者树分治,对于仙人掌你肯定也只能这么做了。

如果我们能建立“虚仙人掌”,肯定可以解决这个问题。思考熊

我们想一想就能想清楚虚仙人掌的一种最笨但是也绝对正确并且可以通过这题的建立方法,先按$\mathrm{dfs}$序排序,再求出相邻节点间的$\mathrm{lca}$(注意这里$\mathrm{dfs}$序和$\mathrm{lca}$都是在它的$\mathrm{dfs}$遍历树上做,后面的深度也是),接着我们取出每一个点所在环的根和环上最深的点,再排序并取一遍相邻节点$\mathrm{lca}$,然后建出$\mathrm{dfs}$树上的虚树,接着再每个环的最浅的点和最深的点之间连边,边权为它们原先连的边的权值(它们原先显然一定连了边),由于我们要求的是最短路径,其实这里连它们之间在环上走的两条路径的较小值也没有关系,不会对任何最短路径造成影响,这一个画一画图就知道了。

根据上述结论,连虚树上的边时,可以将虚仙人掌上的环边和树边一视同仁,统统连它们两个端点在原仙人掌上的最短路径长度。但是这个最短路径长度和树上不同,树上可以直接用离根的距离减一减,仙人掌上就不是这么简单了,离根的最短路长度不具有可减性。是,我们可以用动态仙人掌。但是这样代码复杂度太高。我们考虑一下,如果树上有一个值也不具有可减性,比如路径边权最小值,你会怎么弄?一种方法就是倍增。对仙人掌也这么弄,考虑动态仙人掌维护生成树法的思想,我们记录每个点到它第$2 ^ i$级祖先的最短路长度,同时如果有一个环不完全包含这条路径,且包含第$2 ^ i$级祖先的父亲(显然这个祖先如果是根就不可能存在满足条件的环),那么我们就记录一下这条路径上深度最大的在这个环上的点,合并的时候就根据这个环是走树边还是走非树边来求出最短路,非常简单。

UPD:好像可以记录到根的距离,然后用特殊的方法处理一下就可以直接减了。总之实现上有各种技巧优化时间复杂度和代码复杂度,感觉标程就是个逗比啊TAT......

实际上,std的方法和上述方法有细节上的差异,如果$x$本身连了一条非树边,包含了整个路径及$2 ^ i$级祖先的父亲,那么他也将被记录,但是这样合并的时候将会多出一些小麻烦,因为一个环可能会更新一条路径两次,用后一次更新覆盖掉前一次更新即可。但是如果不用这个方法,$\mathrm{dfs}$树的叶子节点连接的非树边也要特判。不过这些东西都是一些细节问题,稍微处理一下即可。

总之这个算法可以非常愉悦的跑出100分, 时空复杂度均为$O(n\log n)。$鼓掌熊

提交记录在这里

算法七

对于树分治,我们显然也可以想办法把它搞到仙人掌上,也就是用仙人掌分治来解决问题,实现细节和树分治大同小异,每一次去掉一个点时,先把它弄成仙人掌的根,然后断开它连的所有割边,以及所有它所在环的环边,每一次选一个进行上述操作后,剩下来的子仙人掌中大小最大的最小的点来分治即可(其实为了方便我写的程序不一定能取出最小,但绝对剩下来的子仙人掌中大小最大的不超过$\frac{n}{2}$)。

处理每个询问时,根可能连着不少的环。对一个点(除了根),如果在某一个环$C$上或者某一个在$C$上的点(除了根)的子仙人掌,那么称这个点属于环$C$。,直接用两个属于不同子仙人掌或者环的点到根的距离和的最大值更新答案即可(同样要注意判一下询问点是根的情况)。但是我们还要注意属于同一个环但不是环上同一个点的子仙人掌的点,他们两两之间也要更新答案,这个用单调队列很好解决。

时空复杂度均为$O(n\log n)$。鼓掌熊

解法八

松爷给出了另外一种解法,详见http://wangyisong1996.is-programmer.com/user_files/wangyisong1996/File/zjoi2015/cactus-slides/wys-cactus-slides.html#/6

AC代码:

http://uoj.ac/submission/13387

http://uoj.ac/submission/13388

第一份的空间复杂度是$O(n\log n)$,比第二份多一个$O(\log n)$,但代码量更小。

此外,仙人掌分治和虚仙人掌都可以在线,前者在线情况应该会TLE甚至可能MLE(至少我的写法如此= =b),后者本身就可以在线。这种做法就没什么简单办法做到在线了= =b。

解法九

waltz给出了另外一种解法:http://uoj.ac/submission/13649

时间空间代码量都完虐我啊orz......

这个做法是对每个环,新建一个点,向环上每个点连长度为它到环的根的最短路径长度的边,如果对新树dfs,那么每个点到它的任意非新建祖先的最短路径长度就是它们之间在树上的距离,对于lca不是新建点的两个点最短路长度就是它们之间在树上的距离,是新建点的话,在树上的距离也不会小于真实距离,但我们可以单独取出环再单调队列来解决环的问题。这道题成功降级为符合人民大众胃口的既无思考难度也无代码难度的傻逼题。跪烂waltz!

基于这个思路,也许很多仙人掌上问题可能会有更简单的做法?思考熊

乱搞

我们发现对于树的情况,直径就是任取一个点$a$,求出他的最远点$x$,再求出最远点$y$,$x$到$y$的距离,应用到仙人掌上是不正确的。因为一个大环连上一条小边,只有$a$取到$O(1)$个点时才能求出答案,对于其他点就算不断找最远点迭代∞次答案也不正确。(想知道这个算法能拿多少分吗?写写就知道!坏笑熊)

另外我们还可以多次枚举点做根,然后设法求得经过根的最长路径,由于答案路径可能很长,一旦取到了一个答案路径上的点做根就可以求出正确答案。但是一旦答案路径比较短,这个算法就不靠谱了。并且这个算法没法较好的判断是否已经是当前答案已经正确。

如果你通过各种方法乱搞过了,你就可以好好感受一下$\mathrm{extra\ test}$和$\mathrm{hack}$的威力了。坏笑熊

后记

其实这个题如果出成每对点的最短距离和的话,是可以避免乱搞的,而且不难实现,但是由于奇怪的原因,我没有把它改成这样。

在出题人想出一个原始的算法之后,算法又其他人不断被改进,长江后浪推前浪。感觉我从这道题的出题经历中感受到了科技的进步。捂脸熊

5s的时限真是太良心了233,主要是为了欢迎各种奇葩做法。

mx的组合数 题解

2015-03-27 11:58:56 By matthew99

题目地址

http://uoj.ac/problem/86

QAQ我把这题出出来之后,发现以前有一道几乎一样的题,而且我还A过!感觉自己记性真的有点好......捂脸熊

算法一

对于$10\%$的数据,$n, l, r \le 1000$。因此我们直接暴力枚举$x$,然后暴力求组合数即可。

如果你不会模意义下的除法,可以用杨辉三角打出前$1001$行,然后直接查询。

如果你既不会除法也不会杨辉三角(居然能看懂题目?),存在$5\%$的数据$n, l, r \le 10$,答案可以用各种方法直接算出来= =b。

算法二

对于$20\%$的数据,$n, l, r \le 100000$,我们可以用公式 ${n + 1 \choose m} = \frac{n + 1}{n - m + 1}{n \choose m}$递推出所有组合数。

算法三

对于另外$20\%$的数据,$r - l \le 10000$,我们暴力枚举$x$之后,组合数计算可以根据Lucas定理计算,但是直接枚举计算是会超时的。

首先我不知道有多少人听到这个定理后想到的是这个公式

${a \choose b} \bmod p = {\lfloor\frac{a}{p}\rfloor \choose \lfloor\frac{b}{p}\rfloor}{a \bmod p \choose b \bmod p} \bmod p$

而不是

${a \choose b} \bmod p = \prod\limits_{i \ge 0}{a_i \choose b_i} \bmod p$,其中$a_i$表示$a$在$p$进制下从较低位数起的第$i$位。

前者和后者的等价关系很显然。

用第二个公式,我们对每一位都预处理出所有组合数,复杂度为$p \times 位数$,然后枚举$x$之后可以用$O(位数)$的时间直接查询每一位的组合数值然后算出来,如果每次重新计算$x$的$p$进制,复杂度为每次$O(位数 ^ 2)$,如果每次加$1$并进位,还可以做到$O(位数)$,两种复杂度都可以轻松通过这一部分数据。

算法四

首先问题容易转化为小于等于$r$的$x$个数减去小于等于$l - 1$的$x$个数,我们只要考虑形如$x \le bound$的限制即可。

算法三给了我们启发,我们应该从$p$进制下考虑。思考熊

很容易设计出数位DP的状态和转移方程:

$g[i, j]$表示从低位开始前$i$位任意且值为$j$的方案数。 $f[i, j]$表示从低位开始前$i$位对应的$p$进制数不超过$bound$的前$i$位对应的$p$进制数且值为$j$的方案数。

假设$n$的第$i + 1$位为$y$,$bound$的第$i + 1$位为$w$,枚举第$i + 1$位的值$x$,若${x \choose y} = z$则

$g[i + 1, jz \bmod p]$ += $g[i, j]$

若$x \lt w$则$f[i + 1, jz \bmod p]$ += $g[i, j]$

若$x = w$则$f[i + 1, jz \bmod p]$ += $f[i, j]$

时间复杂度为$O(位数 \times p ^ 2)$,结合算法三可以获得$70$分,事实上前$40$分的答案比较稀疏,通过常数优化或许可以直接通过。

算法五

由于$p$是质数那么一定存在原根$g$,在算法四的转移方程中,若$j$,$z$均不为$0$,那么一定存在原根$g$下的关于模$p$的离散对数,通过取离散对数再根据费马小定理,很容易将转移方程中的$jz \bmod p$转化为$g ^ {(ind(j) + ind(z)) \bmod (p - 1)} \bmod p(ind(x)$表示$x$在原根$g$下关于模$p$的离散对数),从而转移方程可化为卷积的形式,FFT即可。

对于$j = 0$或者$z = 0$的情况,我们可以在转移中忽略,先将$1 \rightarrow p - 1$的答案统计出来,然后用总数减掉即可。

由于模数的特殊性,可以用数论变换解决。

于是这题被完美解决啦。

提交记录在这里

鼓掌熊

p = 2挂掉啦!

注意枚举原根要从$1$开始而不是从$2$开始

此外数组要开到$100$左右,而不是$30$或者更少。

太麻烦了

请问你们这些说麻烦的人,都为什么会觉得麻烦?

求原根太麻烦

这题的$p$很小,加上原根很多,直接暴力从$1$到$p$枚举然后直接枚举$1$到$p - 2$次方看有没有提前出现$1$即可,连$p - 1$的约数都不用枚举!捂脸熊

我不想写离散对数的大步小步算法

还是那句话,这题的$p$很小,直接预处理出所有的数的离散对数值即可。

此外逆元也可以预处理,并且还可以使用$O(p \log p)$的算法,不一定要写线性算法。

我不想写高精度

你可以用自带高精度的语言比如$\mathrm{python,java}$等,当然要注意常数问题。

如果你只会$\mathrm{C}$++,UOJ支持$\mathrm{C}$++的__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$),可以避免高精度。超人熊

使用方法可以参考这个提交记录:__$\mathrm{int128}$(__$\mathrm{int128}$_$\mathrm{t}$)

π(n)的计算

2015-03-11 09:23:26 By matthew99

本文中的做法已经被艹了,大家想追求最优算法的话请不要阅读本文。

$\pi(n)\ne\pi n$,更不是$3.141592655\cdots (n)$(←_←),而是小于等于$n$的质数个数,$n$可以是任意实数。

普通算法

直接用线性筛就可以做到$O(n)$。

逗比算法

用$O(n\log n)$的筛法!

不对我会$O(n\log \log n)$(只用质数筛就是$O(n\log\log n)$)

帅气的算法一

根据容斥原理可得,所有小于等于$x$的数中,不能被$n$个不同的质数$p_1, p_2,\cdots,p_n(p_i是第i个质数)$中的任何一个整除的个数是

$\lfloor x\rfloor - \sum\limits_{i}\lfloor\frac{x}{p_i}\rfloor + \sum\limits_{i\lt j}\lfloor\frac{x}{p_ip_j}\rfloor - \sum\limits_{i\lt j\lt k}\lfloor\frac{x}{p_ip_jp_k}\rfloor + \cdots$

若$n = \lfloor \sqrt x \rfloor$这个数显然就是$\pi(n) - \pi(\sqrt n) + 1$。

设$\Phi(x', n')$表示小于等于$x'$的数中($x'$可以是任意实数),不能被$n$个不同的质数$p_1, p_2,\cdots,p_n$中的前$n'$个整除的个数,则根据上面的式子容易推得

$\Phi(x', n') = \Phi(x', n' - 1) - \Phi(\frac{x'}{p_{n'}}, n' - 1)$

递归边界为

$\Phi(x', 0) = \lfloor x'\rfloor$

这个考虑一下上式中每一个$p_k$对式子的贡献即可。

注意到在递归过程中,第一个参数永远是$\lfloor\frac{x}{a}\rfloor$,$a$是某些因数的乘积,而即便$a$取所有值,上述值也不超过$O(\sqrt x)$个,第二个参数显然也是$O(\sqrt x)$个,这么一来如果加上记忆化或者直接递推,时间复杂度上界是$O(x)$,或许存在更低的上界,比如比线性低一个$O(\log x)$或者$O(\log log x)$?(大雾)。

UPD:任之洲同学指出这个算法的计算量实际上是$O(\frac{x}{\log x})$,且给出了一个$O(\frac{n ^ \frac{3}{4}}{\log n})$的做法,并且可以推广到质数的$k$次方和的情况。看起来本文没有什么存在的意义了(雾)。

帅气的算法二

令$P_k(x, n)$表示小于等于$x$的数中恰好含有$k$个大于$p_n$的(可以相同的)质因子且不含有小于等于$p_n$的质因子的个数,又不妨令$P_0(x, n) = 1$,则:

$\Phi(x, n) = \sum\limits_{k = 0}^{+∞}P_k(x, n)$

令$y = \sqrt[3]{x}$,$n = \pi(y)$,则$P_k(x, n) = 0(k \ge 3)$。

而显然有

$P_1(x, n) = \pi(x) - n$

$P_2(x, n) = \sum\limits_{y \lt p \le \sqrt x, p是质数}{\pi(\frac{m}{p}) - \pi(p) + 1}$(设$x = ab$($a, b$是质数)是满足条件的数,那么当且仅当$p = min\{a, b\}$时统计了$x$一次)

所以$\Phi(x, n) = 1 + \pi(x) - n + (\sum\limits_{y \lt p \le \sqrt x}{\pi(\frac{m}{p}) - \pi(p) + 1})$

移项得

$\pi(x) = \Phi(x, n) - 1 + n - (\sum\limits_{y \lt p \le \sqrt x}{\pi(\frac{m}{p}) - \pi(p) + 1})$

预处理$\pi(1)$到$\pi(x ^ \frac{2}{3})$的值,那么除了$\Phi(x, n)$之外,其他的项都可以在$O(n ^ \frac{2}{3})$内求出。

对于$\Phi(x, n)$,由于$n = O(x ^ \frac{1}{3})$,而第一个参数上界是$O(x ^ {\frac{1}{2}})$,因此总的复杂度不超过$O(x ^ \frac{5}{6})$,且有可能更优?(大雾)

总之还是做到比线性低啦!

鼓掌熊

实现

实现成功后我们发现,正如题目中所述,时间复杂度只是个上界,实际上这个算法跑的很快。以下是我用来计算$\pi(10 ^ 9)$的代码,实际上$calc$中的不同参数只有不到70万个,比理论值$10 ^ {7.5}$不知道少到哪里去了,因此如果有更好的复杂度上界,请告诉我。

变量定义和该文章中的定义有所不同,请大家注意分别。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <ctime>
#include <cassert>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>

#define REP(i, a, b) for (int i = (a), _end_ = (b); i != _end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long LL;

const int maxn = 1e6, max0 = 1e5;

int sum[maxn + 5];
int prime[max0 + 5];
int pn = 0;

LL n = 1000000000LL;

int Max = -1;

__gnu_pbds::gp_hash_table<int, int> id;

LL a[40000][1000];
int an = 0;

LL calc(const int &n, const int &x)
{
    if (x < 0) return n;
    if (!id[n]) id[n] = ++an;
    int tmp = id[n];
    if (a[tmp][x] != -1) return a[tmp][x];
    return a[tmp][x] = calc(n, x - 1) - calc(n / prime[x], x - 1);
}

int main()
{
    memset(a, -1, sizeof a);
    for (int i = 2; i <= maxn; ++i)
    {
        if (!sum[i]) 
        {
            if ((LL)i * i * i <= n) Max = pn;
            prime[pn++] = i;
        }
        sum[i] = sum[i - 1] + !sum[i];
        for (int j = 0; j < pn && prime[j] * i <= maxn; ++j)
        {
            sum[i * prime[j]] = 1;
            if (!(i % prime[j])) break;
        }
    }
    LL ans = calc(n, Max) + Max;
    for (int p = Max + 1; (LL)prime[p] * prime[p] <= n; ++p) ans -= sum[n / prime[p]] - sum[prime[p]] + 1;
    cout << ans << endl;
    return 0;
}

该程序的运行结果是50847534,与维基百科上的一致。在本机上(开启O2优化)运行时间为$53\mathrm{ms}$,主要耗时依旧在$\Phi$函数的计算中。

内存的话凑合着看吧,我又没说要直接用这个当模板交题。坏笑熊

参(chao)考(xi)文献

Prime-counting function

在该条目中还提到了更好的算法,有兴趣的人可以去深入研究。

UPD:本文章中的算法已被完艹 ...更多内容参见π(n)的计算++

...妈妈我终于会玩新年的魔塔了!!

2015-03-06 01:20:09 By matthew99

小学的时候玩了那么久的魔塔, 果然还是有点用的2333333(大雾)

鼓掌熊

已未年第一篇博客,祝大家新年快乐

2015-02-19 00:04:28 By matthew99

愿新的一年里,大家每场比赛都能取得理想的成绩。看题就能秒,写题就能对。人人都能拿金牌!

共 19 篇博客