2024 YAC Round 8 题解

A 「爱」与自动手记人偶

题意描述

给定一个长度为 $n$ 的连续字符串，统计每种字符的个数，并按照字符 $\text{ascii}$ 码的顺序从小到大输出结果。（看清楚输出格式）「YAC Round 8」「爱」与自动手记人偶

解题思路 $\text{map}$ 计数

使用 $\text{map}$ 计数并输出即可（$\text{C++}$ 中的 $\text{map}$ 默认以键值对中的键为第一关键字从小到大排序）。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

map<char, int> mp;

int main(){
    ios;

    string s; cin >> s;
    for(auto &ch : s) mp[ch] ++ ;
    for(auto &[ch, x] : mp) cout << ch << ": " << x << "\n";

    return 0;
}

B 小五和恋恋是姐妹

题意描述

输入两个正整数 $x$ 和 $y$，判断两个数是否都是质数并且两数之差是否是 $555$ 的倍数。「YAC Round 8」小五和恋恋是姐妹

解法一 试除法判断质数

用试除法判断质数，同时判断两数之差是否为 $555$ 的倍数即可。（注意判断 $1$）。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

bool check(int x){
    if(x == 1) return false;
    for(int i = 2; i <= (int)sqrt(x); i ++ )
        if(x % i == 0) return false;
    return true;
}

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        int x, y; cin >> x >> y;
        if((x - y) % 555 == 0 && check(x) && check(y)) cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }

    return 0;
}

解法二 线性筛质数

数据范围不大，可以预处理用线性筛筛出所有质数，如果两个数中存在一个或一个以上的数为合数（即不是质数），或者差不是 $555$ 的倍数，那么输出 NO 即可；否则，输出 YES 。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 1e5 + 10;

int prime[N], cnt;
bool st[N];

void work(int n){
    st[1] = true;
    for(int i = 2; i <= n; i ++ ){
        if(!st[i]) prime[ ++ cnt] = i;
        for(int j = 1; prime[j] <= n / i; j ++ ){
            st[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main(){
    ios;

    work(N - 1);

    int T; cin >> T;
    while(T -- ){
        int x, y; cin >> x >> y;
        if(st[x] || st[y] || (x - y) % 555 != 0) cout << "NO" << "\n";
        else cout << "YES" << "\n";
    }

    return 0;
}

C 河城科技牌计算器

题意描述

模板题，计算带有加减乘除运算以及括号的表达式。「YAC Round 8」河城科技牌计算器

解题思路 栈

主要的思路为双栈模拟，其中一个栈存储计算的数字，另一个栈存储运算符号。

$\text{AcWing}$ 原题，AcWing 3302. 表达式求值：多图讲解运算符优先级+详细代码注释 高赞题解肯定比我写得好。（其实是我这次想偷懒了 😋

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

string s;
stack<int> nums;
stack<char> ops;
//运算符优先级
unordered_map<char, int> mp{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };

void caculate(){
    //栈顶的两个数字
    int b = nums.top();
    nums.pop();
    int a = nums.top();
    nums.pop();

    char op = ops.top();
    ops.pop();

    int res = 0;
    if(op == '+') res = (a + b);
    if(op == '-') res = (a - b);
    if(op == '*') res = (a * b);
    if(op == '/') res = (a / b);

    nums.push(res);
}

int main(){
    ios;

    cin >> s;
    int n = s.size();
    for(int i = 0; i < n; i ++ ){
        if(isdigit(s[i])){
            //计算当前数字
            int cur = 0, j = i;
            while(j < n && isdigit(s[j])){
                cur = cur * 10 + (s[j] - '0');
                j ++ ;
            }
            nums.push(cur);
            i = j - 1;
        }else if(s[i] == '('){
            ops.push(s[i]);     //左括号直接入栈
        }else if(s[i] == ')'){
            //遇到右括号 优先计算括号里的
            while(ops.top() != '(')
                caculate();     //遇到左括号停止
            ops.pop();          //弹出左括号
        }else{
            while(!ops.empty() && mp[ops.top()] >= mp[s[i]])
                caculate();     //入栈运算符优先级低，先算栈内的
            ops.push(s[i]);
        }
    }

    while(!ops.empty()) caculate();
    int ans = nums.top();
    cout << ans << "\n";

    return 0;
}

D 连后序遍历都忘记了，咋办？

题意描述

给定一颗二叉树的 前序遍历序列 和 中序遍历序列，节点编号从 $1 \sim n$，构造出原二叉树，并输出镜像二叉树的后序遍历序列。「YAC Round 8」连后序遍历都忘记了，咋办？

解题思路 递归

一年多以前写过一篇博客，专门讲的已知两种遍历方式构造二叉树。不过是一年前了，现在来看像是黑历史…🥹 [数据结构] 根据前中后序遍历中的两种构造二叉树

镜像的部分比较简单，后序遍历递归的时候只要先递归遍历右子树再递归遍历左子树即可。

相比较 PTA 中 团体天梯练习 L2-011 玩转二叉树 略简单一些。（哈哈，这篇博客也是快一年前写的了🥲

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int n;
unordered_map<int, int> in_idx;  //中序遍历的对应下标
vector<int> pre;  //中序 前序
typedef struct node{
    int val;
    struct node *left, *right;
}node;
node *T;
vector<int> res; 

// 中序遍历和前序遍历构造二叉树
node* build(int in_l, int in_r, int pre_l, int pre_r){
    if(in_l > in_r || pre_l > pre_r) return NULL;
    int root_val = pre[pre_l];   //前序遍历第一个节点为子树根节点
    int mid = in_idx[root_val];  //定位根节点坐标
    int left_num = mid - in_l;   //左子树节点个数

    node *root = new node;
    root->val = root_val;
    root->left = build(in_l, mid - 1, pre_l + 1, pre_l + left_num);
    root->right = build(mid + 1, in_r, pre_l + left_num + 1, pre_r);

    return root;
}

void postorder(node *root){
    if(root == NULL) return;
    postorder(root->right);
    postorder(root->left);
    res.push_back(root->val);
}

int main(){
    ios;

    cin >> n;
    pre.resize(n);
    for(int i = 0; i < n; i ++ ) cin >> pre[i];
    for(int i = 0; i < n; i ++ ){
        int x; cin >> x;
        in_idx[x] = i;        //记录中序遍历各节点值对应的下标
    }

    T = build(0, n - 1, 0, n - 1);  //建树

    postorder(T);

    for(int i = 0; i <= n - 1; i ++ ) cout << res[i] << " \n"[i==n-1];
    
    return 0;
}

E 不要再打骚扰电话了！

题意描述

给定一个 $n \times n$ 的网格图，相邻的区域都有边，但是有部分相邻区域的边断开了。两个点可以通过若干条边互相到达，求有多少对点无法互相到达。「YAC Round 8」不要再打骚扰电话了！

解题思路

我们转换一下问题，要求有多少对点之间无法互相到达，也就是不连通的点的对数，那么我们可以求出图中的每个连通块，并统计每个连通块中的点数。

最后不连通的点的对数，显然就是两两连通块之间点数乘积累加和（注意不要重复计算）；当然也可以累加每个连通块点数与其他不在当前连通块的点数，最后再除以 $2$ 即可。

记录断开的边的方式有很多种，可以记录每个点与其相邻四个方向是否断开，实现很简单；也可以将每个点 $(x, y)$ 映射为 $(x - 1) \times n + y$，对于一个断开的边，$(x_u, y_u)$ 到 $(x_v, y_v)$，对应的映射值为 $u$ 和 $v$，此时用
map<pair<int, int>, bool> 来记录 $(u, v)$ 即可。

求连通块及连通块内点数方法也很多，可以用 $\text{BFS}$，也可以并查集维护集合大小。

解法一 BFS

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
typedef pair<int, int> pii;
typedef long long ll;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int N = 1e4 + 10;

int n, m, q; 
map<pii, bool> ban; // 记录接触不良的电话线路

int getID(int x, int y){ return (x - 1) * n + y; }

bool vis[110][110]; // 标记是否访问过
int g[110][110];    // 是否有居民
int sz[N];  // 每个连通块居民个数
int num;    // 连通块标记

void bfs(int sx, int sy){
    queue<pii> q;
    q.emplace(sx, sy);
    vis[sx][sy] = true;

    while(q.size()){
        auto [x, y] = q.front();
        q.pop();

        sz[num] += g[x][y];

        for(int k = 0; k < 4; k ++ ){
            int nx = x + dx[k], ny = y + dy[k];
            if(nx < 1 || ny < 1 || nx > n || ny > n) continue;
            if(vis[nx][ny] || ban[MP(getID(x, y), getID(nx, ny))]) continue;
            q.emplace(nx, ny);
            vis[nx][ny] = true;
        }
    }
}

int main(){
    ios;

    cin >> n >> m >> q;
    while(q -- ){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        int u = getID(x1, y1), v = getID(x2, y2);
        ban[MP(u, v)] = ban[MP(v, u)] = true;
    }

    for(int i = 1, x, y; i <= m; i ++ ) cin >> x >> y, g[x][y] = 1;

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            if(!vis[i][j]) num ++ , bfs(i, j);

    ll res = 0;
    for(int i = 1; i <= num; i ++ ) res += sz[i] * (m - sz[i]);
    cout << res / 2 << "\n";  // 每一对算了两次，故除以2

    return 0;
}

解法二 并查集

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
typedef pair<int, int> pii;
typedef long long ll;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int N = 1e4 + 10;

int n, m, q; 
map<pii, bool> ban; // 记录接触不良的电话线路

int getID(int x, int y){ return (x - 1) * n + y; }

int fa[N], s[N];    // 并查集 维护集合大小

int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y){
    int fx = find(x), fy = find(y);
    if(fx ^ fy) fa[fy] = fx, s[fx] += s[fy];
}

int main(){
    ios;

    cin >> n >> m >> q;
    while(q -- ){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        int u = getID(x1, y1), v = getID(x2, y2);
        if(u > v) swap(u, v); // 建边时只需要向下和向右连边即可，故记录小到大的ban
        ban[MP(u, v)] = true;
    }

    for(int i = 1; i <= n * n; i ++ ) fa[i] = i; // 初始化并查集
    for(int i = 1; i <= m; i ++ ){
        int x, y; cin >> x >> y;
        int u = getID(x, y);
        s[u] = 1;             // 有居民才初始化大小为1，否则初始为0
    }

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ ){
            int u = getID(i, j);
            for(int k = 0; k < 2; k ++ ){
                int ni = i + dx[k], nj = j + dy[k];
                if(ni < 1 || nj < 1 || ni > n || nj > n) continue;
                int v = getID(ni, nj);
                if(ban[MP(u, v)]) continue;
                merge(u, v);  // 合并
            }
        }

    ll res = 0;
    for(int i = 1; i <= n * n; i ++ )
        if(fa[i] == i) res += s[i] * (m - s[i]);
    cout << res / 2 << "\n"; // 每一对居民算了两次，故除以2

    return 0;
}

F 最喜欢的字符串 I

题意描述

给定一个长度为 $n$ 的字符串 $s$，其中包含字母和数字。从左往右依次读取每个字符，如果它是字母，那么将它加入字符串 $t$ 中，如果是数字(例如 $d$ )，那么你需要将字符串 $t$ 复制 $d - 1$ 次并添加到字符串 $t$ 的末尾。「YAC Round 8」最喜欢的字符串 I

解题思路

如果我们有一个像 $\text{"appleappleappleappleappleapple"}$ 这样的解码字符串和一个像 $\text{K=24}$ 这样的索引，那么如果 $\text{K=4}$，答案是相同的。

一般来说，当解码的字符串等于某个长度为 $\text{size}$ 的单词重复某些次数（例如 $\text{apple}$ 与 $\text{size=5}$ 组合重复 $6$ 次）时，索引 $\text{K}$ 的答案与索引 $\text{K \% size}$ 的答案相同。

我们可以通过逆向工作，跟踪解码字符串的大小。每当解码的字符串等于某些单词 重复 $d$ 次时，我们就可以将 $\text{K}$ 减少到 $\text{K \% len(word)}$ 。

首先，我们可以先正向处理，找出解码后的字符串的长度。 之后，我们可以逆向工作，跟踪 $\text{size}$： 解析符号 S[0], S[1], ..., S[i] 后解码字符串的长度。

如果我们看到一个数字 S[i]，则表示在解析 S[0]，S[1]，...，S[i-1] 之后解码字符串的大小将是 $\text{size / int(S[i])}$。 否则，将是 $\text{size - 1}$。

#include<bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;

char work(string s, int K) {
    ll size = 0;
    int N = s.size();

    for(int i = 0; i < N; i ++ ) {
        if(isdigit(s[i])) size *= s[i] - '0';
        else size ++ ;
    }

    for (int i = N - 1; i >= 0; i -- ){
        K %= size;
        if (K == 0 && isalpha(s[i])) return s[i];

        if(isdigit(s[i])) size /= s[i] - '0';
        else size -- ;
    }

    return ' ';
}

int main(){
    ios;

    string s; cin >> s;
    int k; cin >> k;
    cout << work(s, k) << "\n";

    return 0;
}