Codeforces Round 598 (Div. 3)

作者: ffacs 分类: Codeforces 发布时间: 2019-12-31 03:42

A

你有\(a\)\(n\)元硬币和\(b\)个一元硬币,问是否可以正好凑出\(s\)元。

解法

贪心,肯定先用最多的\(n\)元,剩下的再用一元来凑。\(n\)元最多可以用\(min(a,s/n)\)个,也就是判断\(min(a,s/n)*n+b>=s\)

B

给一个\(1..n,n \leq 100\)的全排列,每一个位置最多只能和后一个位置进行一次交换,问可以得到的最小排列是多少。

解法

刚开始读错题了,以为最多进行\(n-1\)次交换,问最小排列,于是卡了很久。然后就去看了\(D\),发现\(D\)才是这个题意...于是回来重新读题。所以先把每个数字所在的位置求出来。然后从1开始往前移动,用一个used数组记录是否已经使用。还需要注意如果前面的比当前的小了也就不再移动。

C

你站在\(0\)处,要去\(n+1\)处,有\(m\)块木板,每块木板长度\(c_i,\sum_{i-1}^{m}c_i \leq n\),你每次可以移动\([1,d]\)步,且一定要落在木板上。让你安排木板的位置,问你是否能到达对岸,如果能输出方案。

解法

这题的通过人数比D还少。首先我们考虑怎么能走得最远,每一次都走\(d\)步,且从木板的最右端开始走。也就是说最远能走\(m*(d-1)+\sum c_i\) 如果$(m+1)*(d-1)+c_i < n $那么就比不可能,不然就必定可能,因为如果你板子超过了,你只要前面几步走小一点就行了。输出方案的话就是让前面都尽可能走大步,后面让板子连在一起就行了。

D

给你长度为\(1e6\)的01字符串,最多能进行\(k\)次相邻交换,问可以得到的字典序最小的串是什么。

解法

比B还好写啊。首先肯定是贪心,你肯定是先移动最前面的0的。先一次遍历,把每个0的位置都存入队列。再次遍历位置,如果这个位置最近的0移动到这里大于剩下的次数那么就输出0,否则输出1

E

\(n (2e5)\)个人,每个人有一个能力值,至少三个人才能组成一队,队伍的和谐度就是队伍里能力最大值减最小值。每个人都要在一个队伍里。求队伍和谐度之和的最小值。

解法

这个题DP应该是很容易想到了,但是的\(O( n^2)\)复杂度肯定是不行的,于是就往歪的地方想了。看完题解以后恍然大悟,最优情况下不可能有人数大于5的队伍,因为显然分成更小的会减小答案。首先排序,连续的区间组队肯定比不连续的更优。所以设\(dp[i]\)为到\(i\)出的最小值,一共有三种情况,\(i\)三个人一队,\(i\)四个人一队,\(i\)五个人一队。\(dp[i]\)的初始值要记得设为\(INF\)

发表评论

电子邮件地址不会被公开。 必填项已用*标注