UOJ Logo WrongAnswer的博客

博客

失败者的辣鸡本质——记51nod算法马拉松25

2017-06-02 20:26:42 By WrongAnswer

帖子公开得有点晚。

可以说很失败。


开场看A,感觉二分代码有点奇怪,不知道题目有没问题,就去看B。

B一眼想到一种做法,每个数建一个点,相等的放同一层,得到一个分层图,问有多少种连边方案使得图是一条链。看了下 $n\le 30000$,相同的数不超过 $100$ 个,也就是每层不超过 $100$ 个点,觉得挺靠谱。

然后就开始推,结果被细节恶心到了。我的想法是按一层一层顺序把边加进去,状态 $f(i,j)$ 记前 $i$ 层构成 $j$ 条链的方案数。然而是链不是环,还得记前 $i$ 层有没包含起点和终点,于是搞了个这个玩意:$f(i,j,s,t)$。

然后思博了,中间填边的时候,我以为给 $j$ 条链每条确定一个前继节点一个后继节点就行了,然后发现有环,接着就懵逼了好长时间。

想了好几种解决方法,可惜都是错的。

于是回头看A,看了讨论知道二分代码没错,那一定是我理解错了,我平时的二分习惯相当于代码里面的 $l$ 减掉 $1$,$r$ 加上 $1$ 的。

这样就好理解了。然后又想错了,一开始想到把二分结构的线段树建出来然后DP,发现线段树的节点长度只有 $O(\log n)$ 种,准备写个STL的 map 来大力DP一波。

于是开始写转移,写着写着突然发现不妙,题目求的是 $r=k$ 的概率,我连我要求啥都没搞清楚,靠。

然后继续想,发现DP只有一条路走下去,那就只要乘法原理就行了,没必要DP。接着写完主过程发现要求 $n!$,然而 $n\le 10^9$……

打表大法好,把 $(10^7i)!$ 打出来就做完了。终于在21:30左右过了A。

再去看C,这种题似曾相识的感觉(用myy的话说就是deja vu),好像强上笛卡尔树就行。然而我并不知道两个序列的笛卡尔树怎么弄。

就YY了一个分治算法,$f(l,r)$ 求 $[l,r]$ 内的满足条件的区间个数,如果 $[l,r]$ 内 $A$ 的最大值不等于 $B$ 的最大值,沿着大的那个分成两个区间递归下去,否则,设两个最大值在 $i,j$ 位置($i < j$),那么 $l\le i,j\le r$ 的 $[l,r]$ 都满足条件,然后加上 $f(l,j-1)+f(i+1,r)-f(i+1,j-1)$,递归下去算。

以为很靠谱,然后准备写,写前想想这玩意儿复杂度是个什么东东。——糟糕,炸了。

如果 $i$ 很接近 $l$,$j$ 很接近 $r$,那么序列长度没啥变化,大概按 $T(n)=3T(n-1)$ 估计,变成指数级算法了,比暴力还辣鸡,靠。

重新想,觉得只要构 $A$ 的笛卡尔树,然后对每个 $i$ 考虑 $A$ 中以 $A_i$ 为最大值的区间(即 $i$ 子树内的区间)中合法的个数。分析了一会儿意识到并不复杂,只要在 $B$ 中找到 $i$ 左右第一个大于等于 $A_i$ 及大于 $A_i$ 的 $B_j$ 就能求出答案,单调栈上二分一下?

不久把C搞出来了,22:20。看了一会儿后面的题,觉得E的 $b-a\le 10^8$ 好像是区间长度相关的算法,写了一个区间筛,光荣TLE。别的题也没啥思路。

接着想再折腾一下B,然而太迟了= =就先回去睡觉了。睡觉时继续脑补怎么fix这个算法。

第二天起来继续刚B,注意到左边每条链有两条边连向右边的点,那就等价于在右边连一条边,这样 $a$ 个点连 $j$ 条边就是把 $a$ 个点排列成 $a-j$ 个序列,就可以转移了。但还是怀疑想复杂了,B题为什么这么麻烦。

看到排行榜已经有10个人AK了,心灰意冷。

然而由于起点和终点的限制很麻烦,还是写了很久。

写完调样例也调了很久,发现我的DP对 $s,t$ 考虑是错的,变成起点和终点产生以后不会再和其它路径合并,然后就改。改完以后过了样例。

运气不错,交上去直接过了。然而还是怀疑把题做复杂掉了,代码比较长。

这时候大概10点,去做D了。

一开始思路挺对,把式子推了一会儿,发现有规律,有的项消掉了,最后剩下几个 $\sum_{i=0}^n{n\choose i}i^{k}$ 形式的东西。凭借经验判断这是 $2^n$ 乘一个 $k$ 次多项式,但这个多项式并不会求。。。插值?

接着就一直往插值方向去想,发现我把一个点值求出来都要至少 $O(n)$,求 $O(k)$ 个点值完全没救。优化的话,想到FFT,但是过不了,就扔了。

把表打出来看规律,发现次数不超过 $3$ 的规律很明显,次数一超过 $3$ 就各种鬼畜。联想到xumingkuan的互测题(我这题得分全场倒数),感觉不会又是什么黑科技题吧,反正没搞出来,GG。

中午吃饭的时候,突然想到——

诶,模数 $m$ 不是 $10^6$ 级别吗?

诶,答案不是关于 $n$ 的多项式吗?

把 $n$ 对 $m$ 取模就行了?

吃完饭就开始写,也没去优化log,写完过了样例就交,结果WA一块TLE一块的。TLE是复杂度不对,WA呢?

和暴力拍了拍,发现跑出来的结果不一样,然后把暴力的 $n$ 也模 $m$,一样了……

莫非是结论错了??这时候我突然想到答案不是 $n$ 的多项式而是 $2^n$ 乘一个关于 $n$ 的多项式。。。那就判一判呗。

12:20,D过了。

看了下E和F,好像F比较可搞?就先去做F了。

嗯,我比较傻逼,果然一开始想歪了。

一开始想DP发现状态怎么记都要状压,没救。然后分析性质,一个区间翻两次肯定不优,那就只能翻一次,用 $x_{l,r}$ 表示 $[l,r]$ 这个区间翻的次数。则最后 $i$ 点被翻的次数奇偶性就是 $\sum_{l\le i}\sum_{r\ge i}x_{l,r}\bmod 2$。

如果用 $y_{i,j}$ 表示 $\sum_{l\le i}\sum_{r\ge j}x_{l,r}\bmod 2$,那么 $x_{i,j}=y_{i,j}\oplus y_{i,j-1}\oplus y_{i-1,j}\oplus y_{i-1,j-1}$,这东西如果是1就要花费代价。

好像可以最小割建图。

然后就开始想4个变量怎么建图。2个的话很简单,4个能不能先把某3个捆绑在一起?试了试,根本建不出表示与关系的图。

又想能不能设置边权满足条件,也弄不清楚。以及想到把点染色来做,然而不起作用。

想了2h+,觉得实在没救。回过头来再分析一下什么条件没用上。

嗯,如果翻转 $[a,b]$ 和 $[a,c]$,效果就相当于翻转 $[b+1,c]$。如果把差分搞出来,消掉两个差分相当于找一条最短路?想到BZOJ3003。

这样就变成求差分之间的最大权匹配,mdzz一般图最大权匹配真的可写?反正我写不出来。

不过为了AC,我还是从UOJ上抠了个带花树板子下来改了改。于是就把F题过了。

最后是E。

由于区间筛法根本做不了,索性把 $b-a\le 10^8$ 这一辣鸡条件扔了。

接着继续作大死,一开始想用筛法函数做,然后果然出问题了,一个数被小于等于 $p$ 的数筛掉不代表这个数不含大于 $p$ 的质因数。然后想到反着筛,似乎是对的。当时我还没想过复杂度是多少,觉得预处理几个东西就能做了。

然后。。。

写写写,调调调,好不容易调对了。一交,TLE得乱七八糟。

又调了一会儿。

突然意识到有一个DP第二维会爆炸!复杂度不是 $O(n^\frac{3}{4}\log^{-1}n)$ 的!

惨啊!重新推重新推。

接着的思路是统计 $[1,n]$ 以内只包含 $p$ 以内质因数的整数个数,用 $[1,b]$ 减去 $[1,a-1]$ 即可。记 $f(n,m)$ 为 $[1,n]$ 内只包含 $[m,p]$ 以内质因数的整数个数,然后DP一波……?

第二维看起来超过 $\sqrt n$ 就可以 $O(1)$ 了?这么看来就是 $O(n^\frac{3}{4}\log^{-1}n)$ 了?

写了一发交上去……

A了……

最后是22:48:19,比rank 10晚了21h+,失败告终。


51nod六题,题题掉坑。

好几题都是花了两三个小时想甚至写出来,然后出问题,把整个算法推掉重做。

A题就一乘法原理,想到奇怪的DP。

B题想太复杂了,题解有更简单的考虑方法。

C题一开始以为自己想到了很厉害的做法,想了很久才发现很爆炸。而且看了题解正解 $O(n)$,我写的是 $O(n\log n)$,还好出题人没卡= =

D题都推出是多项式了,把 $n$ 对 $m$ 取模都没想到,去想插值了……想了很久才意识到。况且 $n$ 这么大就算能插值也过不了。

E题搞了两三个小时的错误复杂度的筛法函数DP,最后才意识到是个简单的DP。看了题解好像 $b-a\le 10^8$ 这个条件还是有用的?可以记在DP状态里,当 $a=b$ 时节省状态数?

F题搞了两三个小时的网络流最小割建图,最后才意识到是类似我做过的题。

怎么说呢,尽管参加了这么多场比赛(NOIP一等奖和APIO Au都拿了两个)但我终究还是不会做题,有的题老是被第一感觉带走,然后就想歪了,回过头来一看发现是水题。。。

想题思路也不是很清楚,B题如果理清思路也并不是特别复杂。。。

以及E和F我都做过类似的题,怎么想了那么久都没意识过来正确思路。。。

总之平时太不用功,以前刷过的题并没有好好消化。。。

不过就算没掉坑也进不了前10。。。睡一觉起来就10个AK了。。。

评论

JOHNKRAM
WA爷爷大!
AntiLeaf
您都这么强了还要恶意卖萌,我等蒟蒻也就只能默默点个差评了
kczno1
话说e题如果倒着来 dp[n][m]表示[1,n]只包含[1,m]内的质数的数的个数 可以吗 我就是这样的 但是会很难过 是不是复杂度错了
matthew99
什么叫用我的话来说就是déjà vu...这本来就是在不止一个语言中有的短语好吧...

发表评论

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