PlentyOfPenalty的博客

博客

Plenty of Penalty 2024 Winter Training

2024-01-20 18:06:17 By PlentyOfPenalty

转战知乎了:https://zhuanlan.zhihu.com/p/680044277

1/5/2024 EC-Final 22'

TBD

1/13/2024 EC-Final 23'

TBD

1/21/2024 UCup 1 Stage 15. Hangzhou

这场整体来说做的不是很顺利,每个题都爆了很多发才过,再次暴露出本队写不来 dirty 题的短板。

L 其实不是很前期的题,刚开始有些思路但是不是很清晰,基本上是边写边改,最后还有一个数组忘开 long long ,吃了很多罚时并且浪费了一些时间。

D 不难,但是有些降智,一开始没有想到把问题反过来变成类似完全背包的问题,后来恍然大悟了。鉴定为久疏战场(

B 由于题面错误(混淆了 dividend 和 divisor)导致调了很久,大大拖慢了做题节奏。同时本机的 isnan 函数和 isinf 函数返回了和 qoj 评测集不一样的结果,这一点有待进一步调试。

C 并不 hard,我很快就发现了关键性质和贪心策略,但却在容易处理的 Tong 的情况中想当然了,却一直在反复查看贪心部分,而实际上这部分是对的,白爆了好几发。

E 一开始以为问题可以一层层递归下去做,知道最后 45min 才意识到内部和外部不是一个问题,而应转化为用 $1\times 2$ 骨牌覆盖的问题,又没有第一时间想到二分图匹配而是上了个乱搞,搞到最后也没有通过。(经典 trick 没记牢导致的)

下面是补题环节:

K,想着想着就忘掉了很关键的叶子数量 $\le 50$ 的性质(这种事情我(@add10k)以前也发生过。。。)思路有些新颖但也不算太难,还是该想出来的。

M 看到 $n+m \le 72$ 感觉是要分大小再做的题,但是因为一直没什么人过所以没有细想。其实如果先想到 $n$ 比较小的 $2^n \times n$ 做法的话还是可以观察出 $m-n$ 小的时候的做法的,比较可惜。

1/22/2024 UCup 2 Stage 6. Warsaw

M 开场以为是签到,WA了一发后很快发现有问题。好在没浪费很多时间。后来右因为一些小细节 WA 了几发以后过了。

A 可以转化为一个类似数位 DP 的问题,开始本机和 1e7 范围的暴力都拍上了不知道怎么挂的,最后发现 dp 数组在没有用到的部分可能越界访问,并最终导致错误。后来想来应该在这种场景引入记忆化搜索,减小一定计算量的同时规避掉这种问题。

F 开场的时候 mem 有一个关于可持久化线段树的大常数做法,写了写放弃了。后面丢给 xry,最后写的比较复杂,大概是维护笛卡尔树,然后对每个值相同的联通块维护一些类似 Splay 的操作。调了很久,不知道是不是有简单做法。

K 就体现出我们队内的配合了,xry 想到了最短路数组的转移方式,丢给 mem 之后成功想到了一个清真的可持久化线段树维护方法,最后成功 1A。

G 很快就想到了确定有问题的行/列之后的解方程做法,但是在计算这些行/列的时候没有发现不能任取 12 行,而是需要关于那些错误的量满秩才行, 试图通过将$Ax=b$变成$RAx=Rb$,其中R是随机矩阵,使得大多数位置都满秩,这个做法其实也能通过,主要问题是没有看到 ascending order 以及后面解方程也只取了12条。 更好的处理方法是,判断$AB=C$是否成立是一个经典问题,随机一个行向量去乘即可。

1/23/2024 UCup 1 Stage 12. Ōokayama

L 属于是开场就看过的题,但是 mem 由于早上意识不清醒,在意识到一开始的计数方式会算重之后,没有及时想当修改方案,导致这题在前期一直没有被开。最后一小时才和 xry 双线这个题,但也没能在比赛结束前调出来。实际上最后的做法也和题解很不一样,题解注意到答案函数是积性的,故而可以只计算 $p^k$ 的位置从而简化,mem 做法则纯纯是暴力多项式处理,复杂度是 $O(\text{能过})$。

J 假了一次,后来发现只需要求 $( i , R_i )$ 形成的凸壳,然后判断是否每个区间都和凸壳有交即可。

K 把问题变成求多边形整点数量,一开始以为要半平面交/类欧之类的东西,后来发现可以求上下凸壳,然后由于斜率都是整数所以不需要类欧,只需要等差数列求和。细节有一点点多,写完还不知道哪里爆了long long,好在最后开int128过了。

M 比较快转化成了可重的最小链覆盖(最小路径覆盖),但我们都只知道不可重的时候可以转成二分图匹配,可重的时候得$O(n^3/w)$传递闭包之后变成不可重,想了很久,最后转化成了必定选所有点的条件下最小化流量,用费用流解决了。补题的时候发现只需要再将右侧点连回左侧的对应点跑一个最大流即可,$O((m+n)\sqrt n)$.

下面是补题环节:

补题呢怎么咕了???

1/24/2024 Hangzhou 22'

A 是个前期的数论,但是一直拖到 2h 的 timing 才过,主要问题是一直 RE。虽然定位到这个连数组都没开的程序大概是在给 $0$ 求逆元的时候会 Floating point exception,但我们还是花了 -5 的代价才定位到所有会导致这一问题的 bug。

E 是个有点意思的构造,mem 开场把榜看歪了导致 5 分钟会了这题的 90%,但是最后 10% 构造不出来(隔一个位置的情况,还有最后的 corner case)。中间趁着没人的时候写了个暴力。后来 xry 老师急中生智让 mem 用暴力跑一下这几种做不了的情况的构造,然后就拿下了。看来对于这种构造题,Brute force is all you need。(既然写了暴力,看看暴力能不能辅助构造

B 讨论了半天才从三个 log 搞成两个 log,add10k 对此题有点高论,请他稍后在此处补充:(咕咕咕)。

整体来说这场大部分题都比较可做,前 1h 几乎每个题都有人过,但是我们出门被 A 猛创,其他几个题也过的不太顺利,最后 B 差一点没过比较遗憾。9 题 + plethora of penalty 惨遭天狐座俘虏,离奖杯线也差了不少罚时 TAT。

1/25/2024 UCup 2 Stage 18. Dolgoprudny

B 是构造,一开始有了一些想法但猜了过严的结论,导致会把 YES 判成 NO,卡了比较长时间才发现 13 也是 YES。后面和 xry battle 了比较长的时间,终于发明了神奇的基于插入和递归的方法,顺利解决。

H 是一道多项式好题,但是 mem 现在多项式水平倒退严重,搞了半天也没有搞出来。主要还是对多项式牛顿迭代的理解不够深刻,具体的想法大概会放到博客里。

反正三个小时过后发现真一个都做不出来,就跑路吃饭了。被 Qingyu 发现后惨遭猛 D,下次不这样了呜呜呜。

1/26/2024 Shenyang 22'

F 可以假定如果总子矩阵个数是偶数就可以构造,这样就转化为 $1\times n$ 的构造,然后复制 $m$ 份(或者 $n,m$ 交换)。即构造 $\{a_i\}$ 使得 $\sum a_i=n$ 且 $\sum \binom{a_i+1}2 = \frac 12 \binom{n+1}2$。 这里满足前一个条件比较麻烦,不妨把第二个等式两边都减掉 $2n$,转化为使得 $\sum a_i\le n$ 且 $\sum \binom{a_i}2 = \frac{n^2-3n}{2}$。前一个条件变成了小于等于,大力猜想一发贪心取就是对的就过了。

H,回文字动机题,mem 口胡出来交给 add10k 做,结果他表演一个把 $1\le |S_i|\le 10^6$ 看成字符集 $10^6$ 然后大叫 PAM 做不了开 map 特别慢,最后发现根本没这回事,然后就 1A 了。

I,平衡树题(xrj:我很久很久没有写过 Splay 了,奈何印象太深刻了),一开始插入的时候没有 pushdown,好在样例比较强,结果就 1A 了。Splay 的在各种往下走的时候需要注意下要不要 pushdown。UPD:离线离散化后用线段树很容易维护,还是 naïve 了点。

这场感觉强度有点小大,虽然 dirt 的次数不多但是总罚时还是爆了,最后憾负昔日沈阳王幽灵乐团,看来还得再接再厉。

TBD

PlentyOfPenalty Avatar