20210920。网址:https://codeforces.com/contest/1551。
编程细节:下标定义不要一会[1,n]一会[0,n)啊…
用价值为1的硬币a枚+价值为2的硬币b枚,买价值为n的东西,希望ab之差的绝对值尽量小。大水题。
给我们一个字符串s,用红色和绿色给s上色,规则如下:
问我们涂成红色的字母有多少个。
做法:记录每个字母的数量。如果某字母数量≥2,分配一个到红色、一个到绿色、剩下都不上色。如果==1,分配它到目前比较少的颜色。上完色之后,红色数量不一定等于绿色数量,但最多差1,所以输出两个数量中较小的那个。
给我们一个整数序列a1~an,用k种颜色给它们上色,规则如下(和B1差不多):
让我们输出上色方案(而不是简单给出涂色数量)。
做法:
给我们一堆用abcde组成的词语,选取最大数量的词语来写小说,使得某一字母出现次数>其他4个字母出现次数的和。输出这个最大数量。
(给出的词语可能重复。词语不能重复使用。)
做法:
给我们n*m(n行m列)的棋盘,保证n*m是偶数。给我们n*m/2个牌,每一个牌都是日字形的,可以横着放可以竖着放。问我们,能不能用这些牌摆满棋盘,使得横着放的牌恰好有k块。如果能的话,输出摆法。
做法:
给我们一个整数序列a1~an。【一个move】的意思是删掉一个数,如23415删掉3变成2415。我们希望做尽可能少的move,使得出现≥k个【数值=下标】的数。输出最少的move次数;如果做不到【通过move操作得到≥k个数值=下标的数】,输出-1。
思路是dp。用dp[i][j]表示,考虑前i个数,其中有j个数没有被move掉,含有【数值=下标】的数的最大数量。我们从n到0枚举j,dp[n][j]即为n-j次move后得到的【数值=下标】最大数量,一旦dp[n][j]≥k,就break输出n-j。
如何得到dp[i][j]呢?我们考虑第i个数,第i个数被move掉的情况下,有dp[i][j]=max(dp[i][j],dp[i-1][j])
。第i个数没有被move掉的情况下,有dp[i][j]=max(dp[i][j],dp[i-1][j-1]+(a[i]==j?1:0))
,最后那个?:用来考察第i个数是否【数值=下标】。外层循环是i从0到n-1,内存循环是j从0到i,就得到dp了。
……(叹)。
给我们一棵n个顶点的树和一个整数k,让我们选k个顶点,要求这k个顶点两两之间距离相等,问有多少种选法。(看完题目我就直接放弃思考去看题解了…)
首先,对于k=2的情况,输出n*(n-1)/2,任意两个顶点都可以。(注意特判!)
然后,对于k=3的情况,3个顶点一定是星型结构的。即,设这三个顶点为ABC,它们一定都与一个顶点Q连接,QA距离=QB距离=QC距离。
解释:如果ABC两两连接的路径都没有公共顶点,则从A到B可以通过AB路径,也可以通过AC+CB路径,此时产生了环,不符合树的定义。那么,如果AB和AC有公共顶点Q,但BC不通过Q,也会出现同样的问题,从B到C可以走BC也可以走BQC。所以,为了【顶点之间只有一条通路】,3个顶点需要是星型结构的。
接下来,对于k≥3的情况,我们拿4个顶点ABCD出来。设ABC的中心节点是Q,BCD的中心节点是P,如果P和Q不是同一个顶点,则从B到C可以走BQC也可以走BPC,又出现了环。我们固定ABC,遍历剩下k-3个顶点作为D,就可以得到一个很强的结论:这k个顶点都是星型结构的。
做法:
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*cnt[i]
,即【不使用第i个子树】+【使用第i个子树】。外层循环是i从1到QL,内层循环是j从1到k,dp[n][k]即为所求。编程细节:dp初始化为0,但dp[x][0]需要全赋值为1。手机扫一扫
移动阅读更方便
你可能感兴趣的文章