属实是失踪人口了,想了一下还是把题解打到这儿。conteset地址:https://codeforces.com/contest/1797
A.
题目大意:n*m的方格上给两个点,询问最少增加的障碍格子使得这两个点不连通。
解题思路:水题,但是手速有点慢。直接问靠不靠墙,靠几面墙,不靠墙答案4,靠一面答案3,靠两面答案2,取两个点的min。
B.
题目大意:给一个n*n的方阵,询问能不能恰好改k次(单个点0变1或1变0算一次)改成中心对称图形。
解题思路:水题,但是读错题了,一开始以为是不超过k次,发现读错题后随便改了就交了,没改全,疯狂+20,惨啊。正解:直接暴力改点,然后判n的奇偶和k的奇偶。
C.
题目大意:交互题,给一个n*m的棋盘,能提问三次,问国王最少走多少步能走到你问的点,问完后输出国王坐标。国王能朝八个方向走。
解题思路:一眼秒,但是又读错题了,第一发没注意图片,以为只能上下左右,惨遭+20,后面改了改1AC了。正解:先问(1,1),得到a,再问(1+a,1)和(1,a+1),三个方程联立求解。他跟上下左右不同的地方在于上下左右是菱形(斜线),它是两条直线(正方形的两边)
D.
题目大意:给你一棵树,每个点有一个权值,子树的权值等于子树上所有节点的权值和。现在有1e5个操作,每个操作有两种情况:1、询问某个子树的权值;2、交换某个点和他重儿子的父子关系。重儿子就是所有儿子中节点个数最多的点
解题思路:前面+20加得太多了,心态估计有点崩了,这道题竟然往树链剖分上面在想。场上也捋清了这个只会影响x和son[x]两个点的值,但不知道怎么去找x的次重儿子。属于是很蠢了,没想到开pq,第二天写了个可删堆过了。但set跑得更快。
E.
题目大意:给你1e5个不超过5e6的数,1e5种操作:每种操作有两种可能:1、把区间l,r的每个数都变成他的欧拉函数;2、对于区间l,r,你可以选择其中的任意一个数字变成他的欧拉函数,这算一次操作,问最少多少次操作之后区间里所有数相等(但不实际修改数字)
解题思路:线段树板题,很板,但赛上习惯太差了,就是很磨蹭啊,没有很坚定地想在赛上把这道题冲出来,慢悠悠地边想边写,果然没写完。其实很简单,orz。
正解:phi的下降次数很快,log就到1了。就算lazy不能叠加但暴力单点改也行,主要是合并,区间维护一个变一致的最小次数,以及这个次数下一致的值是多少,然后就类似求个LCA(最近公共一致值),树高不超过log,直接暴力搞,总时间复杂度mlognlogn。
标签:题目,cf864,错题,解题,权值,大意,20,赛后 From: https://www.cnblogs.com/L-Excalibur/p/17300100.html