Educational Codeforces Round 59 题解

发表于 | 分类于 |
字数统计: 2,101 字

这场比赛区分度比较大。E，F，G题均比较难。

A

题目大意：给定一个数字串，求一种方法将该串分割成至少两个非空部分，并且每个部分形成的数从左到右严格递增。如123456，可以分割成3个部分1，23，456。

由于没有更多的限制条件，所以可以直接把这个串分割成两个部分，前一部分只包含第一个数字。这样如果串长大于2就必然可行，否则需要特判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
char s[305];
int main(){
    int q;
    cin >> q;
    while(q--){
        cin >> n;
        scanf("%s", s);
        if(n == 2){
            if(s[1] <= s[0]) printf("NO\n");
            else printf("YES\n2\n%c %c\n", s[0], s[1]);
        }else{
            printf("YES\n2\n%c %s\n", s[0], s + 1);
        }
    }
    return 0;
}

B

题目大意：给定$k, x$，求第$k$个“数字根”为$x$的数。多组询问。

知道了数字根的性质这道题就会做了。答案就是$9(k-1)+x$。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll q, x;
int main(){
    cin >> n;
    while(n--){
        cin >> q >> x;
        cout << (q - 1ll) * 9ll + x << endl;
    }
    return 0;
}

C

题目链接

可以发现我们只要对字符串分段处理即可，即对于每一个连续的相同字母构成的串，只要取其中能获得的分数最大的$k$个字母进行敲击即可。
用排序或者堆都可以，时间复杂度$O(n\log 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
int a[200005];
char s[200005];
ll ans = 0;
int tmp[200005], cnt = 0;
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; ){
        int j = i;
        ll sum = 0;
        while(j <= n && s[i] == s[j])
            sum += 1ll * a[j], j++; 
        if(j - i <= k){
            ans += sum;
        }else{
            for(cnt = 0; cnt + i < j; ++cnt)
                tmp[cnt] = a[i + cnt];
            sort(tmp, tmp + cnt);
            for(int t = 0; t < k; ++t)
                ans += 1ll * tmp[cnt - 1 - t];
        }
        i = j;
    }
    printf("%I64d\n", ans);
    return 0;
}

D

题目大意：找到最大的$x$使得$n\times n$的01矩阵$A$能被压缩成为$\frac{n}{x} \times \frac{n}{x}$矩阵$B$，使得$\forall i \in [1, n], j \in [1, n], A[i][j] = B[\lceil \frac{n}{x} \rceil][\lceil \frac{n}{x} \rceil]$。

大暴力。枚举$n$的约数，从大到小判断即可。所谓判断，即判断每一个$x\times x$的矩阵中的数据是否完全相同。使用二维前缀和辅助判断过程。
注意不要写成二分$x$，因为答案不一定有单调性。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int ds[10005], cnt = 0;
int ma[5205][5205], sum[5205][5205] = {0};
char s[1305];
bool judge(int x){
    for(int i = x; i <= n; i += x)
        for(int j = x; j <= n; j += x){
            int res = sum[i][j] - sum[i - x][j] - sum[i][j - x] + sum[i - x][j - x];
            if(res > 0 && res < x * x) return false;
        }
    return true;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        if(n % i == 0) ds[++cnt] = i;
    for(int i = 1; i <= n; ++i){
        scanf("%s", s + 1);
        int tt = n >> 2;
        for(int j = 1; j <= tt; ++j){
            int re = (isdigit(s[j]) ? s[j] - '0': s[j] - 'A' + 10);
            for(int k = 1, t = 4; k <= 8; k <<= 1, --t)
                if(k & re) ma[i][(j - 1) * 4 + t] = 1;
                else ma[i][(j - 1) * 4 + t] = 0;
        }
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            sum[i][j] = sum[i][j - 1] + ma[i][j];
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            sum[i][j] += sum[i - 1][j];
    int ans = 1;
    for(int i = cnt; i >= 2; --i){
        if(judge(ds[i])){
            ans = ds[i];
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

E

题目大意：给定一个01串，每次可以对一段0或者一段1进行消除，得到的分数和长度有关，消除之后被消除的段的两侧合并。求整个串被全部消除时最大的分数。

这道题的状态设计非常有意思。容易将当前区间的两端位置加入到状态中，但这还不够。
设$f(dig, i, j, k)$为当前区间为$[i, j]$，且区间中消除到有$k$个$dig$时，可以得到的最大分数。显然，答案为$f(0, 1, n, 0)$。这样就能方便的转移了。
当$k\neq 0$时，要考虑从$k-1$转移过来。此时考虑从$[i, j]$中遍历$l$，令$dig=s[l]$，并将从$l$左或者从$l$右开始的一部分作为从$k-1$转移过来的部分，另一部分消去。因为消去的顺序不影响结果，此处将左边一半消去。从而有：

当$k=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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[105] = {0};
char s[105];
int sum[105] = {0};
ll f[2][105][105][105] = {0};
int main(){
    scanf("%d%s", &n, s + 1);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + s[i] - '0';
    memset(f, -1, sizeof(f));
    for(int i = 1; i <= n; ++i){
        if(s[i] == '0'){
            f[0][i][i][1] = 0;
        }else{
            f[1][i][i][1] = 0;
        }
        f[0][i][i][0] = f[1][i][i][0] = a[1];
    }
    for(int i = 1; i <= n; ++i)
        for(int j = i - 1; j >= 0; --j)
            f[0][i][j][0] = f[1][i][j][0] = 0;
            
    for(int i = 1; i < n; ++i){
        for(int j = 1; j + i <= n; ++j){
            int lim = max(i + 1 - (sum[j + i] - sum[j - 1]), sum[j + i] - sum[j - 1]);
            for(int k = 1; k <= lim; ++k){
                for(int l = j; l < j + i; ++l){
                    int sig = s[l] - '0';
                    ll &dp = f[sig][j][j + i][k];
                    if(f[sig][l + 1][j + i][k - 1] >= 0)
                        dp = max(dp, f[0][j][l - 1][0] + f[sig][l + 1][j + i][k - 1]);
                }
            }

            int sig = s[j + i] - '0';
            ll &dp = f[sig][j][j + i][1];
            dp = max(dp, f[0][j][j + i - 1][0]);

            for(int k = 1; k <= lim; ++k){
                if(f[0][j][j + i][k] >= 0)
                    f[0][j][j + i][0] = max(f[0][j][j + i][k] + a[k], f[0][j][j + i][0]);
                if(f[1][j][j + i][k] >= 0)
                    f[0][j][j + i][0] = max(f[1][j][j + i][k] + a[k], f[0][j][j + i][0]);
            }
            f[1][j][j + i][0] = f[0][j][j + i][0];
        }
    }
    printf("%I64d\n", f[0][1][n][0]);
    return 0;
}

事实上，根据上面所述，可以将状态改设为$f(i, j, k)$，压掉$dig$一维，将$dig$锁定为$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
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, a[105] = {0};
char s[105];
int sum[105] = {0};
ll f[105][105][105] = {0};
int main(){
    scanf("%d%s", &n, s + 1);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + s[i] - '0';
    memset(f, -1, sizeof(f));

    for(int i = 1; i <= n; ++i)
        f[i][i][1] = 0, f[i][i][0] = a[1];
    for(int i = 0; i <= n; ++i)
        for(int j = i - 1; j >= 0; --j)
            f[i][j][0] = 0;
    f[n + 1][n][0] = 0;
            
    for(int i = 1; i < n; ++i){
        for(int j = 1; j + i <= n; ++j){
            int lim = max(i + 1 - (sum[j + i] - sum[j - 1]), sum[j + i] - sum[j - 1]);
            for(int k = 1; k <= lim; ++k){
                for(int l = j; l <= j + i; ++l){
                    if(s[j] != s[l]) continue;
                    if(f[j][l - 1][k - 1] >= 0)
                        f[j][j + i][k] = max(f[j][j + i][k], f[j][l - 1][k - 1] + f[l + 1][j + i][0]);
                }
            }
            for(int k = 1; k <= lim; ++k){
                if(f[j][j + i][k] >= 0)
                    f[j][j + i][0] = max(f[j][j + i][0], f[j][j + i][k] + a[k]);
            }
        }
    }
    printf("%I64d\n", f[1][n][0]);
    return 0;
}

F

题目大意：有$n$份贷款，每一份贷款有三个参数$a, b, k$，表示贷款当月可以获得$a$元，之后$k$个月每个月要还$b$元。一个月最多贷一次款，一种款只能贷一次。求某个月可能可以持有的金额的最大值。

建立矩阵，每一列表示一种贷款带来的收益/负债。问题转化为从这$n\times n$矩阵中选出$n$个数，使得每个数所在行列均不相交，并且和最大。
这是一个经典问题，用匈牙利算法可以解决。

1
2