2021 睿抗机器人开发者大赛CAIP-编程技能赛-本科组（国赛）
7-1 绿地围栏
分数 20
作者 陈越
单位 浙江大学
市政规划了一块绿地，需要采购一批围栏将绿地围起来。
为了简单起见，我们假设绿地的形状是个封闭连通的规则多边形，即所有边都是互相垂直或平行的，并且没有交叉的十字边。我们指定某条垂直边上的一个点为原点 (0,0)，然后按照顺时针记录这个多边形的拐角顶点的位置。显然两个相邻的点坐标中，总有一个是不变的，因为当我们从一个点沿着平行于 x 轴的边移动到下一个点时，这两个点的 y 坐标是不变的；当我们从一个点沿着平行于 y 轴的边移动到下一个点时，这两个点的 x 坐标是不变的，所以我们可以用一种简化的方式去记录这些拐角，即对于从原点开始顺时针出现的拐角点 P1、P2、P3、…… 我们只需要记录 y1、x2、y3、…… 即可，其中 Pi 的坐标是 (xi,yi)。
采购的围栏每一条有固定长度 L，但是可以从任何地方弯折 90 度角，并且超长的部分也可以截掉。我们需要在两条围栏的衔接处打桩固定连接。现按顺时针方向给出绿地多边形各个拐角的简化坐标列表，请你计算需要采购多少条围栏，以及应该在哪里打桩。
输入格式：
输入第一行给出 2 个正整数，分别是：N（≤103），为绿地拐角点的个数（原点不算在内）；以及 L（≤100），是一条围栏的长度。
随后给出 N 个整数，即从原点开始，按顺时针方向给出多边形各个拐角的简化坐标列表。每个坐标的绝对值均不超过 104。数字间以空格分隔。题目保证没有重叠或交叉的边。
输出格式：
每行按格式 x y 输出一对坐标，即从原点出发顺时针给出的打桩点的坐标 (x,y)。注意原点肯定要打一个桩。规定从原点出发顺时针布置围栏，优先使用整条围栏，最后回到原点时，有多余的围栏才会被截掉。
输入样例：
14 5
2 1 1 4 3 5 2 6 -1 4 0 2 -1 0
输出样例：
0 0
2 1
5 3
6 -1
2 0
样例说明：
样例对应的多边形如下图所示（其中红色方块为原点）：
容易算出围栏的总长度为 24，而每条围栏的长度为 5，所以需要 5 条围栏，多余的 1 个单位长度的围栏可以拆掉。从红色的原点出发，每隔 5 个单位打一根桩，图中蓝色方块即为打桩的位置。
#include <bits/stdc++.h>
using namespace std;
// 点结构体
struct Point {
int x, y;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, L;
cin >> N >> L;
vector<int> b(N+1);
for (int i = 1; i <= N; i++) {
cin >> b[i];
}
// 还原顶点 P[0]..P[N+1]
vector<Point> P(N+2);
P[0] = {0, 0};
for (int i = 1; i <= N; i++) {
if (i & 1) {
// 奇数：固定 x，改变 y
P[i].x = P[i-1].x;
P[i].y = b[i];
} else {
// 偶数：固定 y，改变 x
P[i].x = b[i];
P[i].y = P[i-1].y;
}
}
// 回到原点
P[N+1] = {0, 0};
// 计算各边长度及前缀和 S
vector<int> S(N+2, 0);
for (int i = 0; i <= N; i++) {
int dx = abs(P[i+1].x - P[i].x);
int dy = abs(P[i+1].y - P[i].y);
S[i+1] = S[i] + dx + dy;
}
int perim = S[N+1];
// 对每个 k*L (k=0..floor(perim/L)) 打桩
int maxK = perim / L;
int idx = 0; // 当前扫描到的边段
for (int k = 0; k <= maxK; k++) {
int d = k * L; // 目标距离
// 移动 idx 直到 S[idx] <= d < S[idx+1]
while (idx < N+1 && S[idx+1] <= d) idx++;
int delta = d - S[idx]; // 在 P[idx]→P[idx+1] 段上的偏移
// 边方向
int dx = P[idx+1].x - P[idx].x;
int dy = P[idx+1].y - P[idx].y;
int sx = (dx > 0) - (dx < 0);
int sy = (dy > 0) - (dy < 0);
int px = P[idx].x + sx * delta;
int py = P[idx].y + sy * delta;
if(k>0&&px==0&&py==0){
return 0;
}
cout << px << " " << py << "\n";
}
return 0;
}
7-2 队列插入
分数 25
作者 DAI, Longao
单位 杭州百腾教育科技有限公司
现在有一个空队列 Q 以及 N 个数字需要按顺序插入，你可以选择插入队列的头部或尾部，请问在合理选择插入方式的前提下，插入后的队列的最长上升子序列的长度最大是多少？
最长上升子序列指的是在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。子序列指的是通过删除原序列中零个或多个元素后获得的序列。
输入格式:
输入第一行是一个数 N (1≤N≤1000)，表示有 N 个要按顺序插入的数字。
接下来一行 N 个数，表示要插入的数字，数字已经按插入顺序排列好，并且都在 32 位整数范围内。
输出格式:
输出两行，第一行是一个数字，表示最大的最长上升子序列的长度。
接下来一行，输出插入的方案，其中用L表示插入到头部，用R表示插入到尾部。当有多个相同长度的方案时，选择字典序最小的方案（L 的字典序小于 R）。
输入样例:
8
1 3 2 4 2 4 5 0
输出样例:
5
LLLLLRRL
样例解释：
样例最后队列内容为：0 2 4 2 3 1 4 5
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <string>
#include <functional>
using namespace std;
// 使用二分查找计算最长上升子序列的长度
int calculateLIS(const vector<int>& arr) {
if (arr.empty()) return 0;
vector<int> dp;
for (int x : arr) {
auto it = lower_bound(dp.begin(), dp.end(), x);
if (it == dp.end()) {
dp.push_back(x);
} else {
*it = x;
}
}
return dp.size();
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
int maxLIS = 0;
string bestSolution = "";
// 使用DFS搜索所有可能的插入方案
function<void(int, deque<int>&, string&)> dfs = [&](int idx, deque<int>& q, string& path) {
// 如果所有数字都已插入，计算当前方案的LIS长度
if (idx == n) {
vector<int> arr(q.begin(), q.end());
int currentLIS = calculateLIS(arr);
// 更新最优解（优先选择LIS更长的，其次选择字典序更小的）
if (currentLIS > maxLIS || (currentLIS == maxLIS && path < bestSolution)) {
maxLIS = currentLIS;
bestSolution = path;
}
return;
}
// 剪枝：如果当前LIS + 剩余数字个数 <= 已知最优解，则无需继续搜索
vector<int> arr(q.begin(), q.end());
int currentLIS = calculateLIS(arr);
if (currentLIS + (n - idx) <= maxLIS) {
return;
}
// 优先尝试插入到头部（L），因为L的字典序小于R
q.push_front(nums[idx]);
path.push_back('L');
dfs(idx + 1, q, path);
path.pop_back();
q.pop_front();
// 然后尝试插入到尾部（R）
q.push_back(nums[idx]);
path.push_back('R');
dfs(idx + 1, q, path);
path.pop_back();
q.pop_back();
};
deque<int> q;
string path = "";
dfs(0, q, path);
cout << maxLIS << endl;
cout << bestSolution << endl;
return 0;
}
7-3 账户安全预警
分数 25
作者 陈越
单位 浙江大学
拼题 A 系统为提高用户账户的安全性，打算开发一个自动安全预警的功能。对每个账户的每次登录，系统会记录其登录的 IP 地址。每隔一段时间，系统将统计每个账户从多少不同的 IP 地址分别登录了多少次。如果某个账户的登录 IP 超过了 TIP 种，并且登录过于频繁，超过了 Tlogin 次，则会自动向管理员发出警报。
下面就请你实现这个预警功能。
输入格式：
输入首先在第一行中给出三个正整数：N（≤104）为登录记录的条数；TIP 和
Tlogin，定义如题面中所描述，均不超过 100。
随后 N 行，每行格式为：
账户邮箱 IP地址
其中 账户邮箱 为长度不超过 40 的、不包含空格的非空字符串；IP地址 为形如 xxx.xxx.xxx.xxx 的合法 IP 地址。
输出格式：
按照登录所用不同 IP 的数量的非递增顺序，输出每个预警账户的信息。格式为：
账户邮箱
IP1 登录次数
IP2 登录次数
……
其中 IP 按登录次数的非递增顺序输出，如有并列，则按 IP 的递增字典序输出。此外，对所用不同 IP 的数量并列的用户，按其账户邮箱的递增字典序输出。
另一方面，即使没有账户达到预警线，也输出登录所用不同 IP 的数量最多的一批账户的信息。
输入样例 1：
24 3 4
daohaole@qq.com 218.109.231.189
1jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 113.18.235.143
jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 218.109.231.189
chenyuelaolao@zju.edu.cn 111.18.235.143
1jiadelaolao@163.com 115.192.203.187
daohaole@qq.com 113.189.58.141
1jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 112.18.58.145
1jiadelaolao@163.com 114.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
daohaole@qq.com 123.89.158.214
chenyuelaolao@zju.edu.cn 112.18.235.143
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 114.192.203.187
youdaohaole@qq.com 113.189.58.141
youdaohaole@qq.com 123.89.158.214
1jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 112.18.58.145
输出样例 1：
1jiadelaolao@163.com
111.192.203.187 1
112.192.203.187 1
113.192.203.187 1
114.192.203.187 1
115.192.203.187 1
daohaole@qq.com
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1
youdaohaole@qq.com
218.109.231.189 2
112.18.58.145 1
113.189.58.141 1
123.89.158.214 1
输入样例 2：
24 5 8
daohaole@qq.com 218.109.231.189
1jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
jiadelaolao@163.com 112.192.203.187
chenyuelaolao@zju.edu.cn 113.18.235.143
jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 218.109.231.189
chenyuelaolao@zju.edu.cn 111.18.235.143
1jiadelaolao@163.com 115.192.203.187
daohaole@qq.com 113.189.58.141
1jiadelaolao@163.com 111.192.203.187
daohaole@qq.com 112.18.58.145
1jiadelaolao@163.com 114.192.203.187
chenyuelaolao@zju.edu.cn 112.18.235.143
daohaole@qq.com 123.89.158.214
chenyuelaolao@zju.edu.cn 112.18.235.143
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 218.109.231.189
jiadelaolao@163.com 114.192.203.187
youdaohaole@qq.com 113.189.58.141
youdaohaole@qq.com 123.89.158.214
1jiadelaolao@163.com 113.192.203.187
youdaohaole@qq.com 112.18.58.145
输出样例 2：
1jiadelaolao@163.com
111.192.203.187 1
112.192.203.187 1
113.192.203.187 1
114.192.203.187 1
115.192.203.187 1
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, T_IP, T_login;
cin >> N >> T_IP >> T_login;
// 统计
map<string, map<string,int>> cnt; // cnt[email][ip] = 次数
map<string,int> totlogin; // totlogin[email]
for (int i = 0; i < N; i++) {
string email, ip;
cin >> email >> ip;
cnt[email][ip]++;
totlogin[email]++;
}
// 计算不同IP数
map<string,int> ipnum;
for (auto &p : cnt) {
ipnum[p.first] = p.second.size();
}
// 筛预警：ipnum > T_IP 且 totlogin > T_login
vector<string> warns;
for (auto &p : ipnum) {
const string &email = p.first;
if (p.second > T_IP && totlogin[email] > T_login) {
warns.push_back(email);
}
}
// 如果没人预警，就找 ipnum 最大的一批
if (warns.empty()) {
int mx = 0;
for (auto &p : ipnum) {
mx = max(mx, p.second);
}
for (auto &p : ipnum) {
if (p.second == mx) warns.push_back(p.first);
}
}
// 排序账号：ipnum降序，email升序
sort(warns.begin(), warns.end(), [&](const string &a, const string &b){
if (ipnum[a] != ipnum[b]) return ipnum[a] > ipnum[b];
return a < b;
});
// 输出
for (auto &email : warns) {
cout << email << "\n";
// 收集该用户所有 (ip,次数)
vector<pair<string,int>> vip;
for (auto &q : cnt[email]) {
vip.emplace_back(q.first, q.second);
}
// 排序：次数降序，ip升序
sort(vip.begin(), vip.end(), [&](auto &x, auto &y){
if (x.second != y.second) return x.second > y.second;
return x.first < y.first;
});
// 打印
for (auto &pr : vip) {
cout << pr.first << " " << pr.second << "\n";
}
}
return 0;
}
7-4 猛犸不上 Ban
分数 30
作者 DAI, Longao
单位 杭州百腾教育科技有限公司
在一个名叫刀塔的国家里，有一只猛犸正在到处跑着，希望能够用它的长角抛物技能来撞飞别人。已知刀塔国有 N 座城市，城市之间由 M 条道路互相连接，为了拦住这头猛犸，每条道路上设置了 Vi 人的团队。
这只猛犸从 S 号城市出发，它可以选择：
- 在不重复地经过若干条道路后回到 S 号城市；
- 在不重复地经过若干条道路后到达 T 号城市。
猛犸经过一条道路后，就会把路上的人全部撞飞。作为一头爱喝雪碧的仁慈的猛犸，自然希望尽可能的少撞飞人。请你帮忙计算一下在最优的选择下，最少需要撞飞多少人才能够到达目标城市？
输入格式:
输入第一行是四个正整数 N,M,S,T (2≤N≤500,1≤M≤105)，表示有 N 个城市，M 条道路，猛犸从 S 号城市出发，可以选择到达 T 号城市。
接下来的 M 行，每行三个正整数 Xi,Yi,Vi (0≤Vi≤100)，表示从 Xi 号城市到 Yi 号城市有一条道路，道路上有 Vi 人的团队。道路可双向通行，城市编号从 1 开始，两个城市之间最多只有一条道路，且没有一条道路连接相同的城市。
数据保证两种选择里至少有一种是可行的。
输出格式:
输出两行，第一行是两个数字，分别对应上面的两种选择分别最少需要撞飞多少人。如果无论撞飞多少人都无法满足选择要求，则输出 -1。
第二行是一个句子，如果第一种（回到原点）的选择比较好，就输出 Win!，否则输出Lose!。
输入样例:
5 6 1 5
1 2 1
2 3 2
3 4 3
4 1 5
3 5 4
4 5 1
输出样例:
在这里给出相应的输出。例如：
11 6
Lose!
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, S, T;
cin >> N >> M >> S >> T;
// 建图（无向）
vector<vector<pair<int,int>>> adj(N+1);
for(int i = 0; i < M; i++){
int x, y, v;
cin >> x >> y >> v;
adj[x].push_back({y,v});
adj[y].push_back({x,v});
}
// 1) Dijkstra 求 S->T 最短
auto dijkstra = [&](int src, int ban_u, int ban_v){
// ban_u, ban_v: 若同 (u,v) 或 (v,u) 则跳过那条边
vector<ll> dist(N+1, INF);
using pli = pair<ll,int>;
priority_queue<pli, vector<pli>, greater<pli>> pq;
dist[src] = 0;
pq.push({0, src});
while(!pq.empty()){
auto [d,u] = pq.top(); pq.pop();
if(d > dist[u]) continue;
for(auto &ed: adj[u]){
int v = ed.first, w = ed.second;
// 如果是要“移除”的那条边，就跳过
if( (u==ban_u && v==ban_v) || (u==ban_v && v==ban_u) )
continue;
if(dist[v] > d + w){
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}
return dist;
};
// 求 S->T
ll best_ST = INF;
{
auto dist = dijkstra(S, -1, -1);
best_ST = dist[T];
}
// 2) 求最小回路：枚举 (S,u) 邻边，移除它后算 S->u
ll best_cycle = INF;
for(auto &ed : adj[S]){
int u = ed.first, w = ed.second;
// 在 Dijkstra 中 ban 这条边
auto dist = dijkstra(S, S, u);
if(dist[u] < INF){
best_cycle = min(best_cycle, dist[u] + w);
}
}
// 输出结果
if(best_cycle >= INF) cout << -1;
else cout << best_cycle;
cout << " ";
if(best_ST >= INF) cout << -1;
else cout << best_ST;
cout << "\n";
// 比较 Win / Lose
// 注意：若某项为 -1（INF），则看另一项是否也是 -1，题目保证至少一种可行
if(best_cycle <= best_ST) cout << "Win!";
else cout << "Lose!";
cout << "\n";
return 0;
}
DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。
更多推荐
17
0- 0
已为社区贡献2条内容
所有评论(0)