8.22练习总结

发布时间 2023-08-22 16:36:34作者: 铃狐sama

模拟3

分数:
期望100+100+20+20,实际90+90+15+0

总体上:

思路还是不错的,但是细节地方没有处理到,详情见后面T1/T2/T3/T4的反思。
多多少少总是有点毛病。

个体上:

第一题:

连续三个已经想到了,但是我选择了修改最后一个而不是中间。
当时贪心的想法是:如果能通过改变最后一个让后面的不合法的话,肯定最好。
但我没思考到,有可能改变最后一个后让原本不幸福的变成了幸福的这种情况。
这样会导致后效性,可能局部成立但后面不成立。好,于是改成改变中间,但也可能G(但是过了呢)。
个人有一种冲动,我分别以前三个开头做一遍,然后答案取min,这样应该就能保证答案的正确性了吧。
实践证明,答案偏小......
所以贪心有问题,改中间的话LLLLLR,改变后LRLLLR,中间显然不合法。
所以应该是dp

第二题:

怎么说呢,我做题时大脑一片混乱,自己hack自己,却没有想到最简单的方法。
个人是已经想到了对于二进制拆分后的数,如果n一个位置为1,但是没法给他提供答案的话,就找比他大的lowbit拆分给他。
但是,困扰我的是比这个数小的情况,因为合并小的不会耗费切的次数。
要是我想到不会有影响的话就好了......

第三题:

直接黑题了,6。
这难度差距有点大啊......这正解就最大流最小割了??
但是还是有反思的地方,那就是“手玩”部分分情况没找全。以及对于限制<=x没有考虑0的情况。
补一个暴力吧......毕竟在考场上不可能想到正解的
实在不会,再见,我宁愿去改T4

第四题:

还是要反思,怎么暴力都能错啊?
原来是特判出问题了啊。
我的特判:如果询问的u和v是一样的,就输出0。
实际上的特判:u和v相同,输出u或者v。
换句话说,想当然了,答案求的是位置,而不是跳的最小步数。
悲。
以下是正解:
没有看出来这是个树形结构(尽管题目有提示)
你看原题的多简洁明了啊 https://www.luogu.com.cn/problem/CF1491H