lonlyn's blog
首页
时间轴
标签
分类
友链
关于
avatar
文章
18
标签
25
分类
2
首页
时间轴
标签
分类
友链
关于
目录
  1. 1. 部分题解（ABFGIK）
    1. 1.1. A. Cut The Wire
      1. 1.1.1. 大意
      2. 1.1.2. 解析
      3. 1.1.3. 代码
    2. 1.2. B. Time-division Multiplexing
      1. 1.2.1. 大意
      2. 1.2.2. 解析
      3. 1.2.3. 代码
    3. 1.3. F. Power Sum
      1. 1.3.1. 大意
      2. 1.3.2. 解析
      3. 1.3.3. 提示
      4. 1.3.4. 代码
    4. 1.4. G. Function
      1. 1.4.1. 大意
      2. 1.4.2. 解析
      3. 1.4.3. 代码
    5. 1.5. I. Command Sequence
      1. 1.5.1. 大意
      2. 1.5.2. 解析
      3. 1.5.3. 代码
    6. 1.6. K. Shooting Bricks
      1. 1.6.1. 大意
      2. 1.6.2. 解析
        1. 1.6.2.1. 一种典型的错误做法
        2. 1.6.2.2. 正确思路
      3. 1.6.3. 代码
    7. 1.7. L. Remove
      1. 1.7.1. 大意
      2. 1.7.2. 解析
      3. 1.7.3. 关于单调性的证明
2021 CCPC 网络赛
|从蒟蒻到蒟蒻的修炼
字数总计:3.9k|阅读时长: 17 分钟
|阅读量:|评论数:

部分题解（ABFGIK）

题目链接：2021中国大学生程序设计竞赛（CCPC）- 网络选拔赛

A. Cut The Wire

大意

有无穷多个点编号 $1,2,3,\dots$。对于编号为 $x$ 的点满足：

  • 如果 $x$ 是偶数，则 $x$ 与 $\frac{x}{2}$ 之间有一条边。
  • 如果 $x$ 是奇数，则 $x$ 与 $3x+1$ 之间有一条边。

给定 $n$，求有多少连边 $(a,b)$ 满足 $a\le n$ 且 $b > n$。

解析

对于第一个条件，可以转化为 $\forall x,(x,2x)\in E$，然后直接计数即可。

代码

cpp
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long 
int T;
int n;
ll ans, a, b;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        ans = 0;
        a = n - n / 2;
        b = n - (n - 1) / 3;
        if (b % 2 == 1 && n % 2 == 1) {
            b = (b + 1) / 2;
        } else {
            b = b / 2;
        }
        printf("%lld\n", a + b);
    }
    return 0;
}

B. Time-division Multiplexing

大意

给定 $n$ 个字符串，每个长度不超过 $12$。生成一个无限长的字符串 $t$：初始化每个字符串的字符位置为开始位置，每一轮选取每个字符串对应位置的字符添到 $t$ 的末尾，再将字符串的位置向后挪一个；若已经到最后，则设在开始位置。

一个例子：若有两个字符串 abcd efghi，则生成的字符串是 ae bf cg dh ai be cf dg ... （为了方便查看，每一轮之间加了一个空格表示，但最终字符串是不包含这些空格的）。

求在无限长的字符串 $t$ 中找到包含所有字符串中出现的字符且长度最短的连续子串，求出其长度即可。

解析

虽然是无限长，但 $t$ 本身存在循环节，我们只要在相邻两个循环节中寻找最小值即可。

考虑得到节选 $t$ 的最大长度：不同长度之间取最小公倍数得到轮数 $lcm(1,2,\dots,12)=27720$，每轮生成附加字符串长度 $n$，找两个循环节。

得到节选的字符串后，采用双指针解决问题即可。

代码

cpp
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
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long 
const int maxn = 110;
int T;
int n;
int len[maxn];
char s[maxn][20];
int lcm, cur;
char t[maxn * 27720 * 2];
int vis[30], totchar, curchar;
int l, r;
int ans;
int gcd(int x, int y) {
    return (!y) ? x : gcd(y, x % y);
}
int main() {
    scanf("%d", &T);
    while (T--) {
        memset(vis, 0, sizeof(vis));
        totchar = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%s", s[i]);
            len[i] = strlen(s[i]);
            for (int j = 0; j < len[i]; ++j) {
                if (!vis[s[i][j] - 'a']) {
                    vis[s[i][j] - 'a'] = 1;
                    ++totchar;
                }
            }
        }

        lcm = len[1];
        for (int i = 2; i <= n; ++i) {
            lcm = lcm / gcd(lcm, len[i]) * len[i];
        }
        lcm = lcm * n * 2;

        cur = 0;
        for (int i = 0; cur < lcm; ++i) {
            for (int j = 1; j <= n; ++j) {
                t[cur++] = s[j][i % len[j]];
            }
        }
        t[cur] = '\0';

        ans = lcm;
        memset(vis, 0, sizeof(vis));
        curchar = 0;
        r = 0;
        ++vis[t[r] - 'a']; ++curchar;
        for (l = 0; l < lcm; ++l) {
            while (r < lcm - 1 && curchar < totchar) {
                ++r;
                if (!vis[t[r] - 'a']) ++curchar;
                ++vis[t[r] - 'a'];
            }
            if (curchar == totchar) {
                ans = min(ans, r - l + 1);
            }
            --vis[t[l] - 'a'];
            if (!vis[t[l] - 'a']) --curchar;
        }
        printf("%d\n", ans);
    }
    return 0;
}

F. Power Sum

大意

给定 $n$，构造长度为 $k\le n+2$ 的数组 $a,a_i\in{-1,1}$，满足 $\sum\limits_{i=1}^{k}{a_i\times i^2}=n$。

解析

平方的增长是比较迅猛的，考虑到题目给出的 $k$ 与 $n$ 范围相似，说明我们构造数组的思路也可以往线性增长上靠拢。考虑相邻的两个平方数相减 $(n+1)^2-n^2=2n+1$，如果直接相加，和仍然不是线性增长。可以考虑再次做差：

$$((n+3)^2-(n+2)^2)-((n+1)^2-n^2)=(2(n+1)+1-(2n+1))=4$$

可以发现恰好 $4$ 个数能构成 $+4$，且与位置无关，实现了线性。

之后我们可以将 $n$ 分解为 $n\pmod 4+\lfloor \frac{n}{4}\rfloor \times 4$，即前面处理得到 $1,2,3$，后面直接 $+4$ 循环即可。$1,2,3$ 的构造不再详细说明，可以发现该方法最长的构造长度恰好是 $n+2$。

提示

做题的时候发现，对于后半部分，如果四个四个字符循环输出会跑的非常慢，但如果把答案处理为一个字符串输出则快很多。

代码

cpp
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long 
const int maxn = 1000010;
int T;
int n, res, cur;
char s[maxn];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        res = n % 4; cur = 0;
        if (res == 0) {
            printf("%d\n", n);
        }
        else if (res == 1) {
            printf("%d\n", n);
            s[cur++] = '1';
        }
        else if (res == 2) {
            printf("%d\n", n + 2);
            s[cur++] = '0';
            s[cur++] = '0';
            s[cur++] = '0';
            s[cur++] = '1';
        }
        else {
            printf("%d\n", n - 1);
            s[cur++] = '0';
            s[cur++] = '1';
        }
        n >>= 2;
        for (int i = 1; i <= n; ++i) {
            s[cur++] = '1';
            s[cur++] = '0';
            s[cur++] = '0';
            s[cur++] = '1';
        }
        s[cur] = '\0';
        printf("%s\n", s);
    }
    return 0;
}

G. Function

大意

设 $g(x)$ 代表 $x$ 在十进制下每位数之和。

设 $f(x)=Ax^2g(x)+Bx^2+Cxg^2(x)+Dxg(x)$，给定 $A,B,C,D$ 和 $N\le 10^{6}$，求 $x\in[1,N]$ 情况下 $\min \lbrace{f(x)}\rbrace$。

解析

$g(x)$ 是处理的难点，如果能确定 $g(x)$，问题就转化为二次函数求极值的问题。

可以看出 $g(x)$ 的取值范围非常小（最大 $6\times 9=54$），考虑枚举 $g(x)$，对每个确定的 $g(x)$ 求 $f(x)$ 的极值即可。

该题要注意一下几点：

  • 当 $g(x)$ 确定时，需要保证枚举的 $x$ 满足 $g(x)$ 条件。
  • 确定 $g(x)$ 后，设 $f(x)=ax^2+bx$:
    • $a=0$，此时不是二次函数，取端点极值。注意此处的端点需满足 $g(x)$ 条件。
    • $a<0$，同 $a=0$。
    • $a>0$，取最靠近 $-\frac{b}{2a}$ 的，注意考虑该位置是否在满足 $g(x)$ 条件的 $x$ 范围内。

代码

cpp
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
67
68
69
70
71
72
73
74
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long 
vector<int> num[60];
void init() {
    int res, tot;
    for (int i = 1; i <= 1000000; ++i) {
        res = i; tot = 0;
        while (res) {
            tot += res % 10;
            res /= 10;
        }
        num[tot].push_back(i);
    }
}
int T;
int a, b, c, d, n;
int g;
ll A, B;
ll ans;
ll calc() {
    if (A <= 0) {
        int p = lower_bound(num[g].begin(), num[g].end(), n) - num[g].begin();
        if (p >= num[g].size() || num[g][p] > n) --p;
        return min(A * num[g][0] * num[g][0] + B * num[g][0], 
                   A * num[g][p] * num[g][p] + B * num[g][p]);
    }
    else {
        ll mid = (-B) / (2 * A);
        int p = lower_bound(num[g].begin(), num[g].end(), mid) - num[g].begin();
        ll res = 6e18;
        // mid is in period [1, n]
        if (p-1 >= 0 && p-1 < num[g].size() && num[g][p-1] <= n) {
            res = min(res, A * num[g][p-1] * num[g][p-1] + B * num[g][p-1]);
        }
        if (p >= 0 && p < num[g].size() && num[g][p] <= n) {
            res = min(res, A * num[g][p] * num[g][p] + B * num[g][p]);
        }
        if (p+1 >= 0 && p+1 < num[g].size() && num[g][p+1] <= n) {
            res = min(res, A * num[g][p+1] * num[g][p+1] + B * num[g][p+1]);
        }

        // outside
        p = lower_bound(num[g].begin(), num[g].end(), n) - num[g].begin();
        if (p >= num[g].size() || num[g][p] > n) --p;
        res = min(min(res, A * num[g][0] * num[g][0] + B * num[g][0]), 
                   A * num[g][p] * num[g][p] + B * num[g][p]);
        return res;
    }
}
int main() {
    init();
    scanf("%d", &T);
    while (T--) {
        ans = 6e18;
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &n);
        for (g = 1; g <= 54; ++g) {
            if (num[g][0] > n) continue;
            A = 1ll * a * g + b;
            B = 1ll * c * g * g + d * g;
            ans = min(ans, calc());
        }
        printf("%lld\n", ans);
    }
    return 0;
}

I. Command Sequence

大意

给定一段操作序列，由上、下、左、右组成，执行每个操作会往对应的方向走一步。

求有多少连续子序列，满足按照该子序列执行操作，最终会回到出发点。

解析

每次经过位置打个标记，该位置在前面出现的次数便是走到这一步的贡献。用一个 map 记录即可。

别忘了初始位置。

代码

cpp
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long 
const int maxn = 100010;
int T;
int n;
int sum1, sum2;
char s[maxn];
ll ans = 0;
struct node {
    int x, y;
} cur;
struct cmp {
    bool operator () (const node &a, const node &b) const {
        return (a.x == b.x) ? a.y < b.y : a.x < b.x;
    }
};
map<node, int, cmp> mp;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        scanf("%s", s+1);
        ans = 0;
        sum1 = sum2 = 0;
        mp.clear();
        cur = (node){0, 0};
        mp[cur] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i] == 'U') {
                ++sum1;
            }
            else if (s[i] == 'D') {
                --sum1;
            }
            else if (s[i] == 'L') {
                ++sum2;
            }
            else if (s[i] == 'R') {
                --sum2;
            }
            cur = (node){sum1, sum2};
            if (mp.count(cur)) {
                ans += mp[cur];
                ++mp[cur];
            } else {
                mp[cur] = 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

K. Shooting Bricks

大意

打砖块。

给你 $k$ 个小球，每个小球能打一个方块。给定 $n\times m$ 个方块，每次可以打一列中最靠外的一个。每个方块有一个得分，同时有些方块在被打碎后，可以获得另外一个球，这种方块用 Y 标识，其他的为 N。

求最大化得分。

解析

一种典型的错误做法

设 $v(i,j)$ 代表对于第 $i$ 列，用 $j$ 个球能得到的最大分数。
设 $f(i,j)$ 代表对于前 $i$ 列，用 $j$ 个球能得到的最大分数，那么状态转移方程：
$$f(i,j)=\max\lbrace{f(i-1,j-k)+v(i,k)}\rbrace$$
最终答案即为 $f(n,k)$。

这种做法忽略了一种问题：需要球的个数 $\not=$ 消耗球的个数。
打个比方，某一列的方块情况为 YNY，如果要打完该列所有的方块，消耗球的数量为 1，需要球的数量为 2。因为在打完 N 之后，虽然看上去消耗一个球的同时又得到一个球没有影响，但必须先有球去打破该方块，才能得到分数的同时再得到一个奖励球。

正确思路

有一个很容易想到的贪心：优先打 Y 类型的方块。因为打 Y 类型的相当于不消耗，且只要有球就可以完成；如果先打了 N 类型的方块，则当没球的时候就没法打 Y 类型的方块，而这些方块可以在打 N 类型方块前完成。

由此我们可以得到一个结论：若场上存在 N 类型方块，则最后打的一定是 N 类型的方块。（如过全是 Y 类型的话，直接一个球打完了，不必进行讨论。）

我们假设最后一个打的方块在第 $k$ 列：

  • 对于第 $k$ 列，打完最后一个 N 方块后便没有球了，就算后面有 Y 方块也无法得到分数。此时的计算个数由需要球的个数决定。
  • 对于其他列，假设我们给该列分配了 $a$ 个球。那么在该列打破了 $a$ 个 N 类型方块后，由于至少有一个求留给了第 $k$ 列，我们可以用第 $k$ 列的球把后面的 Y 方块打破。此时的计算个数由消耗求的个数决定。

设 $v_1(i,j)$ 代表第 $i$ 列消耗 $j$ 个球能得到的最大分数，$v_2(i,j)$ 代表第 $i$ 列只有 $j$ 个球时能得到的最大分数。设 $f(i,j,0/1)$ 代表前 $i$ 列中用 $j$ 个球的最大值，$0/1$ 代表是否在前 $i$ 列中存在打的最后一列。

考虑转移，用 $x\gets y$ 表示用 $y$ 去更新 $x$。假设正在考虑第 $i$ 列：

  • 第 $i$ 列是最后被打的方块所在的列：
    • 前 $i-1$ 列中必定没有，且该列至少消耗一个球。$f(i,j,1)\gets f(i-1,j-k,0)+v_2(i,k),k>0$
  • 第 $i$ 列不是最后被打的方块所在的列：
    • 前 $i-1$ 列中有，前面至少消耗一个球。$f(i,j,1)\gets f(i-1,j-k,1)+v_1(i,k),k<j$
    • 前 $i-1$ 列中无。$f(i,j,0)\gets f(i-1,j-k,0)+v_1(i,k)$

代码

cpp
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long 
const int maxn = 210;
int T;
int n, m, K;
int a[maxn][maxn];
char c[maxn][maxn];
int v1[maxn][maxn];
int v2[maxn][maxn];
int f[maxn][maxn][2];
int tot;
int main() {
    scanf("%d", &T);
    while (T--) {
        memset(f, 0, sizeof(f));
        memset(v1, 0, sizeof(v1));
        memset(v2, 0, sizeof(v2));
        scanf("%d%d%d", &n, &m, &K);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                scanf("%d", &a[i][j]);
                c[i][j] = getchar();
                while (c[i][j] != 'Y' && c[i][j] != 'N') c[i][j] = getchar();
            }
        }
        for (int j = 1; j <= m; ++j) {
            tot = 0; 
            for (int i = n; i >= 1; --i) {
                if (c[i][j] == 'N') {
                    ++tot;
                    v1[j][tot] = v1[j][tot-1] + a[i][j];
                    v2[j][tot] = v1[j][tot];
                } else {
                    v1[j][tot] += a[i][j];
                }
            }
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j <= K; ++j) {
                for (int k = 0; k <= min(j, n); ++k) {
                    if (k) f[i][j][1] = max(f[i][j][1], f[i-1][j-k][0] + v2[i][k]);
                    if (k < j) f[i][j][1] = max(f[i][j][1], f[i-1][j-k][1] + v1[i][k]);
                    f[i][j][0] = max(f[i][j][0], f[i-1][j-k][0] + v1[i][k]);
                }
            }
        }
        printf("%d\n", f[m][K][1]);
    }
    return 0;
}

L. Remove

大意

一堆石子有 $n$ 个，给定质数集 $P$。每次操作可以从 $P$ 中选择一个数 $p$ ，从其中去掉 $n\pmod p$ 个石子。给定 $N$，求 $n=1,2,\dots,n$ 时至少多少次能够去掉所有石子。

解析

对于每次执行的操作，可以理解为 $n\to n - n\bmod p$，也可以理解为 $n\to \left\lfloor\frac{n}{p}\right\rfloor\times p$。

先考虑无解情况：最终会进入无论怎么操作，石子的个数不会减少的局面。容易想到 lcm，因为是质数集，也就是所有数的积。对于大于 lcm 的数，也无法通过操作得到小于 lcm 的数。

考虑针对 $n$ 选择合适的 $p$。这里我们可以从直觉上看出，随着 $n$ 增大，需要的步骤是单调不减的。证明详见后面。

有了这个结论，则我们每次选择的数为让 $n \bmod p$ 最大化的 $p$。

每次减法不太好想，我们可以换种思路。对于小于 $p_{max}$ 的数，我们可以直接 $1$ 步得到。对于有解的其他数，我们由小的数去更新大的数。

考虑一个数 $x$ 能推导出的数的范围：

关于单调性的证明

对于 $x$ 个石子，设需要的步数为 $f(x)$。

  • 对于任意 $x$，证明 $f(x)\le f(x+1)$:
    • 我们不妨设 $f(x)>f(x+1)$，即 $x-x\bmod p_1>x+1-(x+1)\bmod p_2$，移项后得到 $(x+1)\bmod p_2 - x\bmod p_1>1$，很明显不存在这种情况，矛盾。原式得证。
  • 由此可以推出 $\forall x<y, f(x)\le f(y)$，单调性得证。
文章作者: lonlyn
文章链接: https://lonlyn.gitee.io/blog/2021/08/30/ccpc2021net/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lonlyn's blog！
比赛总结
评论
繁