对方不想和你说话，并向你扔了一串数…… 而你必须从这一串数字中找到“250”这个高大上的感人数字。
输入格式：
输入在一行中给出不知道多少个绝对值不超过1000的整数，其中保证至少存在一个“250”。
输出格式：
在一行中输出第一次出现的“250”是对方扔过来的第几个数字（计数从1开始）。题目保证输出的数字在整型范围内。
输入样例：
888 666 123 -233 250 13 250 -222
输出样例：
5
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> using namespace std; int main() { int num, cnt = 0; while(cin >> num) { cnt++; if(num == 250) { cout << cnt; break; } } return 0; } |
本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。
输入格式：
输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。
输出格式：
首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。
输入样例：
9
2 6 5 5 -1 5 6 4 7
输出样例：
4
1 9
分析：v[i]中保存i的所有孩子结点，root为家谱中最高辈分的老祖宗，从root开始向下深度优先搜索，求得maxlevel和最后一层的结点编号，保存在set里，最后输出maxlevel和set中所有数字～
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <iostream> #include <vector> #include <set> using namespace std; int maxlevel = 1; vector<vector<int>> v; set<int> s; void dfs(int node, int level) { if (level > maxlevel) { maxlevel = level; s.clear(); s.insert(node); } else if (level == maxlevel) { s.insert(node); } for (int i = 0; i < v[node].size(); i++) dfs(v[node][i], level+1); } int main() { int n, num, root = 0; cin >> n; v.resize(n+1); for (int i = 1; i <= n; i++) { cin >> num; if (num == -1) { root = i; continue; } v[num].push_back(i); } dfs(root, 1); cout << maxlevel << endl; for (auto it = s.begin(); it != s.end(); it++) { if (it != s.begin()) cout << " "; cout << *it; } return 0; } |
周游世界是件浪漫事，但规划旅行路线就不一定了…… 全世界有成千上万条航线、铁路线、大巴线，令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟，每家公司提供一条线路，然后帮助客户规划由联盟内企业支持的旅行路线。本题就要求你帮旅行社实现一个自动规划路线的程序，使得对任何给定的起点和终点，可以找出最顺畅的路线。所谓“最顺畅”，首先是指中途经停站最少；如果经停站一样多，则取需要换乘线路次数最少的路线。
输入格式：
输入在第一行给出一个正整数N（<= 100），即联盟公司的数量。接下来有N行，第i行（i=1, …, N）描述了第i家公司所提供的线路。格式为：
M S[1] S[2] … S[M]
其中M（<= 100）是经停站的数量，S[i]（i=1, …, M）是经停站的编号（由4位0-9的数字组成）。这里假设每条线路都是简单的一条可以双向运行的链路，并且输入保证是按照正确的经停顺序给出的 —— 也就是说，任意一对相邻的S[i]和S[i+1]（i=1, …, M-1）之间都不存在其他经停站点。我们称相邻站点之间的线路为一个运营区间，每个运营区间只承包给一家公司。环线是有可能存在的，但不会不经停任何中间站点就从出发地回到出发地。当然，不同公司的线路是可能在某些站点有交叉的，这些站点就是客户的换乘点，我们假设任意换乘点涉及的不同公司的线路都不超过5条。
在描述了联盟线路之后，题目将给出一个正整数K（<= 10），随后K行，每行给出一位客户的需求，即始发地的编号和目的地的编号，中间以一空格分隔。
输出格式：
处理每一位客户的需求。如果没有现成的线路可以使其到达目的地，就在一行中输出“Sorry, no line is available.”；如果目的地可达，则首先在一行中输出最顺畅路线的经停站数量（始发地和目的地不包括在内），然后按下列格式给出旅行路线：
Go by the line of company #X1 from S1 to S2.
Go by the line of company #X2 from S2 to S3.
……
其中Xi是线路承包公司的编号，Si是经停站的编号。但必须只输出始发地、换乘点和目的地，不能输出中间的经停站。题目保证满足要求的路线是唯一的。
输入样例：
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
4
3011 3013
6666 2001
2004 3001
2222 6666
输出样例：
2
Go by the line of company #3 from 3011 to 3013.
10
Go by the line of company #4 from 6666 to 1306.
Go by the line of company #3 from 1306 to 2302.
Go by the line of company #2 from 2302 to 2001.
6
Go by the line of company #2 from 2004 to 1204.
Go by the line of company #1 from 1204 to 1306.
Go by the line of company #3 from 1306 to 3001.
Sorry, no line is available.
分析：【很简单的，别跑^_^】
一遍DFS即可～DFS过程中要维护两个变量：minCnt-中途经停的最少的站; minTransfer-需要换乘的最小次数～
0.可以这样计算出一条线路的换乘次数：在line[10000][10000]的数组中保存每两个相邻站中间的线路是几号线～从头到尾遍历最终保存的路径，preLine为前一小段的线路编号，如果当前的结点和前一个结点组成的这条路的线路编号和preLine不同，说明有一个换乘，就将cnt+1，最后遍历完累加的cnt即是换乘的次数～
1.可以这样计算出一条线路中途停站的次数：在dfs的时候有个变量cnt，表示当前路线是所需乘的第几个站，每次dfs时候将cnt+1表示向下遍历一层～cnt就是当前中途停站的次数～
2.可以这样输出结果：和计算线路换乘次数的思路一样，每当preLine和当前Line值不同的时候就输出一句话～保存preTransfer表示上一个换乘站，最后不要忘记输出preTransfer和最后一个站之间的路即使最后一个站并不是换乘站～
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <cstdio> #include <vector> using namespace std; vector<vector<int>> v(10000); int line[10000][10000], visit[10000]; vector<int> path, tempPath; int transferCnt(vector<int> a) { int cnt = -1, preLine = 0; for (int i = 1; i < a.size(); i++) { if (line[a[i-1]][a[i]] != preLine) cnt++; preLine = line[a[i-1]][a[i]]; } return cnt; } void dfs(int node, int end, int cnt, int &minCnt, int &minTransfer) { if (node == end && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))) { minCnt = cnt; minTransfer = transferCnt(tempPath); path = tempPath; } if (node == end) return; for (int i = 0; i < v[node].size(); i++) { if (visit[v[node][i]] == 0) { visit[v[node][i]] = 1; tempPath.push_back(v[node][i]); dfs(v[node][i], end, cnt + 1, minCnt, minTransfer); visit[v[node][i]] = 0; tempPath.pop_back(); } } } int main() { int n, m, k, pre, temp, a, b; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", &m, &pre); for (int j = 1; j < m; j++) { scanf("%d", &temp); v[pre].push_back(temp); v[temp].push_back(pre); line[pre][temp] = line[temp][pre] = i + 1; pre = temp; } } scanf("%d", &k); for (int i = 0; i < k; i++) { scanf("%d%d", &a, &b); int minCnt = 99999, minTransfer = 99999; tempPath.clear(); tempPath.push_back(a); visit[a] = 1; dfs(a, b, 0, minCnt, minTransfer); visit[a] = 0; if (minCnt == 99999) { printf("Sorry, no line is available.\n"); continue; } printf("%d\n", minCnt); int preLine = 0, preTransfer = a; for (int j = 1; j < path.size(); j++) { if (line[path[j-1]][path[j]] != preLine) { if (preLine != 0) printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]); preLine = line[path[j-1]][path[j]]; preTransfer = path[j-1]; } } printf("Go by the line of company #%d from %04d to %04d.\n", preLine, preTransfer, b); } return 0; } |
喵喵喵～
In the big cities, the subway systems always look so complex to the visitors. To give you some sense, the following figure shows the map of Beijing subway. Now you are supposed to help people with your computer skills! Given the starting position of your user, your task is to find the quickest way to his/her destination.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (< =100), the number of subway lines. Then N lines follow, with the i-th (i = 1, …, N) line describes the i-th subway line in the format:
M S[1] S[2] … S[M]
where M (<= 100) is the number of stops, and S[i]’s (i = 1, … M) are the indices of the stations (the indices are 4-digit numbers from 0000 to 9999) along the line. It is guaranteed that the stations are given in the correct order — that is, the train travels between S[i] and S[i+1] (i = 1, …, M-1) without any stop.
Note: It is possible to have loops, but not self-loop (no train starts from S and stops at S without passing through another station). Each station interval belongs to a unique subway line. Although the lines may cross each other at some stations (so called “transfer stations”), no station can be the conjunction of more than 5 lines.
After the description of the subway, another positive integer K (<= 10) is given. Then K lines follow, each gives a query from your user: the two indices as the starting station and the destination, respectively.
The following figure shows the sample map.
Note: It is guaranteed that all the stations are reachable, and all the queries consist of legal station numbers.
Output Specification:
For each query, first print in a line the minimum number of stops. Then you are supposed to show the optimal path in a friendly format as the following:
Take Line#X1 from S1 to S2.
Take Line#X2 from S2 to S3.
……
where Xi’s are the line numbers and Si’s are the station indices. Note: Besides the starting and ending stations, only the transfer stations shall be printed.
If the quickest path is not unique, output the one with the minimum number of transfers, which is guaranteed to be unique.
Sample Input:
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
3
3011 3013
6666 2001
2004 3001
Sample Output:
2
Take Line#3 from 3011 to 3013.
10
Take Line#4 from 6666 to 1306.
Take Line#3 from 1306 to 2302.
Take Line#2 from 2302 to 2001.
6
Take Line#2 from 2004 to 1204.
Take Line#1 from 1204 to 1306.
Take Line#3 from 1306 to 3001.
题目大意：找出一条路线，使得对任何给定的起点和终点，可以找出中途经停站最少的路线；如果经停站一样多，则取需要换乘线路次数最少的路线～
【很简单的，别跑^_^】
分析：一遍DFS即可～DFS过程中要维护两个变量：minCnt-中途经停的最少的站; minTransfer-需要换乘的最小次数～
0.可以这样计算出一条线路的换乘次数：在line[10000][10000]的数组中保存每两个相邻站中间的线路是几号线～从头到尾遍历最终保存的路径，preLine为前一小段的线路编号，如果当前的结点和前一个结点组成的这条路的线路编号和preLine不同，说明有一个换乘，就将cnt+1，最后遍历完累加的cnt即是换乘的次数～
update：由于新的PAT系统中会显示原解法有一个测试用例内存超限，考虑到line[10000][10000]存储的方式太暴力了，所以将line换成了unordered_map<int, int> line存储的方式，第一个int用来存储线路，每次将前四位存储第一个线路，后四位存储第二个线路，使用a[i-1]*10000+a[i]的方式存储，第二个int用来保存两个相邻中间的线路是几号线～
1.可以这样计算出一条线路中途停站的次数：在dfs的时候有个变量cnt，表示当前路线是所需乘的第几个站，每次dfs时候将cnt+1表示向下遍历一层～cnt就是当前中途停站的次数～
2.可以这样输出结果：和计算线路换乘次数的思路一样，每当preLine和当前Line值不同的时候就输出一句话～保存preTransfer表示上一个换乘站，最后不要忘记输出preTransfer和最后一个站之间的路即使最后一个站并不是换乘站～
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> #include <vector> #include <unordered_map> using namespace std; vector<vector<int>> v(10000); int visit[10000], minCnt, minTransfer, start, end1; unordered_map<int, int> line; vector<int> path, tempPath; int transferCnt(vector<int> a) { int cnt = -1, preLine = 0; for (int i = 1; i < a.size(); i++) { if (line[a[i-1]*10000+a[i]] != preLine) cnt++; preLine = line[a[i-1]*10000+a[i]]; } return cnt; } void dfs(int node, int cnt) { if (node == end1 && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))) { minCnt = cnt; minTransfer = transferCnt(tempPath); path = tempPath; } if (node == end1) return; for (int i = 0; i < v[node].size(); i++) { if (visit[v[node][i]] == 0) { visit[v[node][i]] = 1; tempPath.push_back(v[node][i]); dfs(v[node][i], cnt + 1); visit[v[node][i]] = 0; tempPath.pop_back(); } } } int main() { int n, m, k, pre, temp; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d%d", &m, &pre); for (int j = 1; j < m; j++) { scanf("%d", &temp); v[pre].push_back(temp); v[temp].push_back(pre); line[pre*10000+temp] = line[temp*10000+pre] = i + 1; pre = temp; } } scanf("%d", &k); for (int i = 0; i < k; i++) { scanf("%d%d", &start, &end1); minCnt = 99999, minTransfer = 99999; tempPath.clear(); tempPath.push_back(start); visit[start] = 1; dfs(start, 0); visit[start] = 0; printf("%d\n", minCnt); int preLine = 0, preTransfer = start; for (int j = 1; j < path.size(); j++) { if (line[path[j-1]*10000+path[j]] != preLine) { if (preLine != 0) printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]); preLine = line[path[j-1]*10000+path[j]]; preTransfer = path[j-1]; } } printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, end1); } return 0; } |
喵呜～
Recommendation system predicts the preference that a user would give to an item. Now you are asked to program a very simple recommendation system that rates the user’s preference by the number of times that an item has been accessed by this user.
Input Specification:
Each input file contains one test case. For each test case, the first line contains two positive integers: N (<= 50000), the total number of queries, and K (<= 10), the maximum number of recommendations the system must show to the user. Then given in the second line are the indices of items that the user is accessing — for the sake of simplicity, all the items are indexed from 1 to N. All the numbers in a line are separated by a space.
Output Specification:
For each case, process the queries one by one. Output the recommendations for each query in a line in the format:
query: rec[1] rec[2] … rec[K]
where query is the item that the user is accessing, and rec[i] (i = 1, … K) is the i-th item that the system recommends to the user. The first K items that have been accessed most frequently are supposed to be recommended in non-increasing order of their frequencies. If there is a tie, the items will be ordered by their indices in increasing order.
Note: there is no output for the first item since it is impossible to give any recommendation at the time. It is guaranteed to have the output for at least one query.
Sample Input:
12 3
3 5 7 5 5 3 2 1 8 3 8 12
Sample Output:
5: 3
7: 3 5
5: 3 5 7
5: 5 3 7
3: 5 3 7
2: 5 3 7
1: 5 3 2
8: 5 3 1
3: 5 3 1
8: 3 5 1
12: 3 5 8
题目大意：根据用户每次点击的东西的编号，输出他在点当前编号之前应该给这个用户推荐的商品的编号～只推荐k个～也就是输出用户曾经点击过的商品编号的最多的前k个～如果恰好两个商品有相同的点击次数，就输出编号较小的那个～
分析：【并不复杂～只是写的比较详细～不怕不怕～(摸头…】因为每个商品有两个属性：编号value和出现的次数cnt，编号具有唯一性，然后set又会根据大小自动排序，所以我们可以考虑将value和cnt组成一个node属性，把所有商品编号和它对应的次数变成node放入set里面，重载小于号，使<根据set中node的cnt排序，如果cnt相等就按照node的value排序～
这样set里面就是按照出现次数排序好的商品node，每次输出set的前k个node的value值就可以～（要记住，因为是点击前推荐，所以我们在接收完num的值后，应该先输出再插入让set帮忙排序当前num，当前的这个点击编号暂时先不算在输出结果里面的～）
首先在struct node里面重载<号，如果当前cnt不等于a.cnt就将cnt大的排在前，否则将value小的排在前面～
每次输入的时候，先不插入，先输出，当i != 0时候开始输出，因为i==0时候用户才第一次点击，没有可以推荐的～(沮丧脸…) 输出的同时记录输出过的个数tempCnt，当tempCnt < k的时候输出，因为只要前k个～所以就从头到尾依次输出set中的值就可以啦～
book[num]标记num出现的次数，每次寻找set中当前值为num和次数为book[num]的那个值，如果找到了就把他移除，（找到说明这个数已经出现过啦，cnt已经不对啦，先移除掉吧～）然后将book[num]+1，在将node(num, book[num])插入到set中，set会帮忙根据我们自定义的<的规则自动排序哒～
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <iostream> #include <set> using namespace std; int book[50001]; struct node { int value, cnt; bool operator < (const node &a) const { return (cnt != a.cnt) ? cnt > a.cnt : value < a.value; } }; int main() { int n, k, num; scanf("%d%d", &n, &k); set<node> s; for (int i = 0; i < n; i++) { scanf("%d", &num); if (i != 0) { printf("%d:", num); int tempCnt = 0; for(auto it = s.begin(); tempCnt < k && it != s.end(); it++) { printf(" %d", it->value); tempCnt++; } printf("\n"); } auto it = s.find(node{num, book[num]}); if (it != s.end()) s.erase(it); book[num]++; s.insert(node{num, book[num]}); } return 0; } |
某国的足球联赛中有N支参赛球队，编号从1至N。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。
联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个1至N的排列{ T1 T2 … TN }，满足：球队T1战胜过球队T2，球队T2战胜过球队T3，……，球队T(N-1)战胜过球队TN，球队TN战胜过球队T1。
现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。
注：排列{ a1 a2 …aN }在字典序上小于排列{ b1 b2 … bN }，当且仅当存在整数K（1 <= K <= N），满足：aK < bK且对于任意小于K的正整数i，ai=bi。
输入格式：
输入第一行给出一个整数N（2 <= N <= 20），为参赛球队数。随后N行，每行N个字符，给出了NxN的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：“W”表示球队i战胜球队j，“L”表示球队i负于球队j，“D”表示两队打平，“-”表示无效（当i=j时）。输入中无多余空格。
输出格式：
按题目要求找到“食物链”T1 T2 … TN，将这N个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，输出“No Solution”。
输入样例1：
5
-LWDW
W-LDW
WW-LW
DWW-W
DDLW-
输出样例1：
1 3 5 4 2
输入样例2：
5
-WDDW
D-DWL
DD-DW
DDW-D
DDDD-
输出样例2：
No Solution
分析：
0.既然是字典序最小的，而且必须包含所有的球队编号，那如果存在的话1肯定是结果数组的第一位～
1.接收数据：用v[21][21]存储比赛结果，如果是W就将v[i][j]置为1，表示i战胜过j，如果是L就将v[j][i]置为1，表示j战胜过i，其余的不用管～
2.dfs(int index, int num)：index从1到n用来表示当前即将写入的结果数组result的下标，num表示当前的球队的编号，从1开始。
3.flag用来标记是否已经找到一个这样的结果数组，如果已经找到了（flag == 1）就return; 否则将当前下标index的result写入num值。
当index等于n的时候，并且v[num][1]等于true，表示已经写到了n个球员，而且这个球队num也曾经战胜过球队1～如果仅仅是index == n，就直接return不用继续向下找了～
4.cut标记剪枝，首先cut等于false，当所有没有访问过的结点中没有一个结点的v[i][1] == true，即没有一个球队战胜过1，就直接return，因为这条路径肯定找不到回路啦～
5.然后将num球队编号标记为已经访问过【visit[num] = true;】遍历num所有打败过的球队，并将index + 1，直到dfs结束的最后将visit标记回false
6.最后根据flag的值输出结果，如果flag为0说明没有满足题意的球队，就输出No Solution，如果flag = 1就输出result数组中保存的结果～
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <cstdio> using namespace std; int n, flag = 0; int result[21]; bool v[21][21], visit[21]; void dfs(int index, int num) { if (flag == 1) return; result[index] = num; if (index == n && v[num][1] == true) { flag = 1; return; } if (index == n) return; bool cut = false; for (int i = 1; i <= n; i++) { if (visit[i] == false && v[i][1] == true) cut = true; } if (cut == false) return; visit[num] = true; for (int i = 1; i <= n; i++) { if (visit[i] == false && v[num][i] == true) dfs(index + 1, i); } visit[num] = false; } int main() { scanf("%d", &n); char s[21]; for (int i = 1; i <= n; i++) { scanf("%s", s + 1); for (int j = 1; j <= n; j++) { if (s[j] == 'W') v[i][j] = true; if (s[j] == 'L') v[j][i] = true; } } dfs(1, 1); if (flag == 1) { for (int i = 1; i <= n; i++) printf("%s%d", i == 1 ? "" : " ", result[i]); } else { printf("No Solution"); } return 0; } |