Codeforces Round #508 (Div. 2) 解题报告

比赛链接:codeforces round #508 (Div.2)

A – Equality

统计前k个字母中出现的最少的字母的个数,再乘以k。

B – Non-Coprime Partition

假设$gcd(\sum_{i=1}^{n} S_1,\sum_{i=1}^{n} S_2) = g, \sum_{i=1}^{n} S_1 = T_1=gp_1, \sum_{i=1}^{n} S_2 = T_2=gp_2$,则$\sum_{i=1}^{n} i=T_1+T_2 = \frac{n(n+1)}{2}=g(p_1+p_2)$,所以$g|\frac{n(n+1)}{2}$,所以我们只需要找出一个大于一的$k$,满足$k|\frac{n(n+1)}{2}$,就一定满足$g|\frac{n(n+1)}{2}$。然后我们只需要把$k$作为第一个序列,其余的数放入第二个序列即可。

C – Gambling

一个人可以做两个操作:加上自己的一个并移除或者移除对方的一个。假如我们做第一个操作,那么我们一定会选自己的最大的,假如执行后者,我们也会删除对方的最大的以满足让对方的体验尽可能差。所以如果我当前的最大的大于对方的最大的,我一定会删除对方的(设想如果我加上我的,他一定会加上他的最大的,但是我删除对方的,对方也会删除我的,这样我损失比他小),否则加上自己最大的。

D – Slime

考虑对于每一个$a_i$对答案的贡献要么是$+a_i$,要么是$-a_i$(0可以看作是+0或者-0)。我们不妨手写几个例子:

  • $[3,-1,-5,0] \xrightarrow[]{[+,-,+,+]} [4,-5,0] \xrightarrow[]{[+,-,+,+]} [4,-5] \xrightarrow[]{[+,-,-,-]} [9]$
  • $[2,1,2,1] \xrightarrow[]{[-,+,+,+]} [-1,2,1] \xrightarrow[]{[-,+,-,+]} [-3,1] \xrightarrow[]{[+,-,+,+]} [4]$
  • $[0,-1,-1,-1,-1] \xrightarrow[]{[0,-,+,+,+]} [1,-1,-1,-1]\xrightarrow[]{[0,-,-,+,+]} [2,-1,-1] \\ \xrightarrow[]{[0,-,-,-,+]} [3,-1]\xrightarrow[]{[0,-,-,-,-]} [4] ([0,-,-,-,-] \Leftrightarrow [+,-,-,-,-])$

我们发现最终一定是一个+或者一个-,其他都是一样的。当序列既有正也有负的时候,最后的值就是所有数字的绝对和相加(这个值是可以通过加法和减法得到的),如果全正或者全负,我们会发现最终符号不一样的是那个最小值。注意判断$n=1$的特殊情况。

E,F

待填坑

说点什么

avatar
50
  Subscribe  
提醒