Educational Codeforces Round 93

十一月 02, 2020 8569

做题情况

都是 Practice。A 和 B 上来就秒了，C 有思路但是想错了一个统计答案的细节，D 之前听过 wyh 讲因此也秒了，E 只有初步思路

A. Bad Triangle

解题思路

只要三条边 a, b, c 满足 a + b \leq c ，那么这三条边就无法组成三角形。

所以一个很显然的想法就是，最大化 c 同时最小化 a + b 。发现 c 可以直接取最大值， a, b 可以取两个最小值，这样可以最大化 c - (a + b) 。如果这还没有解那就真没解了，输出 -1 即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 5e4 + 10;

int n, aa[MAXN];

bool check(int a, int b, int c) {
    return (1ll * aa[a] + 1ll * aa[b]) > (1ll * aa[c]);
}

int main() {
    int T = read();
    while (T --> 0) {
        n = read();
        for (int i = 1; i <= n; ++i) aa[i] = read();
        if (aa[n] >= aa[1] + aa[2]) 
            printf("%d %d %d\n", 1, 2, n);
        else puts("-1");
    }
    return 0;
}

B. Substring Removal Game

解题思路

注意到如果 Alice 移除了一个 0 或者好几个 0 把两段 1 连了起来，那么 Bob 就可以直接获得这两段 1，这相当于给对手送分啊！

所以最优策略显然就是把当前最长的一段 1 拿走。

这也就是为什么不给样例解释，解释了就都会了，那还解释个🔨。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
std::priority_queue<int> q;

int main() {
    std::ios::sync_with_stdio(false);
    int T; cin >> T;
    while (T --> 0) {
        std::string s; cin >> s;
        int ones = 0;
        for (int i = 0, siz = (int) s.size(); i < siz; ++i) {
            if (s[i] == '1') ++ones;
            else if (ones) { q.push(ones); ones = 0; }
        } if (ones) q.push(ones);
        int ans = 0;
        while (!q.empty()) {
            ans += q.top(); q.pop();
            if (!q.empty()) q.pop();
        } printf("%d\n", ans);
    }
    return 0;
}

C. Good Subarrays

解题思路

对着柿子一顿瞎推，可以搞出这个玩意儿：

首先定义前缀和数组

p_i = \sum_{j = 1}^{i}a_i

然后有

\begin{aligned} &\sum\limits_{i=l}^{r} a_i = r - l + 1 \\\Rightarrow &p_r - p_{l - 1} = r - (l - 1) \\\Rightarrow &p_r - r = p_{l - 1} - (l - 1) \end{aligned}

接下来定义

q_i = p_i - i

所以上面的柿子可以变成

\Rightarrow q_r = q_{l - 1}

统计一下这样的数对 (l - 1, r) 的数量即可。

用一个桶就可以实现了。

另外要注意一个小点，初始化的时候 q_0 = 1 ，因为 q_0 的意义是存在 k\ \mathrm{s.t.} \sum_{i = 1}^{k}a_i = k ，也是符合题目条件的。

代码实现

注意负下标问题。建议使用 std::map 或者坐标平移一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int MAXN = 1e5 + 10;

int n, aa[MAXN];
std::map<int, int> bwl;
char input[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T --> 0) {
        scanf("%d", &n); scanf("%s", input + 1);
        long long int ans = 0; bwl.clear(); bwl[0] = 1;
        for (int i = 1; i <= n; ++i) {
            ans += bwl[aa[i] = (input[i] - '0') + aa[i - 1] - 1];
            ++bwl[aa[i]];
        } printf("%lld\n", ans); bwl.clear();
    }
    return 0;
}

D. Colored Rectangles

解题思路

dp。

设 f[i][j][k] 表示红色用了 i 对，绿色用了 j 对，蓝色用了 k 对的最大面积。

初始值就对 f[1][1][0], f[1][0][1], f[0][1][1] 单独算一下。

转移方程：

f[i][j] = \min \left\{ \begin{array}{l} f[i - 1][j - 1][k] + r_i \times g_j \\ f[i - 1][j][k - 1] + r_i \times b_k \\ f[i][j - 1][k - 1] + g_j \times b_k \end{array} \right.

也就是枚举一下当前要选哪两种颜色，然后转移。

需要注意一个问题，就是答案不一定是 f[R][G][B] ，因为木棍可能用不完。

答案应该为 \max_{i, j, k} f[i][j][k] ，在转移的时候顺便更新一下即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 200 + 10;

int rs, gs, bs;
long long int rr[MAXN], gg[MAXN], bb[MAXN];
long long int dp[MAXN][MAXN][MAXN];

int main() {
    rs = read(); gs = read(); bs = read();
    for (int i = 1; i <= rs; ++i) rr[i] = read();
    for (int i = 1; i <= gs; ++i) gg[i] = read();
    for (int i = 1; i <= bs; ++i) bb[i] = read();
    std::sort(rr + 1, rr + 1 + rs, std::greater<long long int>());
    std::sort(gg + 1, gg + 1 + gs, std::greater<long long int>());
    std::sort(bb + 1, bb + 1 + bs, std::greater<long long int>());
    long long int ans = 0;
    dp[1][1][0] = rr[1] * gg[1];
    dp[1][0][1] = rr[1] * bb[1];
    dp[0][1][1] = gg[1] * bb[1];
    for (int i = 0; i <= rs; ++i) {
        for (int j = 0; j <= gs; ++j) {
            for (int k = 0; k <= bs; ++k) {
                dp[i][j][k] = std::max(
                    std::max(
                        (i && j ? dp[i - 1][j - 1][k] : 0) + rr[i] * gg[j],
                        (i && k ? dp[i - 1][j][k - 1] : 0) + rr[i] * bb[k]
                    ),
                    std::max(
                        (j && k ? dp[i][j - 1][k - 1] : 0) + gg[j] * bb[k],
                        dp[i][j][k]
                    )
                ); ans = std::max(ans, dp[i][j][k]);
            }
        }
    } printf("%lld\n", ans);
    return 0;
}

E. Two Types of Spells

解题思路

先来看看如果不带修咋办。

通过一阵艰难的手玩，可以发现，最优情况一定是用所有雷电法术把前面最大的都翻倍掉，假定有 k 个雷电法术，那么答案就是所有法术能量值之和加上前 k 大的法术能量值之和。

但是有一个例外：如果排前面的法术全是雷电法术的话，那么肯定有一个雷电法术无法被翻倍，有一个火球法术要被翻倍。最优的情况显然是不翻倍最小的雷电法术，翻倍最大的火球法术。所以这时候，答案应该减去最小的雷电法术值，加上最大的火球法术值。

然后试试上修改。发现要求答案涉及所有法术值总和，前 k 大法术值总和，还要动态调整确定最大的火球法术值、最小的雷电法术值。

此时就可以请出万能的 std::set 了！

代码细节

维护四个 set：分别存所有的火球法术值、雷电法术值、前 k 大（可以翻倍）的法术值、不在前 k 大里面（无法翻倍）的法术值；两个值：总法术值、可翻倍的法术值

对于一个加入的法术，先往对应的分类 set 里（火球 or 雷电）塞一个，然后判断一下这条法术有没有可能成为被翻倍的法术，有就直接往可以翻倍的 set 里面塞。

对于一个删除的法术，只需要在这几个 set 里面找一找删掉就行。

然后对可翻倍的 set 大小进行维护：如果大于 k 了就把最小的元素踢掉，如果小于 k 了就加进来不可翻倍 set 里最大的。

然后按照上面讲的东西求答案就行了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int FIR = 0;
const int LIG = 1;

int n;
long long int sum, dbd; // sum 为伤害总和，dbd 为翻倍来的额外伤害
std::set<long long int> fire, light;
std::set<long long int> doubled, nondbd;

void insert(int typ, long long int pwr) {
    sum += pwr;
    if (typ == FIR) fire.insert(pwr);
    else light.insert(pwr);
    // 满足条件就往翻倍里面塞，大不了一会维护的时候再清出来
    if (nondbd.empty() || (pwr > *nondbd.rbegin()))
        doubled.insert(pwr), dbd += pwr;
    else nondbd.insert(pwr);
}

void erase(int typ, long long int pwr) {
    sum -= pwr;
    if (typ == FIR) fire.erase(pwr);
    else light.erase(pwr);
    if (doubled.count(pwr)) doubled.erase(pwr), dbd -= pwr;
    else nondbd.erase(pwr);
}

void maintain() {
    if (doubled.size() > light.size()) {
        int exa = *doubled.begin();
        doubled.erase(exa); dbd -= exa;
        nondbd.insert(exa);
    } else if (doubled.size() < light.size()) {
        int exa = *nondbd.rbegin();
        nondbd.erase(exa);
        doubled.insert(exa); dbd += exa;
    }
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int typ = read(); long long int pwr = read();
        if (pwr > 0) insert(typ, pwr);
        else erase(typ, -pwr);
        maintain();
        if (!doubled.size() && !nondbd.size()) puts("0");
        else {
            // 如果前面能翻倍的全是雷电法术就换掉一个
            if (fire.empty() || *light.begin() > *fire.rbegin()) {
                printf("%lld\n", sum + dbd - *light.begin() + (fire.empty() ? 0 : *fire.rbegin()));
            } else printf("%lld\n", sum + dbd);
        }
    }
    return 0;
}