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

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

简单点说就是,在字符串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~

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算法可以确定两个结点的公共祖先~

 

PAT 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

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

PAT 1150 Travelling Salesman Problem(25 分)- 甲级

The “travelling salesman problem” asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. (Quoted from “https://en.wikipedia.org/wiki/Travelling_salesman_problem”.)

In this problem, you are supposed to find, from a given list of cycles, the one that is the closest to the solution of a travelling salesman problem.

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<N≤200), the number of cities, and M, the number of edges in an undirected graph. Then M lines follow, each describes an edge in the format City1 City2 Dist, where the cities are numbered from 1 to N and the distance Dist is positive and is no more than 100. The next line gives a positive integer K which is the number of paths, followed by K lines of paths, each in the format:

n C1 C2 ……Cn​​

where n is the number of cities in the list, and C​i‘s are the cities on a path.

Output Specification:
For each path, print in a line Path X: TotalDist (Description) where X is the index (starting from 1) of that path, TotalDist its total distance (if this distance does not exist, output NA instead), and Description is one of the following:

TS simple cycle if it is a simple cycle that visits every city;
TS cycle if it is a cycle that visits every city, but not a simple cycle;
Not a TS cycle if it is NOT a cycle that visits every city.
Finally print in a line Shortest Dist(X) = TotalDist where X is the index of the cycle that is the closest to the solution of a travelling salesman problem, and TotalDist is its total distance. It is guaranteed that such a solution is unique.

Sample Input:
6 10
6 2 1
3 4 1
1 5 1
2 5 1
3 1 8
4 1 6
1 6 1
6 3 1
1 2 1
4 5 1
7
7 5 1 4 3 6 2 5
7 6 1 3 4 5 2 6
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 2 5 4 3 1
7 6 3 2 5 4 1 6
Sample Output:
Path 1: 11 (TS simple cycle)
Path 2: 13 (TS simple cycle)
Path 3: 10 (Not a TS cycle)
Path 4: 8 (TS cycle)
Path 5: 3 (Not a TS cycle)
Path 6: 13 (Not a TS cycle)
Path 7: NA (Not a TS cycle)
Shortest Dist(4) = 8

题目大意:给出一条路径,判断这条路径是这个图的旅行商环路、简单旅行商环路还是非旅行商环路~

分析:如果给出的路径存在某两个连续的点不可达或者第一个结点和最后一个结点不同或者这个路径没有访问过图中所有的点,那么它就不是一个旅行商环路(flag = 0)~如果满足了旅行商环路的条件,那么再判断这个旅行商环路是否是简单旅行商环路,即是否访问过n+1个结点(源点访问两次)~最后输出这些旅行商环路中经过的路径最短的路径编号和路径长度~

PAT 1149 Dangerous Goods Packaging(25 分)- 甲级

When shipping goods with containers, we have to be careful not to pack some incompatible goods into the same container, or we might get ourselves in serious trouble. For example, oxidizing agent (氧化剂) must not be packed with flammable liquid (易燃液体), or it can cause explosion.

Now you are given a long list of incompatible goods, and several lists of goods to be shipped. You are supposed to tell if all the goods in a list can be packed into the same container.

Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers: N (≤10^4), the number of pairs of incompatible goods, and M (≤100), the number of lists of goods to be shipped.

Then two blocks follow. The first block contains N pairs of incompatible goods, each pair occupies a line; and the second one contains M lists of goods to be shipped, each list occupies a line in the following format:

K G[1] G[2] … G[K]
where K (≤1,000) is the number of goods and G[i]’s are the IDs of the goods. To make it simple, each good is represented by a 5-digit ID number. All the numbers in a line are separated by spaces.

Output Specification:
For each shipping list, print in a line Yes if there are no incompatible goods in the list, or No if not.

Sample Input:
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
Sample Output:
No
Yes
Yes

题目大意:集装箱运输货物时,我们必须特别小心,不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱,否则很容易造成爆炸。给定一张不相容物品的清单,需要你检查每一张集装箱货品清单,判断它们是否能装在同一只箱子里。对每箱货物清单,判断是否可以安全运输。如果没有不相容物品,则在一行中输出 Yes,否则输出 No~

分析:用map存储每一个货物的所有不兼容货物~在判断给出的一堆货物是否是相容的时候,判断任一货物的不兼容货物是否在这堆货物中~如果存在不兼容的货物,则这堆货物不能相容~如果遍历完所有的货物,都找不到不兼容的两个货物,则这堆货物就是兼容的~