2021 多校 杭电 第五场

补题

1013:

md
std确实是我这个做法
感觉有鬼了
dp 多加一个点进来 g 数组变小了
if(g[0]+t0>m)ok0=0;
改成 if(g[0]+t0>m)ok0=0,g[0]=oo; 就过了
我是伞兵
当时感觉暴力不好写,得 d^n 就没对排

事实上 n=5 就出错了,这种题还是应该拍,和字符串啥的不太一样,小数据就可能出错,不能再像之前每次等到有了数据说自己伞兵了(官方给的数据通过 909/1000)

比赛记录

三人在线训练,开着语音基本不说话,只发发在干啥

每次开局读题我说我读了,bzy又说他读了,就很气,然后今天就没做啥签到题,也基本躺了

貌似 zzs 爆发了


11 点闹钟,醒是醒了,但是好像忘了要比赛,翻身又睡,12点被zzs闹钟叫醒,就叫个外卖待在宿舍打比赛了

09 自闭了一会儿,想不出什么好的解法,但是有人 5min 就过了,硬这头皮写了:对每个颜色记录出现的位置,然后做出可能的区间,再按+1-1求下正序对就行了。后来看到群有们说这是个原题 「CodePlus 2017 11 月赛」Yazid 的新生舞会, +1-1 的逆序对数可以 (O(n)) 做,写的好像也很短,被吊打

期间 zzs 叫我去看 A,看了看和 【SDOI 2017 树点染色】本质没有什么区别,ACCESS 操作就是暴力改边的轻重,套个树剖线段树记录链上有没有轻链,再线段树的最底层再调用另一个来修改,所以只用考虑单点轻重链的变化。查询 dist(u,v) 就记录一下边权和即可;子树距离可以考虑子树内每条边的贡献,如果是轻边,那么就有子树大小的贡献,否则没有贡献;查询 4 如果按 LCT 想很简单,只要维护每条链长就行,但是我不想写,维护每个点所在链的最大深度,减去每个点的深度就好。然后就写了 240 行,不算第一次忘流同步 1A。

期间 zzs&bzy 过了 114514 个题

写完感觉没自己啥事了,看到 zzs TLE 12,就拉他代码本地跑,要 13s,然后他改用我以为写的很慢的多项式全家桶就过了 (3s多),惊讶到,拉下来本地跑一跑,然后就 RE,发现自己修不了,可能是我 gcc 版本高了,之前写的 VLA 会 RE,得改改板子了。

然后去看 13,和群有确认下题意后,感觉就二分直径,在 dp,f[x][0/1] 表示 x 子树内链不超过 二分的值的前提下,x 没用那个操作和用了那个操作的以 x 为链头的最长链的最小值,然后就一直 WA,叫 zzs 帮忙来看也没发现问题。


原文地址:https://www.cnblogs.com/flukehn/p/15096802.html