前言

---

题解

睿抗机器人开发者大赛CAIP-编程技能赛-历年真题 汇总

2021 RoboCom 世界机器人开发者大赛-本科组。
很奇怪的比赛体验，T2 队列插入，应该是最难的，T_T，反而T3，T4更容易快速得分。

---

7-1 绿地围栏

分值: 20

思路： 模拟

特别注意,

1. 下一个点可能跨越多条线段
2. 一条线段可能有多个分割点
3. 如果最后一个点是(0,0), 需要忽略

大概有两种，思路

1. 按增量1步长，模拟推进
2. 按$d=min(围栏长度L,剩余线段的长度)$推进

代码是按第二种思路推进并模拟的，但第一种真心推荐。

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, l;
    cin >> n >> l;
    vector<int> arr;
    for (int i = 0; i < n ;i++) {
        int v;
        cin >> v;
        arr.push_back(v);
    }
    n++;
    arr.push_back(0);
    
    int ans = 0;
    int x = 0, y = 0;

    cout << x << " " << y << endl;
    for (int i = 0; i < n ;i++) {
        if (i % 2 == 0) {
            int delta = abs(arr[i] - y);
            int sign = arr[i] - y >= 0 ? 1 : -1;
             while (delta > 0) {
                int d = (ans % l != 0) ? (l - ans % l) : l;
                if (d <= delta) {
                    ans += d;
                    y += d * sign;
                    if (x != 0 || y != 0) {
                    	cout << x << " " << y << "\n";
                    }
                    delta -= d;
                } else {
                    ans += delta;
                    y += delta * sign;
                    break;
                }
            }
        } else {
            int delta = abs(arr[i] - x);

            int sign = arr[i] - x >= 0 ? 1 : -1;
            while (delta > 0) {
                int d = (ans % l != 0) ? (l - ans % l) : l;
                if (d <= delta) {
                    ans += d;
                    x += d * sign;
                    if (x != 0 || y != 0) {
                    	cout << x << " " << y << "\n";
                    }
                    delta -= d;
                } else {
                    ans += delta;
                    x += delta * sign;
                    break;
                }
            }
        }
    }
    
    return 0;
}

---

7-2 队列插入

分值: 25
思路: 枚举+LIS
这题难就难在
$$当最优解相等时，需求字典序最小$$

当思绪陷入僵局的时候，可以把问题简化，或者添加额外限制条件，来找到解题线索。

把求解的问题，松弛

$$只求最长的递增序列$$

结合数据范围$n\le 1000$，可以枚举v，

1. 使得 $\ge v$按右侧push，然后寻找最长递增序列 $big$
2. 使得$<v$按左侧push，然后寻找最长递减序列 $small$

然后求 $max(bi{g}_v+smal{l}_v)$

那在回到字典序最小这个核心问题，寻找是否有什么特性，可以天然满足字典序最小。

最长递增序列的构造性质：
$$即逆序反向构建即最小，这个可以反证法来保证$$

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int &x: arr) cin >> x;

    // 预处理，构建以v值开头的最长严格递降数组长度
    map<int, int> hp;
    hp[arr[n - 1]] = 1;
    for (int i = n - 2; i >= 0; i--) {
        int v = arr[i];
        hp[v] = max(hp[v], 1);
        for (int j = i + 1; j < n; j++) {
            if (v > arr[j]) {
                hp[v] = max(hp[v], hp[arr[j]] + 1);
            }
        }
    }

    int ans = 0;
    string ansStr(n, 'L');
    for (auto &[k, v] : hp) {
        if (ans < v) ans = v;
    }

    for (int i = 0; i < n; i++) {
        vector<int> dp(n, 0);
        vector<int> lis;
        for (int j = i; j < n; j++) {
            int v = arr[j];
            if (v < arr[i]) continue;
            int l = 0, r = lis.size() - 1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (v > lis[m]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }

            if (l >= lis.size()) {
                lis.push_back(v);
                dp[j] = lis.size();
            } else {
                lis[l] = v;
                dp[j] = l + 1;
            }            
        }

        string s(n, 'L');
        int mz = lis.size(), xz = lis.size();
        for (int j = n - 1; xz > 0 && j >= i; j--) {
            if (dp[j] == xz) {
                s[j] = 'R';
                xz--;
            }
        }
    
        int tmpAns = mz;
        for (auto &[k, v]: hp) {
            if (k < arr[i] && tmpAns < mz + v) {
                tmpAns = mz + v;
            }
        }
        
        if (tmpAns > ans || (tmpAns == ans && s < ansStr)) {
            ans = tmpAns;
            ansStr = s;
        }
    }
    cout << ans << "\n";
    cout << ansStr << "\n";
    
    return 0;
}

---

7-3 账户安全预警

分值: 25分
思路: 模拟，纯阅读理解

#include <bits/stdc++.h>

using namespace std;

struct T {
    string e;
    int ipn, ipc;
    bool operator<(const T&o) const {
        if (ipc != o.ipc) return ipc > o.ipc;
        return e < o.e;
    }
};

struct E {
    string ip;
    int cnt;
    bool operator<(const E&o) const {
        if (cnt != o.cnt) return cnt > o.cnt;
        return ip < o.ip;
    }
};

int main() {
    int n, t1, t2;
    cin >> n >> t1 >> t2;

    map<string, map<string, int>> hp;
    map<string, int> cnt;
    
    for (int i = 0; i < n; i++) {
        string e, ip;
        cin >> e >> ip;
        cnt[e]++;
        hp[e][ip]++;
    }

    vector<T> vec;
    for (auto [k, v] : cnt) {
        vec.push_back({k, v, (int)hp[k].size()});
    }
    sort(vec.begin(), vec.end());

    int maxn = 0;
    bool ok = false;
    for (T &t: vec) {
        maxn = max(maxn, t.ipc);
        if (t.ipc > t1 && t.ipn > t2) {
            vector<E> vec2;
            for (auto [k, v]: hp[t.e]) {
                vec2.push_back({k, v});
            }
            ok = true;
            cout << t.e << "\n";
            sort(vec2.begin(), vec2.end());
            for (E &e: vec2) {
                cout << e.ip << " " << e.cnt << "\n";
            }
        }
    }

    if (!ok) {
        for (T &t: vec) {
            if (t.ipc == maxn) {
                vector<E> vec2;
                for (auto [k, v]: hp[t.e]) {
                    vec2.push_back({k, v});
                }
                cout << t.e << "\n";
                sort(vec2.begin(), vec2.end());
                for (E &e: vec2) {
                    cout << e.ip << " " << e.cnt << "\n";
                }
            }
        }
    }

    return 0;
}

---

7-4 猛犸不上 Ban

分值：30
思路: 枚举 + 图论

这只猛犸从 S 号城市出发，它可以选择：

• 在不重复地经过若干条道路后回到 S 号城市；
• 在不重复地经过若干条道路后到达 T 号城市。

对于第一个选择，我们可以用dijkstra算法，轻松搞定。
其实题目难在第二个选择上，即在无向图中，找到一个没有重边的环。

既然关键词是：没有重复边

同时注意到题目限制条件：$2\le N\le 500,1\le M\le 10^5$

可以枚举S节点的出边e1，进行全图的dijkstra处理得到path。然后在枚举S节点的其他出边e2，以及该出边对应的节点v，结果为
m i n { p a t h [ v ] + w s v } {min \{ path[v] + w_{sv} \} } min{path[v]+wsv​}
path为s通过e1出发构建的最短路径， e2为s到v的边

朴素dijkstra的时间复杂度为$O(n^2)$, 用堆优化的$(n+m)\ast log(m)$

整体的时间复杂度为
$$n\ast T_{dijkstra}=min(n\ast (n+m)\ast log(m),n\ast n^2)=n^3$$

即采用枚举出边+朴素dijkstra， $O(n^3)$

• 堆优化的dijkstra解法 (144 / 800 ms)

#include <bits/stdc++.h>

using namespace std;

struct E {
    int v, w;
    bool operator<(const E&e) const {
        return w > e.w;
    }
};

const int inf = 1e9;

int dijkstra(int s, int e, vector<vector<E>> &g) {
    int n = g.size();
    vector<int> dp(n, inf);
    dp[s] = 0;

    priority_queue<E, vector<E>> pq;
    pq.push({s, 0});

    while (!pq.empty()) {
        E e = pq.top(); pq.pop();
        if (e.w > dp[e.v]) continue;
        for (E &x: g[e.v]) {
            if (dp[x.v] > dp[e.v] + x.w) {
                dp[x.v] = dp[e.v] + x.w;
                pq.push({x.v, dp[x.v]});
            }
        }
    }

    return dp[e];
}

int circle(int s, int good, vector<vector<E>> &g) {
    int n = g.size();
    vector<int> dp(n, inf);
    dp[s] = 0;

    priority_queue<E, vector<E>> pq;
    pq.push({s, 0});

    while (!pq.empty()) {
        E e = pq.top(); pq.pop();
        if (e.w > dp[e.v]) continue;
        if (e.v == s) {
            for (E &x: g[e.v]) {
                if (x.v == good && dp[x.v] > dp[e.v] + x.w) {
                    dp[x.v] = dp[e.v] + x.w;
                    pq.push({x.v, dp[x.v]});
                }
            }
        } else {
            for (E &x: g[e.v]) {
                if (dp[x.v] > dp[e.v] + x.w) {
                    dp[x.v] = dp[e.v] + x.w;
                    pq.push({x.v, dp[x.v]});
                }
            }
        }
    }

    int ans = inf;

    for (E &e: g[s]) {
        if (e.v != good) {
            ans = min(ans, dp[e.v] + e.w);
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;

    vector<vector<E>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    int ans1 = inf;
    for (E &e: g[s]) {
        int tmp = circle(s, e.v, g);
        ans1 = min(ans1, tmp);
    }
    int ans2 = dijkstra(s, t, g);
    
    if (ans1 == inf && ans2 == inf) {
        cout << -1 << "\n";
    } else {
        cout << (ans1 == inf ? -1 : ans1) << " " << (ans2 == inf ? -1 : ans2) << "\n";
        cout << ((ans1 < ans2) ? "Win!" : "Lose!") << "\n";
    }

    return 0;
}

• 朴素dijkstra的解法（537 / 800 ms）

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

int dijkstra(int s, int e, vector<vector<int>> &g) {
    int n = g.size();
    
    vector<bool> vis(n);
    vector<int> dp(n, inf);
    dp[s] = 0;

    for (int i = 0; i < n; i++) {
        int nxt = -1;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && (nxt == -1 || dp[nxt] > dp[j])) {
                nxt = j;
            }
        }
        if (nxt == -1) break;
        
        vis[nxt] = true;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && dp[j] > g[nxt][j] + dp[nxt]) {
                dp[j] = g[nxt][j] + dp[nxt];
            }
        }
    }

    return dp[e];
}

int circle(int s, int good, vector<vector<int>> &g) {
    int n = g.size();
    vector<bool> vis(n);
    vector<int> dp(n, inf);
    dp[s] = 0;

    for (int i = 0; i < n; i++) {
        int nxt = -1;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && (nxt == -1 || dp[nxt] > dp[j])) {
                nxt = j;
            }
        }
        if (nxt == -1) break;
        
        vis[nxt] = true;
        if (nxt == s) {
            if (dp[good] > g[s][good] + dp[s]) {
                dp[good] = g[s][good] + dp[s];
            }
        } else {
            for (int j = 0; j < n; j++) {
                    if (!vis[j] && dp[j] > g[nxt][j] + dp[nxt]) {
                        dp[j] = g[nxt][j] + dp[nxt];
                    }
            }
        }
    }

    int ans = inf;
    for (int i = 0; i < n; i++) {
        if (i != good && i != s) {
            ans = min(ans, dp[i] + g[s][i]);
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--; t--;

    vector<vector<int>> g(n, vector<int>(n, inf));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        g[u][v] = w;
        g[v][u] = w;
    }

    int ans1 = inf;
    for (int i = 0; i < n; i++) {
        if (i != s && g[s][i] < inf) {
            int tmp = circle(s, i, g);
            ans1 = min(ans1, tmp);
        }
    }
    int ans2 = dijkstra(s, t, g);
    
    if (ans1 == inf && ans2 == inf) {
        cout << -1 << "\n";
    } else {
        cout << (ans1 == inf ? -1 : ans1) << " " << (ans2 == inf ? -1 : ans2) << "\n";
        cout << ((ans1 < ans2) ? "Win!" : "Lose!") << "\n";
    }

    return 0;
}

让人意外的是，前者比后者更优秀，T_T
所以这也是 PTA 离谱的地方，它的测试数据永远处于 薛定谔的猫 状态。

有的时候，撑死胆大的。
有的时候，坟头草三丈。

---

写在最后