逆序输出排列\(p\)即可。
依据题意,若\(a_i\)大于\(0\),那么\(a_i\)可以免费地用在增加后续值为负的元素。
从前往后遍历数组\(a\),用一个计数器记录可免费用的正数和,每遇到一个正的\(a_i\)就加到计数器上;遇到负的\(a_i\)时就尽可能地用花费免费可用的正数去增加这个\(a_i\)。
这样遍历完一遍之后,数组中的元素就都只能花钱去操作了,求正元素的和或者求负元素的和后取相反数都可以。
通过观察可以发现:满足条件的01串必定以\(k\)为周期。
然后就只需要判断\(s\)是否可能以\(k\)为周期,以及\(s[0...k-1]\)是否可能满足条件。
实际上就是若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胜。
题目是看懂了,但是冇得思路,之后看情况补(咕咕咕)。
17min过了前3题,看了下排名是26,然后就开始自闭了
看到D题题面人傻了,本来博弈论就不太熟悉,还给整了个树上博弈,所以不太有信心做出来。仔细看了之后发现结论还是比较好推的,就是犯了低级错误疯狂WA on test2。
Codeforces Round #668 (Div. 2)/Codeforces1405 题解(A-D)
原文:https://www.cnblogs.com/zengzk/p/13624522.html