目录
RC-v1 智能管家
人上了年纪，记性就会变差，时常不得不翻箱倒柜找东西。智能照护中心现在请你做一个简单的智能管家程序，把老人家里的东西逐一编号，放进若干个收纳箱里。当然收纳箱也是有编号的，你的程序要记录下哪个东西放在哪个收纳箱里。当老人问起某几件东西时，你的程序要告诉老人家，东西分别放在哪些箱子里。
输入格式：
输入在第一行中给出 2 个正整数：N（≤105）是老人家藏物品的数量（所有物品从 1 到 N 编号）；M（≤104 且 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
提示:
编译器 Java (javac) Java (javac) 其他编译器 其他编译器 代码长度限制 时间限制 内存限制 时间限制 内存限制 16 KB 1800 ms 512 MB 400 ms 64 MB
代码思路:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main{
// 优化输入输出速度
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] strings = br.readLine().split(" ");
// N是物品的数量(物品从1到N编号)
int N = Integer.parseInt(strings[0]);
// M是收纳箱的数量(收纳箱从1到M编号)
int M = Integer.parseInt(strings[1]);
// 第几个数字就是编号为几的物品所存放的收纳箱的编号.数组arraysN是用来录入收纳箱的编号的,而数组索引与第几个数字意义一样.
int arraysN[] = new int[N + 1];
// 记录每个收纳箱里有几件查询的物品
int arraysM[] = new int[M + 1];
// 录入每件物品收纳箱的编号(第几个数字就是编号为几的物品所存放的收纳箱的编号)
strings = br.readLine().split(" ");
for (int i = 1; i < arraysN.length; i++) {
arraysN[i] = Integer.parseInt(strings[i - 1]);
}
int K = Integer.parseInt(br.readLine());
// 字符串相加太耗时间,使用StringBuilder提高代码效率.
StringBuilder sb = new StringBuilder();
while (K-- > 0) {
strings = br.readLine().split(" ");
// 记录被查的物品在哪个收纳箱里并且有几个被查的物品.
for (int i = 0; i < strings.length - 1; i++) {
// arraysM是记录每个抽屉里有几件查询的物品
// arraysN[i]是收纳箱的编号
// i是要查找的物品的编号
// 被查询的物品对应的箱子数量加1
int temp = Integer.parseInt(strings[i]);
arraysM[arraysN[temp]]++;
}
for (int i = 1; i < arraysM.length; i++) {
int temp = arraysM[i];
if (temp == 0) {
continue;
}
sb.append("B");
sb.append(i);
sb.append("-");
sb.append(temp);
sb.append(" ");
// 清除已经使用过的值,防止下一行查询报错.
arraysM[i] = 0;
}
sb.deleteCharAt(sb.length() - 1);
// 每行查询后换行,满足题目要求
sb.append("\n");
}
out.print(sb);
out.flush();
out.close();
}
}
RC-v2 智能陪护
智能陪护系统是一个自动为老人们分配机器人护工的系统。系统中有若干个机器人排队候选，当有老人下单时，系统自动将队列最前面的机器人派送给老人，该机器人就在老人下单的当天上岗了。当老人结算时，这个机器人就立刻结束任务，回到队列末尾排队等待下一次任务，必要时可以在当天就开始接任务。
本题就请你实现这样一个自动分配功能。
注意：如果同一天有多位老人下单或结算，保证先处理结算的，使得机器人能及时回到队列；然后处理下单——系统中另有一个下单队列，下单的老人们按照处理的顺序排队；最后分配，按下单队列中排队的顺序将机器人护工分配给老人们。
对于同时下达相同指令的，则按照老人ID的升序排队处理。如果系统中没有机器人护工了，则排队的老人们需要在下单队列中等待。
输入格式：
输入在第一行中给出 2 个正整数：N（≤104）是机器人护工的数量—— 这里假设所有机器人护工从 1 到 N 编号，且一开始按照编号升序在系统队列中排队；K（≤105）是系统订单信息的条数。随后 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
提示:
编译器 Java (javac) Java (javac) 其他编译器 其他编译器 代码长度限制 时间限制 内存限制 时间限制 内存限制 16 KB 1100 ms 512 MB 400 ms 64 MB
代码思路:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class Main{
// 优化输入输出速度
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
// readLine()是获取一行数据,split(" ")是以(" ")为条件分割获取的一行数据.提高获取数据的速度.
String strings[] = br.readLine().split(" ");
// 机器人护工的数量
int N = Integer.parseInt(strings[0]);
// 系统订单信息的条数
int K = Integer.parseInt(strings[1]);
Instruct instruct[] = new Instruct[K];
for (int i = 0; i < K; i++) {
strings = br.readLine().split(" ");
instruct[i] = new Instruct(strings[0], strings[1], strings[2]);
}
// 将instruct数组按照题目要求排序,排序条件如下:
// 1.下单和结算时间不一样,则按照时间从小到大排;
// 2.下单和结算时间一样,但下单和结算不一样,结算排在前面;
// 3.下单和结算时间一样,但下单和结算一样,则按照老人ID的升序排队处理.
Arrays.sort(instruct, new Comparator<Instruct>() {
@Override
public int compare(Instruct o1, Instruct o2) {
if (o1.date.equals(o2.date)) {
if (o1.inst.equals(o2.inst)) {
return o1.ID.compareTo(o2.ID);
} else {
return o1.inst.compareTo(o2.inst);
}
} else {
return o1.date.compareTo(o2.date);
}
}
});
// 机器人护工队列.
Queue<Integer> robot = new LinkedList<Integer>();
for (int i = 1; i <= N; i++) {
robot.add(i);
}
// 等待老年人队列
Queue<String> wait = new LinkedList<String>();
// 老年人与护工映射
Map<String, Integer> map = new HashMap<String, Integer>();
// 存储输出信息
StringBuilder sb = new StringBuilder();
for (int i = 0; i < instruct.length; i++) {
String ID = instruct[i].ID;
// 下单操作.
if (instruct[i].inst.equals("1")) {
if (robot.size() != 0) {
Integer robotp = robot.poll();
map.put(ID, robotp);
sb.append(ID);
sb.append(" - ");
sb.append(robotp);
sb.append("\n");
} else {
// 将老人放入等待队列中,等待有服务机器人.
wait.add(ID);
}
} // 结算操作.
else {
if (map.containsKey(ID)) {
// 查看等待队列里有无等待的老人,无等待的老人机器人护工回队列.
if (wait.size() != 0) {
String waitp = wait.poll();
map.put(waitp, map.get(ID));
sb.append(waitp);
sb.append(" - ");
sb.append(map.get(ID));
sb.append("\n");
} else {
robot.add(map.get(ID));
}
} else {
wait.remove(ID);
sb.append(ID);
sb.append(" - NONE\n");
}
}
}
sb.append(robot.poll());
while (!robot.isEmpty()) {
sb.append(" ");
sb.append(robot.poll());
}
out.print(sb);
out.flush();
out.close();
}
}
class Instruct {
String ID;
String inst;
String date;
public Instruct(String ID, String inst, String date) {
super();
this.ID = ID;
this.inst = inst;
this.date = date;
}
}
RC-v3 智能护理中心统计
智能护理中心系统将辖下的护理点分属若干个大区，例如华东区、华北区等；每个大区又分若干个省来进行管理；省又分市，等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责，每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能，来统计任何一个管理结点所负责照看的老人的数量。
注意这是一个动态问题，即随时可能有老人加入某个管理结点，并且老人是有可能从一个管理结点换到另一个管理结点去的。
输入格式：
输入在第一行中给出 2 个正整数：N（≤104）是老人的总数量，即老人们从 1 到 N 编号；M（≤105）是归属关系的总数。
接下来是 M 行，每行给出一对归属关系，格式为：
A B
表示 A 归属于 B。A 或 B 如果是某个管理结点，则用不超过 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
提示:
编译器 Java (javac) Java (javac) 其他编译器 其他编译器 代码长度限制 时间限制 内存限制 时间限制 内存限制 16 KB 2500 ms 512 MB 2500ms 64 MB
代码思路:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
public class Main{
// 输入输出优化
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
// 管理节点
static Map<String, ArrayList<String>> node = new HashMap<String, ArrayList<String>>();
// 管理老人
static Map<String, ArrayList<String>> oldies = new HashMap<String, ArrayList<String>>();
// 管理老人上级
static Map<String, String> oldie = new HashMap<String, String>();
public static void main(String[] args) throws IOException {
String strings[] = br.readLine().split(" ");
int N = Integer.parseInt(strings[0]);
int M = Integer.parseInt(strings[1]);
StringBuilder sb = new StringBuilder();
while (M-- > 0) {
strings = br.readLine().split(" ");
char temp = strings[0].charAt(0);
if (temp >= 'A' && temp <= 'Z') {
if (!node.containsKey(strings[1])) {
node.put(strings[1], new ArrayList<String>());
}
node.get(strings[1]).add(strings[0]);
} else {
if (!oldies.containsKey(strings[1])) {
oldies.put(strings[1], new ArrayList<String>());
}
oldies.get(strings[1]).add(strings[0]);
oldie.put(strings[0], strings[1]);
}
}
while (true) {
strings = br.readLine().split(" ");
if (strings[0].equals("T")) {
// strings[1]表示老人编号 strings[0]表示要去的管理结点
// 老人要入院或转院
if (oldies.containsKey(oldie.get(strings[1]))) {
oldies.get(oldie.get(strings[1])).remove(strings[1]);
}
if (!oldies.containsKey(strings[2])) {
oldies.put(strings[2], new ArrayList<String>());
}
oldies.get(strings[2]).add(strings[1]);
oldie.put(strings[1], strings[2]);
} else if (strings[0].equals("Q")) {
sb.append(getsum(strings[1]));
sb.append("\n");
} else {
break;
}
}
out.print(sb);
out.flush();
out.close();
}
static int getsum(String string) {
Queue<String> queue = new LinkedList<String>();
queue.add(string);
int num = 0;
if (oldies.containsKey(string)) {
num = oldies.get(string).size();
}
while (!queue.isEmpty()) {
String temp = queue.poll();
if (!node.containsKey(temp)) {
continue;
}
for (String string1 : node.get(temp)) {
queue.add(string1);
if (oldies.containsKey(string1)) {
num += oldies.get(string1).size();
}
}
}
return num;
}
}
RC-v4 情人节的蜜语
不懂浪漫的程序员在情人节这天给心上人送了一支玫瑰，外加一张字条，是这样写的：
WveAitS
oDGWHJh
MLNeZTY
PKeRrQA
BXFuICV
这是什么意思呢？作为程序员的情人，你得聪明到可以看懂，这个字条里藏了这么一条信息：WithTrueLove。用 . 替换掉所有无关的字母后，真正的字条其实是这样的：
.ve.it.
o..W..h
.L...T.
..e.r..
...u...
即从 W 开始，每步向该字母周围的 8 个方向之一移动，到下一个字母，如此可以串出目标句子。
如果有个疯狂的程序员做了一张巨大的纸条（应该是大字报了，不是纸条了），让你猜里面藏了什么甜言蜜语，你就只好写个程序来猜了……
输入格式：
输入首先在第一行给出 2 个正整数 m 和 n，均不超过 100，分别为字符的行数和列数。随后给出 m 行，每行 n 个英文字母，为纸条的内容。
接下来一行给出一个仅由英文字母组成的、长度不超过 20 的字符串，是你猜测的句子。
输出格式：
按照 m 行 n 列的格式，输出用 . 替换掉所有无关的字母后，纸条的内容。
注意匹配时大小写要区分，纸条上的每个字母最多只能匹配一次。题目保证能匹配到唯一解。
输入样例：
5 7
WveAitS
oDGWHJh
MLNeZTY
PKeRrQA
BXFuICV
WithTrueLove
输出样例：
.ve.it.
o..W..h
.L...T.
..e.r..
...u...
提示:
编译器 Java (javac) Java (javac) 其他编译器 其他编译器 代码长度限制 时间限制 内存限制 时间限制 内存限制 16 KB 400 ms 512 MB 400ms 64MB
代码思路:
import java.util.Arrays;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
static int m;
static int n;
static int fx[][] = { { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { -1, 0 } };
static char ch[][];
static char ch1[][];
static boolean bu;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StringBuilder str11 = new StringBuilder();
static int leng;
public static void main(String[] args) throws IOException {
String[] lineArr = br.readLine().split(" ");
m = Integer.parseInt(lineArr[0]);
n = Integer.parseInt(lineArr[1]);
ch = new char[m][n];
ch1 = new char[m][n];
for (int i = 0; i < m; i++) {
ch[i] = br.readLine().toCharArray();
Arrays.fill(ch1[i], '.');
}
String string = br.readLine();
leng = string.length();
for (int i = 0; i < m; i++) {
if (bu) {
break;
}
for (int j = 0; j < n; j++) {
if (bu) {
break;
}
if (ch[i][j] == string.charAt(0)) {
dfs(i + 1, j, string, 0);
}
}
}
out.print(str11);
out.flush();
out.close();
}
static void dfs(int i, int j, String string, int n1) {
if (n1 == leng) {
bu = true;
for (int ai = 0; ai < m; ai++) {
for (int aj = 0; aj < n; aj++) {
str11.append(ch1[ai][aj]);
}
str11.append('\n');
}
return;
}
for (int k = 0; k < 8; k++) {
int i1 = i + fx[k][0];
int j1 = j + fx[k][1];
if (i1 >= 0 & i1 < m & j1 >= 0 & j1 < n && ch[i1][j1] == string.charAt(n1) && ch1[i1][j1] == '.') {
ch1[i1][j1] = ch[i1][j1];
dfs(i1, j1, string, n1 + 1);
if (bu) {
return;
}
ch1[i1][j1] = '.';
}
}
}
}
