2022ccpc

A. Mocha 上小学啦

题意：

一个数由互不相同的 $n$ 位数字组成。
- 输出 $$n$$ 位的满足上述条件的最小整数（不含前导零）。
- 不存在则输出 $$-1$$ 。

思路：

签到题。
- 当 n <= 10 时，最小的 $$n$$ 位数的序列为 [1, 0, 2, 3, 4, 5, 6, 7, 8, 9]。
- 当 n > 10 时不存在可以满足条件的数。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int a[] = {1, 0, 2, 3, 4, 5, 6, 7, 8, 9};

void solve() {
    int n; cin >> n;
    if (n > 10) cout << -1 << endl; // 大于10不存在满足条件的数
    else {
        for (int i = 0; i < n; i++) cout << a[i]; // 注意交换1和0的顺序
    }
    return;
}

int main() {
    IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

E. Serval 的俳句

原题链接

题意：

给定一个长度为 $$n$$ 的字符串 $$S$$ 。求是否存在长度为 $$17$$ 的子序列满足：

$$S'_1, S'_2, S'_3, S'_4, S'_5$$ 为同一个字符；
$S'_6, S'_7, \dots, S'_{11}, S'_{12}$ 为同一个字符；
$S'_{13}, S'_{14}, S'_{15}, S'_{16}, S'_{17}$ 为同一个字符。

存在输出该子序列，不存在则输出 none。

思路：

签到题。

暴力枚举 $$S_i$$ ，统计满足的 $$S'_1 - S'_5$$ ，若可以找到满足的子序列，标记该字符后进入下一层循环；
暴力枚举 $$S_j$$ ，统计满足的 $S'_6 - S'_{12}$ ，若可以找到满足的子序列，标记该字符后进入下一层循环；
暴力枚举 $$S_k$$ ，统计满足的 $S'_{13} - S'_{17}$ ，若可以找到满足的子序列，则将上面标记的直接输出即可。
当 n < 17 时或者没有找到满足条件的子序列，则输出 none。
由于每一段的子序列很短，最坏的情况是 $26^3 \times 5^2 \times 7 = 3075800$ ，实际上的情况会远小于该时间复杂度，所以完全 OK。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 200;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve() {
    int n; cin >> n;
    if (n < 17) { // 长度不够，不可能找到
        cout << "none" << endl;
        return;
    }
    string s; cin >> s;
    int vis1[N] = {0}; // 统计相同的前5个字符
    for (int i = 0; i < s.size(); i++) {
        vis1[s[i]]++;
        if (vis1[s[i]] == 5) {
            char op1 = s[i]; // 标记前5个字符
            int vis2[N] = {0}; // 统计相同的中间7个字符
            for (int j = i + 1; j < s.size(); j++) {
                vis2[s[j]]++;
                if (vis2[s[j]] == 7) {
                    char op2 = s[j]; // 标记中间7个字符
                    int vis3[N] = {0}; // 统计相同的后5个字符
                    for (int k = j + 1; k < s.size(); k++) {
                        vis3[s[k]]++;
                        if (vis3[s[k]] == 5) { // 找到最后5个字符，直接输出
                            for (int u = 0; u < 5; u++) cout << op1;
                            for (int u = 0; u < 7; u++) cout << op2;
                            for (int u = 0; u < 5; u++) cout << s[k];
                            return;
                        }
                    }
                }
            }
        }
    }
    // 找不到满足条件的序列
    cout << "none" << endl;
}

int main() {
    IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

F. 集合之和

原题链接

题意：

对于两个有限的数集 $$A, B$$ ，定义 $$A + B$$ 为： $A + B = \{x + y \mid x \in A, y \in B\}$
记有限数集 $$A$$ 的元素个数为 $$|A|$$ 。
给定 $$n$$ ，求满足 $$|A + A| = n$$ ，且满足 $\forall x \in A, 0 \le x \le 5 \times 10^5$ 的数集 $$A$$ 。
若存在 $$A$$ 满足上述条件，输出集合 $$A$$ 的大小并输出其元素（任意解均可），不存在则输出 $$-1$$ 。

思路：

思维，规律，构造。

构造简单数集 $A = \{0,1,2,\dots,k\}, |A| = k$ ，则 $A + A = \{0,1,2,\dots,2k\}, |A+A| = 2k + 1$ 。

通过上述构造，显然当 $$n$$ 为奇数时一定有解，我们只需要构造满足如上规则的数集即可。

接下来讨论 $$n$$ 为偶数的情况：

$$|A| = 2, |A+A| = 3$$ ，当 $$n = 2$$ 时无解；
$|A| = 3, 5 \le |A+A| \le 6$ ，当 $$n = 4$$ 时无解；
其他情况下，构造数集 $A = \{0,2,3,\dots,k\}$ ，则 $A+A = \{0,2,3,\dots,2k\}, |A+A| = 2k$ 。

综上所述，根据 $$n$$ 的奇偶性按照上述规则构造即可。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, string> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int n;

void solve() {
    cin >> n;
    if (n == 2 || n == 4) {
        cout << -1 << endl;
        return;
    }
    if (n % 2 != 0) {  // 奇数构造 0,1,2,...,(n-1)/2
        cout << (n - 1) / 2 + 1 << endl;
        for (int i = 0; i <= (n - 1) / 2; i++) cout << i << ' ';
    } else {  // 偶数构造 0,2,3,...,n/2
        cout << n / 2 << endl;
        cout << 0 << ' ';
        for (int i = 2; i <= n / 2; i++) cout << i << ' ';
    }
}

int main() {
    IOS;
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}

G. Mocha 上大班啦

原题链接

题意：

给定 $n$ 个 $01$ 串以及 $q$ 次操作，每次操作会把第 $i$ 个串的 $l-r$ 位替换为和第 $j$ 个串的 $l-r$ 位分别进行与运算的结果。
- 第 $$i$$ 次操作有概率 $$p_i$$ 成功。
- 询问最后 $$n$$ 个串与运算得到的串中 $$1$$ 的个数。

思路：

思维题。
- 概率期望套皮，其实无需处理。
- 只要一位中出现过 $$0$$ ，由于进行的是“与”位运算，操作多少次都不会影响任何一个 $$01$$ 串第 $$i$$ 位的值，结果一定是 $$0$$ 。
- 故直接计算初始 $$01$$ 串与操作后的 $$1$$ 的个数即为答案。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, string> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

const int N = 1010;

char a[N][4 * N];

int n, m;

void solve() {
    int res = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    int q; cin >> q;
    while (q--) {
        for (int i = 0; i < 5; i++) {
            int op; cin >> op;
        }
    }

    for (int i = 0; i < m; i++) {
        int cnt = 1;
        for (int j = 0; j < n; j++) {
            if (a[j][i] == '0') cnt = 0;
        }
        res += cnt;
    }

    cout << res << endl;
}

int main() {
    IOS;
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}

H. 旋转水管

原题链接

题意：

给定一个 (2 \times m) 的水管图，水管有 I、L 两种类型，且两种水管均可以旋转。问是否可以通过旋转水管，使得水从第 (x) 列流入后从第 (y) 列流出。

思路：

采用 DFS 搜索。

水管的出水状态与流入状态相关，因此需要记录上一个格子流入下一个格子时的方向状态。
分析状态转换规则可知：
- 对于 I 形的水管，流出状态与流入状态相同。
- 对于 L 形的水管：
  - 当流入方向是向上 ((\uparrow)) 或向下 ((\downarrow)) 时，流出方向有两种可能：向左 ((\leftarrow)) 或向右 ((\rightarrow))。
  - 当流入方向是向左 ((\leftarrow)) 或向右 ((\rightarrow)) 时，流出方向有两种可能：向上 ((\uparrow)) 或向下 ((\downarrow))。

根据上述分析，我们可以定义对应方向状态的坐标偏移量，在搜索过程中通过加上该偏移量来实现坐标转移，从而判断水的流动是否合法。

代码：

cpp

#include <iostream>
#include <cstring>
using namespace std;

const int MAXM = 1000;
int m, sl, el;
int flag;
int vis[2][MAXM];
char mp[2][MAXM];

void dfs(int l, int r, int st) {
    if (flag == 1) return;  //满足条件直接返回

    if (l == 1 && r == el - 1) {  //到达出口的情况合法
        flag = 1;  //标记答案
        return;
    }

    if (l < 0 || l >= 2 || r < 0 || r >= m) return;  //越界直接返回

    if (vis[l][r]) return;  //走过该点返回

    vis[l][r] = 1;  //标记走过

    if (l >= 0 && l < 2 && r >= 0 && r < m) {
        if (mp[l][r] == 'I') {  //进入状态和流出状态相同
            if (st == 0) dfs(l + 1, r, 0);
            if (st == 1) dfs(l, r + 1, 1);
            if (st == 2) dfs(l - 1, r, 2);
            if (st == 3) dfs(l, r - 1, 3);
        } else {
            if (st == 0 || st == 2) {  //从下面或上面流入的状态
                dfs(l, r + 1, 1);
                dfs(l, r - 1, 3);
            }
            if (st == 1 || st == 3) {  //从左边或右边流入的状态
                dfs(l + 1, r, 0);
                dfs(l - 1, r, 2);
            }
        }
    }

    vis[l][r] = 0;  //回溯时恢复现场
}

bool solve() {
    cin >> m >> sl >> el;
    for (int i = 0; i < 2; i++) cin >> mp[i];

    flag = 0;  //多实例，初始化
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j <= m; j++) vis[i][j] = 0;
    }

    dfs(0, sl - 1, 0);

    return flag;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int _ = 1;
    cin >> _;

    while (_--) {
        if (solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

赛后回顾与总结

生涯第一次参加 CCPC，先贴一张战绩：

铜牌线是 188，我们队伍 191 喜提铁牌 ~~（bushi）~~ 啊吧啊吧。。。

赛程回顾

两个大三的队友还是很给力的，上来就切掉了 $A$ 题，拿下了一个漂亮的 AC。
- 我之后粗略地计算了一下 $$E$$ 题的时间复杂度，于是直接三个循环暴力切掉了，虽然因为统计字母数量的 vis 数组开小了，白白吃了一发 WA，~~为全队奠定了打铁的基础~~。
- 然后我发现 $$H$$ 题是个搜索貌似能行？从此队伍少了一个人……
- 队友开搞 $$F$$ ，上机打表，我在纸上手撕 $$H$$ 。
- 队友开搞 $$G$$ ，最后发现是道沙笔套皮期望的诈骗题，光速写完不测样例直接冲，小 WA 一下就过了，没有一开始切掉就很可惜。
- 然后 $$zhgg$$ 开始帮我调我的沙笔 $$H$$ 题，因为觉得 $$BFS$$ 的思路完全没问题，死磕到底，最后头晕脑胀，坐标都搞混了，剩半小时重写一次最后都没搞出来，直接大寄 (。_。)。
- 最后绝望看榜 $$200+$$ 的名次，去掉打星的队伍粗略算一下能拿铜牌线~~（赛后发现还是太天真）~~，不过维他柠檬茶是真的好喝，逃。

赛后总结：

打铁的根本原因还是自己能力太弱小了。
- 其本质就是我的懒惰，在本该出成绩的时期，思想上懈怠、行动上松懈了。训练量达不到还妄想着出成绩。
- 这次参赛也明显感受到了经验的不足，两个大三的队友异常镇定和发挥稳定，相较而言，没有大赛经验的我在比赛时手忙脚乱，拖累了团队。
- 最后是比赛题目的分配和合作，团队协同参赛的我们互相没有磨合好，队友在讨论时我独自去切没有把握的题，最后还没有解出来，也错过了讨论和看其他题目的机会和时间。

PS：

今后的计划：
- 加训；
- 加训；
- 还是 TMD 加训。
和队友抽空多打几场 VP，训练团队合作。
卧薪尝胆，下次 $$ICPC$$ 必将胜利。

5. 动态规划

6. 学校培训

动态规划

搜索

数学

贪心

字符串

图论

力扣

其他

Acwing

Codeforces

Atcoder

CCPC

LeetCode

2022ccpc

A. Mocha 上小学啦

E. Serval 的俳句

F. 集合之和

G. Mocha 上大班啦

H. 旋转水管

赛后回顾与总结

2022ccpc ​

A. Mocha 上小学啦 ​

E. Serval 的俳句 ​

F. 集合之和 ​

G. Mocha 上大班啦 ​

H. 旋转水管 ​

赛后回顾与总结 ​

2022ccpc

A. Mocha 上小学啦

E. Serval 的俳句

F. 集合之和

G. Mocha 上大班啦

H. 旋转水管

赛后回顾与总结