鉴于自己太菜了不会做F(只看出F是个很难的dp),所以只写一下A到E的题解。
A
题意:给两个数 和
,让你构造一个长度为
的数组,数组中所有数的和为
。让
尽可能大。求这个最大值。
预估难度:800
知识点:思维
思路:显然构造成 这样就可以了,输出
即可。但要注意特判n等于0或者1的情况,这种情况有可能一端或两端没有0。
B
题意:给两个长度为 的数组,每次可以交换
数组 和
数组中任意一个数。最多k次交换机会,让
数组中所有数之和尽可能大。
预估难度:900
知识点:贪心
思路:每次将 中最小值和
中最大值交换即可。可以用排序或贪心队列实现(由于数据量特别小,暴力也是可以的)
C
题意: 棋盘中每个格子有一个棋子。每次移动可以将一个棋子移到相邻的格子(可以斜着移动)。问把所有棋子移到同一个格子的移动总次数的最小值。
预估难度:1100
知识点:数学、计数
思路:由于n是奇数,显然只要把所有棋子都移到中间的就可以了。分别统计 步、
步...等棋子的数量即可。
D
题意:给一个正整数 ,让你构造一个长度为
的排列。构造方式如下:每次取一个最长的全是
的连续段,将这个段的最中间的那个
赋值成下一个数。若有多个最长的连续段,取最左。
预估难度:1500
知识点:构造、优先队列
思路:用一个优先队列维护所有区间即可,每次最长的区间出队,它的左半段和右半段入队。注意处理长度为 的区间的终止情况。
E
题意:给一段灯泡的开关情况,每次操作可以把开变成关、或者关变成开。让你用尽量少的操作,使得所有开着的灯泡相邻距离为 。
预估难度:1800
知识点:dp、预处理
思路:显然最后留着的开着的灯泡,其位置对 取模余数一定相等。那么我们可以对模
到
的所有情况分别进行计算。
首先预处理一下所有模 为
的开着的灯的数量,记为
。那么对于最后留着的为模
为
的情况,首先要将非模
为
的所有灯全部关掉,即
次操作。然后再统计模
为
内部的情况。
对于这种情况的统计,可以这样想:开着的灯记为 ,关着的灯记为
,那么相当于求经典的最大连续子串和的问题(可以不取子串,即max初始化为
)。
最后维护一下 的最小值即可。这里可以发现,两个
抵消掉了,因此最开始的预处理是没有必要的(笑),不过可以帮忙理清思路。