Educational Codeforces Round 92

十一月 12, 2020 7901

做题情况

CSP 后复键。做得并不好，A 没想出来，B, C 和 D 都有完整思路但一些细节不会写。

A. LCM Problem

解题思路

放在 A 上的数学题，那肯定是考虑特殊情况。

注意到 l \leq x \leq \mathrm{lcm}(x, y) ，那么为了让 y 尽量小从而满足 < r 的限制，我们可以考虑最小化 x ，也就是让 x = l 。从而， \mathrm{lcm}(x, y) 可以小到 l ，只要 y 是 x 的倍数即可：所以最小的一组解就是 x = l, y = 2l ，如果 r < 2l 就一定无解。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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();
        if (l * 2 > r) puts("-1 -1");
        else printf("%d %d\n", l, l * 2);
    }
    return 0;
}

B. Array Walk

解题思路

考虑 dp。

设 f[i][j] 表示当前在位置 i ，往左走了 j 次的最大收益。

转移：

f[i][j] = \max(f[i - 1][j], f[i + 1][j - 1]) + a[i]

显然 i - 1 + 2j 为当前走的步数，那么当 i - 1 + 2j = 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
44
45
46
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;
}
 
/**
 * 
 * 一个小 dp
 * 设 f[i][j] 表示当前在位置 i，往左走了 j 次的最大值
 * 转移方程：
 * f[i][j] = max(f[i + 1][j - 1], f[i - 1][j]) + a[i]
 * 
 */
 
const int MAXN = 1e5 + 10;
const int MAXZ = 5 + 2;
 
int n, k, z;
int aa[MAXN];
int dp[MAXN][MAXZ];
int ans;
 
void cleanup() {
    memset(dp, 0, sizeof dp); ans = 0;
}
 
int main() {
    int T = read();
    while (T --> 0) {
        n = read(); k = read(); z = read();
        for (int i = 1; i <= n; ++i) aa[i] = read();
        for (int j = 0; j <= z; ++j) {
            for (int i = 1; i <= n; ++i) {
                dp[i][j] = dp[i - 1][j];
                if (i != n && j) dp[i][j] = std::max(dp[i][j], dp[i + 1][j - 1]);
                dp[i][j] += aa[i];
                if (i - 1 + j * 2 == k) ans = std::max(ans, dp[i][j]);
            }
        }
        printf("%d\n", ans);
        cleanup();
    }
    return 0;
}

C. Good String

解题思路

显然 Good String 只会长这样：ababababababab 或者 aaaaaaaaaa

那么我们只需要枚举当前要保留哪两个数字，然后大力贪心即可。

代码实现

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 x; scanf("%d", &x); return x;
}
 
const int MAXN = 2e5 + 10;
 
int n;
char ss[MAXN];
 
int main() {
    int T = read();
    while (T --> 0) {
        scanf("%s", ss + 1);
        n = (int) strlen(ss + 1);
        int mx = 0;
        for (int a = 0; a <= 9; ++a) {
            for (int b = 0; b <= 9; ++b) {
                int len = 0;
                for (int i = 1; i <= n; ++i) {
                    if (len % 2 == 0) {
                        len += (ss[i] - '0' == a);
                    } else {
                        len += (ss[i] - '0' == b);
                    }
                }
                if (len % 2 == 1 && a != b) --len;
                mx = std::max(mx, len);
            }
        } printf("%d\n", n - mx);
    }
    return 0;
}

D. Segment Intersections

解题思路

每一对线段最开始都是相同的，那么我们只需要考虑一对线段，然后把它乘个 n 即可。

为了方便，首先先求出初始情况下线段交的长度，把它乘 n 然后用它把 k 减掉。

我们令两条线段为 [l_1, r_1],[l_2, r_2](l_1 < l_2) ，那么有三种情况：

线段有交

l_1 \leq l_2 \leq r_1 \leq r2 

1
2
==[======]===
======[===]==

显然，应该先将两条线段扩展到一样，这样每一次扩展都会用 1 的花费让答案增加 1。假设一共需要扩展 t 次，那么所有线段一共可以扩展 tn 次，答案可以增加 tn 。

如果这个 tn \geq k ，就说明能用不超过 tn 次操作来让答案超过 k 。直接输出 k 即可。

否则，我们就需要扩展两次来让长度增加 1：

1
2
3
==[===]== 向右扩展一次 -> ==[====]=
==[===]== 向右扩展一次 -> ==[====]=
一共是两次，答案才能增加 1

那么，对于剩下的 k - tn ，我们需要花费 2(k - tn) 才能得到答案。所以这种情况下，最终答案就是 2(k - tn) + tn = 2k - tn 。输出这个即可。

线段包含

l_1 \leq l_2 \leq r_2 \leq r_1 

1
2
==[=====]==
===[==]====

和上面差不多，先把第二条线段扩展到第一条线段，然后再用两次操作使答案加一。其实并不需要单独讨论。

线段不交

l_1 \leq r_1 \leq l_2 \leq r_2 

1
2
==[===]=====
=======[==]=

一个显然的想法，类似地，先把两条线段扩展到一样长再处理。
但是考虑这样一种情况：当两条线段之间的距离足够大时，把所有线段扩展成一样长并不比选定一个然后使劲扩展更优。

1
2
==[=]=========
==========[=]=

这种情况下其实就可以暴力处理了：枚举要扩展多少条线段，计算扩展这些线段的花费取最小值即可。

时间复杂度： O(n)

代码实现

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
64
65
66
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;
}
 
struct Interval {
    int l, r;
    Interval(int l = 0, int r = 0) : l(l), r(r) {}
    int length() { return r - l; }
    friend int operator & (const Interval &a, const Interval &b) {
        return std::max(0, std::min(a.r, b.r) - std::max(a.l, b.l));
    }
    friend bool operator < (const Interval &a, const Interval &b) {
        return a.l == b.l ? a.r < b.r : a.l < b.l;
    }
    friend bool operator == (const Interval &a, const Interval &b) {
        return a.l == b.l && a.r == b.r;
    }
} aa, bb;
 
long long int n, k;
 
void read(int arg) {
    arg = 0;
    n = read(); k = read();
    int l = read(); int r = read();
    aa = Interval(l, r);
    l = read(); r = read();
    bb = Interval(l,r);
    if (bb < aa) std::swap(bb, aa);
    k -= (aa & bb) * n;
}
 
int main() {
    int T = read();
    while (T --> 0) {
        read(0);
        if (k <= 0) { puts("0"); continue; }
        // aa.l <= bb.l
        if (aa.r <= bb.l) {
            // 最麻烦的，两个区间不交
            long long int ans = 0x7f7f7f7f7f7f7f7f;
            int ptr = 1;
            int full = bb.r - aa.l, expand = bb.l - aa.r;
            if (1ll * n * full <= k) {
                printf("%lld\n", 1ll * n * (full + expand) + (k - 1ll * n * full) * 2);
            } else {
                while (ptr <= n) {
                    if (ptr * full <= k) ans = std::min(ans, ptr * (expand + full) + (k - 1ll * ptr * full) * 2);
                    else break;
                    ++ptr;
                } ans = std::min(ans, 1ll * k + 1ll * ((k - 1) / full + 1) * expand);
                printf("%lld\n", ans);
            }
        } else { // aa.l <= bb.l <= bb.r
            int exl = std::abs(bb.l - aa.l);
            int exr = std::abs(aa.r - bb.r);
            if (1ll * (exl + exr) * n >= k) {
                printf("%d\n", k);
            } else printf("%lld\n", 2ll * k - 1ll * (exl + exr) * n);
        }
    }
    return 0;
}