多校中期总结

才发现时间过得挺快 多校都打了一半了

大概的流程是题目从头看,如果能在前面遇到签到题就去写,有时候读完前几题感觉不好写,就去看榜,可能会在中间出现签到题的样子。

如果比较稳的话,简单的题目花费时间应该是在几十分钟不到一小时完成的,但是出现过由于自己脑残加手残,在简单题目上浪费了很多机时,

为队伍增加了许多罚时的情况,表现的尤为明显的就是第二场的最后一题,在20多个人过的时候写完,在200多人过的时候才AC,WA两次又浪费了

一个小时,很惭愧,在其他场也都或多或少出现过在简答题目上卡住的情况,原因大多是自己写的有问题,写完的代码存在一些似是而非的地方,比如

EC训练的k++,根本没想到会在那里GG,还有打反变量的情况。赛后自己也反思了,可能是最近光顾着写计算几何了,对平时的题目缺乏训练,

导致很多之前不会有的问题产生,最近也减缓了计算几何的进展,开始补题,做cf上的题目了。过了比赛的切水部分,自己的参与度就明显下降了,

还是因为自己的姿势水平低下和智商低下= =,对于中等及以上的题目看法太肤浅,甚至根本没有思路,比如那一场的贪心从开头写到了最后,想想

自己最开始那种naive的做法,感觉很蠢。。。这也是我考虑做其他题目的原因,如果还是不去做一些其他题,思维就会愈发僵化,完全成为不了战力。

还有kc曾提到的,我们读不完题目的情况,我在上一场在过完签到题前后尝试浏览了所有题目(因为可能无法短时间想清楚解法,所以尝试了先去看题

但是好像自己没能及时把题意告诉队友= =)自己负责的部分计算几何,现在也说不上熟练,很多常见的套路算是学习了,但是真正的中等偏难及以上的题目

还是无法解决,比如EC那道天降正义,目前还是主要帮忙验证思路,辅助过题的样子,自己提供算法的情况很少。

团队方面,每个主要算法都有人负责(大概?),我和潘学姐从头看,kc从后面看,前中的节奏感觉还稳(如果不被我搞砸的话= =),后面的话感觉就有些

分散了,也会从心里感到压力,没有前面那么充实。

自己犯的一些错误是在每篇中记录的,大概会有汇总。

这两天做的一些题:

多校4 1008 phone call

有一些边,每次可以花费一些代价让一棵树上两个路径中的点互相联通,问最后和1联通的点最多有多少,花费在此情况下最少是多少

看起来就像是一个最小生成树,我们把所有操作按照权值从小到大排序,每次将路径的贡献加到路径LCA所在的集合上,然后把两个集合合并,

需要记录的就是每个点距离他最近的没有被合并的祖先是哪一个,用并查集维护即可

CF 427div2 E

交互题,现在有一个数组,共有n个数(n <= 1000),有两个数是y n - 2个是x 保证 x != y , x > 0, y > 0,给你n,x,y,不超过19次询问一些位置

元素的异或和来确定 两个y的位置

假如只有一个数y的话我们可以在log的时间内找出来y的位置,而现在有两个,肯定不能直接二分

因为两个y在不同位置,所以他们位置的二进制表示至少有一位不同,我们把n个位置按照二进制位分组,肯定会有一组是  x ^ y 或者 y,表示有一个y

的下标在该二进制位为1,所有这样的位置组成了数diff,就可以知道p1 ^ p2 = diff.那我们只要确定其中一个y的位置即可,只需要在其中一个不同的

二进制位分组中二分就可以找到一个y的位置 总次数不会超过19

CF 427div2 F

n个点n条无向边的连通图,每条边有一个权值,问去掉一条边之后,所有点依旧联通,任意两点距离的最大值最小是多少。

首先可以知道图一定是一个环套上许多树的情况,删掉的一定是环上的一条边,最大距离在每个树内,或者再两个树间产生,

树内最大值可以记录最大次大得到。对于树间的情况,先把每个环上每个点的权值赋为他树上最大的距离,最朴素的做法是枚举删掉哪条边,然后

计算剩余的点对的最大距离,这个可以通过线段树优化到一次查询log,将环展开延长一倍,相当于每次询问一个长度为环的点数的区间内的最大值,

是a[x] + dis[x - 1] + a[y] - dis[y - 1]的最大值 (y < x) 维护 a + dis, a - dis, sum即可 也没有修改

卡了很久是想了单调队列的做法,其实是错的,不能保证y < x 然而正解其实是O(n)的DP 相当于考虑枚举一条环上的边,从他左侧顺时针延伸多少,

右侧逆时针延伸多少

原文地址:https://www.cnblogs.com/drzdk/p/7327557.html