首页 > 其他分享 >【cf864】赛后结

【cf864】赛后结

时间:2023-04-09 12:12:03浏览次数:56  
标签:题目 cf864 错题 解题 权值 大意 20 赛后

属实是失踪人口了,想了一下还是把题解打到这儿。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

相关文章

  • Codeforces Round 863 (Div. 3) A-C 赛后思路复盘
    A(思维)思路:观察样例可知数越大放在前面越优。遍历字符串,判断当前位置的数字和要插入的数字的关系,如果要插入的数大于当前数,那么就插入到当前数的前面。string里有一个insert函数,可以把指定字符串插入到指定下标之前。在原串下标为pos的字符前插入字符串strbasic_string&insert......
  • NKCTF MISC赛后复现
    一、hard-misc1.base32在线解码,得到公众号回复指定内容,得到flag二、blue1.使用DiskGenius挂载虚拟磁盘2.在文件夹中找一找,在主分区的目录下找到含有flag的txt三、三体1.观察图片颜色,猜测通道中有数据,使用zsteg分析一下bmp文件zsteg-a1.bmp2.发现b8,b,lsb,xy这一通......
  • 2023 ECfinal 赛后
    情绪倾泻警告3.261:30他妈的……这种感觉,这种在决赛场上失利的感觉,THUPC,NOI,三年的ECfinal,全部都是……他们在祝我成功,每次都是,但我每次都……整整一个下午一个晚......
  • 【LGR-(-17)】洛谷入门赛 #8 个人赛后总结
    【LGR-(-17)】洛谷入门赛#8个人赛后总结前言这是本蒟蒻的第一篇博客,也是对第一次参加洛谷比赛的总结,如果有错误请指出。引子本蒟蒻第一次看到比赛时就迫不及待的报了......
  • kaggle Santa 2022 赛后总结
    kaggleSanta2022赛后总结比赛表述:https://www.kaggle.com/competitions/santa-2022/overview/description2023年春节前参加了kagglesanta-2022比赛,最后获得了铜牌......
  • Atcoder ABC285 赛后总结
    A—EdgeChecker2传送门题目大意给你一棵树,输入两个\(1-15\)的数\(a,b\),求\(a\)是否是\(b\)老爹父亲这颗树如图:题目解法超级无敌暴力法(wu一种最最最简......
  • Codeforces Round #844(Div. 1 + Div. 2) 赛后补题
    A.ParallelProjection#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#definecerr(x)std::cerr<<(#x)<<"is"<<(x)<<'\n'#defineIOS......
  • Nepnep x CATCTF赛后复现
    因为开赛时咩了,当时只签了几个到,只能赛后复现一下一、Cat_Jump1.刚开始使用VM挂载试了一下,打开后没什么反应,索性直接010打开搜索一下flag的头2.得到flagCatCTF{EFI_1s......
  • CF864C Bus 题解
    题目传送门题目大意一辆汽车从\(0\)到\(a\)往返\(k\div2\)次(也就是去算一次,回算一次);原来有\(b\)升油,每行驶一单位距离消耗一升油,在\(f\)有加油站(可以加满油......
  • ICPC_2022_Xian&&Guiling 赛后补题
    FindMaximum一个很重要的性质就是f(x)表示的是x在三进制下的位数加上各位上的数字之和这个观察f(x)的题面也很容易看出来所以只需要尽量让x在三进制下2最多即可直接枚举贪......