Educational Codeforces Round 97

十月 31, 2020 6912

做题情况

A 和 B 压根不会，C 有了 dp 状态但是没写出来式子，D 秒了，E 有了思路但是不会写

A. Marketing Scheme

解题思路

考虑极限情况，也就是 l \bmod a = \frac{a}{2} 时，一种情况是 a = 2l 。

要保证 r \bmod a \geq \frac{a}{2} ，就要保证 \forall x \in [l, r], x \bmod 2l \geq l ，而当 x = 2l 时上式为 0，所以 x 一定取不到 2l ，也即合法的 x 取值区间为 [l, 2l) 。

故只需判断 r 和 2l 的大小关系即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

int l, r;

int main() {
    int T = read();
    while (T --> 0) {
        l = read(); r = read();
        puts(l * 2 <= r ? "NO" : "YES");
    }
    return 0;
}

B. Reverse Binary Strings

解题思路

题目让我们解决掉所有相同字符子串，那么答案可能就会和这玩意有关。

观察可以看出，所有的全 0 串与所有的全 1 串其实存在一种对应关系：

1
2
3
4
5
6
7
8
9
比如说 1100100110 这个字符串
可以划分成 [11][00]1(00)(11)0
中括号的两个子串是对应的，小括号的两个子串是对应的
可以通过分别一次旋转来破坏掉两个子串；

比如说 00110110 这个字符串
可以划分成 (00)(11)[00][11]0{11}0
小括号、中括号分别对应，大括号的一个子串没有对应
可以通过一次旋转破坏掉有对应的子串，另一次旋转单独破坏没有对应的子串

所以如果存在 2t 个相同字符子串，就需要 t 次操作来解决所有连续字符串；如果存在 2t + 1 个相同字符子串，就需要 \left\lfloor\frac{2t + 1}{2}\right\rfloor + 1=t + 1 次操作。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int MAXN = 100000 + 10;

/**
 * 
 * 考虑连续串的对应关系
 * 
 */

int n;
char ss[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T --> 0) {
        scanf("%d", &n);
        scanf("%s", ss + 1);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            cnt += (ss[i] == ss[i - 1]);
        } printf("%d\n", (cnt + 1) >> 1);
    }
    return 0;
}

C. Chef Monocarp

解题思路

很显然先排个序肯定不会差。

然后考虑 dp。设 f[i][j] 表示第 i 道菜在 j 时刻被取出来的最小 Unpleasant 值。

转移方程？

枚举上一道菜啥时候取出来的。

f[i][j] = \min_{1\leq k < j}\{f[i - 1][k]\} + |t_i - j|

边界？

不合法的值肯定是正无穷，先 memset 一下。
然后可以证明总时间一定不会超过 2n （其实可以更精确，但是这个复杂度能过了），因为最差情况下就拖到第 n+1\sim 2n 秒把 n 道菜全取出来，再往后都是浪费时间，所以时间的上限就是 2n 。

然后预处理 \forall 1\leq i \leq 2n, f[1][i] = |t_1 - i| ，接着从 2 开始 dp 就完事了。

代码实现

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
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 n;
int opm[MAXN], dp[MAXN][MAXN << 1];

int main() {
    int T = read();
    while (T --> 0) {
        n = read();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= (n << 1); ++j) {
                dp[i][j] = 0x7f7f7f7f;
            }
            opm[i] = read();
        } std::sort(opm + 1, opm + 1 + n);
        for (int j = 1; j <= (n << 1); ++j) {
            dp[1][j] = std::abs(opm[1] - j);
        }
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= (n << 1); ++j) {
                for (int k = 1; k < j; ++k) {
                    // 垃圾 vscode 这里把 std::abs 返回值报成 <error-type>
                    // 于是就只能分开写
                    int newt = (int) (dp[i - 1][k] + int(std::abs(opm[i] - j)));
                    dp[i][j] = std::min(dp[i][j], newt);
                }
            }
        }
        printf("%d\n", *std::min_element(dp[n] + 1, dp[n] + 1 + (n << 1)));
    }
    return 0;
}

D. Minimal Height Tree

解题思路

题目里的一个重要信息：

g[k] is the list of all children of vertex k, sorted in ascending order

有了这个信息，就可以确定一个性质：

某个节点的所有儿子的编号在 BFS 序中一定连续且单调上升。

所以就可以直接贪心，每次选一串单调上升的连续子序列作为某一个节点的所有儿子。如果当前深度还有节点没有儿子就放上去，否则就转移到下一个深度上放。

代码实现

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
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 = 2e5 + 10;

int n, aa[MAXN];
std::vector<int> fa[MAXN]; // fa[i] 表示深度为 i 的（可用的）所有点
int dep;

void solve() {
    int p = 2, fap = 0;
    while (p <= n) {
        fa[dep + 1].push_back(p); ++p;
        while (p <= n && aa[p - 1] < aa[p]) {
            fa[dep + 1].push_back(p);
            ++p;
        }
        if (fap < (int) fa[dep].size() - 1) ++fap;
        else { ++dep; fap = 0; }
    }
    if (fap) ++dep;
}

int main() {
    int T = read();
    while (T --> 0) {
        n = read(); dep = 0;
        for (int i = 1; i <= n; ++i) aa[i] = read();
        fa[0].push_back(1);
        solve();
        printf("%d\n", dep);
        for (int i = 0; i <= dep + 1; ++i) fa[i].clear();
    }
    return 0;
}

E. Make It Increasing

解题思路

（算是）一个经典结论：

如果 a_i 单调上升，那么 a_i - i 单调不降，反之亦然。

整数区间的单调上升限制比较多，首先转成单调不降。

先来考虑一下没有锁定的该怎么做。
很显然，我们要把一段序列搞成单调不降的，最优的方法就是修改最长不降子序列以外的东西，所以答案就是序列长度 - 最长不降子序列长度。

如果有锁定的该怎么办？

凉拌。根本不需要处理。
因为锁定的相当于一个分界线，前后两块是独立的，分别做最长不降子序列计算答案即可。

代码实现

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
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 = 500000 + 10;

int n, k, aa[MAXN], ban[MAXN];

int main() {
    n = read(); k = read();
    for (int i = 1; i <= n; ++i) aa[i] = read() - i;
    for (int i = 1; i <= k; ++i) ban[i] = read();
    ban[0] = 0, ban[k + 1] = n + 1;
    aa[0] = -2147482333, aa[n + 1] = 2147482333;
    int ans = 0;
    for (int i = 0; i <= k; ++i) {
        int l = ban[i], r = ban[i + 1];
        if (aa[l] > aa[r]) return (puts("-1") & 0);
        std::vector<int> lis;
        for (int j = l + 1; j <= r - 1; ++j)
            if (aa[l] <= aa[j] && aa[j] <= aa[r]) {
                auto pos = std::upper_bound(lis.begin(), lis.end(), aa[j]);
                if (pos == lis.end()) lis.push_back(aa[j]);
                else *pos = aa[j];
            }
        ans += r - l - 1 - lis.size();
    } printf("%d\n", ans);
    return 0;
}