CodeChef LTIME23

VictorWonder posted @ 2015年4月27日 07:50 in CodeChef with tags 回文树 数论 数论函数变换 解题报告 , 975 阅读
首先得声明一下,这套题不全是我自己做的,第二题是lzw帮忙做的。因为lzw那边突然无法登入CC,会直接转入一个wpkg.org的网址(现在,我的电脑上也出现了这种情况),所以他提议和我一起做这场CC,然后,由他来解决T2(因为在他电脑出状况之前,他T2已经做得差不多了),所以最后,T2是lzw做出来的。
虽然是两人联手,结果由于我在关键时刻掉链子,最后没有AK,有点郁闷。
 
Problem A-TICKETS5
      开始做这道题的时候,还没有中文题面,然后,因为本人英语渣,看错了题,放过了单词alternate(这个词是交替的意思),以为只要字符串出现的字符只有两种就行了,然后竟然AC了(我可以吐槽数据吗),后来才发现,两种不一样的字符竟然需要交替出现。
 
Problem B-HCLEAN
      这道题是lzw做的,我没仔细看,现在大致说一下我的想法,当D<4的时候,肯定是不行的,因为不可能存在边,当D$\geqslant$4的时候,至少两两顶点之间是可以连的,因为是n维正方体,肯定是存在一条哈密顿路的。于是,我们可以直接构造出一种方案(构成一个环),然后再找到输入数据要求的那个顶点所在的位置,最后从这里开始输出就行了。那该如何构造呢?我们还能发现,n维坐标,每位要么是1,要么是-1,和二进制数非常相似。接着,我们又想起来(其实我是经过lzw提醒才想到这东西的),有种东西叫做格雷码,要求相邻两个数只有一个二进制位是不一样的,所以,我们就先求出格雷码,最后找到起点开始输出就行了。
 
Problem C-XETF
      这题最开始的时候,题目看错了,以为是求出所有非n约数的数的K次方之和,坑了一个多小时之后,眼看就要解决了,突然发现题目看错了,真是欲哭无泪。然后赶紧补救,结果因为时间问题,没能搞完。最后还少拿了28分,真是可惜。第三部分数据的公式都已经推出来了,结果后来由于乘起来爆了long long,一直WA,然后我就以为是公式(最开始的公式是Claris给我的),可是自己手推公式又没有多少时间了。下面讲一下做法。
      subtask1就是暴力+快速幂,相信大家应该都会。subtask2直接就是$\varphi(n)$,估计大家也应该都会。subtask3的公式是$\frac{n*\varphi(n)}{2}$,对于大于2的数n,$\varphi(n)$是偶数,所以这个公式的结果永远都是整数。唯一要注意的是,n和$\varphi(n)$乘起来会爆long long,所以要先取模再乘,然后再乘以2的逆元就行了。公式的推导过程也给出来吧:$$A_{1}+A_2+...+A_{\varphi(n)}=\sum_{i=1}^{n}i*[gcd(i,n)=1]=\sum_{i=1}^{n}i*\sum_{d|i,d|n}\mu(d)=\sum_{d|n}\mu(d)*\frac{\left( \frac{n}{d}+1\right)*n}{2}$$
$$= \frac{n}{2}*\left(\sum_{d|n}\mu(d)*\frac{n}{d}+\sum_{d|n}\mu(d)\right)=\frac{n}{2}*(\varphi(n)+\left[n=1\right])$$
      subtask4的公式其实我们也是推出来了的,感觉实现起来比较麻烦,然后就没搞(主要原因还是时间来不及了),我们推出来的最后的答案是$\sum_{d|n}\mu(d)*d^k*S_k\left(\frac{n}{d}\right)$,其中$S_k(n)=\sum_{i=1}^{n}i^k$,主要的复杂度在于求$S_k(n)$,杜教有一份课件,叫做多项式与求和,里面给出了各种做法,最快好像能做到$O(k)$?如果感兴趣的话可以去看一下。
 
Problem D-PALPROB
      这道题我竟然是第一个AC的,真是高兴。这道题要求出所有的回文串的出现次数,这当然要用回文树了,直接扒了模板过来。然后,就有点讨厌了,要求回文值,回文串S的回文值是S前$\lfloor \frac{|S|}{2}\rfloor$的字符组成的字符串的回文值+1,字符的回文值为1。回文树的构造过程中,有种东西叫做后缀链,指向的是当前回文串的最长回文后缀。既然一个字符串是回文串,那么前一半和后一半应该是反过来的,但是,这并没有影响,因为后一半的回文值>0当且仅当后一半也是回文串,那么在这种情况下,S的前一半和后一半就是相同的了。我开始的时候怀着侥幸的心理打了一个暴力,沿着后缀链走,直到找到一个位置,使得其代表的回文串的长度恰好为$\lfloor\frac{|S|}{2}\rfloor$ ,但是,谁知道出题人竟然用的同样是回文树,而且还考虑到了这种情况——全部都是一样的字符就可以将这种做法给卡掉了。于是,我换了种做法,每个结点我们都用一棵线段树记录,从当前结点开始,沿着后缀链走,长度为i的回文串的回文值是多少,那么,当前回文串的回文值就是线段树中,$\lfloor\frac{|S|}{2}\rfloor$这个位置的权值+1。因为要打十万棵线段树,很明显会MLE+TLE,所以我打了主席树,很快就能求出答案了。

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter