距离上次我一个人参加PAT考试已经过去快一个学期了，想想上次自己也是搞笑，自己一个人被这个书包就去了ZZ，人生地不熟的，乘坐公交车还坐反了。考完试因为不知道要等到考试结束就可以领取成绩证书，自己连那张不及格的证书都没有领，就急着赶火车回到了学校。因为这个周末就参加考试了，所以考试前做几道题熟悉一下试题的难度。
今天再做一下上次没有做出来的题目发现，这些题真的没涉及到什么算法，都是一些基础的模拟题，可是有些数据卡的我是不知所措，所以也很难得满分。
1086 就不告诉你 （15 分）
做作业的时候，邻座的小盆友问你：“五乘以七等于多少？”你应该不失礼貌地围笑着告诉他：“五十三。”本题就要求你，对任何一对给定的正整数，倒着输出它们的乘积。
输入格式：
输入在第一行给出两个不超过 1000 的正整数 A 和 B，其间以空格分隔。
输出格式：
在一行中倒着输出 A 和 B 的乘积。
输入样例：
5 7
输出样例：
53
题解：
首先将数字转换成字符串，然后用reverse翻转字符串，去掉字符串前面的0，然后输出就好了。
代码：
#include<iostream>
#include<string>
#include<algorithm> using namespace std; int main() {
int x, y, i; cin >> x >> y; string ans = to_string(x*y); reverse(ans.begin(), ans.end()); for (i = 0; i < ans.length(); ++i) if (ans[i] != '0') break; for (; i < ans.length(); ++i) cout << ans[i];
cout << endl; return 0;
}
1087 有多少不同的值 （20 分）
当自然数 n 依次取 1、2、3、……、N 时，算式 ⌊n/2⌋+⌊n/3⌋+⌊n/5⌋ 有多少个不同的值？（注：⌊x⌋ 为取整函数，表示不超过 x 的最大自然数，即 x 的整数部分。）
输入格式：
输入给出一个正整数 N（2≤N≤104）。
输出格式：
在一行中输出题面中算式取到的不同值的个数。
输入样例：
2017
输出样例：
1480
题解：
用set去重，最后返回set容器的size即可。
代码：
#include<iostream>
#include<set> using namespace std; int main() {
int n;
cin >> n; set<int> ans;
for (int i = 1; i <= n; ++i) {
int temp = i/2 + i/3 + i/5;
ans.insert(temp);
} cout << ans.size() << endl; return 0;
}
1088 三人行 （20 分）
子曰：“三人行，必有我师焉。择其善者而从之，其不善者而改之。”
本题给定甲、乙、丙三个人的能力值关系为：甲的能力值确定是 2 位正整数；把甲的能力值的 2 个数字调换位置就是乙的能力值；甲乙两人能力差是丙的能力值的 X 倍；乙的能力值是丙的 Y 倍。请你指出谁比你强应“从之”，谁比你弱应“改之”。
输入格式：
输入在一行中给出三个数，依次为：M（你自己的能力值）、X 和 Y。三个数字均为不超过 1000 的正整数。
输出格式：
在一行中首先输出甲的能力值，随后依次输出甲、乙、丙三人与你的关系：如果其比你强，输出 Cong；平等则输出 Ping；比你弱则输出 Gai。其间以 1 个空格分隔，行首尾不得有多余空格。
注意：如果解不唯一，则以甲的最大解为准进行判断；如果解不存在，则输出 No Solution。
输入样例 1：
48 3 7
输出样例 1：
48 Ping Cong Gai
输入样例 2：
48 11 6
输出样例 2：
No Solution
题解：
刚开始看成了是输出M的值，一直不过。值得注意的是丙的值可能是double类型的，可是我测试一下发现用int也能过通过。中间有一组数据被卡了，不知道是哪里出错了（-2）。
代码：
#include<iostream>
using namespace std;
void judge(int x, int y) {
if (x == y) cout << "Ping";
else if (x < y) cout << "Cong";
else cout << "Gai";
}
int main() {
int m, x, y;
cin >> m >> x >> y;
int p1, p2;
double p3;
for (int i = 99; i > 9; --i) {
p1 = i;
int t1, t2;
t1 = i % 10;
t2 = i / 10;
p2 = t1 * 10 + t2;
int sub = abs(p1 - p2);
p3 = sub * 1.0 / x;
if (p3 * y == p2) {
cout << p1 << ' ';
judge(m, p1);
cout << ' ';
judge(m, p2);
cout << ' ';
judge(m, p3);
cout << endl;
return 0;
}
}
cout << "No Solution" << endl;
return 0;
}
1089 狼人杀-简单版 （20 分）
以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？
本题是这个问题的升级版：已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？
输入格式：
输入在第一行中给出一个正整数 N（5≤N≤100）。随后 N 行，第 i 行给出第 i 号玩家说的话（1≤i≤N），即一个玩家编号，用正号表示好人，负号表示狼人。
输出格式：
如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 A=a[1],...,a[M] 和 B=b[1],...,b[M]，若存在 0≤k<M 使得 a[i]=b[i] （i≤k），且 a[k+1]<b[k+1]，则称序列 A 小于序列 B。若无解则输出 No Solution。
输入样例 1：
5
-2
+3
-4
+5
+4
输出样例 1：
1 4
输入样例 2：
6
+6
+3
+1
-5
-2
+4
输出样例 2（解不唯一）：
1 5
输入样例 3：
5
-2
-3
-4
-5
-1
输出样例 3：
No Solution
题解：
枚举所有可能的结果，在假设中的“好人”中如果还存在狼人，则不满足条件。根据题意“有狼人撒谎但并不是所有狼人都在撒谎”可知有一个狼人说的是真话，另外个狼人说的是假话。说真话的狼人不可能这出另外一个狼人来。说假话的狼人一定会陷害“好人”。
根据刚才的假设，我写的代码只能通过两组数据，不知道为什么会出错。（-12）
代码：
#include<iostream>
#include<string>
#include<vector>
#include<algorithm> using namespace std; bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second < b.second;
else return a.first < b.first;
} int main() {
int n;
string str;
vector<string> lang;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> str;
lang.push_back(str);
} vector<pair<int, int>> ans;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
vector<int> temp(n+1, 0);
string wolf1, wolf2;
for (int k = 0; k < n; ++k) {
char c = lang[k][0];
string s(lang[k].begin()+1, lang[k].end());
int num = stoi(s);
if (k+1 == i) {
wolf1 = lang[k];
continue;
}
if (k+1 == j) {
wolf2 = lang[k];
continue;
}
if (c == '-') temp[num]--;
// else temp[num]--;
} if (wolf1[0] == '-' && wolf2[0] == '-')
continue; // 检查除了假设的狼之外是否还存在其他的狼
// 若存在则说明这种假设不合理
int flag = true;
for (int k = 1; k <= n; ++k) {
if (temp[k] < 0 && k != i && k != j) {
flag = false;
break;
}
}
if (flag) {
ans.push_back(make_pair(i, j));
}
}
}
if (!ans.empty()) {
sort(ans.begin(), ans.end(), cmp);
cout << ans[0].first << " " << ans[0].second << endl;
} else {
cout << "No Solution" << endl;
} return 0;
}
大佬的解法：（https://blog.csdn.net/liuchuo/article/details/82560831）
分析：
每个人说的数字保存在v数组中，i从1～n、j从i+1～n遍历，分别假设i和j是狼人，a数组表示该人是狼人还是好人，等于1表示是好人，等于-1表示是狼人。k从1～n分别判断k所说的话是真是假，k说的话和真实情况不同（即v[k] * a[abs(v[k])] < 0）则表示k在说谎，则将k放在lie数组中；遍历完成后判断lie数组，如果说谎人数等于2并且这两个说谎的人一个是好人一个是狼人（即a[lie[0]] + a[lie[1]] == 0）表示满足题意，此时输出i和j并return，否则最后的时候输出No Solution～
code:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n+1);
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
vector<int> lie, a(n + 1, 1);
a[i] = a[j] = -1;
for (int k = 1; k <= n; k++)
if (v[k] * a[abs(v[k])] < 0) lie.push_back(k);
if (lie.size() == 2 && a[lie[0]] + a[lie[1]] == 0) {
cout << i << " " << j;
return 0;
}
}
}
cout << "No Solution";
return 0;
}
1090 危险品装箱 （25 分）
集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。
本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。
输入格式：
输入第一行给出两个正整数：N (≤104) 是成对的不相容物品的对数；M (≤100) 是集装箱货品清单的单数。
随后数据分两大块给出。第一块有 N 行，每行给出一对不相容的物品。第二块有 M 行，每行给出一箱货物的清单，格式如下：
K G[1] G[2] ... G[K]
其中 K (≤1000) 是物品件数，G[i] 是物品的编号。简单起见，每件物品用一个 5 位数的编号代表。两个数字之间用空格分隔。
输出格式：
对每箱货物清单，判断是否可以安全运输。如果没有不相容物品，则在一行中输出 Yes，否则输出 No。
输入样例：
6 3
20001 20002
20003 20004
20005 20006
20003 20001
20005 20004
20004 20006
4 00001 20004 00002 20003
5 98823 20002 20003 20006 10010
3 12345 67890 23333
输出样例：
No
Yes
Yes
题解：
记得当时考试的时候，弄了很长时间没有弄出来，没想到这次竟然一遍就过了。感觉正解应该是用并查集，但是自己菜写不出了，所以就模拟了一下。
代码：
#include<iostream>
#include<algorithm>
#include<map>
#include<set> using namespace std; int main() {
int n, m;
cin >> n >> m; map<int, set<int>> obj;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
obj[x].insert(y);
}
for (int i = 0; i < m; ++i) {
int num, No;
cin >> num;
set<int> list;
for (int j = 0; j < num; ++j) {
cin >> No;
list.insert(No);
}
bool flag = true;
set<int>::iterator it = list.begin();
for (; it != list.end(); ++it) {
int root = *it;
for (set<int>::iterator m_it = obj[root].begin(); m_it != obj[root].end(); ++m_it) {
int leaf = *m_it;
if (list.count(leaf)) {
cout << "No" << endl;
flag = false;
break;
}
}
if (!flag) break;
}
if (flag) cout << "Yes" << endl;
} return 0;
}
算下来，在自己可以google的情况下，我得了86分，虽然不是很满意，但确实比上次参加比赛进步了不少。希望这周末的考试也能取得一个好成绩吧。