---

前言

---

题解

2023 睿抗机器人开发者大赛CAIP-编程技能赛-专科组（国赛)。

最后一题是搜索+剪枝，还要注意整数溢出的问题。

---

RC-v1 另类单位圆

分值: 20分

思路: 模拟

全枚举即可， 时间复杂度为$O(10^8)$

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int minV = (int)1e9;
    int minX = 0, minY = 0;
    int maxV = 0;
    int maxX = 0, maxY = 0;
    for (int i = a; i <= b; i++) {
        for (int j = a; j <= b; j++) {
            int v = abs(i * i - i * j - j * j);
            if (v != 1) continue;

            int ov = i + j;
            if (minV > ov) {
                minV = ov;
                minX = i; minY = j;
            }
            if (maxV < ov) {
                maxV = ov;
                maxX = i; maxY = j;
            }
        }
    }
    cout << "(" << minX << ", " << minY << ")\n";
    cout << "(" << maxX << ", " << maxY << ")\n";
    return 0;
}

---

RC-v2 含茶量

分值： 25分

思路: api调用题 + 模拟

1. 归一化，把大写字符串统一为小写字符串
2. 用暴力匹配字符串即可，不需要用kmp，z函数，因此chatgp固定且不长

#include <bits/stdc++.h>

using namespace std;

struct T {
  string k; int v;
    T(string k, int v) : k(k), v(v) {}
};

int main() {

    string line;
    getline(cin, line);
    int n = atoi(line.c_str());

    vector<T> vec;
    map<string, int> hp;
    while (n-- > 0) {
        string name;
        getline(cin, name);
        getline(cin, line);
        for (size_t i = 0; i < line.size();i++) {
            if (line[i] >= 'A' && line[i] <= 'Z') {
                line[i] = line[i] - 'A' + 'a';
            }
        }

        int cnt = 0;
        int pos = 0;
        while ((pos = line.find("chatgpt", pos)) != string::npos) {
            pos += 7;
            cnt++;
        }
        if (cnt > 0) hp[name] += cnt;
    }
    for (auto &e: hp) vec.push_back(T(e.first, e.second));
    
    sort(vec.begin(), vec.end(), [](auto &a, auto &b) {
        if (a.v != b.v) return a.v > b.v;
        return a.k < b.k;
    });
    
    int limit = vec.size() > 3 ? 3 : vec.size();
    for (int i = 0; i < limit; i++) {
        cout << vec[i].k << " " << vec[i].v << "\n";
    }

    return 0;
}

---

RC-v3 软件窗体的层级管理

分值：25分

思路: 层序bfs

这题的关键点在于，树的节点个数n ($n\le 1000$), 因此，每次查询按该节点分层bfs即可。

时间复杂度为 $O(n\ast q)$

#include <bits/stdc++.h>

using namespace std;

void solve(vector<vector<int>> &g, int s) {
    // 层序遍历
    int ans = 0, ansLevel = 0;
    deque<int> que;
    que.push_back(s);

    int level = 0;
    while (!que.empty()) {
        int sz = que.size();
        // ans = max(ans, sz);
        level++;
        if (ans < sz) {
            ans = sz;
            ansLevel = level;
        }
        for (int i = 0; i < sz; i++) {
            int u = que.front(); que.pop_front();
            for (int v: g[u]) {
                que.push_back(v);
            }
        }
    }
    cout << ansLevel << " " << ans << "\n";
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int id, k;
        cin >> id >> k;
        for (int j = 0; j < k; j++) {
            int next;
            cin >> next;
            g[id].push_back(next);
        }
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u; 
        cin >> u;
        solve(g, u);
    }
    
    return 0;
}

---

RC-v4 加号放哪里

分值: 30分

思路: 搜索+剪枝

为何贪心不行，比如从中间切割

举个特殊的例子

100000000000001

这种形态，显然中间切割不是最佳的

所以采用搜索，同时需要引入剪枝的策略，比如贪心获得一个近似解，加速搜索。

需要注意：$10^{20}超过int64范围$

用uint64_t，或者__int128来规避这个问题

#include <bits/stdc++.h>

using namespace std;

using i128 = __int128;

i128 convert(string s) {
    i128 r = 0;
    for (auto &c: s) {
        r = r * 10 + (c - '0');
    }
    return r;
}

string i128string(i128 v) {
    string r;
    while (v > 0) {
        r.push_back((char)(v % 10 + '0'));
        v /= 10;
    }
    reverse(r.begin(), r.end());
    return r;
}

const int inf = 0x3f3f3f3f;
int gAns = inf;
int gMin = 9;

void dfs(int d, string s) {
    i128 v = convert(s);
    if (v < 10) {
        if (gAns > d) {
            gAns = d;
            gMin = v;
        } else if (gAns == d && gMin > v) {
            gMin = v;
        }
        return;
    }
    // cutoff
    if (gAns < d) return;
    int n = s.size();
    for (int i = 0; i < n - 1; i++) {
        i128 left = convert(s.substr(0, i+1));
        i128 right = convert(s.substr(i + 1));
        i128 v = left + right;
        dfs(d + 1, i128string(v));
    }
}

int main() {
    string s;
    cin >> s;
    dfs(0, s);
    cout << gAns << " " << gMin << "\n";
    return 0;
}

---

写在最后