7-1 小偷踩点
俗话说不怕贼偷，就怕贼惦记。
小偷在作案前有时会在居民家的门、墙上做一些标记，每一种记号代表一个含义，一般人看不懂，但同行一看便知道这个家庭的情况。不过派出所干警也不是吃素的，很快破译了这些记号的含义（如上图），并且在辖区内广为张贴，告知居民。
随后小偷们又改变了方法，将这些记号从 1 到 N 编号，然后将这些编号按照某种规则重新打乱再做标记，标记变成了一串数字。不过这种新的编号方法又被破译了！干警们发现这些数字的规律可以用一个二维矩阵来表示：矩阵有 10 列，顺序对应数字 0 到 9；矩阵一般不超过 10 行，每行对应一个 0 到 9 之间的数字，这些数字保证不重复。小偷的新标记由若干个两位数组成，每个数字的十位对应行、个位对应列，而对应位置上的数字就是原始标记的编号。
如上图 40 种标记从上到下、从左到右顺序编号后，按下图所示的规律打乱，则如果我们看到标记“71”，就是行标记为 7，列标记为 1 的单元格对应的数字 11，对应原始标记中第 11 个，即“很有钱”。那么标记“71 78 57”就表示原始标记的第 11、8、7 号，意思是“很有钱”、“没有防范”、“计划行动”。
本题就请你编写程序，自动破译小偷的新标记。
输入格式：
输入第一行给出 2 个正整数：N（≤100）为小偷的原始标记个数，M（≤10）为新标记对照矩阵的行数。
随后 N 行，第 i 行给出第 i 个标记的解释，由不超过 100 个英文字母和空格组成。
接下来一行给出 M 个数字，为 0 到 9 之间的数字，保证不重复，其中第 i 个数对应矩阵第 i 行。
接下来 M 行，每行给出 10 个数字，或者是 1 到 N 之间的一个编号，或者是 −1 表示没有对应的编号。
最后一行给出小偷留在墙上的数字标记，格式为：
k t[1] ... t[k]
其中 k 是数字个数（不超过 N），后面跟着 k 个数字。
输出格式：
对小偷留下的每个数字，在一行中输出其对应的意义，顺序与输入顺序相同。如果没有对应的意义，则在对应行中输出 ?。
输入样例：
10 2
jia li you ren
kong fang zi
jia you e gou
dan shen
hen you qian
xiao xin lin ju
you bao jing qi
jin kuai dong shou
xia ci zai lai
bu bi jin ru
6 2
-1 6 5 1 -1 10 3 4 -1 9
2 4 7 -1 3 -1 5 -1 8 2
5 20 64 61 22 13
输出样例：
kong fang zi
?
xiao xin lin ju
you bao jing qi
?
解题：模拟 哈希表
思路
把对应数据输入数组和二维数组中后通过哈希表建立关系然后查找。注意如果二维数组开的比较大，要把所有元素初始化为 0，然后在最后做判断哪些是没有数据的。
代码
代码1
#include <iostream>
#include <limits>
using namespace std;
int main() {
int N, M, mat[10][10] = {0};
scanf("%d%d", &N, &M);
cin.ignore(numeric_limits<streamsize>::max(), '\n');
string marks[N + 1];
for (int i = 1; i <= N; ++i) getline(cin, marks[i]);
int row_nums[M];
for (int i = 0; i < M; ++i) scanf("%d", &row_nums[i]);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < 10; ++j) {
scanf("%d", &mat[row_nums[i]][j]);
}
}
int k;
scanf("%d", &k);
int num, idx;
while (k--) {
scanf("%d", &num);
idx = mat[num / 10][num % 10];
if (idx <= 0) printf("?\n");
else printf("%s\n", marks[idx].c_str());
}
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(Reader.next());
int M = Integer.parseInt(Reader.next());
String[] marks = new String[N + 1];
for (int i = 1; i <= N; i++) marks[i] = Reader.nextLine();
int[] rows = new int[M];
for (int i = 0; i < M; i++) rows[i] = Integer.parseInt(Reader.next());
int[][] map = new int[10][10];
for (int row : rows) {
for (int i = 0; i < 10; i++) {
map[row][i] = Integer.parseInt(Reader.next());
}
}
int k = Integer.parseInt(Reader.next());
while (k-- > 0) {
// 取字符的方式会出错
// String numStr = Reader.next();
// int r = numStr.charAt(0) - '0';
// int c = numStr.charAt(1) - '0';
int num = Integer.parseInt(Reader.next());
int r = num / 10, c = num % 10;
int idx = map[r][c];
System.out.println(idx < 1 ? '?' : marks[idx]);
}
}
static class Reader {
static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st = new StringTokenizer("");
static String next() throws IOException {
while (!st.hasMoreTokens()) {
st = new StringTokenizer(BR.readLine());
}
return st.nextToken();
}
static String nextLine() throws IOException {
return BR.readLine();
}
}
}
代码2
#include <cstdio>
#include <iostream>
#include <limits>
#include <cstring>
using namespace std;
const int N = 110, M = 15;
int n, m, k;
string mp[N];
int rows[M];
int g[N][M];
int _ = []() {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
return 0;
}();
int main() {
cin >> n >> m;
string s;
cin.ignore(numeric_limits<streamsize>::max(), '\n');
for (int i = 1; i <= n; ++i) {
getline(cin, s);
mp[i] = s;
}
for (int i = 0; i < m; ++i) {
int r; cin >> r;
rows[i] = r;
}
memset(g, -1, sizeof(g));
for (int i = 0; i < m; ++i) {
int& r = rows[i];
for (int j = 0; j < 10; ++j) cin >> g[r][j];
}
cin >> k;
while (k--) {
int x; cin >> x;
int y = x % 10;
x /= 10;
cout << (~g[x][y] ? mp[g[x][y]] : "?") << '\n';
}
return 0;
}
7-2 盲盒包装流水线
众所周知，PAT 有 9 枚徽章，分别对应青铜、白银、黄金、白金、钻石、大师、王者、大圣、天神这 9 个段位，只有成绩非常优秀的考生才有资格获得刻有自己名字的徽章。现在，PAT 制作了徽章的小型纪念版，要制成盲盒给大家玩了！
下图是一条盲盒包装流水线的示意图。首先徽章通过进货口被压入货栈里，空盒在履带上从左向右传送。每次从货栈里弹出一枚徽章，进入打包机，装入一只空盒，打包后继续向右边传送。当货栈为空时，打包机会暂停，等待下一批徽章压入货栈。
每只盒子都有一个编号，小拼姐姐手里有进入流水线的空盒编号顺序表，也有每一批送往货栈的徽章顺序表，这样她其实可以知道每只盒子里装了哪种徽章。有些小朋友收到了盲盒，就想在拆封前问无所不知的小拼姐姐，盒子里的徽章是哪一种。但是因为盲盒总量有 105 这么多，小拼姐姐可记不住每只盒子里装的是什么，于是你就被请来写个程序帮小拼姐姐回复这种信息。
输入格式：
输入第一行给出 2 个正整数，分别为盲盒总量 N（≤105）和货栈容量 S（≤100）。接下来一行给出 N 只盒子的编号，编号由 5 位数字组成，给出的顺序是空盒进入传送带的顺序。随后 N/S（保证是整数）行，每行给出一批 S 枚徽章的类型，为 1-9 的数字，给出的顺序是从进货口入栈的顺序。
再下面给出一个正整数 K（≤104），为查询次数。随后 K 行，每行给出一个 5 位编号。
输出格式：
对每个查询编号，在一行中输出该盒子中装的徽章类型。如果编号是错误的，则在一行中输出 Wrong Number。
输入样例：
10 5
00132 10093 92001 23333 66666 88888 09009 34658 82750 69251
1 2 3 4 5
9 8 7 6 1
5
66666
88888
69251
55555
10093
输出样例：
1
1
9
Wrong Number
4
解题：模拟 哈希表
思路
每 S 个勋章要倒序放入对应的盒子，所以可以从第 S 个盒子放到第 1 个 盒子，从第 2*S 个盒子放到第 S+1 个盒子…依此类推维护一个哈希表，然后从哈希表中查出来输出。
代码
代码1
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
int N, S;
scanf("%d%d", &N, &S);
int boxes[N];
for (int i = 0; i < N; ++i) scanf("%d", &boxes[i]);
unordered_map<int, int> mp;
int rows = N / S;
for (int i = 0; i < rows; i++) {
for (int j = (i + 1) * S - 1; j >= i * S; --j) {
scanf("%d", &mp[boxes[j]]);
}
}
int K, k;
scanf("%d", &K);
while (K--) {
scanf("%d", &k);
if (mp.count(k)) printf("%d\n", mp[k]);
else printf("Wrong Number\n");
}
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(Reader.next());
int S = Integer.parseInt(Reader.next());
String[] nums = new String[N];
for (int i = 0; i < N; i++) nums[i] = Reader.next();
int idx = S - 1;
Map<String, String> map = new HashMap<>();
for (int i = 0; i < N / S; i++) {
for (int j = idx; j >= i * S; j--) {
map.put(nums[j], Reader.next());
}
idx += S;
}
int K = Integer.parseInt(Reader.next());
while (K-- > 0) {
System.out.println(map.getOrDefault(Reader.next(), "Wrong Number"));
}
}
static class Reader {
static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st = new StringTokenizer("");
static String next() throws IOException {
while (!st.hasMoreTokens()) {
st = new StringTokenizer(BR.readLine());
}
return st.nextToken();
}
static String nextLine() throws IOException {
return BR.readLine();
}
}
}
代码2
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int n, s, k;
int boxes[N];
int mp[N];
int main() {
scanf("%d%d", &n, &s);
for (int i = 0; i < n; ++i) scanf("%d", &boxes[i]);
int st = 0, row = n / s;
for (int i = 0; i < row; ++i) {
int idx = st + s - 1;
for (int j = 0; j < s; ++j, --idx) scanf("%d", &mp[boxes[idx]]);
st += s;
}
scanf("%d", &k);
while (k--) {
int x; scanf("%d", &x);
if (!mp[x]) puts("Wrong Number");
else printf("%d\n", mp[x]);
}
return 0;
}
7-3 到底爱不爱我
古代少女有了心上人时，会悄悄折一条树枝，揪那枝上的叶子，揪一片叶子念一句“爱我”，再揪一片念一句“不爱我”…… 这样揪落最后一片叶子的时候，看看是停在“爱”还是“不爱”。
但聪明的慧娘一眼洞穿，只要数一下叶子有多少片，根据这个数字的奇偶性判断是以“爱”开始还是以“不爱”开始，就总是可以最后落在“爱”上。这个游戏顿时就变得无趣了 —— 真的是文科生制造浪漫，理科生杀死浪漫。
于是有着工科生大脑的慧娘打算另外制作一个更有趣的浪漫游戏。她用不同植物的枝条做成了三种“情枝”：
- “专情枝”：是一根有两个分岔的树枝，只有当两个分岔上连接的枝条传过来的情话都是“爱”的时候，这根枝条的根部才传出“爱”；否则树枝根部传出的是“不爱”。
- “博爱枝”：也是一根有两个分岔的树枝，只有当两个分岔上连接的枝条传过来的情话都是“不爱”的时候，这根枝条的根部才传出“不爱”；否则树枝根部传出的都是“爱”。
- “情变枝”：是没有分岔的一根直枝，如果一端接到“爱”，另一端必须传出“不爱”；反之如果一端接到“不爱”，另一端则会传出“爱”。
慧娘将这些树枝摆放在院子里，布了一个“情阵”，先选一根特殊的枝条作为初试一枝，从这枝条的根部开始，扩散开去，令它们根枝相连。然后她在末梢的枝杈旁随意写下“爱”或“不爱”。现在请你写个程序帮她算出来，在初始一枝的根部，她能得到“爱”还是“不爱”？
输入格式：
输入在第一行中给出正整数 N（≤30），是慧娘制作的情枝数量。这里假设她将所有的情枝从 1 到 N 做好了编号。随后 N 行，第 i 行给出第 i 枝的描述，格式为
类型 左分枝连接的编号 右分枝连接的编号
其中 类型 为 1 代表专情、2 代表博爱、3 代表情变。当然如果是情变枝，则后面跟的是其唯一末端连接的情枝编号，并没有两个分枝的信息。如果一个分枝是末梢，并没有连接其它枝条，则对应编号为 0。
接下来一行中给出正整数 K（≤30），是慧娘询问的次数。以下 K 行，每行给出一个由 0 和 1 组成的字符串，其中 0 表示“不爱”，1 表示“爱”—— 这是慧娘从左到右在每个枝杈末梢处写下的。（注意：“从左到右”的意思是，我们从初试一枝出发去遍历所有枝条的末梢时，总是遵循先遍历左边情阵、再遍历右边情阵的顺序）
输出格式：
对慧娘的每个询问，如果她在初始一枝的根部能得到“爱”，就输出 Ai；否则输出 BuAi。
输入样例：
6
2 6 4
1 0 0
3 1
2 0 0
3 0
1 5 2
5
11111
00000
11100
10011
01100
输出样例：
BuAi
Ai
Ai
BuAi
BuAi
样例说明：
样例对应的情阵以及慧娘第 3 问的情势如图所示，其中完整的心对应 1，裂开的心对应 0。
解题：二叉树 DFS 队列
思路
建完树后先用第一个 dfs 搜出所有叶节点，然后输入每个用例后从叶节点向根节点再做 dfs 即可。
代码
#include <cstdio>
using namespace std;
const int N = 200;
int type[N], val[N], l[N], r[N];
bool is_child[N];
int eds[N];
int n, root, cnt, k;
void dfs1(int u) {
if (!u) return;
dfs1(l[u]);
if (u > n) eds[cnt++] = u;
dfs1(r[u]);
}
int dfs2(int u) {
if (u > n) return val[u];
int lv = dfs2(l[u]);
if (type[u] == 3) return !lv;
int rv = dfs2(r[u]);
if (type[u] == 1) return lv & rv;
if (type[u] == 2) return lv | rv;
}
int main() {
scanf("%d", &n);
cnt = n;
for (int u = 1; u <= n; ++u) {
scanf("%d%d", &type[u], &l[u]);
if (!l[u]) l[u] = ++cnt;
if (type[u] != 3) {
scanf("%d", &r[u]);
if (!r[u]) r[u] = ++cnt;
}
is_child[l[u]] = is_child[r[u]] = true;
}
for (int u = 1; u <= n; ++u) {
if (!is_child[u]) root = u;
}
cnt = 0;
dfs1(root);
scanf("%d", &k);
while (k--) {
scanf("\n");
char c;
for (int i = 0; i < cnt; ++i) {
scanf("%c", &c);
val[eds[i]] = c - '0';
}
puts(dfs2(root) ? "Ai" : "BuAi");
}
return 0;
}
7-4 皆大欢喜
喵星人素以有个性著称，铲屎官很难用一种玩具让家里所有的喵主子都高兴起来。于是铲屎官调研了一下各种玩具，记录下每种玩具能让哪些喵高兴、同时让哪些喵生气、另外还有哪些喵无感。现在铲屎官来向你求助，请你告诉他如何用最少的玩具，让所有的喵都高兴起来。
注意：如果一只喵处于高兴的状态，那么它会一直高兴着，直到见到让它生气的玩具；同样地，如果喵不高兴，它会一直不高兴，直到见到让它高兴的玩具。如果一样玩具令喵无感，则不会改变它原来的状态。
输入格式：
输入第一行给出两个正整数，分别是 N (≤10)，为喵的个数；以及 M（≤10），为玩具的个数（假设玩具从 1 到 M 编号）。随后 M 行，每行对应一种玩具，顺序给出 N 只喵的状态：1 表示高兴，-1 表示生气，0 表示无感。
输出格式：
假设初始状态下没有玩具，所有喵都不高兴。在一行中给出逗喵玩具的编号顺序，使得按这个顺序把玩具给喵，能令所有的喵都高兴起来。要求输出最少玩具的解。当这种解不唯一时，输出最小编号序列。题目保证存在解。一行中的数字以 1 个空格分隔，行首尾不得有多余空格。
序列 { a1，a2，…，an } 小于序列 { b1，b2，…，b**n } 的定义是：存在 1≤k<n 使得对所有 i<k 有 ai=bi，并且 ak<bk。
输入样例：
3 4
-1 1 0
1 1 -1
0 -1 1
1 0 0
输出样例：
3 1 4
解题：DFS
思路
爆搜 + 剪枝。
代码
代码1
#include<iostream>
using namespace std;
int N, M;
const int MAX_N = 11;
int used[MAX_N];
int states[MAX_N];
int toys[MAX_N][MAX_N];
int serials[MAX_N], cnt;
int ans[MAX_N], mn = 0x3f3f3f3f;
bool check() {
for (int i = 0; i < N; ++i)
if (states[i] != 1) return false;
return true;
}
void update(int idx) {
for (int i = 0; i < N; ++i) {
const int& state = toys[idx][i];
if (!state) continue;
states[i] = state;
}
}
bool dfs(int toy) {
int backtrace[MAX_N];
copy(begin(states), end(states), begin(backtrace));
update(toy);
used[toy] = true;
serials[cnt++] = toy;
if (check()) {
if (cnt < mn) {
mn = cnt;
copy(begin(serials), end(serials), begin(ans));
}
}
for (int i = 0; i < M; ++i) {
if (!used[i]) {
used[i] = 1;
if (dfs(i)) return true;
used[i] = 0;
}
}
used[toy] = 0;
copy(begin(backtrace), end(backtrace), begin(states));
--cnt;
return false;
}
int main() {
fill(states, states + N, -1);
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
scanf("%d", &toys[i][j]);
}
}
for (int i = 0; i < M; ++i) dfs(i);
for (int i = 0; i < mn; ++i) {
if (i) printf(" ");
printf("%d", ans[i] + 1);
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
static int N, M;
static int[][] toys;
static int[] states;
static boolean[] used;
static List<Integer> serials, ans;
public static void main(String[] args) throws IOException {
N = Reader.nextInt();
M = Reader.nextInt();
states = new int[N];
toys = new int[M][N];
used = new boolean[M];
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
toys[i][j] = Reader.nextInt();
}
}
Arrays.fill(states, -1);
serials = new ArrayList<>();
for (int i = 0; i < M; i++) dfs(i);
StringBuilder sb = new StringBuilder();
for (int i : ans) sb.append(' ').append(i + 1);
System.out.println(sb.substring(1));
}
static void dfs(int toy) {
if (ans != null && serials.size() == ans.size()) return;
int[] backtrace = new int[N];
System.arraycopy(states, 0, backtrace, 0, N);
update(toy);
serials.add(toy);
used[toy] = true;
if (check()) {
if (ans == null || serials.size() < ans.size()) {
ans = new ArrayList<>(serials);
}
}
for (int i = 0; i < M; i++) {
if (!used[i]) dfs(i);
}
used[toy] = false;
System.arraycopy(backtrace, 0, states, 0, N);
serials.remove(serials.size() - 1);
}
static boolean check() {
for (int state : states) {
if (state != 1) return false;
}
return true;
}
static void update(int idx) {
for (int i = 0; i < N; i++) {
int state = toys[idx][i];
if (state == 0) continue;
states[i] = state;
}
}
static class Reader {
static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
static final StreamTokenizer ST = new StreamTokenizer(BR);
static String next() throws IOException {
ST.nextToken();
return ST.sval;
}
static double nextDouble() throws IOException {
ST.nextToken();
return ST.nval;
}
static int nextInt() throws IOException {
return (int) nextDouble();
}
}
}
代码2
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 15;
int cats[N];
int g[N][N];
int n, m;
bool used[N];
int chosen[N];
int mn, ans[N];
void dfs(int u) {
if (u >= mn) return;
bool ap = true;
for (int i = 1; i <= n; ++i) {
if (cats[i] != 1) {
ap = false;
break;
}
}
if (ap && u < mn) {
memcpy(ans, chosen, sizeof(ans));
mn = u;
return;
}
int bak[N];
memcpy(bak, cats, sizeof(bak));
for (int i = 1; i <= m; ++i) {
if (used[i]) continue;
for (int j = 1; j <= n; ++j) {
if (g[i][j]) cats[j] = g[i][j];
}
chosen[u] = i;
used[i] = true;
dfs(u + 1);
used[i] = false;
memcpy(cats, bak, sizeof(cats));
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) scanf("%d", &g[i][j]);
}
memset(cats, -1, sizeof(cats));
mn = m + 1;
dfs(0);
for (int i = 0; i < mn; ++i) {
printf("%d", ans[i]);
printf(i == mn - 1 ? "\n" : " ");
}
return 0;
}
评论区