侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 22 条评论

目 录CONTENT

文章目录

【算法竞赛】2022 RoboCom 世界机器人开发者大赛-高职组(国赛)

GabrielxD
2023-07-08 / 1 评论 / 0 点赞 / 390 阅读 / 3,518 字
温馨提示:
本文最后更新于 2023-07-08,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

RC-v1 智能管家

人上了年纪,记性就会变差,时常不得不翻箱倒柜找东西。智能照护中心现在请你做一个简单的智能管家程序,把老人家里的东西逐一编号,放进若干个收纳箱里。当然收纳箱也是有编号的,你的程序要记录下哪个东西放在哪个收纳箱里。当老人问起某几件东西时,你的程序要告诉老人家,东西分别放在哪些箱子里。

输入格式:

输入在第一行中给出 2 个正整数:N(≤10^5)是老人家藏物品的数量(所有物品从 1 到 N 编号);M(≤10^4 且 M<N)是收纳箱的数量(所有收纳箱从 1 到 M 编号)。随后一行给出 N 个正整数,第 i 个数字就是编号为 i 的物品所存放的收纳箱的编号。

接下来是老人的查询数据:首先在一行中给出正整数 K(≤100),为查询次数;随后 K 行,每行给出一系列要查找的物品的编号,以 0 结尾(这个数字不要处理)。

题目保证每行中的查询编号都无重复,每次至少查询一件物品,并且同一行的数字间以空格分隔。

输出格式:

对每一次查询,在一行中按照收纳箱编号的升序输出存放了被查物品的收纳箱,并且同时输出该箱内有多少件被查的物品。输出格式为 Bi-k,其中 i 是箱子编号,k 是物品个数。两只箱子的信息间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

10 5
3 4 4 1 1 5 3 3 3 4
2
8 1 2 5 0
6 0

输出样例:

B1-1 B3-2 B4-1
B5-1

解题:模拟 哈希表

思路

模拟。

代码
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 1e4 + 10;
int n, m, k;
int boxes[N];
int cnts[M];
set<int> st;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &boxes[i]);
    scanf("%d", &k);
    while (k--) {
        memset(cnts, 0, sizeof(cnts));
        st.clear();
        int x;
        while (~scanf("%d", &x) && x) {
            st.insert(boxes[x]);
            ++cnts[boxes[x]];
        }
        int cnt = 0;
        for (auto& y : st) {
            printf("B%d-%d", y, cnts[y]);
            printf(++cnt == st.size() ? "\n" : " ");
        }
    }

    return 0;
}

RC-v2 智能陪护

智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选,当有老人下单时,系统自动将队列最前面的机器人派送给老人,该机器人就在老人下单的当天上岗了。当老人结算时,这个机器人就立刻结束任务,回到队列末尾排队等待下一次任务,必要时可以在当天就开始接任务。

本题就请你实现这样一个自动分配功能。

注意:如果同一天有多位老人下单或结算,保证先处理结算的,使得机器人能及时回到队列;然后处理下单——系统中另有一个下单队列,下单的老人们按照处理的顺序排队;最后分配,按下单队列中排队的顺序将机器人护工分配给老人们。

对于同时下达相同指令的,则按照老人ID的升序排队处理。如果系统中没有机器人护工了,则排队的老人们需要在下单队列中等待。

输入格式:

输入在第一行中给出 2 个正整数:N(≤10^4)是机器人护工的数量—— 这里假设所有机器人护工从 1 到 N 编号,且一开始按照编号升序在系统队列中排队;K(≤10^5)是系统订单信息的条数。随后 K 行,每行给出一条订单信息,格式为:

老人ID 指令 日期

其中 老人ID 是一个长度不超过 5 的字符串,由英文小写字母和数字组成;指令 为 1 表示下单,为 0 表示结算;日期 是按照 年年年年月月日日 格式给出的,保证是一个 2022 年 1 月 1 日到 3022 年 12 月 31 日 之间的合法日期。

题目保证所有数据合理,即对每位老人,结算一定发生在下单之后,结算了一单才允许下另一单,且不存在只有下单没有结算、或只有结算没有下单的数据。

输出格式:

按照下单的时间顺序,输出机器人护工的分配信息,每行输出一条,格式为:

老人ID - 机器人护工编号

如果到老人结算时,都没有等到一位护工,则对应输出

老人ID - NONE

最后在一行中顺序输出队列中的机器人护工的编号。要求数字间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

3 10
a01 0 20220202
a04 1 20220103
a02 1 20220101
a05 0 20220202
a03 1 20220101
a03 0 20220202
a04 0 20220201
a02 0 20220102
a05 1 20220101
a01 1 20220101

输出样例:

a01 - 1
a02 - 2
a03 - 3
a05 - 2
a04 - NONE
1 3 2

解题:队列 模拟

思路

开俩队列,按题目模拟即可。

代码
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int K = 1e5 + 10;
int n, k;
queue<int> que;
struct Order {
    string name;
    int type, dt;

    bool operator<(const Order& o) const {
        if (dt != o.dt) return dt < o.dt;
        if (type != o.type) return type < o.type;
        return name < o.name;
    }

    friend ostream& operator<<(ostream& out, const Order& o) {
        out << o.name << " " << o.type << " " << o.dt;
        return out;
    }
} orders[K];
unordered_map<string, int> mp;
queue<Order> wt_que;
unordered_map<string, bool> waiting;

int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    return 0;
}();

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) que.push(i);
    for (int i = 0; i < k; ++i) {
        cin >> orders[i].name >> orders[i].type >> orders[i].dt;
    }
    sort(orders, orders + k);
    for (int i = 0; i < k; ++i) {
        const Order& u = orders[i];
        // cout << u << "\n";
        if (u.type) {
            if (!que.empty()) {
                mp[u.name] = que.front();
                cout << u.name << " - " << que.front() << '\n';
                que.pop();
            } else {
                wt_que.push(u);
                waiting[u.name] = true;
            }
        } else {
            if (mp.find(u.name) != mp.end()) {
                while (!wt_que.empty() && !waiting[wt_que.front().name]) wt_que.pop();
                if (!wt_que.empty()) {
                    const Order& v = wt_que.front(); wt_que.pop();
                    mp[v.name] = mp[u.name];
                    cout << v.name << " - " << mp[u.name] << '\n';
                } else que.push(mp[u.name]);
                mp.erase(u.name);
            } else {
                cout << u.name << " - NONE\n";
                waiting[u.name] = false;
            }
        }
    }
    while (!que.empty()) {
        cout << que.front(); que.pop();
        cout << (que.empty() ? "\n" : " ");
    }


    return 0;
}

RC-v3 智能护理中心统计

智能护理中心系统将辖下的护理点分属若干个大区,例如华东区、华北区等;每个大区又分若干个省来进行管理;省又分市,等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责,每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能,来统计任何一个管理结点所负责照看的老人的数量。

注意这是一个动态问题,即随时可能有老人加入某个管理结点,并且老人是有可能从一个管理结点换到另一个管理结点去的。

输入格式:

输入在第一行中给出 2 个正整数:N(≤10^4)是老人的总数量,即老人们从 1 到 N 编号;M(≤10^5)是归属关系的总数。

接下来是 M 行,每行给出一对归属关系,格式为:

A B

表示 A 归属于 BAB 如果是某个管理结点,则用不超过 4 个大写英文字母表示其名称;如果是某位老人,则用老人的编号表示。这里每个 A 保证只有唯一的上级归属 B,且只有这个中心系统本身是没有上级归属的。此外,输入保证没有老人自己承担管理结点的角色,即 B 一定是一个管理结点,不可能是老人的编号。但一个管理结点既可以管辖下级结点,也可以直接护理一部分老人。

随后每行给出一个指令,格式为:

指令 内容

如果 指令T,则表示有老人要入院或转院,内容 是某老人的编号和要去的管理结点的名称,以空格分隔;如果 指令Q,则 内容 是一个管理结点的名称,意思是统计这个结点所负责照看的老人的数量;如果 指令E,则表示输入结束。题目保证指令总数不会超过 100 个。

输出格式:

对每个 T 指令,将对应的老人转存到对应的管理结点名下;对每个 Q 指令,在一行中输出对应管理结点所负责照看的老人的数量。读到 E 指令就结束程序。

输入样例:

10 23
EAST CNTR
ZJ EAST
SD EAST
WEST CNTR
SX WEST
HZ ZJ
JN SD
2 JN
8 JTH
6 XAHP
4 ZDYH
5 ZDYH
ZDYH HZ
HUZ ZJ
JX ZJ
1 JX
3 JN
WZ ZJ
XAHP XIAN
XIAN SX
YL SX
JTH XIAN
7 XAHP
Q EAST
T 1 YL
Q EAST
Q SX
T 8 ZDYH
Q HZ
Q HUZ
T 10 XAHP
Q CNTR
E

输出样例:

5
4
4
3
0
9

解题:DFS

思路

建树+DFS。

代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 1e4 + 10, M = 2e5;
int n, m;
int fa[M], cnts[M];
int cnt;
unordered_map<string, int> mp;

int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    return 0;
}();

void modify(int u, int x) {
    u = fa[u];
    while (u) {
        cnts[u] += x;
        u = fa[u];
    }
}

int main() {
    cin >> n >> m;
    cnt = n;
    string a, b;
    int xa, xb;
    while (m--) {
        cin >> a >> b;
        if (mp.find(b) == mp.end()) xb = mp[b] = ++cnt;
        else xb = mp[b];
        if (a[0] >= '0' && a[0] <= '9') xa = stoi(a);
        else {
            if (mp.find(a) == mp.end()) xa = mp[a] = ++cnt;
            else xa = mp[a];
        }
        fa[xa] = xb;
    }
    for (int u = 1; u <= n; ++u) modify(u, 1);
    char op;
    while ((cin >> op) && op != 'E') {
        if (op == 'Q') {
            cin >> b;
            cout << cnts[mp[b]] << '\n';
        } else {
            cin >> xa >> b;
            modify(xa, -1);
            fa[xa] = mp[b];
            modify(xa, 1);
        }
    }

    return 0;
}

RC-v4 情人节的蜜语

不懂浪漫的程序员在情人节这天给心上人送了一支玫瑰,外加一张字条,是这样写的:

WveAitS
oDGWHJh
MLNeZTY
PKeRrQA
BXFuICV

这是什么意思呢?作为程序员的情人,你得聪明到可以看懂,这个字条里藏了这么一条信息:WithTrueLove。用 . 替换掉所有无关的字母后,真正的字条其实是这样的:

.ve.it.
o..W..h
.L...T.
..e.r..
...u...

即从 W 开始,每步向该字母周围的 8 个方向之一移动,到下一个字母,如此可以串出目标句子。

如果有个疯狂的程序员做了一张巨大的纸条(应该是大字报了,不是纸条了),让你猜里面藏了什么甜言蜜语,你就只好写个程序来猜了……

输入格式:

输入首先在第一行给出 2 个正整数 mn,均不超过 100,分别为字符的行数和列数。随后给出 m 行,每行 n 个英文字母,为纸条的内容。

接下来一行给出一个仅由英文字母组成的、长度不超过 20 的字符串,是你猜测的句子。

输出格式:

按照 mn 列的格式,输出用 . 替换掉所有无关的字母后,纸条的内容。

注意匹配时大小写要区分,纸条上的每个字母最多只能匹配一次。题目保证能匹配到唯一解。

输入样例:

5 7
WveAitS
oDGWHJh
MLNeZTY
PKeRrQA
BXFuICV
WithTrueLove

输出样例:

.ve.it.
o..W..h
.L...T.
..e.r..
...u...

解题:DFS

思路

测试点3 TLE 了。

代码
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 110, DIRS[][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int n, m, len;
char g[N][N];
char s[25];
bool vis[N][N];

bool dfs(int x, int y, int u) {
    if (u == len - 1) return true;
    for (auto& DIR : DIRS) {
        int nx = x + DIR[0], ny = y + DIR[1];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || g[nx][ny] != s[u + 1]) continue;
        vis[nx][ny] = true;
        if (dfs(nx, ny, u + 1)) return true;
        vis[nx][ny] = false;
    }
    return false;
}

int main() {
    scanf("%d%d\n", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%s", g[i]);
    scanf("%s", s);
    len = strlen(s);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == s[0]) {
                vis[i][j] = true;
                if (dfs(i, j, 0)) {
                    for (int x = 0; x < n; ++x) {
                        for (int y = 0; y < m; ++y) {
                            printf("%c", vis[x][y] ? g[x][y] : '.');
                        }
                        puts("");
                    }
                    return 0;
                }
                vis[i][j] = false;
            }
        }
    }

    return 0;
}
0

评论区