UOJ Logo WrongAnswer的博客

博客

2017年4月比赛记录

2017-04-03 11:46:44 By WrongAnswer

马上就要FJOI二试和CTSC了。然而FJOI二试迷之延时至下旬。CTSC就是下个月的事情。比较紧张。


51nod算法马拉松23

这场比赛做得很不及时。

4月1日听到同学讨论才想起有51nod比赛,然后点进去看已经有9个AK了……赚钱基本是没戏了。那就试着做一下呗。点进去第一题,觉得是结论题,然后自信有解就把 $x=\frac{\pi}{6}$ 代入,直接找出循环节,然后写了几个 if 不检查直接交就A掉了……挺送分。那么再看第二题,好像推个式子就行了然而 $m\le 10^7$?输入有点爆炸唉我先码个输入优化,码码码,OK了,然后推了个 $\frac{1}{m}\sum_ia_i$ 的式子交上去结果只过了第一个点……囧……

这么短代码要错肯定是结论错咯。看下题发现题意理解错,每次生成都要加进答案,再推了一波让人难以置信的是答案居然和输入的 $a_i$ 无关。。。???然后读入两个 $n,m$ 输出 $\frac{n(n-1)}{2m}$ 就过了?就过了?输入优化都没删。。。怎么都是纯数学题啊2333【讲道理这种题出在数学考试都是可以的

然后看第三题,一开始理解错以为要枚举小的对大的分段,好像还得分块,还不能处理图的情况,觉得做不了。immortalCO问我答案是不是就是次大值,我当时想到某道CF题觉得不太可能吧看了下那道CF题,发现一个条件 $a_i > a_j$。。。靠,读错题了。那看来真的是严格次大值无误。然而想了很久还是搞不清楚怎么对每个点 $v$ 求能到 $v$ 的点权中比 $v$ 的值小的最大值,好难啊先扔了。

这时候dick32165401他们好像在刚D题,就去看D。

一开始觉得状态要记原点到6个点的最短路,这样状态数至少 $O(m^6)$ 了……思考了一会儿明白了相邻两格最短路差不超过1,那就是 $100^2\times 3^5$ 级别的状态数了挺能接受,转移的时候就枚举下一列的状态,总共 $100^2\times 3^5\times 2^6$ 好像能过,就写了一会儿写完了。交上去WA掉。发现 $n,m$ 又打反,尼玛我怎么老是犯这种毛病啊QAQ第二次就过了。

这时候好像有10人AK了。惨。

E题一开始想分治之类的东西结果毫无进展,一定是我想复杂了。然后看着式子联想到一道自己出过(其实是我出完以后在BZOJ看到一模一样的题)的区间逆序数,好像只能分块搞,不过这题离线所以写个莫队+BIT好像能卡过去……然后写了一会儿写出来,接着你们懂的本SB又是过了样例WA飞了,为啥?immortalCO:你输出的时候 unsigned long long 开了没?我:没……

感觉正式比赛出这种情况就真的毁前途。看F。一开始想了想暴力怎么写,然后写完交上去想验证暴力正确性结果除了第一个点全是大数据,我去。。。不过样例和第一个点过了应该就没错了。接着开始用莫比乌斯反演推式子,推了一会儿推出一个 $\sum_{i=1}^n\sum_{j=1}^n[(i,j)=1]$ 状物,我想这应该就是 $2\varphi(n)-1$ 吧,验证了下好像是对的。接着式子就变成了分段求区间次大因数和以及区间 $\varphi$ 和,后一个好像有原题上个杜教筛容斥就行,$O(n^\frac{2}{3})$,问题是前一个怎么求不是很会= =

然后想暴力该怎么写,就是埃氏筛法,好像和筛法函数长得很像?接着就开始推筛法函数的DP,推了几步发现中间某一步要求 $\sum_{i=1}^ni^K$,$n$ 又很大,好像只能强上插值了……于是目前的想法是“插值+容斥+DP”三合一,感觉会很难写很难调。

然而好像拉格朗日插值没逆元,还是写 $O(K^2)$ 的牛顿插值吧,然而并不会牛顿插值的式子,上网搜了一堆资料结果半懂不懂的,决定自己推,然后推对了……RP不错,接着开始写,写完一测发现萎了。。。怎么回事?调调调。。。卧槽我的方法用到了除以阶乘然而阶乘不一定有逆元,日。。。

最后还是只好质因数分解保平安了2333写完以后开始写容斥求 $\varphi(x)$ 前缀和,由于一开始忘记预处理 $\varphi(1)=1$ 导致怎么都是错,也费了好多时间。终于开始写筛法函数了,一开始还把定义搞错把质数也筛掉了,后来觉得不妙才改了,然而还是出一堆问题。接着两三个小时发现一堆bug,一个个改完以后终于过样例了,然后第一个点WA了,又调了一下发现丢了一个 pow

结局是艰难地过掉了F。。。感觉这种难度的题我还得折腾这么久我这迟早要完啊。。。

然后C还是不会做。。。4月2日起来继续想,想了很久一直往强连通分量去想,结果不知道怎么提取第一个比自己小的权值,还是做不出来。最后想出枚举权值区间floodfill再把这个权值的点去掉,求出每个点能到达它的不等于自己的最大权值,又想想觉得不对= =于是改成floodfill搞出每个点能到达它的最大和次大权值,这样就靠谱了。于是12点多把C题过了。论最后想出来的是C题是一种怎样的体验2333

最后rank14 GG,可能我早点开始打也不太能进前10。

看完题解之后

C题原来缩强连通分量以后直接递推一发就做完了,不知道我当时在想什么

E题分块做好像就能不带log了,当然莫队把BIT换成分块维护好像也能优化掉log(不过好像更难写就懒得优化了)

F题居然可以多设几个函数来搞,不用插值了……不过不知道常数会不会大


集训队互测 Round 1

开场看T1,感觉得推什么复杂的式子,不知道有没结论,于是先写个随机模拟打个表再说,然后发现 $k=1$ 时答案全是 $0$。看下子任务居然有 $k\le 1$ 的部分分,难道是我写错了?再看 $k=2$ 的,发现是 $\frac{m(n-1)}{n^2}$,这个应该有分……好我写一写,交。

交上去居然是 Invisible,这不科学啊一定是OJ的问题……于是OJ修了一会儿看到结果,才5分= =然而怎么右边显示了标准输出?趁着工作人员修OJ的时候调代码,然后发现期望忘记除以方案总数了。。。接着又看了看表看出 $k=3$ 是 $\frac{m(n-1)(n-2)}{n^3}$ 感觉挺稳,觉得答案应该就是 $\frac{m(n-1)(n-2)\cdots(n-k+1)}{n^k}$,接着发现 $k\ge 4$ 就挂了……

算了先交 $k=3$。看到得了45分就放心了。然后试着推通用的式子,然而每次计算是 $O(m)$ 的,而且怎么都化简不了。先放一边。

接着去看T2,这题不出意外一定是JOHNKRAM的题,联想到WC时的仙人掌计数……已经不打算想正解了,那就写 $O(n^2)$ 吧。

推了一下好像得预处理 $i$ 个点的强连通图个数?然后就开始想,想到后面以为只要求这个了,又想到清华集训2014的主旋律,然而我并没有A。。。然后又是线上比赛,不如找一份std对着写?点开以后意识到问题并不是这么简单……

继续推,发现主旋律做法还是有用的,然而接着处于掉坑状态,想了非常久还是没想出怎么做。后来干脆考虑每种图会被枚举到多少次,接着就好像会 $O(n^2)$ 了,只要DP出每种点数的和合法图个数,然后枚举源点集合大小加起来就是答案了。

写到210min的时候终于写完,居然对了。70分到手,有点开心。

最后看T3,好像是个比较麻烦的题,感觉我不可能做出来了,就写了个15分暴力交上去。交完以后发现 $K\le 5000$ 可以离散化啊= =就写了离散化交上去,发现前面WA掉了。。。原来是数组开小了2333

改完以后想多捞点分,就想 $q=0$ 可不可做,似乎只要找出每一列最后一次被染色的时刻然后按这个顺序做一遍,不需要什么复杂的数据结构就搞定了,不过不太确定能否写对。不过还是试着写写吧……

最后10min终于调过样例,交上去。后来看到自己这题得了50分,挺满意的了。

然后还想rush一下T1的另外15分,结果没时间了。

最后45+70+50=165,出榜以后发现我这一堆暴力加起来居然有rank 2……有点爽。再看下其他人,好多大爷都是刚某道题没时间做别的题,然后送了我这个机会……所以我实力还是不行的。

看完题解之后

xumingkuan的T1好神奇啊。题解里讲了“有可能出现的情况是找出 $k=3$ 的答案公式,与 $k=2$ 时的答案公式形式相似,试图推出一个普适的规律,然而发现 $k=4$ 时这个规律就挂了”,这不就是我的情况吗2333

也许学过stirling相关知识这题就能多做一些分?我的姿势水平还需要提高。。。

JOHNKRAM的T2我可能需要多花一些时间理解。

zsyzssoft的T3可能细节偏多?然而场上2人AC,可能我还是没跟上大家的水平啊。


集训队互测 Round 2

还是开场看T1,以为直接状压就行了,结果 $O(3^nn^2)$ 写完一交才4分,好气啊,暴力分真少。优化一发,好像只要考虑包含某个点的集合就行了,再交,20分。分数这么低一定是我想偏了。

然后发现这题 $p=17$ 居然是给出的,一定是有什么很妙的算法,想到了Codechef的BIKE。那就只要一开始把所有式子DFT一下,乘的时候只要 $O(p)$,最后IDFT回来就行了。不过不太确定能否AC。

当然由于时间效率是 $3^{16}\times 17=7.3\times 10^8$,$3\texttt{s}$ 还是跑出来了……$O(3^np)$ 能过看来这题肯定大家都会。接着看T2。

然后就说明了我有多弱……一开始没注意到对 $M$ 取模,然后觉得好像可以网络流,正在想怎么建图的时候发现了要对 $M$ 取模,于是瞬间不会了。原本想二分贪心,结果发现二分也是错的。脑补了好几种贪心,结果全是错的,然后一点思路都没有了。

接着放弃T2去想T3了。一开始觉得条件有点复杂,不过如果枚举了 $m$ 就可以压位高斯消元了,$O(\frac{n^4}{w})$,这大概有30分。不过要跑 $n$ 次高斯消元,可能我有些性质没用上?

于是仔细分析了一下性质,发现 $m$ 每增加 $1$,就少一个约束,多一个变量,好像处理起来不方便。如果 $m$ 减少 $1$,就多一个约束,少一个变量,直接把最后一列删掉,然后用前面的行消这一行,这样复杂度就优化到 $O(\frac{n^3}{w})$ 了?不知道能不能60分的说。。。

接着开始写,写了挺久的,写完过了两个样例交上去,一直Waiting,就继续想第二题,还是没想出来。

测出来了,0分。点进去一看,全都是WA和TLE。

样例怎么这么弱啊,怎么过了两个样例都能爆0。。。难道是系统差?自定义测试一发,过了。

那肯定是我写挂了。写了个 $O(2^nn^2)$ 暴力拍,拍了一会儿拍出一个问题,改完以后过了对拍。交。继续想第二题,还是没想出来。

测出来了,0分。点进去一看,全都是WA和TLE。

这就尴尬了……无论如何都拍不出错怎么交上去就是0分?难道是我题目理解错了?

把 $O(2^nn^2)$ 暴力特判 if(n>20)return 0; 交上去。

测出来了,0分。点进去一看,全都是WA,而且都是0s。不可能跑这么快啊?难道是……数据……犹豫了一会儿把暴力的 gets(a) 换成 scanf("%s",a),交上去,10分了。估计是毛爷爷用Windows造的数据导致文件末有多余字符 gets 会挂,惨啊= =

再把原来的代码交上去,40分,中间TLE了。好像被卡常数了,开始优化。接着发现我数组开的 $50000\times 782$ 于是 memcpy 炸复杂度了……改完交了两发(有一发优化错了)一共经过7次提交终于过60分了,真是艰难。

最后1个多小时继续刚T2,然而除了 $K=1$ 的特判和答案小于 $M$ 的网络流以外都不会,我好菜啊……最后还是写了这两档一共25分,然而不明原因得了40分,而且9~11测试点还是WA的。好玄学,不过也没时间做什么了。

结果是GG了,100+40+60=200,rank 7。一看怎么大家都会T2,惨啊……果然T1大家都会,T3也有很多60。

于是就成了T2最低分选手。。。我做的题还是太少啊。。。

看完题解之后

cy的T1正解是 $O(2^nn^2p)$ 的,好像比较麻烦。。。(反正我没去想就是了)不过似乎 $3^{17-1}$ 和 $2^{17}\times 17^2$ 运行效率差不多的样子?

yjqqqaq表示他的T2是NOI第一题难度,想想我NOI2016 D2T1的分数……

T2正解是贪心+结论,最后一步用数据结构优化。然而我不仅没看出只要判断连续 $K$ 个数的结论,还没看出有解时答案为最大值的结论,更没有看出答案不超过 $2M$……可以说我是完全不会。另外好像直接输出最大值好像就有很多分???

matthew99的T3竟然真的是WC讲的Berlekamp-Massey算法……yyt16384 AC了好劲啊。

有空的时候我也学一学这个算法。


Codechef APRIL17

难得参加了一场Codechef。感觉这场比往常的都水啊,最后都是比谁Challenge分数高。

除了最后一题以外几乎是倒着往前做的。

Chef and Digits(DGTCNT)

一眼看觉得是个数位DP?仔细看下,原来是带了 $10$ 个约束的计数,约束这么少感觉容斥一波就行了= =先把 $[L,R]$ 转成 $[1,R+1)$ 和 $[1,L)$ 的差,求 $[1,N)$ 有多少个 $x$ 满足时,枚举 $x$ 和 $N$ 的LCP和第一个不同的数,然后容斥,枚举数字集合 $S$,要求 $\forall i\in S$,$i$ 在 $x$ 中恰好出现 $a_i$ 次,组合数算算就好,再乘上 $(-1)^{|S|}$ 就行了?于是一下子码完,肉眼调了几个SB错误,就过了第一个样例。

然后第二个样例一直过不去。自己出了几组小数据都没问题。

对着代码想了好一会儿终于发现哪里错了,我的做法假设 $x$ 和 $N$ 位数相同,于是把前导零算进去了!改……先强制最高位不能是 $0$……然后把之前的代码强制复制一遍,枚举一下 $x$ 的长度再搞搞……

然后过了两个样例,用暴力和正解拍了几组大数据就交了,一发AC。爽。

Bear and Random Grid(RNDGRID)

点进来就看到数据随机生成,题意大概是给一个有障碍的矩阵和一个操作序列,求从每个格子出发按这个操作序列走第一次碰到障碍或出界的时刻,粗略感觉随机走的话走几步就碰到障碍了,于是直接模拟2333然后发现不对劲,如果矩阵是空的就挂了- -

再想想这个做法期望复杂度是 $O(\frac{N^2}{P})$,$P$ 小的时候会跪。

不过 $P=0$ 的话没有障碍,就可以预处理每个点第一次出界的时刻。那么 $P$ 很小做法应该也类似。又想了想就明白只要对每个障碍和每个 $i$ 找出从哪个点出发走操作序列长度为 $i$ 的前缀能到它就能更新答案了,这么搞复杂度是 $O(N^2PL)$。

那就把 $P$ 以 $\frac{1}{\sqrt L}$ 分界一下就能做到期望 $O(N^2\sqrt L)$……然而我本机上调参用的是二分,于是二分出 $P=1.2\%$ 两个做法都是 $3.8\texttt{s}$ 左右,好像可以过就交了……

事实证明Codechef的运行效率比本机快得多,交上去一个点还不到 $1\texttt{s}$ 就AC了。

Stable market(SMARKET)

首先想到了游程编码一发,然后问一个区间的时候把两个端点所在的段取出来,判一判是否大于等于 $k$,查一下区间里有多少个不小于 $k$ 的段就行了吧。

整个思路无比显然。。查区间不小于 $k$ 的数先想到了可持久化线段树,然后发现这题可以离线,就用个BiT搞= =挺好写的。

然而我居然TLE了一发。。。??什么鬼,原来是数组忘清空了= =b想到去年NOI有些大佬D1T1本来高我5分因为这个错误炸成比我少85分感觉我还是RP选手= =

Chef and Divisor Tree(CHEFDIV)

一看 $B-A < 10^5$ 就知道可以枚举整数 $n\in[A,B]$ 然后求 $n$ 的答案 $f(n)$,一开始打了个表没看出熟悉的东西,就质因数分解一下 $n=\prod_{i=0}^{k-1}p_i^{c_i}$,$f(n)$ 就是每次把一个正的 $c_i$ 减掉 $1$,过程中 $\prod_{i=0}^{k-1}(1+c_i)$ 的和。联想到自己以前给NOIP组出的一道题就猜了个结论每次找个最大的 $c_i$ 减,再用之前打的表验证了一下感觉没问题。

然后懒得优化直接写了个 $O((B-A)\log^2B)$(可能有更好的上界?反正跑的挺快),结果过完样例交上去后面的点挂了。然后发现我犯了两个错误,一个是存质因数的数组用了 int,于是用 $\sqrt n$ 以内的质数分解完以后如果大于 $1$ 再把剩下的数加进数组就溢出了……另一个就不说了

for(int i=2;i<1000;i++)if(!a[i]){ // 于是1000~1000000的质数都没被考虑进去
    for(int j=i*i;j<=1000000;j+=i)a[j]=1;
    for(long long j=(L+i-1)/i<i?i*i:(L+i-1)/i*i;j<=R;j+=i)f[j-L][c[j-L]++]=i;
}

改完两个bug过了……

Bear and Clique Distances(CLIQUED)

把团上的点和一个附加结点都连上边以后就是裸的最短路咯,写写写,写完了,测样例,过了,交,AC。

Bear and Row 01(ROWSOLD)

一开始看错题以为是最小化的SB题,再想想原来是最大化,不过好像也很简单,猜个结论每次把最左边能右移的右移,好像没错,试试,写完,测样例,过了,交,AC。

Dish Of Life(DISHLIFE)

水水的模拟,先统计每个数出现次数,有 $0$ 次就是 sad,没有的话枚举删哪一个看看有没哪个次数会变 $0$。偷懒直接上了 vector

Similar Dishes(SIMDISH)

水水的模拟,然而偷懒直接上了 stringsortlower_boundupper_bound

Heavy-Light Decomposition(HLD)

终于来做最后一题了,不过比想象中要简单。

一开始瞎猜了几个贪心,每次取个深度最大的连重链,然后凭借多年写树链剖分的经验这样只要弄一条链然后从下往上依次在每个点挂长度为 $1,2,3,\cdots$ 的链就能叉掉。又猜是不是按子树大小贪心,发现在某个结点上瞎挂一堆叶结点就能卡掉。看来直接贪心会炸。

那就树形DP。一开始的想法是记 $f(i,j)$ 为 $i$ 上方的重链长度为 $j$,$i$ 子树内的最大cost。转移的时候枚举重链连向哪个子结点,好像能转移。一看数据范围 $N\le 100,000$……

于是又在想更靠谱的状态设计,如果 $j$ 改成定义为 $i$ 下方的重链长度呢?如果能够不遍历深度最大的子结点的DP数组复杂度就对了。链的长度怎么搞呢?那就令距离链的顶端 $1,2,3,5,9,\cdots,2^i+1$ 的重边和所有轻边长度为1,其它为0。接着开始想递推方程。

如果所有子结点 $c_1,c_2,\cdots,c_k$ 中,重链连的是 $c_m$,那么

$$f(i,j)=\max\{g(c_1),g(c_2),\cdots,f'(c_m,j-1)+[d=1\lor\exists k\in\mathrm{N},d=2^k+1],\cdots,g(c_k)\}$$

其中 $g(i)=\max\{f(i,j)\}$。至于 $f'$ 呢,是个好像有后效性的玩意。。。不太好做?

看了下AC人数感觉这题肯定不难,一定是我没想到点子上。

脑补了一下,发现 $c_m$ 肯定是 $g$ 值最大的子结点,那么只要记 $g(c_1),\cdots,g(c_k)$ 中的最大值 $g(c_m)$ 和次大值 $v$ 就OK了,一边DFS一边方案就确定了,$j$ 这一维都不需要了。接着就只剩快速计算 $i$ 到 $m$ 子树的点 $v$ 的最大cost了,因为只有当 $v$ 往上第一次到 $i$ 所在重链到达的点到 $i$ 的cost是 $1,2,3,5,9,\cdots$ 的时候才会加1,所以只要每个点 $i$ 维护这个点往下的轻边子树到它的最大深度 $d_i$,然后把 $O(\log n)$ 个点 $d_i$ 加1,就解决了。

看起来确实挺简单,就开始码了。因为懒得写不定长数组所以用了 vector,不过空间复杂度是 $O(n)$ 的,不虚。过样例就一遍AC了挺开心。

(CH) Serejs and Billiards(SEABIL)

体现我近似算法水平低的时候到了。

看完题,先想分数为正的有什么好的搞法,一开始想把球一个个打进洞,这样步数上界是 $2M$ 的。在想能不能先把球打到对角线上,然后一次全打进洞,就想到每列打一次把这一列的球全打到主对角线上,再把所有球一次打进洞,步数上界 $N+1$,不错的样子。写完得了60分。

再搞搞分数有负数的吧,感受了下如果不考虑球的分数正负的话实际得分期望是负的,不爽,得把负的都搞掉。然而把负的打到一个边角可能会把影响正的,经过思考,打算这么构造:负的球打到相邻偶数列,正的球打到相邻奇数列,接着把正的打到对角线上,再一次打进洞。这样步数上界期望大概 $\frac{M+N}{2}$ 吧,好像没什么优化余地了,就写了。

写完一交得了98.5分,以为这分数应该不错,结果一看榜怎么全是99+分的。。。GG。。。

最后1h还是没能搞出更高的分。。。最后rank 24滚粗,再见。。。


集训队互测 Round 3(围观)

因为这场由immortalCO、fateice和我出题,所以我不是参赛者而是观察者……

我出的是T3,一道槽点一大堆的提交答案题。

其实也没什么想说的吧。当然这场被很多人当成辣鸡比赛= =

不少人整场疯狂交T2(10个点,时限8s的题),有一段时间评测队列卡了五六个Waiting,卡评测严重。主要原因是这题 $n\le 20,000$,数据组数 $t\le 5$,$\sum n\le 70,000$,于是大家都想用 $O(n^2)$ 卡常数过掉……

由于我的T3下发的checker直接告诉了分数,于是大家不怎么提交,一般都是最后再交。不过悲催的是yyt16384最后没交上去,惨。。。

最后就是我的题估分大爆炸。当时给fateice验题的时候,fateice一小时做了6个点,当时还觉得现场好几个小时大家应该很容易上60的,结果。。。没人上60。。。【一定是fateice太强啦!

不知道会不会给人一种“FJ卡常队”的印象……去年AKF的集训队互测也有人被卡常数,今年呢,T1没人写正解就不说了,T2卡常数,T3也有人被卡了常数……T3 57分(最高分)xumingkuan有的点被卡了些结点个数的常数,于是少了点分,惨……

选个时间把这场放到UOJ上让大家玩一玩?


集训队互测 Round 4

开场看了下三题,觉得T1好像很可做,先跑一遍Manacher在每次指针右移的时候记下区间,就可以转化成每次询问右下角有多少个点。。。开始写的时候突然发现这个做法是错的。。。

然后开始fix,脑补了各种回文串的性质无果;转成后缀数组的每个后缀维护一个集合,区间插入一个数,发现集合难合并;考虑维护所有不同回文串的最左出现位置,不断删第一个字母,看起来很靠谱结果复杂度是错的……总之一共想了2个多小时还是一无所获。哎。

算了去想后面的题,第二题一开始想到 $[a,b]$ 的一个左子结点 $[a,c]$ 被覆盖的条件是 $l\le a\le c\le r < b$,写了个暴力交上去只有10分,原来我 $type=0$ 的也异或上一次答案了。。。算了我想想稍微不暴力点的做法。

发现这是个三维偏序,不资磁!不过 $a\le b < c$ 是个好性质,我们转化一下,答案是满足 $1\le a\le c\le r$ 的个数减去满足 $1\le a\le b\le r$ 的个数,再转化一下就是区间长度($r-l+1$)减去 $l\le a\le b\le r$ 的非叶结点 $[a,b]$ 个数,就变成了二维偏序了。写了一下发现结论没错,好像能做。

然而又要在线又要带修改……强上两个log吧。线段树套线段树?不资磁,空间是 $O(n\log^2 n)$ 的。那就线段树套……平衡树?虽然时间还是 $O(n\log^2n)$ 但空间只有 $O(n\log n)$ 了,效果也许不错?

于是就陷入了深坑。

15点多开始线段树套平衡树,到16点半的时候调出来了,交上去,60分。一看,被卡了8个点的内存。

惨。

我就在想,$64\texttt{MB}$ 可以开 $1.6\times 10^7$ 个 int,$200000\times 20$ 个结点,每个节点大概长这样:

struct snode{
    int val,siz;
    snode*fa,*ch[2];
};

如果每个节点是 $8$ 个 int 大小,那就起码 $128\texttt{MB}$,有点崩。然而明明只要查后缀区间为什么要写线段树?写个树状数组就行了啊期望还能省一半内存= =

于是又花了20多分钟改成了树状数组套平衡树,交上去,还是60分。。。

想了好久还是不知道怎么优化。至今不明白为什么连 $64\texttt{MB}$ 都卡不进去。

一看比赛只剩1h了,得赶紧写掉剩下两题暴力。

于是先写了T3的 $O(n\min\{n,m\})$ 暴力,一开始写错了一次,调了一会儿过了35。

又写了T1的 $O(n^2\log n+qn\log n)$ 暴力,20分。

最后又想多rush T3的分又想优化T2的内存,结果都没成功。

于是20+60+35=115滚粗。。。T2一堆100,只有我一个60。。。然而T2分这么低居然还有rank 4。。。

immortalCO T2标算AC,太强啦!

fateice T2神奇算法AC,太强啦!

看完题解之后

philipsweng的T1正解是回文树+分块,然而我不会回文树,哎我怎么这么菜啊

srwudi的T2确实带给选手们无与伦比的卡内存做题体验啊……不过说到底还是我自己的问题,我还!是!不!会!分!析!问!题!性!质!推了个二维偏序就不管了,最后GG……

线段树结点和普通区间相比有明显的规律啊,覆盖区间的结点一定是一段递增一段递减,然而我怎么就把问题给一般化了,问题一般化就丢性质了。。。immortalCO教导得是啊。

yyt16384的T3看起来不可做,当然也可能是我太弱了。


集训队互测 Round 5

血崩。

由于晚上熬夜出题,状态不好,看到题啥思路都没有。于是想想T1,好像是后缀自动机,然而我不会,于是写了后缀Trie的35分。又想想T2,好像可以FWT,结果细节考虑不清楚,怎么都是错的,最后调来调去弄了30分,不知道为什么2、3过了4没过。然后又去看T3,觉得是三合一的恶心题,没啥写的欲望。然后花了很久才写掉了第一个subtask。回头准备试着写SAM,然而考场上确实不应该写不熟悉的算法,还是放弃了。T2感觉造数据很麻烦,就盯着代码看,没看出问题。。。GG。。。T3的第二个subtask好像可以均摊搞搞,写着写着开始怀疑人生,觉得复杂度爆炸,于是不写了。。。最后还是把subtask3的裸暴力写了,然而前面的点莫名其妙地WA了,又没法Rejudge,就只剩25分了。

结果#9滚大粗。。。35+30+25=90。。。膜immortalCO 170分#1。

最后一次互测考成这样我对自己已经没什么信心了。大概我就只有rank 9的水平吧。况且最近也没时间刷题了,只能CTSC坐等GG同时围观immortalCO怒拿rank 1进国家队了。

看完题解之后

SkyDec的T1是继sone3之后的又一道神字符串题,不想做。然而把我的后缀Trie换成后缀自动机就有60分了啊……我一定要想办法学会后缀自动机。

qiaoranliqu的T2感觉自己状态好的话完全是可以想出来的,因为我前段时间学过FWT了。。。然而自己傻逼到盯着50分一直码写挂了还懒得调感觉我心态实在太糟糕。。。(也可能是晚上睡太少了)

sunyaofeng的T3后两个subtask正解好复杂啊,可是immortalCO说敢写暴力就能AC,orz……我纠结了好久的错误复杂度光荣滚粗……


FJOI2017 二试

一场挂得心碎的省选。

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

NOIP和省选一试优势全部浪没。失去了所有对好成绩的梦想。


51nod算法马拉松24

见另外的博客。

又好久没打Codeforces了,CTSC前如果有不在半夜的CF还是挺想打一打的。尽管打了有可能掉rating,但不掉rating怎么涨rating?

51nod算法马拉松22参赛总结

2017-03-06 09:57:03 By WrongAnswer

又一次RP爆发卡线rank 10……有点爽……


由于周五是我出的校内训练,所以等21:30讲完题回家路上才开始看题。

路上用手机看题。A题看完以后想到FJOI2016一试T3,其实就是Codechef原题FRBSUM。看起来很复杂,其实注意到一个核心性质:把 $S$ 中的元素排序得到 $a_1\le a_2\le\cdots\le a_n$ 以后,最小的满足 $a_i > 1+\sum_{j=1}^{i-1}a_j$ 的 $i$ 对应的 $\sum_{j=1}^{i-1}a_j$ 就是 $S$ 的优美值。

因为当 $0 < i' < i$ 时,如果 $\{a_1,\cdots,a_{i'-1}\}$ 能配出的数为 $[0,\sum_{j=1}^{i'-1}a_j]$,那么 $\{a_1,\cdots,a_{i'}\}$ 就能配出 $[0,\sum_{j=1}^{i'-1}a_j]\cup[a_{i'},\sum_{j=1}^{i'}a_j]=[0,\sum_{j=1}^{i'}a_j]$。而由于 $a_i$ 已排序,所以 $a_{i'} > 1+\sum_{j=1}^{i-1}(i'\ge i)$,因此 $1+\sum_{j=1}^{i-1}$ 配不出来。这样求优美值就很简单了:排序以后,一开始 $\mathrm{sum}=0$,从小到大把 $a_i$ 加入 $\mathrm{sum}$,一旦加入前发现 $a_i\not\in[0,1+\mathrm{sum}]$ 就得到答案了。(FJOI原题是多次询问区间答案,做法是用可持久化线段树加速查询 $[0,\mathrm{sum}+1]$ 区间内的数,因为一次可以把多个数加进 $\mathrm{sum}$,所以 $\mathrm{sum}$ 只会增加 $O(\log\sum a_i)$ 次)

想到这里,这题差不多就会做了,从小到大选 $S_1$ 中的元素,如果 $S_1$ 中没有 $[0,\mathrm{sum}+1]$ 内的元素($\mathrm{sum}$ 为已选元素之和),那么就从 $S_2$ 中贪心选出尽量大的数加入 $S_3$(因为答案是选出数的和,所以不贪心取最大的话可以调整成更大的数更优),直到 $S_1$ 和 $S_2$ 剩下元素都大于 $1+\mathrm{sum}$ 或 $|S_3|=k$。于是我直接在手机上写完,交上去,TLE。

然而我的复杂度是 $O(nm\log m+Tm)$ 啊,应该不会TLE的?回头看一遍数据范围发现这题输入了 $10^6$ 个数,不加输入优化没什么救,然后就在刚到家的时候把输入优化码完,AC了。

回家上电脑接着看了后几题。B题一开始以为是个无聊的卡精度马尔可夫过程,思考了一下才明白决策是自己选的,然后列出来就是最小化一个带一堆 $\min$ 的奇怪式子,不会了。C题题目不是很懂,一大堆 $e$ 看起来很丧。D题让我想到了UOJ #176,然而这题我并不会做,惨啊……

不过好像D可做?用UOJ那题的题解里提到的Boruvka算法,建Trie维护一下可能就OK了?问题是要计数。接着想了一些办法,首先是相同点权构成的点集 $S$ 连的是边权 $0$ 的完全图,一定全部被连起来,方案数是 $|S|^{|S|-2}$。缩完相同点权以后,相同边权的边就没有公共点了,意味着MST唯一?好像很资磁。

于是快要0:00开始写Boruvka,写完一测样例果然萎了。原来……我太SB了,虽然相同边权的边没有公共点但是在缩的时候会把这些边的端点缩到一块去……看样子这么做下去并没有前途。

先去睡觉了。

纠结于5题刚不出来的我冷静了一晚上,感觉好像理解了C题的意思。于是第二天一起来去刚C题。

推了一发式子——

$$[f(x)-e^x]^2=\sum_{i=0}^Na_i^2x^{2i}+2\sum_{i=0}^{N-1}\sum_{j=i+1}^Na_ia_jx^{i+j}-2\sum_{i=0}^Na_ix^ie^x$$

$$(x^i)'=ix^{i-1}\Rightarrow\int_0^1x^i\mathrm{d}x=\frac{1}{i+1}1^{i+1}-\frac{1}{i+1}0^{i+1}=\frac{1}{i+1}$$

然后并没有想清楚 $x^ie^x$ 定积分怎么求,就开始手算小数据:

$$(x^ie^x)'=(ix^{i-1}+x^i)e^x$$

$$\Rightarrow [(x-1)e^x]'=xe^x$$

$$\Rightarrow [(x^2-2x+2)e^x]'=x^2e^x$$

$$\Rightarrow [(x^3-3x^2+6x-6)e^x]'=x^3e^x$$

这样归纳一下好像就推出来了:

$$(e^x\sum_{i=0}^n(-1)^iA_n^ix^{n-i})'=x^ne^x\Rightarrow\int_0^1x^ne^x\mathrm{d}x=e\sum_{i=0}^n(-1)^iA_n^i-(-1)^nn!$$

这么看来原式应该就等于

$$\sum_{i=0}^N\frac{1}{2i+1}a_i^2+2\sum_{i=0}^{N-1}\sum_{j=i+1}^N\frac{1}{i+j+1}a_ia_j-2\sum_{i=0}^N[e\sum_{j=0}^i(-1)^jA_i^j-(-1)^ii!]a_i$$

只有二次诶,那只要对每个 $a_i$ 令偏导为 $0$ 就行了,就能得到一个 $N+1$ 元一次方程组(UPD):

$$\frac{2}{2i+1}a_i+2\sum_{0\le j\le N,j\ne i}\frac{1}{i+j+1}a_j-2[e\sum_{j=0}^i(-1)^jA_i^j-(-1)^ii!]=0$$

用高斯消元解方程组就做完了,可是 $a_i=\sum_{j=0}^\infty p_{ij}\cdot e^j$ 什么鬼??难道要把多项式放进去消元,这个是要炸的呀。看了下方程组发现系数矩阵 $A$ 的数都是有理数,那么解方程 $Ax=b$($x,b$ 为列向量)得到 $x=A^{-1}b$,而 $b$ 中的数都能表示成 $p_0+p_1e$ 的形式,所以答案 $x$ 也能表示成 $p_0+p_1e$ 的形式。

出题人真坑,明明答案是 $p_0+p_1$ 的形式,只有 $p_{i0},p_{i1}$ 是有用的,题面偏要写成 $\sum_{j=0}^\infty p_{ij}$ 误导别人存整个多项式。然后又只要输出有用的那两个数。坑爹!!

推导这里就开始写,写完之后测了下样例 $N=0$ 过了,$N=1$ 的WA了。开始怀疑算法有没错。或者是哪一步推导错了。好虚啊。

手算了一边发现算法是对的,调一发程序,是程序把某个式子算错了= =b

改改改。

终于过样例了。

终于过了C。

看了下榜已经一堆人过5题了,而我只有约四十名。我开始做B题。

一开始想枚举每个点的前继然后怎么搞,觉得好像有反例(?)就犹豫了好长时间。不过想了一会儿还是找到了正确的思路:先确定 $0$ 个星的时候的决策,显然升级概率越大越好,再确定 $1$ 个星时候的决策……

因此,记 $f_i$ 为当前有 $i$ 个星,按照最优策略,第一次变成 $i+1$ 星的期望花费,则枚举选择的魔法石 $j$,有 $1-\mathrm{prob}(i,j)$ 概率失败,失败的话就要从 $i-\mathrm{lose}(i,j)$ 星逐步转移到 $i+1$ 星,因此 $f_i=\min_j\{C_j+[ 1 - \mathrm{prob}(i,j) ]\sum_{k=i-\mathrm{lose}(i,j)}^if_k\}$。

移项得到 $f_i=\min_j\{\frac{C_j}{\mathrm{prob}(i,j)}+[\frac{1}{\mathrm{prob}(i,j)}-1]\sum_{k=i-\mathrm{lose}(i,j)}^{i-1}f_k\}$。直接DP会有精度问题吗?

那我写一下交个看看。写完没过样例因为我把 $C_i$ 写丢了(还查了好一会儿),过了样例交上去。结果,居然直接AC了,完全没有卡精度的迹象。

我也不知道为什么没有出精度问题,也许是运气好吧。上次在51nod做同一个出题人出的马尔可夫过程题还卡了好久的精度呢。

再看D的时候D的通过人数已经好多了。这题一定不难,只是我想复杂了。

于是手工模拟了一遍点集 $\{0,1,2,3,4,5,6,7,8\}$ 的Kruskal过程,整个过程如下:

$$\{0\},\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\}$$

$$\{0,1\},\{2,3\},\{4,5\},\{6,7\}$$

$$\{0,1,2,3\},\{4,5,6,7\}$$

$$\{0,1,2,3,4,5,6,7\}$$

我好像发现了什么……是按二进制位从低到高合并的!

如果在Trie树上呢?连边 $(u,v)$ 的时候,$(u,v)$ 的权值最高位就是 $u,v$ 在Trie上的LCA高度。因此对Trie树 $T$ 模拟Kruskal的方法是这样的:

Kruskal(T):
    若 T 的左子树非空: Kruskal(T 的左子树)
    若 T 的右子树非空: Kruskal(T 的右子树)
    // 以上两步之后最多只剩左右子树两个连通块,并且这两步过程中连的边权都比剩下可能连的边小,因此是正确的
    若 T 的左子树 T1 和右子树 T2 均非空(假设 |T1| < |T2|):
        x = Infinity, c = 0
        DFS 枚举 T1 节点 u,DFS 过程中在 T2 中贪心地找点 v 使得 a[u] xor a[v] 最小: // 由于缩了相同点,每个 u 对应的 v 唯一
            若 a[u] xor a[v] = x: c += 1
            若 a[u] xor a[v] < x: x = a[u] xor a[v], c = 1
    最小生成树边权和加 x,方案数乘 c

这个问题的性质就是左右子树独立,注意到这一点以后就变地简单多了。然后我把原来写的错误的Trie树Boruvka算法删了一大半,改成直接在树上DFS,过了样例,交上去也过了。

过D的时候12:00多。昨晚觉得B、C、D都一副不可做的样子,不过现在都做出来了,有点爽。

还剩E、F两题。

下午开始搞E。有点像个大代码数据结构题,不过如果真是这样的话不虚,因为时间充足,呵呵。

一开始题目看错了,以为是链上插入一个元素,查询过一个点的元素中前 $k$ 小的异或。我想这不就是把链拆成到根的路径以后转成查子树区间 $k$ 小吗,可持久化线段树就搞定了。E题肯定不是这么简单!又读了遍题目,才明白真正的题目意思是:每个点 $i$ 维护一个初值为 $0$ 的数组 $c_i$,每个操作 $(u,v,a,b)$ 把链 $(u,v)$ 上所有点 $i$ 的 $c_i[b]$ 增加 $a$,查询的是 $c_w$ 数组中 $c_w[i]$ 前 $k$ 小的 $i$ 的异或。

这下就不太一样了,因为用可持久化线段树虽然可以对每个 $b$ 查出 $c_w[b]$,却不能查出 $c_w[b]$ 前 $k$ 大的 $b$。不给力。

可能我需要换个想法。如果不是树而是序列呢?那就只要按顺序扫一遍过去,维护一个 $c$ 数组,遇到操作的左端点就把 $c[b]$ 加 $a$,遇到右端点就 $c[b]$ 减 $a$。用线段树维护每个 $x$ 对应的满足 $c[i]=x$ 的 $i$ 个数就能查前 $k$ 小了。可是一样多的按 $i$ 排序怎么搞?

那就把每个 $(c[i],i)$ 表示成一个数 $c[i]\cdot B+i$。

值域好像很大的样子,线段树要动态开节点- -那么如果是树呢?树剖一下?

于是一个操作被拆成了 $O(\log n)$ 个,每次要改线段树,复杂度变成 $O(\log^2 n)$ 了- -

不知道能不能过,而且觉得空间会爆炸的样子。不过空间好像不是 $O(m\log^2 n)$ 而是 $O(m\log n)$?我写下。……写完了,调一发。……过样例了。

然后在51nod上运行了第一个点,MLE。

数组改小。

MLE。

再改小。

MLE。

再改小。

RE。

想放弃。

然后记起51nod好像是64位机?如果我把指针改成 int 下标呢?改。

改完。

测一下。

第一个点过了。

交。

WA

WA

WA

……

那应该是我写挂了。回去和暴力拍小数据,怎么都拍不WA,又拍了好多组大数据也拍不WA。这就很尴尬了QAQ

最后还是死于线段树的区间:right = m * 10000000000ll 打成了 right = 10000000000ll。这个小数据不太可能拍出来……

挣扎了一下午,终于在17:00前用两个 $\log$ 把这题卡过去了。

有希望。

现在剩下F。

所有LCS的和?我只会求 $|s_2|$ 遍LCS。可是显然过不去。

或者是需要一些特殊的状态设计?于是开始设计新的DP,结果不管怎么改都要 $O(|s_1||s_2|^2)$。GG。总觉得自己是想复杂掉坑了,可是又总是找不到可行的方法。

最后还是在rank 1的AKF帮助下才得救……AKF表示这题是“All Substring LCS”,是论文题。于是我就去看了论文,然而由于我太菜鸡了,看了很久才看懂。。。

所以到了第二天的下午才搞掉F。一看排行榜,刚好rank 10。有点感动。


这场比赛还是有一些收获的。

A题的贪心算法还是比较妙的,虽然如果做过Codechef原题以后就没什么难度了- -

B题给我的启发是:形如 $f(i)=a_i+\sum_{j=0}^{i+1}c_{i,j}f(j)$(其中 $\sum_{j=0}^{i+1}c_{i,j}=1,c_{i,i}\ne 1$)这样的方程,可以按照 $i=0,1,2,\cdots$ 的顺序递推,这样的好处是,每个 $f(i)$ 可以表示为 $f(i+1)+p_i$ 的形式,可以归纳证明:

$$f(i)=a_i+\sum_{j=0}^{i-1}c_{i,j}[f(i)+\sum_{k=j}^{i-1}p_k]+c_{i,i}f(i)+c_{i,i+1}f(i+1)$$

$$\Rightarrow f(i)=a_i+(1-c_{i,i+1})f(i)+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k+c_{i,i+1}f(i+1)$$

$$\Rightarrow f(i)=\frac{1}{c_{i,i+1}}(a_i+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k)+f(i+1)$$

即 $p_i=\frac{1}{c_{i,i+1}}(a_i+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k)$,若已知 $f(n)=0$,按 $i=0,1,2,\cdots,n-1$ 顺序递推 $p_i$ 可以求出所有的 $f(i)$。另外我还是很好奇这题为什么要注意精度,直接写应该就过了吧?

C题的收获是求 $x^ie^x$ 的积分以及用偏导求多元二次函数的最值(其实原理和初中学的二次函数一模一样)以及克服看到一大坨数学公式时的畏难情绪

D题的思路很不错,也是容易想错的题,主要是容易往基尔霍夫矩阵等复杂算法考虑,却解决不了。能深入理解Kruskal这一个算法,比涉猎各种复杂的图论算法(如基尔霍夫矩阵等)有意义得多。

E题后来immortalCO给我讲了一个更简单的做法:按照我之前的想法拆链之后,不用可持久化线段树前缀和来查询,而是对每个节点维护子树的 $c$ 数组以及对应的排序列表,用平衡树启发式合并来维护。这样虽然时间也是 $O(n\log^2n)$ 的,但空间是 $O(n)$ 的,不需要强行优化内存常数。想想我去年做一道Codechef的启发式合并题想了好几天才想到正解。可见我还需要加强数据结构的灵活变通能力。

F题的收获是学习了一个新的算法ALCS,这个算法思想是很不错的,利用特殊的单调性来改变状态设计。希望能找到这类问题的更多应用。

一些可能可以使UOJ #289改成真正的提交答案题的方法

2017-03-01 22:03:46 By WrongAnswer

以下是本人的一些脑洞,不喜勿喷。

UOJ #289(【WC2017】排序)是一道提交答案题,然而在UOJ上却以传统题的形式出现。这看起来十分不和谐,违背了UOJ(Universal Online Judge)的“Universal”特点。况且改成传统题以后做题也十分不方便,比如本人第1个测试点写的是 $O(n^2K)$ 的程序,尽管可以跑出来但无法在 $2\texttt{s}$ 内跑出来,于是虽然考场上可以通过,却无法在UOJ上提交通过。

之前本人联系过管理员jiry_2将这题改为提交答案题,得到的答复是:不太行,上传的文件太大了。然而仅仅因为输出文件太大就可以让这题“变味”吗?显然不行!

于是,我有以下几种想法:

1、压缩提交文件大小

这题一共 $\sum T=100$ 组数据,每组数据输出的比较器可以达到 $num=10^6$ 个,这意味着需要输出 $10^8$ 个三元组 $(u,v,t)$。

由于 $1\le u < v\le n\le 10^5$,$1\le t\le 150$,所以本质不同的比较器约有 $7.5\times 10^{11}$ 种,而 $2^{40} > 10^{12}$,意味着存储一个比较器需要用大约 $40$ 个bit。如果要存 $10^8$ 个这样的三元组,那么就需要 $4\times 10^9$ 个bit,约 $500\texttt{MB}$。

这个数据文件实在太大了,能不能压缩?

注意到 $t\le 150$,可以对每一个 $t$ 存这一层所有的 $(u,v)$ 二元组。另外,这些二元组是顺序无关的,可以将所有的二元组按 $u$ 排序,然后存相邻两个 $u$ 的距离。考虑一种比较坏的情况:每层都有 $10^6/150$ 个二元组,相邻的 $u$ 距离相等,这个距离约是 $15$。考虑用这种方法表示一个数:先输出 $t$ 个 $1$,然后输出一个 $0$,最后输出一个 $4t$ 位整数。如果按平均 $t=2$ 来估计,由于同时也要存所有的 $v$,那么输出一个二元组平均需要 $11+17=28$ 个bit,这样总共文件大小就是 $2.8\times 10^9$ 个bit,约 $350\texttt{MB}$。

遗憾的是输出文件似乎仍然很大。并不知道能否用一些数据压缩算法来进一步减小数据大小。不过看起来不太可行……(也许jiry_2有更好的办法?)

2、在本机上进行评测

那么,是不是可以参考现场的评测方法呢?

考试现场是在本机上测试的。实际上,选手在做题的时候就已经知道了得分。

因此可以用一种方法:在本机上测试完之后,将得分提交到UOJ。不过直接提交得分是有问题的,因为选手可以直接改这个得分,如果选手并没有通过这题,但通过直接修改得分而制造了满分的假象,就很不公平了。

我们设计一个程序 $P$,$P$ 接受用户的输入文件,计算出各测试点的得分情况 $S$,然后输出 $O=f(S)$,其中 $f$ 是一个加密函数。提交到UOJ之后,将提交的文件 $O$ 进行解密,得到 $S=f^{-1}(O)$。如果加密函数 $f$ 设计得足够好,在不知道 $f$ 函数的情况下,提交文件 $O$,解密出的 $S=f^{-1}(O)$ 相当于一个随机数,能够通过测试的可能性几乎为 $0$。

这样得到的结果可能是所有人提交的文件都相同,就像UOJ #200一样。其实这并没有什么关系……

Q:如果选手用其他人的提交文件然后直接AC了,怎么办?

A:可以将题目设置为AC以后才能查看代码,如UOJ #259。另外即使不这么做也没关系,可以使加密文件大小超过 $500\texttt{B}$,由于UOJ只能查看提交的前 $500\texttt{B}$ 文件,使用其他人的提交文件也不管用了。

另外此做法可能还是有一些漏洞,欢迎提出。

UPD:目前还有一个待解决的问题:如何防止反编译程序破解加密器。这个问题本人暂时还没想到如何解决,欢迎提供建议。

清华集训2016订正记录(待更新)

2017-02-24 11:32:11 By WrongAnswer

UOJ上终于有了清华集训2016的题,喜闻乐见。于是乎,本人开始考后订正了。

这里是本人参加清华集训2016留下的各种遗憾:http://wronganswer.blog.uoj.ac/blog/2161


Day 1

T1:Alice和Bob又在玩游戏

http://uoj.ac/problem/266

考场情况

这题我的考场情况是这样的:

一眼作业题,我会 $O(n^2)$,很快码完60分。然后不是很会,之后思考的时候通过打表找规律,但没有发现任何有意义的性质,研究了几种构造性的方法但都是错误的。花费1h以上,没做出来。

怎么办?回到原来的式子,强行用个数据结构维护每个子树的所有转移?这样看来就是个Trie树合并?好像会做了。

写了1h,最后10min写完,连样例都没过,没时间调。

最后得分:60。就是开场提交的暴力分。

考后分析

这种博弈论问题属于我最经常掉坑的各类问题之一。显然可以想到一种基于Sprague-Grundy定理的暴力算法:用 $T_v$ 表示以 $v$ 为根的子树,记 $g(v)$ 为 $T_v$ 的Grundy值,转移时枚举选择的点 $x$,设 $T_v$ 中与 $x$ 到 $v$ 的路径相邻的点集为 $S_{v,x}$,那么选择 $x$ 转移到的状态Grundy值为 $\bigoplus_{u\in S_{v,x}}g(u)$。从而 $T_v$ 的所有操作转移到的状态的Grundy值集合 $G_v$ 为

$$G_v=\{\bigoplus_{u\in S_{v,x}}g(u)\lvert x\in T_v\}$$

可得 $g(v)=\mathrm{mex}G_v$。设根节点集合为 $R$,那么先手必胜当且仅当 $\bigoplus_{v\in R}g(v)>0$。关键在于如何快速计算所有的 $g(v)$。

这个问题直接做就行了。用 $C_v$ 表示 $v$ 的子节点集合,设 $x_v=\bigoplus_{u\in C_v}g(u)$。如果选择的点 $x=v$,那么转移到的状态Grundy值为 $x_v$。如果选择的点 $x\ne v$,那么 $x$ 就在以某个 $u\in C_v$ 为根的子树内。枚举这个 $u$,那么对于一个 $x\in C_u$,$x$ 到 $v$ 的路径分成 $x$ 到 $u$ 一段以及 $v$ 单点这两部分。和 $x$ 到 $u$ 这段路径相邻的点集 $S_{u,x}$ 的Grundy值为 $\bigoplus_{y\in S_{u,x}}g(y)$,和 $v$ 相邻的点集的Grundy值为 $x_v\oplus g(u)$,因此

$$G_v=\{x_v\}\cup\bigcup_{u\in C_v}\{\left(\bigoplus_{y\in S_{u,x}}g(y)\right)\oplus x_v\oplus g(u)\lvert x\in C_u\}=\{x_v\}\cup\bigcup_{u\in C_v}\{g'\oplus x_v\oplus g(u)\lvert g'\in G_u\}$$

同样地 $g(v)=\mathrm{mex}G_v$。暴力求出所有集合 $G_v$ 以得到所有 $g(v)$ 复杂度仍然是 $O(n^2)$ 的,可以用数据结构来维护集合。这里的操作是,对每个 $v$ 将所有子节点 $u\in C_v$ 的 $G_u$ 集合中所有数异或上一个数 $x_v\oplus g(u)$,然后求出这些集合的并,再加入一个数 $x_v$。把每个 $G_v$ 建成一个二进制Trie树,整体异或可以用标记实现,查询 $g(v)=\mathrm{mex}G_v$ 可以在树上二分以 $O(\log n)$ 的时间求出。合并集合时,用Trie树合并可以在 $O(n\log n)$ 的时间内完成所有合并。

这样总复杂度就是 $O(Tn\log n)$,得分100。代码实现并不复杂,主要在于要想清楚,注重思维。

总结

这题的得分情况是:现场大多数人AC了这道题,少数(不足20个)没有AC这题的人也有大多数是因为正解写挂导致的。我没能做出此题可以说是很不应该的。可以看出我平时有一大思维误区:做博弈论题不管三七二十一先打个表再说。对于这种没有太多性质、直接用数据结构就能维护的问题,打表并没有什么卵用,反而浪费了太多时间,用朴素的想法去考虑是必不可少的。

阅读更多……

WC2017 暴力之战

2017-02-08 21:15:04 By WrongAnswer

由于我太狭隘了并不知道别的东西有哪些值得写,我就讲下自己这次参加WC比赛的状态吧。

考前几天刷了一波题:http://wronganswer.blog.uoj.ac/blog/2314 ,尽管改变不了我是无实力选手的事实。


8:35,终于开考了。

首先开场的时候看了下三道题。第一题看起来是个要推性质的题,我这种辣鸡水平就别想做出来了。第二题是个卡常数题,感觉很丧病。第三题是个构造类提交答案题,不太确定自己能搞多少分。

于是开场看第1题,发现有 10 分 $n\le 8$,开个 $8^7$ 的数组暴力 DFS 就过了,再看下面 $m=n-1$ 有 10 分,树上以 $0$ 为起点的路径只有 $n$ 条,DFS 枚举路径然后更新答案。后面还有 20 分 $m=n$,基环外向树,那么路径肯定是从起点往环上走,绕几圈,再往下走到终点,那么把起点和终点都移到根,去掉 $0$,看下环是不是循环同构的。

这样分三个 namespace 写就有 $40$ 分了,写完以后把树和暴力拍,过了,很开心,然后把基环外向树和暴力拍,WA 了,调了好久发现我只判了环是循环同构的,没判剩下树的部分相同,改完就过了。

接着再想有没别的部分分拿,想想网格图感觉就是个八数码,这不是 NP-Hard 的?又想了想每条边最多属于一个环的,发现两个环相接的不会处理,就放弃了。

这样第1题正常情况下就有 $40$ 了,接着看第2题。

第2题是个三合一,第一个Subtask是把 $n$ 个小于 $2^{32}$ 的非负整数排序,我会Radix Sort,不知效率如何。然后我就用链表写了个Radix Sort,写的时候发现指针数组 next 和存答案的数组 b 开了以后就爆内存了,就把输出答案的函数拷到了主程序里面一边遍历一边输出。写完过了测试点1,运行下测试点2,结果……

跑了10+s。

怎么办?我想一定是数组访问不连续导致这么慢。那就在Radix Sort之前先求出每个radix的出现次数,然后开一个连续的数组,算出每个radix对应的区间实现类似不定长数组来替代链表,改完以后WA了。调了好久才发现我原本是倒着 for,改写法以后要正着 for。这样测试点2跑进2s,测试点3……跑不过去。

觉得自己很没救就看子任务2,看起来像卷积,想FFT发现不会处理区间询问,如果再怎么处理一下复杂度就炸。这个点做法应该是压位?于是写了很久的压位,还调了很久,终于调出各种诸如 <<>> 打反之类的错误,终于过了测试点4,却过不了测试点5。想加优化,结果不管怎么优化都要跑十几秒。暴力分即视感。

感觉我真是逗比得不行,明明分没多,我干嘛去写细节巨狗的压位啊= =b

阅读更多……

WC前的刷题记录

2017-02-03 20:53:53 By WrongAnswer

就要WC了,然而我还是一堆简单题不会做。人弱就要多刷题,于是就刷了一些我觉得很难的题。

如果大家发现有什么问题欢迎提出。


目录

  • 1、Codeforces 717A
  • 2、TCO2014 Round 3B Div1 1000
  • 3、Codeforces 722E
  • 4、Codeforces 713D
  • 5、Codeforces 762F
  • 6、UOJ #54
  • 7、Codeforces 715C
  • 8、LYDSY 3451
  • 9、UOJ #59

1、Codeforces 717A

给定整数 $k,l,r$,设 $T$ 为所有长度在 $[l,r]$ 间且不存在相邻两个0的01串的集合,求从 $T$ 中取出恰好 $k$ 个长度相同的串的方案数除以 $1,000,000,007$ 的余数。$1\le k\le 200,1\le l\le r\le 10^{18}$。

http://codeforces.com/problemset/problem/717/A

这场比赛我参加过,然后挂了……主要就是一开始想了很久的这一题,一直以为是矩阵快速幂,结果想了很久没能把矩阵构造出来。最后只好放弃了这题。

后来看了题解才发现这题做法好神。

首先,记 $f_i$ 为长度等于 $i$ 且不存在相邻两个0的01串个数,显然 $f_0=1,f_1=2$。考虑一个长度等于 $i$ 的01串,如果第 $i$ 位是1,那么只需前 $i-1$ 位不存在两个相邻的0即可,有 $f_{i-1}$ 种,如果第 $i$ 位是0,那么第 $i-1$ 位是1,有 $f_{i-2}$ 种,即

$$f_i=f_{i-1}+f_{i-2}$$

不难发现这就是一个Fibonacci数列,如果记 $F_i=\begin{cases}i,&i < 2,\\F_{i-1}+F_{i-2},&i\ge 2\end{cases}$,那么 $f_i=F_{i+2}$,于是答案等于

$$\sum_{i=l}^rC_{f_i}^k=\sum_{i=l}^rC_{F_{i+2}}^k$$

用经典的计数方法,记 $S_n=\sum_{i=0}^{n-1}C_{F_i}^k$,则答案为 $S_{r+3}-S_{l+2}$。

前面的这些转化都很简单,问题来了,如何计算 $S_i$?

阅读更多……

为什么开O2比不开O2慢?

2017-01-31 12:12:58 By WrongAnswer

WC滚粗前的倒数第二帖

UOJ#103先求后缀数组,预处理height数组的Sparse Table,然后用Manacher找出每一个回文串在后缀数组中二分,结果TLE了。

http://uoj.ac/submission/124418

(后来改成在单调栈上二分过了 http://uoj.ac/submission/124428

本机上构造了一组数据 $s=\mathrm{abacabadabacaba...}$($|s|=300000$),跑不到 $1\texttt{s}$ 就跑出来了。在UOJ自定义测试里面运行了 $1\sim 1.1\texttt{s}$。

感觉很奇怪,难道是O2变慢了?

于是本机开了O2,也要跑 $1.1\sim 1.2\texttt{s}$。UOJ自定义测试里面加上 __attribute__((optimize("-O0"))) 以后,也只要 $0.7\sim 0.9\texttt{s}$ 了。

加上 __attribute__((optimize("-O0"))) 以后卡过去了,而且还不一定能卡过去。

http://uoj.ac/submission/124462

另外UOJ#201的题面 $v_4$ 应该改成 $v_3$

记一次冒险的举动

2017-01-26 18:39:35 By WrongAnswer

今天是Goodbye Bingshen。

好久没打UOJ比赛了,于是就来打了一次。

一开场看到第1题,感觉我以前思考过这个问题,于是推了个很简单的结论:如果 $n < 4$,答案是 $1$,否则是 $-1$。交上去以后重新想了下发现证明有问题,但重新证明以后发现结论是对的。

接着看第2题,构造题,继续猜结论,每个点和 $n$ 连边,自己试到 $n \le 9$ 好像都没有反例。也就这么交了。

交完以后重新想了下,发现如果 $n$ 大一点,答案是 $2n-3$,如果先构一条 $5$ 点的链,在中点往下构一个这种树,答案是 $3n-13$。卧槽。

于是就想枚举一下树的深度,然后先构最长链,再递归下去构造。用一个类似记忆化搜索的东西求了下发现最优解深度不超过 $70$,于是就 $10000\times 70^2$ 做完了。

看了下第三题,感觉暴力做法就是对于每个询问 $(s,t)$ 将 $s$ 子树的每个点对应一个平面点 $(w_i,d_i)$($d_i$ 为 $i$ 在树中的深度)然后记 $f(x)=\min\{d_i|w_i\ge x\}$,$s$ 到 $t$ 的最大点权为 $w_\max$,答案就是 $\sum_{x=1}^{w_\max}f(x)+d_t-d_s$。这个好像可以维护一下单调栈之类的东西,然后算一下面积?不过这只是单次询问的。多次询问就把这个东西启发式合并一下……?

Splay启发式合并,应该是 $O(n\log^2n)$ 的?(反正我只会证明是 $O(n\log^2n)$)时限 $2\texttt{s}$?看起来可以过,写一写。

UPD:后来immortalCO告诉我复杂度其实是 $O(n\log n)$

于是就开始码Splay……码了一会儿有点虚犹豫要不要码下去,于是看了后两题。

第4题好神啊,似乎不太可做,先不管了。第5题……居然是个交互式证明,要理解源代码,看了下源代码巨长无比,不太容易理解,也先不管了。

后两题都不太可A,好像还是搞第3题比较有救?

于是继续码Splay。写完基本操作以后开始维护每个点到上一个点的类似面积的东西。代码写得很长,而且自己看着都觉得常数大有点要TLE的样子。

子任务制啊,要是挂了岂不是只有暴力分了?惨!

不过既然已经写了那我就把它写完吧。写完维护面积和、树上二分、插入节点以及删除左侧不在单调栈上的节点,最后写完查询,代码已经差不多4KB了。

然后,测一下样例1,RE了……实现逻辑出了不少问题,改了一会儿输出了6……原来我忘了加上 $d_t-d_s$ 了。加上以后过了样例1,再测样例2,发现输出的顺序是乱的,才发现忘了离线询问顺序输出答案。加了个存答案的数组就搞定了。

感觉应该差不多了。交一发。

然后。

阅读更多……

做TopCoder题的一些总结

2017-01-25 10:17:36 By WrongAnswer

集训队第一次作业结束了。作业是TopCoder的156题(我完成了154题,理论上8分完成分我可以得到7.8分)。虽然我在提交的时候出了各种问题,感觉作业分会爆炸。然而我并不想退役QAQ

以下是我做TopCoder的一些总结。


1、题目形式

TopCoder和大多数OJ的题不太一样,大多数OJ都是使用用标准输入输出,而TopCoder只需实现一个关键的类(class)中的一个函数即可。函数传入的参数和返回值取代了标准输入输出。

TC的输入输出规模比较小,大多数题的数据范围都在 $50$ 以内,这是因为太大的数据点超出了Arena的容纳范围。事实上数据范围只有 $50$ 的题仍然颇有难度,这一点在之后会提到。

大多数的题目和日常做的OI题还是很类似的,但侧重点不一样。TC的组合计数以及组合优化类问题比较多,大多数题的主要难点在于思维上(当然也不乏代码题),很多题都是“暴力是指数级复杂度,难点在于想出一个多项式算法”,例如SRM 577的500,只要想到DP状态如何设计,很高的复杂度都能通过。当然也有一些 $O(n^3)$ 卡 $O(n^4)$ 之类的题,通常需要用特殊的方式进行输入(如输入字符串解密数字,输入随机数种子递推出随机数)。

2、解题遇到的困难

TC题比较难(当然是对我而言,对于C_SUNSHINE、matthew99、immortalCO等神犇来说应该是比较容易的?),我在做的时候遇到了不少的困难。

有一类问题,一开始看到的时候毫无思路,经过长时间多种方向的尝试最后才解决。

SRM 562的1000是一道有结论的树形DP问题,这题我研究了很久,终于推出了两种不同情况下的结论。其中一种情况是:$2k > n$ 时,排列 $p_0,p_1,...,p_{n-1}$ 合法当且仅当:①$p_{n-k},p_{n-k+1},...,p_{k-1}$ 这 $2k-n$ 个点构成一个连通块;②将该连通块删掉后,如果 $p_i,p_j$ 位于同一连通块,那么或者 $i,j < n-k$,或者 $i,j\ge k$;③对任意 $i < n-k$,$p_i,p_{i+1},...,p_{n-k-1}$ 构成连通块,以及对任意 $i\ge k$,$p_k,p_{k+1},...,p_{i-1}$ 构成连通块。想到这个结论以后我开始尝试用树形DP求出有多少个连通块大小恰为 $2k-n$,用树形背包的经典算法容易把满足③的排列个数也算进来,但是,对于每种选连通块的方案,贡献为满足②的把点分成 $i < n-k$ 和 $i\ge k$ 两类的方案数,这个我并不会统计。绕了不少弯路才发现其实是不从“对每个 $[n-k,k)$ 求有多少个 $[0,n-k)$ 和 $[k,n)$ 以及它们的排列方案数”考虑而是从“对每个 $[0,n-k)$、$[n-k,k)$、$[k,n)$ 求有多少个排列方案数”,也就是DP时把位于中间和位于两边的点数都计入状态。这样问题就得以解决了。事实证明这样的求和的问题转化思路是相当有趣的,以后可以出这类的题。

阅读更多……

失败的FJWC2017&FJOI2017

2017-01-19 19:21:56 By WrongAnswer

高二第二次参加省冬令营以及省选。退役前的倒数第二次冬令营。

并不希望得到多么好的成绩,只希望不要挂得太惨。

然而很遗憾,我挂惨了。


1月18日

报到。由于是外地生,和Paladin100100住进了宾馆。宾馆的质量不想吐槽。

晚上刷TC。一个晚上才刚出一道SRM 594的550网络流,1000想了个DP感觉可以优化然而没做出来,SRM 595的900调细节调了好久没调出来。我好菜啊。


1月19日

省冬第一天。

上午讲了一些偏基础的图论建模技巧,包括网络流建模技巧。有几道题还是蛮有趣的。

中午吃完饭发现手机屏幕又坏了,不明原因。有点郁闷。

下午训练。只有三个小时,手速赛差评。

第一题:给定 $h\times w$ 的矩阵,常数 $m$ 以及 $n$ 个子矩形,每个子矩形可以用 $x_1,y_1,x_2,y_2,v$ 描述,表示从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的子矩形最大值为 $v$。问有多少个矩阵满足每个数都是 $1$ 到 $m$ 的整数,且满足子矩形要求。$h,w,m\le 10^4$,$n\le 10$,$1\le x_1\le x_2\le h$,$1\le y_1\le y_2\le w$,$v\le m$。

看到 $n\le 10$ 想了想就是个容斥裸题。花了十几分钟写了个离散化+容斥过了样例就不管了。

第二题:题意比较复杂,简单的说就是给定有向图 $G=(V,E)$ 和 $s\in V$,求所有点对 $(u,v)$ 满足存在两条点不相交的路径 $s\rightarrow u$ 和 $s\rightarrow v$。$|V|\le 10^3$,$|E|\le 10^4$。

理解了很久的题意,感觉是支配树?因为如果 $s$ 到 $u,v$ 有同一个必经点就挂了,否则……好像都能构造出两条路径……可是我不会写支配树QAQ

第三题:给定字符串 $s$ 和常数 $K$,支持两种操作,一种是给定 $l,r,c$,对所有 $l\le i\le r$ 修改 $s_i$ 为 $c$,另一种是给定 $l,r$,求有多少对 $l\le l'\le r'\le r$ 且 $r'-l'+1 \le K$ 使得 $s[l..r]$ 是回文串。

看起来挺可做的啊……我来推一下。如果建个线段树,那么信息怎么合并?好像合并是 $O(K)$ 的于是单次 $O(K\log|s|)$ 不是很优秀啊。不太会。那就分块试试?以 $B>50$ 为块大小,记录下块内和块间的长度不超过 $K$ 的回文串个数,修改和查询时枚举整个的块,不满的用 manacher 暴力统计即可,就可以做到修改和查询复杂度均为 $O(B+\frac{|s|}{B}+K)$ 了?然而细节很多的样子……先是推导过程已经让我挺烦的,然后觉得这题如果不做出来应该没什么救,就刚了2个小时……写完分块准备敲 manacher 发现并不熟练QAQ

决定回去做第二题。数据规模这么小,能否不写支配树?那就是枚举两个点,把非源的必经点集合求个交,如果为空说明可行。$O(|V||E|+\frac{|V|^3}{w})$ 不知道能不能A。

第三题写了个暴力,分块写完 manacher 还没写,发现似乎有问题,然而没剩多少时间了,决定交暴力。

感觉今天正常应该有100+100+20=220吧?

出了考场,突然意识到一个问题——我离散化没检查,似乎写错了!样例里面的相邻矩形边界相差都是 $1$,发现不了这个问题!!

卧槽!!!

阅读更多……

共 38 篇博客