Educational Codeforces Round 90 (Rated for Div. 2)

作者: ffacs 分类: Codeforces 发布时间: 2020-07-10 14:25

B

题意

一个长度小于 $100$ 的 $01$ 串。每次可以删除两个 相邻的不同的字符 。不能删除则输。问先手输还是后手输。

题解

只要 $0$ 和 $1$ 都还有就一定能继续删除。所以总共能删 $\min(count(0),count(1))$ 次。

C

题意

给定字符串 $s$ ,求出下面代码运行后 $\text{res}$ 的值

res = 0
for init = 0 to inf
    cur = init
    ok = true
    for i = 1 to |s|
        res = res + 1
        if s[i] == '+'
            cur = cur + 1
        else
            cur = cur - 1
        if cur < 0
            ok = false
            break
    if ok
        break

题解

这段代码求的从 $\text{init}$ 开始,遇到 $-$ 则减一,遇到 $+$ 则加一,若小于 $0$ 则 $\text{break}$ 的各个位置和。我们先求一下如果从 $0$ 开始到这个位置会变成多少。还有前缀的最小值。这样我们就可以知道哪些数字开始是可以到达这个位置的了。

D

题意

一个数组 $n \le 2e5$ ,可以选一个区间进行翻转,要求使得数组偶数位上的和最大。求最大值。

题解

容易发现,如果翻转区间长度是奇数数,那么偶数位上的和是不变的。我们只要考虑长度为偶数的。要求的就是某个偶数长度的区间 奇数位上的和-偶数位上的和的最大值。那么求一下前缀和和前缀最小值即可。要注意奇偶分类。

E

题意

设 $f(x)$ 是十进制数 $x$ 的每一位数字之和。求最小的非负整数使得 $\sum_{x}^{x+k}=n$ 其中,$1\le n\le l50,0 \le k\le 9$。

题解

从 $k$ 进行考虑。因为 $0\le k \le 9$。 如果 $x$ 的最后一位是 $0$ 的话,那么 $x,x+1…x+k$ 除最后一位数字都是一样的,可以贪心算出来。如果最后一位会使得某个数字开始有进位,那么我们再枚举 $x$ 的倒数第二位,如果倒数第二位不是 $9$ 的话在这一位就都不会进位,否则再枚举倒数第三位。这样 $dfs$ 的复杂度是多项式的。

F

题意

一个环,环上 $n\le 1e6$ 个点,$n$ 后面是 $1$ 。有 $n$ 个供电站, 第 $i$ 个给 $i$ 和 $i$ 后面的点提供电。第 $i$ 个点需要 $a_i$ 的电,第 $i$ 个供电站能提供最多 $b_i$ 的电。问能否满足每个点的需求。

题解

一开始一眼看成网络流,但网络流复杂度太大,因为它能给出的信息会更多(每个点的分配情况)。我们发现确定完一个供电站的一段,后面的供电情况就可以贪心求出。那么我们假设第 $1$ 个供电站给第 $1$ 个点提供 $x$ 。如果 $x$ 太大的话就不一定能保证后面点的需求,如果 $x$ 太小的话又不能满足 $1$ 的需求。我们设第 $n$ 个供电站给 $1$ 的电是 $y$ 。那么在可行的情况下,$x$ 减少 $1$ ,$y$ 最多减少 $1$ 。所以就求可行的情况下 $x$ 的最小值即可。对 $x$ 进行二分。如果中间某个地方需求不足则要增大 $x$。最后求一下在给 $x$ 的情况下能否全部满足即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注