GoodBye ICPC

2016 心灵之约观光团


2016 浙江大学程序设计竞赛 一等奖

2016 浙江省程序设计竞赛 三等奖


2016 rkmxtxwd 热裤暮夏天下无敌


2016 ACM/ICPC 大连 银牌  36th place.

2016 ACM/ICPC 北京 银牌  29th place.


2017 LeatherClub 广东老乡


2017 ACM/ICPC 西安 金牌  17th place.

2017 CCPC 杭州 金牌  10th place.

2017 ACM/ICPC 南宁 金牌  9th place.

2017 ACM/ICPC 上海 ECL-final 铜牌  128th place.


虽然很想继续...但是明年还要找工作(or保研???),还要为了生计奔波,感觉自己除了竞赛什么都不会...其实竞赛也始终没有变成很强的选手...所以只能说再见了吧..

GoodBye ICPC

2017 CCPC 杭州赛区小结 By ruiker @ LeatherClub

Day 0

上午和shb/lsmll/sfiction/jtjl从玉泉打车去武林广场,然后坐(站)了一万年的地铁,终于到了浙理工。报道之后数次建议jtjl去浙传看看女生都被jtjl拒绝,看起来这个人真的是个基佬。

下午就是热身赛,场地小的爆炸,感觉一个过道都容纳不了两个搞学长。热身赛A题,我们一看三分钟就有人过,肯定是个暴力啊,然后喜获TLE,换了个合理复杂度的暴力,才过掉。之后johann写了个大模拟B,我和lzw讨论了半天矩形切割,lzw就去写了个异常扭曲的算法,过掉了C,胜利AK,热身赛rank7。然后我来测试一下环境,发现eclipse好像不太好用啊,似乎无法运行程序,于是被志愿者教做人了。之后我就很贱的跑去shb那里,问他eclipse好不好使呀,然后强行教了shb做人。

赛前的晚上,发现我们队好像没有数列表,妄图抢走RBQ队的数列表,被jtjl怒斥。

Day 1

这次比赛是复旦大学出题,所以对题目质量期望还是比较高的。johann和lzw瞬间发现签到题A,A1y5。我去看了IJKL,感觉J是个傻吊题,就让lzw接着写,J1y16。然后此时BCD都有队伍过了,我们三个就分头开BCD,lzw很快会做了B,B1y26。然后我和johann讨论了一下,也很快会做了D,D1y40。获得了超级顺利的前期。

C题是一个不平衡博弈,看上去就是个智商题。三个人想了半天,感觉没什么思路,他们两个似乎对题意有了些奇怪的理解,就发了一波clarification,结果复旦给了我们一个错误的题意。当时觉得这个题意好难...完全不会做,后来发现按照复旦回答我们的题意,似乎这样根本过不了样例啊?就又发了一个clarification,复旦终于告诉了我们正确的题意...然后我去了趟厕所,猜了个结论,和lzw说了一下,他表示好像有点合理,C1y76

之后我们三个讨论了一下,很快也讨论出了K的做法,但这个时候复旦又发了个clarification,说题面中的下取整变成了类型强转...然后三个人再次陷入绝望。讨论了半天,终于扭曲的解决掉了这个问题,已经快写了一半,复旦又发了个clarification,说题意不变还是下取整...然后K又出现了一些超时问题,终于K3y181

这时还能在金牌区苟延残喘,我们觉得还是要再过一题才能有金。开了E和G,感觉没有一道题能做。johann试图去开F的大暴力,被我拦住了。三个人一直卡思路卡到了封榜。lzw表示他在被我要求学习FWT的时候,看过一个例题,题意和这个E有一些相似,需要树分治然后怎样怎样搞一搞,但是这个怎样搞的他已经忘了。johann想到了G的一个奇怪的转化,讨论了一下发现只有N^2的递推做法,感觉一看就过不了。但是这个时候反正已经爆炸了,就让johann先上去莽一下。突然lzw说会E的树分治做法了,跟我乱讲一通我听的迷迷糊糊,然后lzw自己好像也不太懂,就上机乱写一通,竟然E1y272,害怕极了。

最后半个小时,我和lzw大致了解了刚才做法的正确性,johann乱搞G,自然没有通过,后来询问一队,发现是个奇怪的按秩NTT?

经验教训

杭州强队多,牌子少,感觉能得到金牌完全是侥幸。后期能力实在太不足了啊,根本做不出难题...

 

 

2017 ACM/ICPC 西安赛区小结 by ruiker @LeatherClub

lzw视角: http://www.cnblogs.com/vb4896/p/7754224.html

 

Day -1

 

一大早和sfiction/zya一起从玉泉出发去机场,前一天上毛概的时候因为台阶太高体重太大,崴了一下脚,走路下楼痛苦异常。星期三和学长们整理模板的时候,发现每个人都要带一大坨模板,lzw甚至还要带一堆数学类书籍,书包感觉要爆炸。

继续阅读“2017 ACM/ICPC 西安赛区小结 by ruiker @LeatherClub”

后缀自动机

因为我知道后缀自动机的构造是比较难以理解的,所以我想先知道后缀自动机构建出来的东西是什么。

首先后缀自动机构造出来的一定是一个自动机,这个自动机可以接收一个字符串所有的后缀,显然这个自动机是一个DAG图。

然后这个自动机的每个状态代表什么呢?代表结束位置相同的子串,比如ab和aab在aabaab中都在3,6位置结尾,那么这两个串可以认为在后缀自动机中是同一个状态。

后缀自动机大概维护这么几个东西:

MAXLEN[ST] : ST对应的最长的字符串

MINLEN[ST] : ST对应的最短的字符串

TRANS[ST][] : ST对应的转移函数

SLINK[ST] : ST对应的最小的超集,比如(3,6,9)(3,6)的超集。SLINK指向的状态一定是当前状态的一个前缀,而且形成的一定是一棵树

ENDPOS[ST] : ST状态包含的子串的结束位置个数,可以通过SLINK树自底向上来求出

至于这个后缀自动机的构造方法,就抄个板子?

http://hihocoder.com/problemset/problem/1445

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中出现了多少不同的旋律?

这个不同旋律出现的次数,对于每个状态,不同的子串个数为maxlen-minlen+1,然后对每个状态算一算就好了。

http://hihocoder.com/problemset/problem/1449

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一个音乐旋律被表示为一段数构成的数列。

现在小Hi想知道一部作品中所有长度为K的旋律中出现次数最多的旋律的出现次数。但是K不是固定的,小Hi想知道对于所有的K的答案。

通过slink树,我们可以构建出每个状态的结束位置个数,这样的话就知道了每个maxlen出现了多少次,因为最后的答案一定是按照长度单调递减的,所以就维护一个类似于前缀最大值就好了。

http://hihocoder.com/problemset/problem/1457

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

神奇的是小Hi发现了一部名字叫《十进制进行曲大全》的作品集,顾名思义,这部作品集里有许多作品,但是所有的作品有一个共同特征:只用了十个音符,所有的音符都表示成0-9的数字。

现在小Hi想知道这部作品中所有不同的旋律的“和”(也就是把串看成数字,在十进制下的求和,允许有前导0)。答案有可能很大,我们需要对(10^9 + 7)取摸。

用像后缀数组处理多串的方法,把所有的串都串起来,然后在DAG跑个DP套DP就好了。

http://hihocoder.com/problemset/problem/1465

小Hi平时的一大兴趣爱好就是演奏钢琴。我们知道一段音乐旋律可以被表示为一段数构成的数列。

小Hi发现旋律可以循环,每次把一段旋律里面最前面一个音换到最后面就成为了原旋律的“循环相似旋律”,还可以对“循环相似旋律”进行相同的变换能继续得到原串的“循环相似旋律”。

小Hi对此产生了浓厚的兴趣,他有若干段旋律,和一部音乐作品。对于每一段旋律,他想知道有多少在音乐作品中的子串(重复便多次计)和该旋律是“循环相似旋律”。

对于循环同构的一个处理方法就是把字符串翻倍,然后看看最长公共子串是不是大于N,问题就是怎么求这个最长公共子串。

我们用类似kmp的方法处理,然后用endpos记一下数,就好了。

虚树

其实虚树这一套没什么,就是一个板子。主要解决的是给一个树,然后对树上的某个点集搞些什么操作啊询问啊,之类的问题。

就是把原树的dfs序搞出来,然后把要搞的点和lca拿出来,搞一棵新的树,用单调栈来时限,其实就是一个模板。

例题是bzoj 3611

给定一棵树,然后询问一个点集的所有互相之间的路径和以及最长路径最短路径

把虚树建出来,然后就树dp随便维护最长链最短链就好了,很显然。

Shift-and 算法

去年大连的一个题目,当时现场赛的时候就没做出来。赛后出题人说是“经典”的shift-and算法(经典个jb啊?),不过到现在才补,也是挺菜的。
例题是hdu 5972

给一个长度为n的模式子串,子串的每个位置分别可以是一些数字,即一个位置可以被多个数字匹配。再给定一个母串,问子串可以在哪些位置和木串匹配,并且输出匹配成功后的所有子串。

这个shift-and其实还是挺简单的,就是搞一个01串,代表之前多少个已经匹配啦,该匹配哪一个啦。然后预处理一个东西,表示这个字符可以匹配这个位置,然后两个东西直接and一下,如果两个可以匹配的话,那就是1,其中一个不行的话就是0。正常的字符串子串的复杂度是O(N*M)的,这个的话,时间复杂度可以除个64,是一个bitset的一个很好的用法。

Codeforces Round #417 (Div. 2) E

E. Sagheer and Apple Tree
这场比赛的其余题目都比较无聊,不过这个博弈题倒是很有意思。
然后我仔细看题的时候发现看错题了...md...
如果没看错能不能想出来呢?
因为从根到叶子节点的路径长度奇偶性相同,所以我们可以根据根到某个点的路径长度来进行染色。
奇偶性和叶子节点相同的染成红色,否则染成黑色。
如果某些苹果从红色节点丢到了黑色节点或者从红色节点被吃掉,那么这个动作相当于取石子游戏中的取石子,游戏正常继续。
如果某些苹果从黑色节点丢到了红色节点,那么先手可以把苹果丢回去。
于是sg值就是红色节点的a[i]的异或和。
用个桶维护一下就能算出答案了。