Codeforces Round #643 (Div. 2)题解

Tutorial:Codeforces Round #643 (Div. 2) Editorial - Codeforces

A
问题:已知操作:a_n+1=a_n+minD(a_n)*maxD(a_n),其中的两个函数分别代表求该数中各个位数中的最小数和最大数,如2376523中两个函数的值是2和7。
对一个数进行k次操作,k非常非常大,求k次操作后的值。

可以发现这个加法操作加的数一定小于100,所以加到下一个1000时一定会出现x0xx的情况,由于有0所以之后都是加0,所以可以直接模拟,有0时跳出。

B
问题:给一个数组,你可以从数组中拿数出来组成1组,数的值代表这个数所在的组最少要有多少个数。求最多能组成多少组?

用贪心思想,升序排序后,能组一组的数组一组,最后的组数就是答案。

C
问题:计算符合条件的三角形

直接用公式计数,题解中还有用前缀和的,不过根据题意是加了两次前缀,很有意思,有兴趣可以看下代码。

D
问题:现在有n和s,代表一个长度为n的数组,数组中的元素之和为s。要求构建一个数组和一个数k,使得数组中的任意非空子集的元素之和不能是k或s-k。

可以构造一个数组,前面的元素全为1,最后一个元素为s-前面元素的和,k取n,能够满足题目要求。(题解的构造方法是前面的元素全为2,k取1)

E
问题:现在有n个数,可以进行如下操作:
将1个数+1,花费a
将1个非0数-1,花费r
将1个数+1,将1个非0数-1,花费m
要所有数相等,求最小花费。

首先易知m=min(m,a+r)。
然后假设h是固定的,设p为各个数小于h的部分的和,q为大于的部分的和。若p>q,则花费c=a(p-q)+mq,反之同理。
然后假设h+1,代入上述公式,发现花费增加了an-m(n-x),x为大小不大于h的数的个数。x仅在h等于某个初始数的值时发生变化。
所以当h变化时,对应的花费c是个线性分段函数,变化点为h等于某个初始数的值时。
还要注意,当h=(sum(hi)/n)(这里设数组中的数的和为sum(hi))时,也要当做变化点考虑进去。(由于这里的h可能不是整数,所以还要考虑加上两个点)原因可能是因为此时p==q,要考虑两个公式代哪个进去。
于是乎最后只需要对每个变化点求对应的花费然后取最小值就是答案。(还有一个题解用了玄学三分,跳出三分的条件是右边界-左边界小于1e6,然后对范围内的每个值都当成h来求最小值)
对于固定的h如何快速求p、q呢?可以用前缀和处理排序后的hi得到对应的数的总和,存在pre中,然后pos*h-pre_pos得到p,q也可以用类似的方法求出。(pos可以用lower_bound快速求出)

啊对了还没有公式支持,我抽空折腾一下:joy:

粤 ICP 备 2020080455 号