首页 > 其他 > 详细

Codeforces Round #668 (Div. 2)/Codeforces1405 题解(A-D)

时间:2020-09-07 08:12:04      阅读:90      评论:0      收藏:0      [点我收藏+]

AC代码

A. Permutation Forgery

逆序输出排列\(p\)即可。

B. Array Cancellation

依据题意,若\(a_i\)大于\(0\),那么\(a_i\)可以免费地用在增加后续值为负的元素。

从前往后遍历数组\(a\),用一个计数器记录可免费用的正数和,每遇到一个正的\(a_i\)就加到计数器上;遇到负的\(a_i\)时就尽可能地用花费免费可用的正数去增加这个\(a_i\)

这样遍历完一遍之后,数组中的元素就都只能花钱去操作了,求正元素的和或者求负元素的和后取相反数都可以。

C. Balanced Bitstring

通过观察可以发现:满足条件的01串必定以\(k\)为周期。

然后就只需要判断\(s\)是否可能以\(k\)为周期,以及\(s[0...k-1]\)是否可能满足条件。

D. Tree Tag

实际上就是若Alice和Bob之间的距离小于等于\(da\),那么Alice就赢了。

感觉sample2就是在暗示讨论一条链,在最好的情况下也就是树的直径就可以。

首先,Bob最优的操作就是先躲到直径的一端,然后等者Alice靠近时再借机跳走。

然后,在最差的情况下,Alice和Bob之间的距离为\(da+1\),也就是若Alice再靠近Bob一步且Bob不操作,Bob就输了。这个时候,若Alice不靠近,Bob就不需要操作;若Alice靠近,Bob就需要跳到离Alice新位置的距离大于\(da\)的位置。Alice用最优操作的情况下,Bob的移动距离要大于\(2da+1\)

然后就可以得出结论:当且仅当Alice和Bob的初始距离大于\(da\),且\(db\)和树的直径都大于等于\(2da + 1\)时,Bob胜,反之Alice胜。

E. Fixed Point Removal

题目是看懂了,但是冇得思路,之后看情况补(咕咕咕)

总结

17min过了前3题,看了下排名是26,然后就开始自闭了

看到D题题面人傻了,本来博弈论就不太熟悉,还给整了个树上博弈,所以不太有信心做出来。仔细看了之后发现结论还是比较好推的,就是犯了低级错误疯狂WA on test2。

Codeforces Round #668 (Div. 2)/Codeforces1405 题解(A-D)

原文:https://www.cnblogs.com/zengzk/p/13624522.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!