UOJ Logo WrongAnswer的博客

博客

Codechef 6月月赛总结

2017-06-12 19:17:15 By WrongAnswer

这次月赛打得不好。传统题难度不大,就是最后一题比较码农。最后区分度主要在Challenge上,然后我Challenge切不动,就滚粗了。

做的时候也几乎是倒着做的。


Cloning(CLONEME)

如果是判断两个序列排序后是否相同,这等价于判断每个数出现的次数是否相同。把每个位置上的数 $a$ 用项 $x^a$ 表示,就转成判断区间和的多项式是否相同。随机质数 $x,p$ 然后在模 $p$ 意义下判断多项式的值是否相等,取 $2$ 个模数基本上不会错了。

但这题要求允许一个位置不同,怎么办呢?

我的想法比较naive就是了。。。用 $c_1[x],c_2[x]$ 分别表示第一个和第二个区间中 $x$ 出现次数,那么两个区间similar的条件是或者 $c_1,c_2$ 相同,或者 $\min\{x|c_1[x]\ne c_2[x]\}=\max\{x|c_1[x]\ne c_2[x]\}$。

考虑如何快速求 $\min\{x|c_1[x]\ne c_2[x]\}$,可以二分 $x$,然后判断 $c_1$ 和 $c_2$ 的前 $x$ 项是否都相等,把 $c_1$ 和 $c_2$ 前 $x$ 项对应的多项式(模意义下)的值搞出来比较就行了。

至于怎么搞出来呢,其实要算的是这个东西:

$$\sum_{l\le i\le r,a_i\le k}x^{a_i}$$

用可持久化线段树前缀和维护每个前缀的区间多项式值,将 $r$ 的线段树与 $l-1$ 的线段树相减后在其上二分即可求出 $\min\{x|c_1[x]\ne c_2[x]\}$ 和 $\max\{x|c_1[x]\ne c_2[x]\}$。

复杂度 $O((N+Q)\log A)$。也许有更优做法……?


Persistent oak(OAK)

一道比较裸的数据结构码农题……

树枝之间构成了有根树的结构。用 $W_v$ 表示结点 $v$ 目前还能再承受的重量,初始状态下,$W_v=w_v$。

对于第1种操作,在结点 $u$ 上挂 $x$ 的重量,那么断开的结点是 $u$ 的祖先中最深的一个 $a$,满足 $W_a < x$。断开 $a$ 相当于把以 $a$ 为根的子树内的重量清零(即对结点 $a$ 进行第2种操作)。如果没有结点断开,则 $u$ 及其所有祖先 $v$ 的 $W_v$ 值都会减少 $x$。

对于第2种操作,将以 $u$ 为根的子树清空,记目前以 $u$ 为根的子树的总重为 $U$,即 $U=w_u-W_u$,该操作将以 $u$ 为根的子树中的结点 $v$ 的 $W_v$ 恢复为 $w_v$,将 $u$ 的祖先 $v$ 的 $W_v$ 增加 $U$。

这两个操作可以用树链剖分线段树来维护,复杂度 $O(n+m\log^2n)$。由于题目要求可持久化,要用可持久化线段树。区间修改的标记最好永久化,可以省内存。(我用的 unsigned 自然溢出,比较两个数时判断两数的差是否不大于 $10^7$,感觉卡不掉)

写起来细节好麻烦啊……前后总共花了大概一天才切掉这题。(当然也有可能是我太菜了)

(论连写两题可持久化线段树是一种怎样的体验)


Chef and Prime Queries(PRMQ)

用 $P$ 表示质数集合,$e(x,p)$ 表示最大的 $t$ 使得 $p^t|x$,则要求的式子是

$$F(L,R,X,Y)=\sum_{i=X}^Y[i\in P]\sum_{j=L}^Re(a_j,i)=\sum_{i=X}^Y\sum_{j=L}^R[i\in P]e(a_j,i)$$

考虑构造一个矩阵,矩阵的第 $i$ 行第 $j$ 列为 $[i\in P]e(a_j,i)$,由于 $10^6$ 以内每个数最多 $7$ 个质因数,因此矩阵中非 $0$ 的数不超过 $7N$ 个。

接下来就是询问子矩形的数值和,把询问转成

$$F(L,R,X,Y)=F(1,R,1,Y)-F(1,R,1,X-1)-F(1,L-1,1,Y)+F(1,L-1,1,X-1)$$

就可以离线之后用树状数组做。时间的话,$(7N+4Q)\log_2a_i\le 2.2\times 10^7$,可以接受的。


Pairwise union of sets(UNIONSET)

感觉很迷的一道题,数据范围这么小似乎就是个暴力题?

暴力枚举两个集合 $i,j$,$O(len_i+len_j)$ 判断两个集合并集是否为全集,总复杂度就是 $O\left(\sum_{i=1}^N\sum_{j=1}^N(len_i+len_j)\right)=O\left(N\sum_{i=1}^Nlen_i\right)$。还可以 $i$ 枚举较大的集合,$j$ 枚举较小的集合,如果 $len_i+len_j < K$ 就不判,省掉至少一半常数。

什么……这就能过了???


Triplets(SUMQ)

这题感觉很像NOIP2015普及组T3。。。

做法也相当简单,稍微化简一下式子

$$\sum_{x\in A}\sum_{y\in B}\sum_{z\in C}[x\le y][y\ge z](x+y)(y+z)$$

$$=\sum_{y\in B}\sum_{x\in A,x\le y}\sum_{z\in C,z\le y}(y^2+xy+yz+xz)$$

$$=\sum_{y\in B}\left(y^2\sum_{x\in A,x\le y}\sum_{z\in C,z\le y}1+y\sum_{x\in A,x\le y}x\sum_{z\in C,z\le y}1+y\sum_{z\in C,z\le y}z\sum_{x\in A,x\le y}1+\sum_{x\in A,x\le y}x\sum_{z\in C,z\le y}z\right)$$

把三个数组从小到大排序,然后从小到大枚举 $y$,用Two-Pointers技巧维护最大的 $x\in A$ 满足 $x\le y$ 以及最大的 $z\in A$ 满足 $z\le y$,同时维护 $\sum_{x\in A,x\le y}1$,$\sum_{x\in A,x\le y}x$,$\sum_{z\in C,z\le y}1$,$\sum_{z\in C,z\le y}z$,就做完了。

复杂度 $O(p\log p+q\log q+r\log r)$。


Chef and the Feast(NEO01)

这题我想了挺久的样子,当然也有可能是我太弱了

直接做不好做,先推几个结论。以下用 $(C,S)$ 表示大小为 $C$,和为 $S$ 的集合。

结论一:存在最优解,只有一个集合的和非负。

证明:假设存在两个集合 $(C_1,S_1),(C_2,S_2)$,其中 $S_1,S_2\ge 0$,合并两个集合,得到 $(C_1+C_2,S_1+S_2)$。

新的带权和为 $(C_1+C_2)(S_1+S_2)=C_1S_1+C_1S_2+C_2S_1+C_2S_2\ge C_1S_1+C_2S_2$。

所以可以把非负的集合两两合并,总和不会变少。

结论二:存在最优解,除了和非负的集合以外,每个集合最多包含一个元素。

证明:假设存在集合 $(C,S)$,$C>1,S < 0$。不妨设 $x$ 为集合中的元素,且 $x < 0$。则将集合拆分成 $(C-1,S-x)$ 和 $(1,x)$。

新的带权和为 $(C-1)(S-x)+x=CS-Cx-S+2x=CS+(2-C)x-S>CS$。

所以可以将和为负数且包含多个元素的集合中的负数拆分出来,总和不会变少。

推论:最优的集合划分方案一定是一个包含所有非负数和若干个负数的集合 $X$ 与其余的只包含单个元素的集合。

枚举 $X$ 的大小,把非负数全部放入 $X$。接着考虑哪些数要放入 $X$,由于放入 $X$ 的数的系数不小于 $1$,而不放入 $X$ 的数的系数等于 $1$,故应把最大的几个数放入 $X$。

最后写法是,将序列 $A$ 排序并预处理前缀和,然后枚举 $X$ 的大小 $k$,把后 $k$ 个数分一组,前 $N-k$ 个数每个分一组,用前缀和 $O(1)$ 算答案。

复杂度 $O(N\log N)$。

(感觉这题有更好的分析方法啊?这题只是第三题啊我怎么做得这么麻烦啊?)


Xenny and Coin Rankings(XENRANK)

水水的纯数学题,不想写题解了。

#include<cstdio>
int main(){
    int T,U,V;scanf("%d",&T);
    while(T--)scanf("%d%d",&U,&V),printf("%lld\n",(U+V)*(U+V+1ll)/2+U+1);
}

A Good Set(GOODSET)

水水的智商题,不想写题解了。

#include<cstdio>
int main(){
    int T,n;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int x=500;n--;x--)printf("%d%c",x," \n"[!n]);
    }
}

刚掉这些题以后,最后剩下两题ES和SBTR。看了下题,感觉不太可做。

Euler Sum(ES)

求 $\sum_{i=1}^n\lfloor ei\rfloor$,$n\le 10^{4000}$。等等——代码长度限制1KB?!FML?

C++不可A,钦点我们要用Java或者Python这些自带高精度的语言。。。还好我会那么一点儿Python。。。

一开始想是不是要利用 $e$ 的性质而不用求出 $e$ 的高精度近似值,后来想想觉得没救。因为如果这题能做,$n=10^{4000}$ 的答案减去 $n=10^{4000}-1$ 的答案就能得到 $e$ 的高精度近似值……嗯也许这题做法很暴力qaq

继续想,感觉似乎见过类似的题,好像强上类欧几里得算法可以搞过去?

接着就

from decimal import *
getcontext().prec=1000

接着 $e=\sum_{i=0}^k\frac{1}{i!}$ 暴力算出 $e$ 的小数点后1000位,然后用类欧几里得算法搞搞搞。。。至于这么搞呢,大概就是考虑函数 $y=kx+b$ 的图象在 $x\in[1,n]$ 区域与 $x$ 轴之间的整点个数,一开始令 $k=e,b=0$,然后每次先把 $k,b$ 模 $1$(同时累加上模掉部分的点数),再把坐标系转90度,把原点移到原来坐标系的 $(n,\lfloor kn+b\rfloor)$ 位置,一直迭代就行啦。

调了很久调过样例,又调了一会儿参数轻而易举把 $n=10^{100}$ 跑过去了,正欢喜的时候测下 $n=10^{4000}$……TLE飞了……

算了先交拿个50分再说,接着想办法优化= =

然后你懂得本sb干了什么事情,各种优化运算次数调精度甚至一边迭代一边把 getcontext().prec 改小什么的都用上了,就是要跑好几十秒,没救2333

接着觉得这题不是什么类欧几里得能搞过去的,就继续想……然而并没有想出更好做法= =b

然后,某天晚上突发奇想,类欧几里得的原始形式不是 $y=\frac{ax+b}{c}$($a,b,c\in\mathbf{Z}$)吗?如果把 $e$ 写成分数不是就不用 decimal 了?而且从NOI2016上学到的知识,分数类跑得比高精度小数快……

嗯!这样一定会快很多!

然后重新写了一发分数版的类欧几里得算法,居然直接AC了,2333

一看虽然这题时限是2s但Python时限10s,于是我的程序7s+跑过去了……感动……

做完9题以后终于可以专心搞Challenge了。。。


Saboteur (Challenge)(SBTR)

唉。。。说多了都是泪。。。姿势水平不够最后只有89.918分,被fjzzq2002等大爷怒踩。。。

看完题,发现如果转成补集,就是求最大点权和树形导出子图。然后看数据类型,

1、$N\le 20$,暴力。。。

2、$N\le 40$,好像暴力要加一些剪枝?

3、$M=N$,基环外向树,枚举删掉一个点?

4、$M\le N+3$,好像做法差不多?

5、$M=\frac{N(N-1)}{2}$,这不就是取一条边吗。。。

6、Wheel Graph,不懂

7、Random Graph,没啥思路

于是开始刚 $N\le 40$,想着想着想到我的集训队论文上去了,感觉可以只搜极大树形导出子图,用Bron-Kerbosch算法思想,维护两个集合,一个是当前选的点 $S$,一个是剩下的允许加入的点 $U$,每次枚举一个 $U$ 中与 $S$ 相邻的点是否加入 $S$,如果不加入则从 $U$ 中删掉。

这样可以不重不漏枚举所有树形导出子图,然而没法只搜极大……可是这并不像极大独立集那样可以找个点Pivot来优化复杂度……

不管了先写一发,然后和大暴力拍没问题,很好……随机几组 $N=40$ 的数据……啊,跑了4s……

然后想用点度递增序作搜索序什么的,写完发现跑更慢,GG。

不是很会优化,先交吧至少能过第一个数据……卧槽爆0了?!

TLE了。。。算了明天再看什么情况

……

第二天起来,对着代码看了一会儿,加了个优化,把 $U$ 中加入 $S$ 会成环的直接从 $U$ 中删掉,这样剪枝能剪更彻底些,然后不管怎么随机的 $N=40$ 的数据都秒出了,妙。再交……又爆0了?!

WA。。。

论WrongAnswer为什么叫WrongAnswer。。。查了半天的错根本没查出有错,然后判了个如果 $K\le 40$ 就跑搜索,否则直接输出0。然后,就有分了?【虽然只有1.6分并没有什么卵用】

看了下评分方式才知道怎么回事——我TM又没认真读题!评分是按照每个点的答案之和的倒数给的(?),怪不得挂一个点就全WA……【不过我还是想吐槽这种奇葩评分方式】

又打了个完全图的取一条边,分似乎没多的样子……

感觉要多分得先把随机数据搞过去……怎么乱搞呢?就这样:把搜索改成随机贪心,用BFS,每次随机一个能扩展的点扩展,多次随机取最优。尽管我也不知道这样能不能搞到足够优的解……

不过还是得试试。写了一发交上去,竟直接97分了!接着我又打了Wheel Graph和基环外向树,Wheel Graph知道是什么以后就是枚举中心取不取然后环上取最值,很好写,基环外向树统计每个子树的点权和之后删环上最小的。打完交,意料之中地分没变。

然后准备打 $M\le N+3$ 的点,看起来也能用我的论文的做法解决,然后就想怎么DP,并没有好的想法设计DP,不管怎么都处理不了连通的限制。接着开始想缩边,把度为1的点往对面缩,再把度为2的点缩成链,一条链表示成一条边,要在边上记这条链上的点集,然后外面枚举关键点,里面跑个类似MST的东西,细节非常多。。。这东西immaotalCO写过,调了一晚上才调出来。我写了一个多小时以后意识到不太可写,就删了。

看来这题的关键就在怎样做随机数据。

接着继续搞随机图,首先是把多次随机弄了个卡时,效果似乎不错的样子= =接着我试着把卡时的时限改大本机上跑,发现会不断地出更优解,就尝试优化随机化的常数。。。当然是没用的咯,因为没啥可优化的。

根据之前乱搞的经验,贪心经常比随机化优秀——比如CTSC2016D2T1,贪心每个点有3分,随机化基本没有,我考场上两种都试了一下,于是部分分拿满了2333 如果把随机化换成每次加入一个点权最大的能加入的点呢?这样只要把BFS队列换成优先队列。来,std::priority_queue<int> 走起……

测了下发现怎么贪心的答案比随机化要大不少啊,有点惨啊是不是贪心比随机化更劣啊??索性全删了。

又尝试了几种乱搞姿势还是不给力。接着突然意识到我程序求的是补集,那么更大意味着更优啊???我的脑子呢???

重新写了一遍优先队列贪心。交上去,分数变低了……为什么?我自己测的数据不都是贪心更优吗?

不管了我两个程序各跑一段时间,交上去分数多了不到1分……但我觉得贪心应该比随机化优很多啊,并不是很懂。

最后还想继续搞点分,并没有想到好的方法。前面一堆人99+分,我怎么都只能排到rank 15……


当然,Challenge最后是有重测的。

重测完我的分数变成了89.918分。

当然,别人分数也变低了,于是我名次上升了。

最后fjzzq2002 990.338分rank 7,我989.918分rank 9,ccz181078 989.907分rank 10,peehs_moorhsum 989.854分rank 11。rank 9~11的分差真是小,果然OI有时候需要运气……

然而再怎么好的运气依旧掩盖不了我不如初中生的事实= =

就要IOI了,再这么弱下去怎么行?刷的题还是太少,多刷题才能积累经验啊。

评论

fjzzq2002
ES这样居然直接用分数也能过QAQ 我写的连分数展开好像跑的差不多快 OAK可以不打标记的,打标记我卡不过去QAQ
YveH
wa爷爷大!
peehs_moorhsum
%%% 然而ES只有我是用Beatty定理做的?
SkyDec
这个ES我一脸懵逼。。 一开始看完题就感觉是乘个10^w转整数类欧,但是类欧是O(log)的,高精度是O(log^2)的。 于是总复杂度是O(log^3),10^4000怎么过? 然后用python写了一发过了。。 再也不黑python跑得慢了。。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。