Code – 第65页

如何在Dev-Cpp中使用C++11中的函数：stoi、to_string、unordered_map、unordered_set、auto

如果想要在Dev-Cpp里面使用C++11特性的函数，比如刷算法中常用的stoi、to_string、unordered_map、unordered_set、auto这些，需要在设置里面让dev支持c++11～需要这样做～

在工具-编译选项-编译器-编译时加入这个命令“-std=c++11”：

然后就可以愉快的用这些好用到飞起的C++11函数啦啦啦啦啦啦～～～

[C++] STL库函数之字符串string::npos的介绍，以及string中的find函数～

npos经常和find一起用～它们两个都在头文件<string>里面～先看用法：

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s = "abc";
    if (s.find("b") != string::npos)
        printf("字符串s中存在b字符～");
    else
        printf("字符串s中不存在b字符～");
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s = "abc";

if (s.find("b") != string::npos)

printf("字符串s中存在b字符～");

else

printf("字符串s中不存在b字符～");

return 0;

}

简单点说就是，在字符串s中查找“b”字符（当然也可以查找一个字符串如“ab”），find函数如果找到了，就会返回第一次出现这个字符的位置，如果没找到怎么办呢，它会返回npos这个位置，npos本质上其实是一个常数，一般来说值是-1，所以s.find(“b”) != string::npos表示找到了“b”这个字符～如果相等就是没找到的意思啦～

我们可以从C++库函数的官方文档(www.cplusplus.com)中找到对这两个函数的解释～

std::string::find——[Return Value]
The position of the first character of the first match.
If no matches were found, the function returns string::npos.

std::string::npos
static const size_t npos = -1;
As a return value, it is usually used to indicate no matches.

以及关于为什么npos的值是-1的解释：

npos is a static member constant value with the greatest possible value for an element of type size_t.
This constant is defined with a value of -1, which because size_t is an unsigned integral type, it is the largest possible representable value for this type.

小米有品·米物蓝牙双模键盘说明书

PAT 1148 Werewolf – Simple Version – 甲级

Werewolf（狼人杀） is a game in which the players are partitioned into two parties: the werewolves and the human beings. Suppose that in a game,

player #1 said: “Player #2 is a werewolf.”;
player #2 said: “Player #3 is a human.”;
player #3 said: “Player #4 is a werewolf.”;
player #4 said: “Player #5 is a human.”; and
player #5 said: “Player #4 is a human.”.
Given that there were 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liers. Can you point out the werewolves?

Now you are asked to solve a harder version of this problem: given that there were N players, with 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liers. You are supposed to point out the werewolves.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (5≤N≤100). Then N lines follow and the i-th line gives the statement of the i-th player (1≤i≤N), which is represented by the index of the player with a positive sign for a human and a negative sign for a werewolf.

Output Specification:
If a solution exists, print in a line in ascending order the indices of the two werewolves. The numbers must be separated by exactly one space with no extra spaces at the beginning or the end of the line. If there are more than one solution, you must output the smallest solution sequence — that is, for two sequences A=a[1],…,a[M] and B=b[1],…,b[M], if there exists 0≤k[k+1]<b[k+1], then A is said to be smaller than B. In case there is no solution, simply print No Solution.

Sample Input 1:
5
-2
+3
-4
+5
+4
Sample Output 1:
1 4
Sample Input 2:
6
+6
+3
+1
-5
-2
+4
Sample Output 2 (the solution is not unique):
1 5
Sample Input 3:
5
-2
-3
-4
-5
-1
Sample Output 3:
No Solution

题目大意：已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家，如果有解，在一行中按递增顺序输出 2 个狼人的编号；如果解不唯一，则输出最小序列解；若无解则输出 No Solution～

分析：每个人说的数字保存在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～

#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;
}

#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;

}

PAT 1151 LCA in a Binary Tree（30 分）- 甲级

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.

Given any two nodes in a binary tree, you are supposed to find their LCA.

Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: M (≤ 1,000), the number of pairs of nodes to be tested; and N (≤ 10,000), the number of keys in the binary tree, respectively. In each of the following two lines, N distinct integers are given as the inorder and preorder traversal sequences of the binary tree, respectively. It is guaranteed that the binary tree can be uniquely determined by the input sequences. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.

Output Specification:
For each given pair of U and V, print in a line LCA of U and V is A. if the LCA is found and A is the key. But if A is one of U and V, print X is an ancestor of Y. where X is A and Y is the other node. If U or V is not found in the binary tree, print in a line ERROR: U is not found. or ERROR: V is not found. or ERROR: U and V are not found..

Sample Input:
6 8
7 2 3 4 6 5 1 8
5 3 7 2 6 4 8 1
2 6
8 1
7 9
12 -3
0 8
99 99
Sample Output:
LCA of 2 and 6 is 3.
8 is an ancestor of 1.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

题目大意：给出中序序列和先序序列，再给出两个点，求这两个点的最近公共祖先～

分析：不用建树～已知某个树的根结点，若a和b在根结点的左边，则a和b的最近公共祖先在当前子树根结点的左子树寻找，如果a和b在当前子树根结点的两边，在当前子树的根结点就是a和b的最近公共祖先，如果a和b在当前子树根结点的右边，则a和b的最近公共祖先就在当前子树的右子树寻找。中序加先序可以唯一确定一棵树，在不构建树的情况下，在每一层的递归中，可以得到树的根结点，在此时并入lca算法可以确定两个结点的公共祖先～

#include <iostream>
#include <vector>
#include <map>
using namespace std;
map<int, int> pos;
vector<int> in, pre;
void lca(int inl, int inr, int preRoot, int a, int b) {
    if (inl > inr) return;
    int inRoot = pos[pre[preRoot]], aIn = pos[a], bIn = pos[b];
    if (aIn < inRoot && bIn < inRoot)
        lca(inl, inRoot-1, preRoot+1, a, b);
    else if ((aIn < inRoot && bIn > inRoot) || (aIn > inRoot && bIn < inRoot))
        printf("LCA of %d and %d is %d.\n", a, b, in[inRoot]);
    else if (aIn > inRoot && bIn > inRoot)
        lca(inRoot+1, inr, preRoot+1+(inRoot-inl), a, b);
    else if (aIn == inRoot)
            printf("%d is an ancestor of %d.\n", a, b);
    else if (bIn == inRoot)
            printf("%d is an ancestor of %d.\n", b, a);
}
int main() {
    int m, n, a, b;
    scanf("%d %d", &m, &n);
    in.resize(n + 1), pre.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &in[i]);
        pos[in[i]] = i;
    }
    for (int i = 1; i <= n; i++) scanf("%d", &pre[i]);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        if (pos[a] == 0 && pos[b] == 0)
            printf("ERROR: %d and %d are not found.\n", a, b);
        else if (pos[a] == 0 || pos[b] == 0)
            printf("ERROR: %d is not found.\n", pos[a] == 0 ? a : b);
        else
            lca(1, n, 1, a, b);
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <map>

using namespace std;

map<int, int> pos;

vector<int> in, pre;

void lca(int inl, int inr, int preRoot, int a, int b) {

if (inl > inr) return;

int inRoot = pos[pre[preRoot]], aIn = pos[a], bIn = pos[b];

if (aIn < inRoot && bIn < inRoot)

lca(inl, inRoot-1, preRoot+1, a, b);

else if ((aIn < inRoot && bIn > inRoot) || (aIn > inRoot && bIn < inRoot))

printf("LCA of %d and %d is %d.\n", a, b, in[inRoot]);

else if (aIn > inRoot && bIn > inRoot)

lca(inRoot+1, inr, preRoot+1+(inRoot-inl), a, b);

else if (aIn == inRoot)

printf("%d is an ancestor of %d.\n", a, b);

else if (bIn == inRoot)

printf("%d is an ancestor of %d.\n", b, a);

}

int main() {

int m, n, a, b;

scanf("%d %d", &m, &n);

in.resize(n + 1), pre.resize(n + 1);

for (int i = 1; i <= n; i++) {

scanf("%d", &in[i]);

pos[in[i]] = i;

}

for (int i = 1; i <= n; i++) scanf("%d", &pre[i]);

for (int i = 0; i < m; i++) {

scanf("%d %d", &a, &b);

if (pos[a] == 0 && pos[b] == 0)

printf("ERROR: %d and %d are not found.\n", a, b);

else if (pos[a] == 0 || pos[b] == 0)

printf("ERROR: %d is not found.\n", pos[a] == 0 ? a : b);

else

lca(1, n, 1, a, b);

}

return 0;

}

1088 三人行（20 分）-PAT乙级真题

子曰：“三人行，必有我师焉。择其善者而从之，其不善者而改之。”

本题给定甲、乙、丙三个人的能力值关系为：甲的能力值确定是 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

分析：丙不一定是int值，可能是4.5这样的数字～所以要用double存储丙～i、j、k分别代表甲乙丙～i从99遍历到10找到符合题意的那个数字即可～

#include <iostream>
#include <cmath>
using namespace std;
int m, x, y;
void print(double t) {
    if (m == t) printf(" Ping");
    else if (m < t) printf(" Cong");
    else printf(" Gai");
}
int main() {
    scanf("%d %d %d", &m, &x, &y);
    for (int i = 99; i >= 10; i--) {
        int j = i % 10 * 10 + i / 10;
        double k = abs(j - i) * 1.0 / x;
        if (j == k * y) {
            cout << i;
            print(i); print(j); print(k);
            return 0;
        }
    }
    cout << "No Solution";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int m, x, y;

void print(double t) {

if (m == t) printf(" Ping");

else if (m < t) printf(" Cong");

else printf(" Gai");

}

int main() {

scanf("%d %d %d", &m, &x, &y);

for (int i = 99; i >= 10; i--) {

int j = i % 10 * 10 + i / 10;

double k = abs(j - i) * 1.0 / x;

if (j == k * y) {

cout << i;

print(i); print(j); print(k);

return 0;

}

cout << "No Solution";

return 0;

}