刷题记录:Codeforces Round #734 (Div. 3)
阅读原文时间:2023年07月09日阅读:1

Codeforces Round #734 (Div. 3)

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差不多):

  • 一个整数或者不上色,或者被涂成一种颜色。
  • 被涂成一种颜色的所有数值,必须两两不相同。
  • 被涂成每一种颜色的数字数量都相等。
  • 这种涂色方法会得到最多的上色数字。

让我们输出上色方案(而不是简单给出涂色数量)。

做法:

  • 在读入整数序列的时候,用三元组(数值大小,位置,颜色)来记录序列信息,颜色都初始化为不上色。
  • 然后按数值大小排序,统计每一个数值有多少个数。
  • 如果某数值个数≥k,则每个颜色分配一个数,剩下不上色;
  • 累加【个数<k的数值】的数量,除k得到【这些零散的数能够把k种颜色全部使用几次】,再乘k就是【零散数值的上色次数】。这一步是为了保证【每一种上色的数量都相等】。
  • 接下来我们对【个数<k的数值】进行上色,每上一次色就--【零散数值的上色次数】。把每一个数分配到目前数量最少的颜色。
  • 最后我们按照位置对序列进行排序,然后输出每个数的颜色。

给我们一堆用abcde组成的词语,选取最大数量的词语来写小说,使得某一字母出现次数>其他4个字母出现次数的和。输出这个最大数量。

(给出的词语可能重复。词语不能重复使用。)

做法:

  • 读入词语,记录该词语的【a数量-bcde数量、b数量-acde数量、…、e数量-abcd数量】这5个值。
  • 接下来,我们希望小说中【a数量>bcde数量】,因此对词语按【a数量-bcde数量】从大到小进行排序,在满足【a数量>bcde数量】的情况下逐个选取,就是贪心法。记录这种选取的数量。
  • 然后,我们希望【b数量-acde数量】,如法炮制。遍历5种情况,对5种情况的答案取max。

给我们n*m(n行m列)的棋盘,保证n*m是偶数。给我们n*m/2个牌,每一个牌都是日字形的,可以横着放可以竖着放。问我们,能不能用这些牌摆满棋盘,使得横着放的牌恰好有k块。如果能的话,输出摆法。

做法:

  • 首先我们希望棋盘的列数是偶数(为了构造方便),如果不是就把棋盘转90°,然后k=n*m/2-k;
  • 接下来,我们像图1这样初始化棋盘。就是说,如果行数是偶数,就像前4行那样铺满棋盘。如果行数是奇数,最后一行像第5行那样横着铺满;最后一行有(列数)/2个横放的牌,这是最少的横放牌数,如果给出的k比这个数目小,输出NO。
  • 看图2——我们可以像图2这样,通过扭转操作增加横放牌的数量。因为每次只能增加2个横放的牌,所以,若【k-最小横放牌数目】不是偶数,也输出NO。
  • 然后,我们从左上开始一行一行遍历,一个单元一个单元地扭转,直到横放牌数符合要求。
  • 编程细节:为了保证输出结果中,牌的字母不相撞,可以像图3这样初始化牌的字母。

给我们一个整数序列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个顶点都是星型结构的。

做法:

  • 我们考虑第r个顶点(最外层循环是从1到n遍历r),以r为树根把树悬挂起来。设与r紧邻的顶点(即第一层顶点)个数为QL,QL也是子树的个数。只有同一层的节点才能互相匹配,得到两两距离相等的星型结构。因此,我们逐层向下考虑,用数组cnt[QL]来记录某一层每个子树的节点个数,计算完这一层后就把cnt更新成下一层的节点个数。
  • 一开始我们把cnt全初始化为1(第一次节点)。这样更新cnt:对每一个子树维护一个set,set里面存放该子树该层的节点。更新的时候,首先声明一个名为temp的新set,然后对set里的每一个节点,遍历它的邻居,如果邻居是“未使用的”,则把它放进temp;遍历完这个节点的邻居后,把这个节点标记为“使用过的”,--对应的cnt。遍历完该子树的set里的所有节点后,清空set,把temp里的节点转移到set里,每转移一个就++cnt。(一开始要把树根r标记为使用。)
  • 对于给定的cnt,求大小为k星型结构个数:使用dp。设dp[i][j]为【只考虑前i个子树时,大小为j星型结构的个数】。状态转移方程是这样的: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。