Codeforces Round #704 (Div. 2)部分题解（A,B,C,D）_codeforces round737 d

oj: CodeForces

题目顺序为倒叙。

D. Genius’s Gambit

oj: CodeForces

题意

给定 $3$ 个整数 $a,b,k$。

找出满足以下条件的两个二进制数 $x,y$：

1. $x$ 和 $y$ 的二进制形式都是由 $a$ 个 $0$ 和 $b$ 个 $1$ 构成。
2. $x-y$ 的二进制形式中有 $k$ 个 $1$ 。

$x$ 和 $y$ 没有前导 $0$ 。

题解

由于 $x-y$ 没有前导 $0$ 限制，所以我们假设 $x-y$ 是由 $k$ 个连续的 $1$ 构成。我们假设这个值为 $z$ 。

那么问题就转化成如何从 $a+b$ 个二进制位中选出 $b$ 个作为 $1$ ，其他的作为 $0$ 来生成一个二进制数，其值加上 $z$ 之后也是由 $a$ 个 $1$ 和 $b$ 个 $0$ 构成。

例如 $z=111_2,a=3,b=3$，那么考虑到 $x$ 和 $y$ 没有前导 $0$ ，又要维持 $a+b$ 的长度，所以 $x$ 和 $y$ 的第 $1$ 位一定都是 $1$ ，那么 $x$ 和 $y$ 就是这样的形式：1*****。

然后我们在 $y$ 的末尾放一个 $1$ ：100001，来消去 $z$ 中的所有 $1$ ，同时进位，此时求得的 $x$ 为 101000。

然后我们就可以在 $y$ 中 $0$ 对应的且没有被选过的位置中取出 $b-2$ 个作为 $1$ ，这样就能保持 $x$ 和 $y$ 中的 $1$ 的数量始终同步。例如 $x$ 和y可以分别是(111000,110001), (101100,100101), (101010,100011)。

不满足以上推导的没有解。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
using namespace std;
typedef long long LL;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int a, b, k;
string ans, ant;

void init() {
    ans.clear();
    ant.clear();
}

void sol() {
    init();
    if(k == a + b) {
        cout << "No\n";
        return;
    }
    int l = min(a + b - k - 1, k ? b - 1 : b);
    _for(i, l) ans.push_back('1');
    _for(i, a) ans.push_back('0');
    _for(i, b - l) ans.push_back('1');
    _for(i, a + b) ant.push_back('0');
    int f = 0;
    for(int i = ans.size() - 1; i >= 0; --i) {
        int tem = ans[i] - '0' + (ans.size() - i <= k) + f;
        if(tem == 1) ant[i] = '1', f = 0;
        else if(tem == 2) f = 1;
        else if(tem == 3) ant[i] = '1', f = 1;
    }
    if(f || ans[0] == '0' || ant[0] == '0') {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    cout << ant << "\n" << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while(cin>>a>>b>>k) {
        sol();
    }
    return 0;
}
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

C. Maximum width

oj: CodeForces

题意

给定两个字符串 $s$ 和 $t$，存在一个数组 $p$ 使得每一个 $i\in [1,m]$ 都有 $s_{p_i}=t_i$。

求出 $\underset{1\le i<m}{\max }\left(p_{i+1}-p_i\right)$。

题解

对每个 $s[i]$ 求出其对应的最靠左的 $t[j]$ 和最靠右的 $t[k]$，那么答案就至少是 $k-j$。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
typedef long long LL;
const int maxn = 200005;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int n, m;
char s[maxn], t[maxn];
int ml[maxn], mr[maxn];

void sol() {
    scanf("%s%s", s, t);
    int p = 0;
    _for(i, m) {
        while(s[p] != t[i]) ++p;
        ml[i] = p++;
    }
    p = n - 1;
    for(int i = m - 1; i >= 0; --i) {
        while(s[p] != t[i]) --p;
        mr[i] = p--;
    }
    int ans = 0;
    for(int i = 1; i < m; ++i) {
        ans = max(ans, mr[i] - ml[i - 1]);
    }
    printf("%d\n", ans);
}

int main() {
    n = read(), m = read();
    sol();
    return 0;
}
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

B. Card Deck

oj: CodeForces

题意

给定一个长度为 $n$ 的数组 $p$。你可以执行以下操作：取出旧数组的后几位，保持其顺序不变，放到新数组里，直到旧数组为空。

求出新数组中 $\sum _{i=1}^n{n}^{n-i}\cdot p_i$ 的最大值。

题解

让最大的值尽量靠前。

每次找剩余数组中的最大值，然后将最大值及其后面的一段取出放到新数组中。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
#define nl(i, n) (i == n - 1 ? "\n" : " ")
using namespace std;
typedef long long LL;
const int maxn = 100005;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int n, a[maxn];
vector<int> ans;
int num[maxn];

void init() {
    ans.clear();
}

void sol() {
    init();
    _for(i, n) a[i] = read();
    _for(i, n) num[a[i]] = i;
    int p = n - 1;
    for(int i = n; i > 0; --i) {
        for(int j = num[i]; j <= p; ++j) ans.push_back(a[j]);
        p = min(p, num[i] - 1);
    }
    _for(i, ans.size()) printf("%d%s", ans[i], nl(i, ans.size()));
}

int main() {
    int T = read();
    _for(i, T) {
        n = read();
        sol();
    }
    return 0;
}
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

A. Three swimmers

oj: CodeForces

题意

有 $n$ 个游泳选手，他们每人游泳的速度不一样，第 $i$ 个人需要 $a[i]$ 分钟完成一个来回，并且他们在无止境地训练。你在第 $p$ 分钟到达现场，请问你最少需要等待多少分钟才能和其中一位选手见面。

题解

对每个选手求出最短等待时间，然后取最小值。

先求出 $p$ 对 $a[i]$ 上取整的商，就可以很容易求出等待时间了。

代码

#include <bits/stdc++.h>
#define _for(i, a) for (int i = 0, lennn = (a); i < lennn; ++i)
#define _rep(i, a, b) for (int i = (a), lennn = (b); i <= lennn; ++i)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

inline LL read() {
    LL x(0), f(1); char ch(getchar());
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

LL p, a, b, c;

void sol() {
    if(p == 0) {
        printf("0\n");
        return;
    }
    LL ans = INF;
    ULL t = 1;
    ans = min(ans, t * (p + a - 1) / a * a - p);
    ans = min(ans, t * (p + b - 1) / b * b - p);
    ans = min(ans, t * (p + c - 1) / c * c - p);
    long long an = ans;
    printf("%lld\n", an);
}

int main() {
    int T = read();
    _for(i, T) {
        p = read(), a = read(), b = read(), c = read();
        sol();
    }
    return 0;
}
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