CF Round598 Div.3

A. Payment Without Change

题意:你有a个面值为n的硬币和b个一元硬币,问能不能整好凑出S

分析:尽可能的用n,剩下的用1去补

B. Minimize the Permutation

题意:给你1-n的置换, n ≤ 100 n\leq 100 n100,每个位置i只允许与i+1发生一次交换。问若干次交换后能得到的字典序最小的置换。

分析:贪心。先把1移到最前面,假设1最初在下标x处,那么把1移到最前面之后,区间[1,x)里的数都不会发生变化了,再递归地处理区间[x,n]。

C. Platforms Jumping

题意:一条数轴上,你在0点,1-n是河水,n+1是对岸,你需要跳跃到对岸。你一次最多跳d,河上有一些木板,你已知每块木板的长度,问能不能合理地安排木板之间的距离(木板之间不能重叠,顺序也不能变),让你可以跳到对岸。

分析:贪心。先把木板都移在对岸,每次你当前位置调不到木板上时,就移动木板到你能跳到的最远处。

D. Binary String Minimizing

题意:给你一个01串,你只能最多k次交换相邻的字符,问能得到的最小字典序的01串

分析:贪心,尽可能地把0移到前面

E. Yet Another Division Into Teams

题意:有n个同学, n ≤ 200 , 000 n\leq 200,000 n200,000,每个同学有一个能力值 a i a_i ai。先要求把这些同学分为若干组,每组至少3人,要求最小化所有组的能力差距之和。能力差距是一个组里最高能力减去最低能力。

分析:不可能出现人数超过5的组,否则可以拆分成更小的组优化目标。因此每个组的人数只能是3,4,5。排序后动态规划求解。

F. Equalizing Two Strings

题意:给你两个长度均为n的字符串, n ≤ 200 , 000 n\leq 200,000 n200,000,字符串只包含26个小写字母。每次你可以指定一个长度k,然后从两个字符串中分别选取一个长度为k的区间,把每个区间内的字符串反转(std::reverse),问能否经过若干次操作使得两个字符串相等。

思路:首先,三个结论:

  1. 如果两个字符串包含的同一字母的个数不同,肯定不能完成。
  2. k都为2就可以模拟出其他k的选法
  3. 在结论2的基础上,如果有一个字符串中有重复字母,任务就一定可以完成。(首先可以用一次操作让两个相同的字母相邻,接着每次操作另一个字符串时,就交换这两个相邻的相同字母)

对于没有重复字母的情况,任务可完成等价于两个串逆序对个数之和为偶数。
先证明必要性:在一个串内,交换两个字母的顺序导致逆序对奇偶性变化。同时在两个串内操作,逆序对之和奇偶性不变,最终答案逆序对和为偶数,必要性得证。
接着构造充分性的证明:可以定义26个字母上一种新的大小关系,使得第一个串中的字母就是从小到大排列的,那么对另一个串进行冒泡排序,同时第一个串随便找两个相邻的字母进行交换。因为逆序对是偶数,当第二个串冒泡排序完成时,第一个串和一开始一样。

最新回复(0)
/jishuombwvM5DHwvRh92XtmH8OAVprmF1kxxi6Zmfl8rK6sQ_3D4858278
8 简首页