PKUWC2020

PKUWC2020——一次刻骨铭心的失败

Day0

看路人女主看到了12:20,似乎颓过头了(然而day1晚上也是差不多时间……)

Day1

开幕式都是老生常谈,下次想咕了

搞了杯咖啡,感觉暖洋洋的,就是有点昏

开题

过了1h,woc我怎么还不会t1啊,往常的t1都是送的,担心到时出来又是人均切我不会……最后还是无奈先跳了

过了2h,口胡了t2的平方做法及fft搞l=r,预计63pt,先写个暴力稳一手。

woc过不了样例2是几个意思,然后就三题跳来跳去,不知不觉3h了,发现自己一分没有,无限接近自闭

推了推t3的m=1,想了个$O(n^{1.5}log^3)$的根号分治,一直搞到剩30min时只能卡常卡到极限数据6s(时限4s),只有70

最后21+0+70,感觉又打出历史新低,心态自闭

xgc居然比我还低,pb切了t1直接180+

我俩都不太想回酒店,就瞎散散步,最后太冷跑进一间偏僻的居酒屋,一进去眼镜都起雾直接报废了的那种温暖,吃着超赞的大阪烧,感觉心情好很多,晚上与我校top2师兄快乐火锅大战到十点

发现t2看错了,以为是随机生成树即概率与集合大小相关

Day2

有一万个不想写的理由,但可能还是要面对自己的失败吧

第一个小时随意看题,t1先写了个nq的贪心:从左往右扫,对于问号,如果左边有未匹配左括号就作为右括号,否则作为左括号;因为这个非常简洁而且看起来一脸经典问题的样子就先入为主了,后来尝试换别的考虑方式都放弃了,而且一开始以为从右往左应该也能做吧,可能是倍增优化合并啥的?总之就是很可做。结果发现萎了,看t2,很快想到笛卡尔树上dp,打算先写个65的暴力验正确性,然后就tm原地搞了2h……

中途不断发现自己想的漏了些情况,对拍修锅修到怀疑人生,还好最后还是肝出来了没有前功尽弃。然而这过程中我没有放弃的主要原因是基本都能胡成如树剖或倍增,结果到最后过的时候已经没啥时间去写这个看起来不太好写的正解了(赛后想想应该确实能胡吧log方或log,但可能做法是确实不优美不好写了,细节比较多)

只剩两小时却还没开始认真想正解,此时整个人都是蒙的了,将那种想正解的心情和状态破坏得一干二净,t3甚至都失去理智在最后时刻匆忙写个按题意模拟的最小割上去获得零分的好成绩。回去看t1,试图冷静然而失败,以为倍增合并就能切了结果还是太莽夫太混乱了写完才发现是错的,又浪费了一些时间

谈笑风生是他们的,我啥也没有,只知道我已经失去任何思考能力了,大概就是个能动的有机物吧


这位老哥造了数据,且里面的题面有样例和部分分

D1T1

题意:令S(P)=将长度为n的排列中字典序不超过排列P的所有排列按从字典序小到大依次首尾连接,如S(213)=123132213,给出P问S(P)的本质不同子序列个数,$n \le 50$;2s

题解:本质不同子序列计数的基本原则是保证子序列中每个字符的位置是上一个字符后面第一个这种字符

考虑如何连接两个串,为方便连接定义$f_S(i,j)=以i开头,选了若干个,最后当需要j时要跳出S$,则连接就是做矩乘

设$A_k=最小的k!个排列依次连接得到的串的矩阵$

显然$A_1(i>0,j \ge 0)=f_{1,2..n}(i,j)=[i \ge j]2^{n-i}+[i<j]2^{j-i-1}(2^{n-j+1}-1)$,为了求答案还要定义$A_1(0,0)=1$

考虑如何$从A_k推到A_{k+1}$,这个过程相当于连接$1,2…n-k-1[剩下k个]$,变化的第$n-k$位代表了$(k-1)!$个排列连接起来的东西,那这一位从t到t+1相当于交换第t和t+1列并交换第t和t+1行。可得$n!$个连接起来的部分分,复杂度$O(n*(n*(n+n^3)))$

其实P特殊也差不多,从$1,2,..n-kP_1,P_2..P_t$的若干次交换形式化地写就是$M_{i,j} \to M’_{P_i,P_j}$(“剩下”区域的P递增编号),复杂度没有影响,code,尽管复杂度是满的开了O2还是飞快

D1T2

题意:给出n个初始只含$a_i$的集合,记每次随机选两个集合合并成一个最后得到k个集合,$f(k)=E(\sum_{j=1}^k (mx_{S_j}-mi_{S_j})^2)$,求$\sum_{k=L}^R f(k)^{97376}$,$n \le 2e5$;2s

题解:显然先根据期望的线性性拆开来算每种集合最后留下来的概率乘权值;另外设$a_i$的第二关键字为i显然没有影响
$$
对于具体的k个集合,概率=\frac{(n-k)!}{\prod_t^k (siz_t-1)!}*\frac{\prod_{t=1}^k (\prod_{i=2}^{siz_t} C_{i}^2)}{\prod_{i=k+1}^{n} C_i^2};另外先判掉f(1)=(a_n-a_1)^2
\\
设g(n,k>0)=x^n!} \frac{x^i}{i!} )^k \frac{n!}{k!}
=x^n} x^i )^k \frac{n!}{k!}=\frac{n!C_{n-1}^{k-1}}{k!2^{n-k}}
\\
f(k>1)=\sum_{l<r} (a_r-a_l)^2 \sum_{m=2}^{n-1} C_{r-l-1}^{m-2}g(n-m,k-1)\frac{(n-k)!2^{n-k}k!(k-1)!}{n!(n-1)!}*\frac{m!}{2^{m-1}}
\\
lr显然卷成b_{r-l+1},
f(k)\frac{n!(n-1)!}{(n-k)!2^{n-k}k!(k-1)!}=
\sum_{m=2}^{n-1}
\frac{g(n-m,k-1) m!}{(m-2)!2^{m-1}}
(h_m=\sum_{ln=m}^n \frac{(ln-2)!}{(ln-m)!} b_{ln})
\\
f(k)\frac{n!(n-1)!(k-2)!}{(n-k)!k!}=\sum_{m=2}^{n-1} \frac{m!h_m(n-m)!(n-m-1)!}{(m-2)!}*\frac{1}{(n-m-k+1)!}
$$

跑三次NTT即可。其实这题只要把第一行的式子写出来,从$O(n^4)$一步步优化到$O(nlogn)$每步都是上步搞完下步的思路就自然出来了,只要细致点别推错,操作都是基本功,最关键还是概率的设计不能搞错了(以后多检查一下题意转化)。

D1T3

题意:有个$n*m$且初始都是0的表格,设位置集合$(s,l,r)=\forall (i,j),gcd(i,s)=1且j \in [l,r]$,先做q1次位置集合加,再做q2次位置集合求和,$n,m,q2 \le 5e4,q1 \le 1e5$;4s

题解:看官方题解或xgc题解吧,后面30分并不想back,70分做法也没啥好分享的,就是瞎jb根号分治

D2T1

题意:给出一个形如?(((?(????((??((的序列,其中问号可选择左括号或右括号,q次独立询问取出串的前len个元素并在前面添加X个左括号后得到的串,最大化其最长的合法括号子序列,$n,q \le 4e5$;1s

题解:当时的想法是,从左往右贪心,如果左边未配对的左括号不够就把当前问号改成左括号,然而这样思考没法合并

其实不要立刻修改,看做是失配的?就做完了(应该不少人能直接这么想吧其实,直接就跳过了我遇到的困难,感觉这种事挺无奈的说)

具体而言,$(a,b,c)=a个失配的左括号,b个失配的?,已经得到c对$,所有失配的?都在失配的左括号左边,这个三元组随便合并,前缀和即可,code

D2T2

题意:给出序列$a_0..a_n$和一个n的排列P,q次询问排列中一段区间$[l,r]$,每次在区间中得到尚未考虑的最大数$p_i$,$设A为a_{i-1}块,B为a_i所在块$,将A和B合并成一个块且这个块的权值$val=val_A/val_B$,问最后$a_r$所在块的权值(一个块一开始就是一个元素且权值为此元素),$n \le 5e5$;4s

题解:很明显是笛卡尔树上搞事情。当时建的是n-1的树,然后一不小心就写得非常麻烦(直接当线段树写也能拿当时的分,但其实当时是想起码拿个80的),其实冷静一下很容易想到给数字负权建2n-1的树,从而只有叶子带权且每个非叶都有左右孩子。

思路一:类比zkw(当时想法)

以左端点向上跳为例,就是将路上碰到的每个有右孩子的点的右孩子子树答案乘起来,且第i个的次幂为-1,直接树剖就是$O(nlog^2n)$,时限较大应该ok(实在不行可以加上什么深度较小暴力跳来防止被二叉树卡)

思路二:类比猫树(题解做法)

那现在就是要求出每个线段树区间的前缀、后缀答案,以后缀为例,就是个线段树合并,打标记就是个区间乘(一定有右孩子,给左孩子的那些后缀乘上右孩子子树答案的逆元),$O(nlogn)$

D2T3

题意:给出$n \le 7e3$点$m \le 1e5$边无自环的边带权(1e4)无向图,额外在上面加入n条边$(i,i\%n+1,1e9)$,设$micut(x,y)=x和y间最小割$,求$\sum_{x<y} micut(x,y)$;3s

题解:肯定断掉恰两条1e9边,答案可以被表示为$[l,r]与[1,n] \setminus [l,r]$间的边权和$sum(l,r)$

这就是m次二维矩形加,$n^2$次二维矩形询问最小值,$micut(x<y)=min\ sum(1..x,x..y-1),sum(x+1..y,y..n)$

观察一下那两个矩形,发现前者枚举x移动y,后者枚举y移动x,配合每列前缀每行后缀最小值就能$O(n^2)$


back题感想

D1T1不会做可以接受,D1T2血亏(主要是因为不知道看错题,度过了2h过不了样例的自闭时间),如果没看错剩下时间不知D1T3能拿多少分(43到70)

D2T1不知道怎么说,毕竟不一样的那小小一点也是本题唯一的难点,没能机智地想到算是活该?D2T2的冲动直接葬送2h,剩2h心态上已经没法冷静下来思考题目了(因为不清楚这天是那种切题拉分还是分档拉分的难度),这大概是想到就去写这种策略的弊端,直接导致败北。

其实想正解的心态没掉跟难度情况也有关系,就当时没法根据自己得分判断大众拉分手段,是想正解还是敲暴力

不过这个t2的暴力说来也很活该,没有再多想想怎么能更简洁就莽了上去(以后写完题多看看别人的做法

总之这次的失败还是各种因素同时相互作用吧

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/2a79e6c2.html
转载请注明出处,谢谢!