2015年11月 – 我的经验分享

A级103道PAT题目的简单总结

2015-11-30:对103道PAT题目做简单的总结：

1001 A+B Format (20) string处理，注意正负号

1002 A+B for Polynomials (25) 直接建立两个数组，相加输出

1003 Emergency (25) Dijkstra+DFS

1004 Counting Leaves (30) 计算每层叶子节点的数量

1005 Spell It Right (20) 字符串操作，计算digit总和并输出英文

1006 Sign In and Sign Out (25) 重写cmp进行排序

1007 Maximum Subsequence Sum (25) 最长连续子序列的和

1008 Elevator (20) 计算电梯时间

1009 Product of Polynomials (25) 多项式相乘，直接创建1000*1000+1个数组

1010 Radix (25) 重点：radix可以>=35，二分法查找radix

1011 World Cup Betting (20) 按照公式计算

1012 The Best Rank (25) 注意分数相同，排名相同

1013 Battle Over Cities (25) 使用并查集

1014 Waiting in Line (30) 银行排队模拟，一分钟一分钟地遍历

1015 Reversible Primes (20) 进制转换，质数判定

1016 Phone Bills (25) 排序，分类

1017 Queueing at Bank (25) 银行排队模拟

1018 Public Bike Management (30) Dijkstra+DFS

1019 General Palindromic Number (20) 回文判定+进制转换

1020 Tree Traversals (25) 后序+中序还原二叉树

1021 Deepest Root (25) BFS求最深的根，并查集。

1022 Digital Library (30) 哈希

1023 Have Fun with Numbers (20) string 大整数运算

1024 Palindromic Number (25) 回文判断（可以考虑manacher）

1025 PAT Ranking (25) 排名，排序

1026 Table Tennis (30) 队列模拟，30秒的四舍五入

1027 Colors in Mars (20) 10进制转换成13进制

1028 List Sorting (25) 排序，strcmp

1029 Median (25) 重点：二分法求两个数的中位数

1030 Travel Plan (30) Dijkstra+DFS

1031 Hello World for U (20) string处理

1032 Sharing (25) 求两个链表的公共点

1033 To Fill or Not to Fill (25) 重点：加油问题，队列，数组

1034 Head of a Gang (30) 并查集

1035 Password (20) 简单的string处理

1036 Boys vs Girls (25) 简写的排序，重写cmp比较函数

1037 Magic Coupon (25) 简写的排序，重写cmp比较函数

1038 Recover the Smallest Number (30) 贪心算法，注意贪心标准

1039 Course List for Student (25) 哈希查询，注意超时

1040 Longest Symmetric String (25) 最长回文字串

1041 Be Unique (20) 简单的哈希

1042 Shuffling Machine (20) 简单的数组位置更换

1043 Is It a Binary Search Tree (25)重点：写两个函数进行判断BST,MirrorBST

1044 Shopping in Mars (25) 尺取法求连续子序列的和

1045 Favorite Color Stripe (30) 动态规划，LCS变形

1046 Shortest Distance (20) 简单的和累加（算是DP）

1047 Student List for Course (25) 重点：选择合适的数据结构

1048 Find Coins (25) 和twosum一样，使用hash遍历一次

1049 Counting Ones (30) 重点：计算‘1’的个数，扩展到计算‘0’的个数

1050 String Subtraction (20) 简单的string处理

1051 Pop Sequence (25) 栈模拟操作

1052 Linked List Sorting (25) 排序，注意head=-1的情况（段错误）

1053 Path of Equal Weight (30) 求根到叶子节点的权重和（DFS）

1054 The Dominant Color (20) moore投票法

1055 The World’s Richest (25) 重点：根据题目特点选择合适的数据结构

1056 Mice and Rice (25) 模拟，注意排名的规则

1057 Stack (30) 重点：栈+树状数组+二分查找

1058 A+B in Hogwarts (20) string+进制转换

1059 Prime Factors (25) 质因数分解，注意输入为1的情况

1060 Are They Equal (25) string处理

1061 Dating (20) string处理

1062 Talent and Virtue (25) 根据要求排序，重写cmp比较函数

1063 Set Similarity (25) 重点：使用合适的数据结构来求集合的相似度

1064 Complete Binary Search Tree (30) 创建完全二叉搜索树，进行中序遍历（记录地址），然后再填值

1065 A+B and C (64bit) (20) string，大整数相加

1066 Root of AVL Tree (25) 重点：AVL树的基本操作

1067 Sort with Swap(0,*) (25) 每次都确保*移动在最终位置，注意优化

1068 Find More Coins (30) DFS

1069 The Black Hole of Numbers (20) string操作

1070 Mooncake (25) 贪心，单位价格高的优先

1071 Speech Patterns (25) 哈希求出现最多的单词（注意题目对单词的定义）

1072 Gas Station (30) 循环+Dijkstra，求出每个加油站到各个屋子的最短路程

1073 Scientific Notation (20) 科学计数法，还原出原数字，string操作

1074 Reversing Linked List (25) 链表翻转，把链表复制到数组，然后再翻转

1075 PAT Judge (25) 统计分数进行排名，重写cmp比较函数

1076 Forwards on Weibo (30) 层序遍历

1077 Kuchiguse (20) 简单的string处理

1078 Hashing (25) 哈希的平方探测实现

1079 Total Sales of Supply Chain (25) 层序遍历

1080 Graduate Admission (30) 事件模拟

1081 Rational Sum (20) 分数相加，gcd（扩展学习lcm的计算）

1082 Read Number in Chinese (25) string处理

1083 List Grades (25) 哈希，排序

1084 Broken Keyboard (20) 哈希

1085 Perfect Sequence (25) M<=m*p，二分法查找，排序

1086 Tree Traversals Again (25) 重点：利用栈进行中序遍历，还原二叉树

1087 All Roads Lead to Rome (30) Dijkstra+DFS

1088 Rational Arithmetic (20) 分数的四则运算

1089 Insert or Merge (25) 插入和归并排序（需要学习归并排序）

1090 Highest Price in Supply Chain (25) 层序遍历，求最深的层

1091 Acute Stroke (30) 并查集

1092 To Buy or Not to Buy (20) 哈希

1093 Count PAT’s (25) 组合数统计

1094 The Largest Generation (25) 层序遍历

1095 Cars on Campus (30) 停车时间模拟

1096 Consecutive Factors (20) 重点：连续因数，DFS

1097 Deduplication on a Linked List (25) 哈希，链表操作

1098 Insertion or Heap Sort (25) 插入和堆排

1099 Build A Binary Search Tree (30) 中序遍历填值，建立二叉树

1100 Mars Numbers (20) 进制转换，10进制转13进制

1101 Quick Sort (25) 重点：判断能够作为pivot的元素，大根堆，小根堆的额外维护操作

1102 Invert a Binary Tree (25) 反转二叉树

1103 Integer Factorization (30) 因式分解，DFS

1103. Integer Factorization (30)

1.题目要求把一个数转化为固定项数的p次方数相加。

2.根据题目的特点，n的最大值不超过400，可以使用深度遍历搜索答案

3.加入限制条件进行剪枝，如i的p次方不能大于n-k+1，因为剩下的数至少均为1，剩下还需要k-1个数需要进行分配，每个数至少分配为1，共k-1，所以i的p次方最大只能为n-（k-1）=n-k+1，而最大值不能超过上一次分配的。

时间限制

1200 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

The K-P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K-P factorization of N for any positive integers N, K and P.

Input Specification:

Each input file contains one test case which gives in a line the three positive integers N (<=400), K (<=N) and P (1<P<=7). The numbers in a line are separated by a space.

Output Specification:

For each case, if the solution exists, output in the format:

N = n₁^P + … n_K^P

where n_i (i=1, … K) is the i-th factor. All the factors must be printed in non-increasing order.

Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 12² + 4² + 2² + 2² + 1², or 11²+ 6² + 2² + 2² + 2², or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen — sequence { a₁, a₂, … a_K } is said to be larger than { b₁, b₂, … b_K } if there exists 1<=L<=K such that a_i=b_i for i<L and a_L>b_L

If there is no solution, simple output “Impossible”.

Sample Input 1:

169 5 2

Sample Output 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
void dfs(int n, int count, int p,int preNum, vector<int>&ans,int ansSum, vector<pair<int,vector<int>>>&totalAns, vector<vector<int>>&num)
{
	if (n == 0 && count == 0)
	{
		totalAns.push_back({ansSum, ans});
	}
	else if ((n == 0 && count != 0) || (n != 0 && count == 0))
		return;
	else
	{
		for (int i = min(n - count+1,preNum); i >= 1; i--)
		{//进行剪枝
			if (num[i][p - 1] != -1 && num[i][p - 1]<=n-count+1)
			{
				ans.push_back(i);
				ansSum += i;
				dfs(n - num[i][p - 1], count - 1, p,i, ans,ansSum, totalAns, num);
				ansSum -= i;
				ans.pop_back();
			}
		}
	}
}
bool cmp(const pair<int, vector<int>>&a, const pair<int, vector<int>>&b)
{
	if (a.first > b.first)
		return true;
	else if (a.first == b.first)
	{
		for (int i = 0; i < a.second.size(); i++)
		{
			if (a.second[i] > b.second[i]) return true;
			else if (a.second[i] < b.second[i]) return false;
		}

	}
	else return false;
}
int main(void)
{
	
	int n, k, p;
	cin >> n >> k >> p;
	vector<vector<int>> num(401, vector<int>(7, 0));
	for (int i = 1; i < 401; i++)
	{
		num[i][0] = i;
		for (int j = 1; j < 7; j++)
		{
			if (num[i][j - 1] == -1) num[i][j] = -1;
			else
			{
				num[i][j] = num[i][j - 1] * i;
				if (num[i][j] > 400) num[i][j] = -1;
			}
		}
	}
	vector<int> ans(0);
	vector<pair<int,vector<int>>> totalAns(0);
	int ansSum = 0;

	dfs(n, k, p,n, ans,ansSum, totalAns, num);
	sort(totalAns.begin(), totalAns.end(), cmp);
	if (totalAns.size() != 0)
	{
		cout << n << " = ";
		for (int i = 0; i < totalAns[0].second.size(); i++)
		{
			cout << totalAns[0].second[i] << "^" << p;
			if (i != totalAns[0].second.size() - 1)
			{
				cout << " + ";
			}
		}
		cout << endl;
	}
	else 
	{
		cout << "Impossible" << endl;
	}

	return 0;
}

1102. Invert a Binary Tree (25)

1.和leetcode中的Invert Binary Tree（easy）题目一样。

2.利用递归函数，每次都把左右子树翻转即可。

翻转函数如下：


void invertTree(TreeNode* root)
{
	if (root != NULL)
	{
		swap(root->l, root->r);
		invertTree(root->l);
		invertTree(root->r);
	}
	
}

时间限制

400 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

The following is from Max Howell @twitter:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Now it’s your turn to prove that YOU CAN invert a binary tree!

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=10) which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node from 0 to N-1, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

Output Specification:

For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output:

3 7 2 6 4 0 5 1
6 5 7 4 3 2 0 1

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
struct TreeNode{
	int val;
	TreeNode*l, *r;
	TreeNode() :val(-1),l(NULL), r(NULL){};
};
void invertTree(TreeNode* root)
{
	if (root != NULL)
	{
		swap(root->l, root->r);
		invertTree(root->l);
		invertTree(root->r);
	}
	
}
void levelOrder(TreeNode*root,vector<int>&ans)
{
	queue<TreeNode*> q;
	if (root != NULL)
	{
		q.push(root);
		int count1 = 1;
		int count2 = 0;
		while (!q.empty())
		{
			for (int i = 0; i < count1; i++)
			{
				TreeNode* head = q.front(); q.pop();
				ans.push_back(head->val);
				if (head->l != NULL)
				{
					q.push(head->l);
					count2++;
				}
				if (head->r != NULL)
				{
					q.push(head->r);
					count2++;
				}
			}
			count1 = count2;
			count2 = 0;
		}

	}
}
void inOrder(TreeNode*root, vector<int>&ans)
{
	if (root != NULL)
	{
		inOrder(root->l, ans);
		ans.push_back(root->val);
		inOrder(root->r, ans);
	}
}
int main(void)
{
	
	int sum;
	cin >> sum;
	vector<TreeNode> tree(sum);
	vector<int> degree(sum,0);
	for (int i = 0; i < sum; i++)
	{
		tree[i].val = i;
		char a, b;
		cin >> a >> b;
		if (a!='-')
		{
			tree[i].l = &tree[a - '0'];
			degree[a - '0']++;
		}
		if (b != '-')
		{
			tree[i].r = &tree[b - '0'];
			degree[b - '0']++;
		}
	}
	TreeNode* root=NULL;
	for (int i = 0; i < sum; i++)
	{
		if (degree[i] == 0)
		{
			root = &tree[i];
			break;
		}
	}
	invertTree(root);
	vector<int> ans1(0);
	vector<int> ans2(0);
	levelOrder(root, ans1);
	inOrder(root, ans2);
	for (int i = 0; i < ans1.size(); i++)
	{
		cout << ans1[i];
		if (i != ans1.size() - 1)
			cout << " ";
	}
	cout << endl;
	for (int i = 0; i < ans2.size(); i++)
	{
		cout << ans2[i];
		if (i != ans2.size() - 1)
			cout << " ";
	}
	cout << endl;
	return 0;
}

1101. Quick Sort (25)

1.题目要求判断一个数组中，哪些元素可以作为当前数组组合的pivot（可以理解为经过了若干轮的快排后，pivot在最终的位置）。

2.这道题目需要考虑采用适当的数据结构，即小根堆和大根堆。

3.判断某个元素是否能够成为pivot，那么该元素左边数组应该构成一个大根堆，堆顶元素应该小于该元素，该元素的右边构成小根堆，堆顶元素大于该元素

4.左边的小根堆，一直插入即可，利用priority_queue，而右边则需要进行维护，需要编写仿函数。

5.右边的大根堆维护机制：建立哈希表times，记录每个元素出现的次数，每往后检测新元素数，把新元素出现的次数-1，同时检测大根堆的堆顶元素，如果出现次数为0则弹出，直至剩下出现次数不为0的堆顶。

时间限制

200 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CAO, Peng

There is a classical process named partition in the famous quick sort algorithm. In this process we typically choose one element as the pivot. Then the elements less than the pivot are moved to its left and those larger than the pivot to its right. Given N distinct positive integers after a run of partition, could you tell how many elements could be the selected pivot for this partition?

For example, given N = 5 and the numbers 1, 3, 2, 4, and 5. We have:

1 could be the pivot since there is no element to its left and all the elements to its right are larger than it;
3 must not be the pivot since although all the elements to its left are smaller, the number 2 to its right is less than it as well;
2 must not be the pivot since although all the elements to its right are larger, the number 3 to its left is larger than it as well;
and for the similar reason, 4 and 5 could also be the pivot.
Hence in total there are 3 pivot candidates.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 10⁵). Then the next line contains N distinct positive integers no larger than 10⁹. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output in the first line the number of pivot candidates. Then in the next line print these candidates in increasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.

Sample Input:
```
5
1 3 2 4 5
```
Sample Output:
```
3
1 4 5
```

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
struct cmp
{
	bool operator()(const int&a, const int&b)
	{
		return a > b;
	}
};
int main(void)
{
	
	int sum;
	cin >> sum;
	int *num = new int[sum];
	map<int, int> times;
	/*vector<int> times(100001, 0);*/
	priority_queue<int> lq;
	priority_queue<int,vector<int>,cmp> rq;
	for (int i = 0; i < sum; i++)
	{
		scanf("%d", &num[i]);
		times[num[i]]++;
		rq.push(num[i]);
	}
	vector<int> ans(0);
	for (int i = 0; i < sum; i++)
	{
		if (i>0) lq.push(num[i - 1]);
		if (rq.size() != 0)
		{//如果右边heap不为空
			times[num[i]]--;//减少num[i]的次数，以维护右边的小根堆
			while (rq.size() != 0 && times[rq.top()] == 0) rq.pop();//检测堆顶元素，出现次数是否为0，如果为0，证明应该被弹出，
			if (rq.size() != 0 && num[i]>rq.top())
			{
				continue;
			}
		}
		if (lq.size() != 0 && num[i] < lq.top())
		{
			continue;
		}
		ans.push_back(num[i]);
	}
	cout << ans.size() << endl;
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++)
	{
		printf("%d", ans[i]);
		if (i != ans.size() - 1)
			cout << " ";
	}
	cout << endl;//注意在后面添加换行
	return 0;
}

1100. Mars Numbers (20)

1.题目考察十进制与13进制之间的转换。

2.注意输入为13，26，39整数时，只输出一个marsNum，后面低位的0不输出。

时间限制

400 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

People on Mars count their numbers with base 13:

Zero on Earth is called “tret” on Mars.
The numbers 1 to 12 on Earch is called “jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec” on Mars, respectively.
For the next higher digit, Mars people name the 12 numbers as “tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou”, respectively.

For examples, the number 29 on Earth is called “hel mar” on Mars; and “elo nov” on Mars corresponds to 115 on Earth. In order to help communication between people from these two planets, you are supposed to write a program for mutual translation between Earth and Mars number systems.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (< 100). Then N lines follow, each contains a number in [0, 169), given either in the form of an Earth number, or that of Mars.

Output Specification:

For each number, print in a line the corresponding number in the other language.

Sample Input:

4
29
5
elo nov
tam

Sample Output:

hel mar
may
115
13

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
bool isNum(string a)
{
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i]>'9' || a[i] < '0')
			return false;
	}
	return true;
}
int main(void)
{
	vector<string> marsNum = { "tret","jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec" };
	vector<string> marsNum2 = { "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou" };
	map<string, int> mars2Num;
	map<string, int> mars2Num2;
	for (int i = 0; i < marsNum.size(); i++)
	{
		mars2Num[marsNum[i]] = i;
	}
	for (int i = 0; i < marsNum2.size(); i++)
	{
		mars2Num2[marsNum2[i]] = i+1;
	}
	string str = "";
	string n = "";
	getline(cin, n);
	int sum = 0;
	for (int i = 0; i < n.size(); i++)
	{
		sum = sum * 10 + n[i] - '0';
	}
	for (int k = 0; k < sum; k++)
	{
		getline(cin, str);
		if (isNum(str))
		{
			int num = 0;
			for (int i = 0; i < str.size(); i++)
			{
				num = num * 10 + str[i] - '0';
			}
			string ans = "";
			int  low = num % 13;//计算高位和地位
			int  high = num / 13;
			if (high == 0)
				ans = marsNum[low];
			else if (low == 0)//注意输入为13，26，39整数时，只输出一个marsNum，后面低位的0不输出
				ans = marsNum2[high - 1] ;
			else
				ans = marsNum2[high - 1] + " " + marsNum[low];
			cout << ans << endl;
		}
		else
		{
			int ans = 0;
			if (str.size() == 3)
			{
				if (mars2Num.find(str) != mars2Num.end())
				{
					ans = mars2Num[str];
				}
				else
				{//找不到，是在十位上
					ans = mars2Num2[str]*13;
				}
			}
			else
			{
				string high = str.substr(0, 3);
				string low = str.substr(4);
				ans = mars2Num2[high] * 13 + mars2Num[low];
			}
			cout << ans << endl;
		}
	}
	return 0;
}

1099. Build A Binary Search Tree (30)

1.这道题目难度不大，根据给出的数组和BST二叉树，进行填值，主要思想如下：

1）先构建二叉树（此时尚未填值）；

2）输出二叉树的中序遍历地址；

3）对数组进行排序；

4）把数组的数输入到中序遍历地址相应的节点值中。

时间限制

100 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.
Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100) which is the total number of nodes in the tree. The next N lines each contains the left and the right children of a node in the format “left_index right_index”, provided that the nodes are numbered from 0 to N-1, and 0 is always the root. If one child is missing, then -1 will represent the NULL child pointer. Finally N distinct integer keys are given in the last line.

Output Specification:

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:
```
9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42
```
Sample Output:
```
58 25 82 11 38 67 45 73 42
```

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

struct TreeNode{
	int val;
	TreeNode*left, *right;
	TreeNode(int x) :val(x), left(NULL), right(NULL){};
	TreeNode() :val(-1), left(NULL), right(NULL){};
};
void inOrder(TreeNode*root,vector<TreeNode*>&in)
{
	if (root != NULL)
	{
		inOrder(root->left, in);
		in.push_back(root);
		inOrder(root->right, in);
	}
}
int main(void)
{
	int n;
	cin >> n;
	if (n == 0) return 0;
	TreeNode *tree = new TreeNode[n];
	
	//建立二叉树
	for (int i = 0; i < n; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		if (a != -1)
			tree[i].left = &tree[a];
		if (b != -1)
			tree[i].right = &tree[b];
	}
	//读取数组
	vector<int> num(n, 0);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}
	//数组排序
	sort(num.begin(), num.end());

	//建立中序遍历数组
	vector<TreeNode*> treeAddress(0);
	inOrder(&tree[0], treeAddress);
	for (int i = 0; i < n; i++)
	{
		treeAddress[i]->val = num[i];
	}

	//进行层序遍历
	queue<TreeNode*> q;
	int count1 = 0;
	int count2 = 0;
	if (num.size() != 0)
	{
		q.push(&tree[0]);
		count1++;
	}
	vector<int> outPut(0);
	while (!q.empty())
	{
		for (int i = 0; i < count1; i++)
		{
			TreeNode* tmp = q.front(); q.pop();
			outPut.push_back(tmp->val);
			if (tmp->left != NULL)
			{
				q.push(tmp->left);
				count2++;
			}
			if (tmp->right != NULL)
			{
				q.push(tmp->right);
				count2++;
			}
		}
		count1 = count2;
		count2 = 0;
	}

	//输出结果
	for (int i = 0; i < outPut.size(); i++)
	{
		cout << outPut[i];
		if (i != outPut.size() - 1)
			cout << " ";
	}
	cout << endl;

	return 0;
}

1098. Insertion or Heap Sort (25)

1.给出一个初始的排列和一个经过N轮排序的排列，求出是使用插入还是堆排序，并输出下一轮的排列。

2.之前一直开在测试点2里，通过实验知道0、2、4测试点是测插入排序的，1、3、5是堆排的。

3.测试点2卡住，主要是因为插入排序的外层循环我从i=0开始，导致第一步出来的结果和原来的一模一样（i=0，相当于没有进行调整），而把i改为1后，则可以正常AC题目。

4.目前只知道测试点2的情况是，经过若干轮插入排序后，得到的target数组与源数组是一样的，其他细节就无从得知。

5.堆排可以自己写函数，也可以使用make_heap；

6.自己写的堆排的程序：

#define LeftChild(i) (2*(i)+1)
void PercDown(vector<int>&num, int i, int n)
{
    int child;
    int tmp;
    for (tmp = num[i]; LeftChild(i) < n; i = child)       {           child = LeftChild(i);           if (child != n - 1 && num[child + 1] > num[child])
             child++;
        if (tmp < num[child])                num[i] = num[child];           else                break;        }  num[i] = tmp;  }  for (int i = n - 1; i>0; i--)
{//进行堆排
     swap(numCopy[0], numCopy[i]);
     PercDown(numCopy, 0, i);
}

时间限制

100 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

Sample Output 2:

Heap Sort
5 4 3 1 0 2 6 7 8 9

AC代码，使用make_heap：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

/*
10
6 4 5 1 0 3 2 7 8 9
5 4 2 1 0 3 6 7 8 9
*/
int main(void)
{
	int n;
	cin >> n;
	vector<int> num(n, 0);
	vector<int> num2(n, 0);
	vector<int> numCopy(n, 0);
	vector<int> target(n, 0);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}
	numCopy = num;
	num2 = num;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &target[i]);
	}

	bool isInsert = false;

	for (int i = 1; i < n; i++)
	{//进行插入排序,从i=1，即第二个元素开始插入排序，i=0时，没必要进行插入排序（为什么测试点2会错？）
		int tmp = num[i];
		int j = i;
		for (; j>0 && num[j - 1]>tmp; j--)
		{
			num[j] = num[j - 1];
		}
		num[j] = tmp;
		if (!isInsert && num == target)
		{//是插入排序
			isInsert = true;
		}
		else if (isInsert)
		{
			break;
		}
	}
	if (isInsert)
	{
		cout << "Insertion Sort" << endl;
		for (int i = 0; i < n; i++)
		{
			cout << num[i];
			if (i != n - 1)
				cout << " ";
		}
		cout << endl;
		return 0;
	}

	bool isHeap = false;

	for (int i = n-1; i>=0; i--)
	{//进行堆排，使用原来的函数进行堆排
		make_heap(numCopy.begin(), numCopy.begin() + i+1);
		if (!isHeap && numCopy == target)
		{
			isHeap = true;
		}
		else if (isHeap)
			break;
		swap(numCopy[0], numCopy[i]);//注意是比较了后再交换

	}
	if (isHeap)
	{//如果是堆排，输出并return
		cout << "Heap Sort" << endl;
		for (int i = 0; i < n; i++)
		{
			cout << numCopy[i];
			if (i != n - 1)
				cout << " ";
		}
		cout << endl;
		return 0;
	}
	return 0;
}

AC代码，使用自己写的堆排：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

/*
10
6 4 5 1 0 3 2 7 8 9
5 4 2 1 0 3 6 7 8 9
*/
#define LeftChild(i) (2*(i)+1)
void PercDown(vector<int>&num, int i, int n)
{
	int child;
	int tmp;
	for (tmp = num[i]; LeftChild(i) < n; i = child)
	{
		child = LeftChild(i);
		if (child != n - 1 && num[child + 1] > num[child])
			child++;
		if (tmp < num[child])
			num[i] = num[child];
		else
			break;
	}
	num[i] = tmp;
}

int main(void)
{
	int n;
	cin >> n;
	vector<int> num(n, 0);
	vector<int> num2(n, 0);
	vector<int> numCopy(n, 0);
	vector<int> target(n, 0);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &num[i]);
	}
	numCopy = num;
	num2 = num;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &target[i]);
	}

	bool isInsert = false;

	for (int i = 1; i < n; i++)
	{//进行插入排序,从i=1，即第二个元素开始插入排序，i=0时，没必要进行插入排序（为什么测试点2会错？）
		int tmp = num[i];
		int j = i;
		for (; j>0 && num[j - 1]>tmp; j--)
		{
			num[j] = num[j - 1];
		}
		num[j] = tmp;
		if (!isInsert && num == target)
		{//是插入排序
			isInsert = true;
		}
		else if (isInsert)
		{
			break;
		}
	}
	if (isInsert)
	{
		cout << "Insertion Sort" << endl;
		for (int i = 0; i < n; i++)
		{
			cout << num[i];
			if (i != n - 1)
				cout << " ";
		}
		cout << endl;
		return 0;
	}
	
	bool isHeap = false;
	for (int i = n / 2; i >= 0; i--)
		PercDown(numCopy, i, n);
	for (int i = n - 1; i>0; i--)
	{//进行堆排
		swap(numCopy[0], numCopy[i]);
		PercDown(numCopy, 0, i);
		if (!isHeap && numCopy == target)
		{
			isHeap = true;
		}
		else if (isHeap)
			break;
		//cout << "Heap Sort" << endl;
		//for (int i = 0; i < n; i++)
		//{
		//	cout << numCopy[i];
		//	if (i != n - 1)
		//		cout << " ";
		//}

	}
	if (isHeap)
	{//如果是堆排，输出并return
		cout << "Heap Sort" << endl;
		for (int i = 0; i < n; i++)
		{
			cout << numCopy[i];
			if (i != n - 1)
				cout << " ";
		}
		cout << endl;
		return 0;
	}
	return 0;
}

1097. Deduplication on a Linked List (25)

1.题目要求删除重复的节点，并把重复的节点建立成一个新的链表，最终输出两个链表，一个是去重的链表，一个是重复节点组成的链表。

2.主要是考察链表的删除和建表操作，使用map进行记录已经存在过的链表节点。

3.注意是删除绝对值相同的节点。

时间限制

300 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

Given a singly linked list L with integer keys, you are supposed to remove the nodes with duplicated absolute values of the keys. That is, for each value K, only the first node of which the value or absolute value of its key equals K will be kept. At the mean time, all the removed nodes must be kept in a separate list. For example, given L being 21→-15→-15→-7→15, you must output 21→-15→-7, and the removed list -15→15.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, and a positive N (<= 10⁵) which is the total number of nodes. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Key Next

where Address is the position of the node, Key is an integer of which absolute value is no more than 10⁴, and Next is the position of the next node.

Output Specification:

For each case, output the resulting linked list first, then the removed list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

Sample Output:

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
/*
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854

00001 2
00002 1 -1
00001 1 00002

*/
struct ListNode{
	int val, add;
	ListNode* next;
	ListNode() :val(-1), add(-1), next(NULL){};
	ListNode(int x,int a) :val(x), add(a), next(NULL){};
};
int main(void)
{
	ListNode *list = new ListNode[100000];
	map<int, bool> exist;
	int headAdd, n;
	cin >> headAdd >> n;
	for (int i = 0; i < n; i++)
	{
		int pre, val, next;
		scanf("%d %d %d", &pre, &val, &next);
		list[pre].val = val;
		list[pre].add = pre;
		if (next != -1)
		{
			list[next].add = next;
			list[pre].next = &list[next];
		}
		else
			list[pre].next = NULL;
	}

	ListNode*head = &list[headAdd];
	ListNode*preHead = head;
	ListNode*newList = new ListNode(-1, -1);
	ListNode*newListHead = newList;
	while (head != NULL)
	{
		if (exist[abs(head->val)])
		{
			preHead->next = head->next;
			newList->next = head;//
			newList = newList->next;//newList现在指向head
			head = preHead->next;
			newList->next = NULL;
		}
		else
		{
			exist[abs(head->val)] = true;
			preHead = head;
			head = head->next;
		}
	}

	head = &list[headAdd];
	while (head != NULL)
	{
		printf("%05d %d ", head->add, head->val);
		if (head->next != NULL)
			printf("%05d\n", head->next->add);
		else
			printf("-1\n");
		head = head->next;
	}
	head = newListHead->next;
	while (head != NULL)
	{
		printf("%05d %d ", head->add, head->val);
		if (head->next != NULL)
			printf("%05d\n", head->next->add);
		else
			printf("-1\n");
		head = head->next;
	}

	return 0;
}

1096. Consecutive Factors (20)

1.题目要求求连续的质因数。

2.最开始卡在最后一个测试点中，后来经过对偶数情况的优化，发现仍然超时，于是考虑是奇数情况下超时，实际上，最后一个测试例子应该是一个非常大的质数；

3.把情况分为奇数和偶数，

1）奇数情况下，答案肯定为1个，遇到第一个整除的数，则直接输出；

但是采用遍历至n时，最后一个测试例子会超时，于是采用质因数分解的算法：

质因数分解算法如下：

情况一：当n是素数时，n的质因素要么是n本身；
情况二：在除去最大质因素的情况下，一定小于等于sqrt（n），如2*17=34，sqrt（34）=5，除去最大质因素17，剩下的质因素小于5 ；

于是，把时间复杂度降为o（sqrt（n）），最终一个例子通过

2）偶数情况下，当n小于6时，只有1个，但是当n大于6时，肯定有两个以上的连续因数，必然包含2*3；

于是我采用了计算各种情况下连续因数相乘时，因数的最大值是多少（即小于INT_MAX），答案如下：


<strong>//下面是质因素数组，虽然最后没有对AC提供帮助，但是可以优化时间复杂度
//偶数情况下，除了2，其他情况下至少有两个连续的因数，2*3
//当已经有2个因数后，接下来只需要求3个因数的情况，在连续3个因数的情况下，满足要求的最大值是1287*1288*1289，所以取边界值1290
//当已经有3个连续因素后，接下来只需要求4个因数的情况，在连续4个因素的情况下，满足要求的最大值是211*212*213*214，所以取边界值215
//其他同理
vector<int> maxFactor = { INT_MAX, n, (int)((double)sqrt(n) + 1), 1290, 215, 73, 35, 21, 14, 10, 0 };//3~13</strong>

3）由这道题目想到的其他问题：

连续两个数相乘，肯定可以被2整除，因为连续的两个数，必然包含偶数

连续三个数相乘，肯定可以被6整除（lcm（2，3）），因为连续的三个数，必然覆盖3的倍数和2的倍数

连续四个数相乘，肯定可以被12整除（lcm（2，3，4）），连续的三个数，必然覆盖2，3，4的倍数

连续若干个数都符合上述特征。

时间限制

400 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3*5*6*7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.

Input Specification:

Each input file contains one test case, which gives the integer N (1<N<2³¹).

Output Specification:

For each test case, print in the first line the maximum number of consecutive factors. Then in the second line, print the smallest sequence of the consecutive factors in the format “factor[1]*factor[2]*…*factor[k]”, where the factors are listed in increasing order, and 1 is NOT included.

Sample Input:

Sample Output:

3
5*6*7

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
//2147483646
void dfsFactor(long long n, long long preNum, vector<int>&factor, vector<vector<int>>&ans,int&factorSize)
{
	if (n % (preNum + 1) == 0)
	{//因数连续，继续DFS
		factor.push_back(preNum + 1);
		dfsFactor(n / (preNum + 1), preNum + 1, factor, ans, factorSize);
	}
	else if (!factor.empty() && factor.size() > factorSize)
	{//不连续时，如果连续因数的数量大于上次最大值，则压入答案中
		factorSize = factor.size();
		ans.push_back(factor);
	}
}
bool cmp(const vector<int>&a, const vector<int>&b)
{
	if (a.size() > b.size())
		return true;
	else if (a.size() == b.size() && a[0] < b[0])
		return true;
	else return false;
}
int main(void)
{
	//分为奇数和偶数情况，奇数情况，肯定不能被6整除，最多只有一个因素，因此分情况处理
	int n;
	cin >> n;
		if (n % 2 == 1)
		{//奇数情况下，采用质因素分解的算法
			/*
			情况一：当n是素数时，n的质因素要么是n本身
			情况二：在除去最大质因素的情况下，一定小于等于sqrt（n），如2*17=34，sqrt（34）=5，除去最大质因素17，剩下的质因素小于5 
			*/
			int temp = (int)((double)sqrt(n) + 1);
			for (int i = 2; i <= temp; ++i)
			{
				if (n%i == 0)
				{
					cout << "1" << endl;
					cout << i << endl;
					return 0;//直接返回
				}
			}
			cout << "1" << endl;
			cout << n << endl;

		}
		else
		{
			//下面是质因素数组，虽然最后没有对AC提供帮助，但是可以优化时间复杂度
			//偶数情况下，除了2，其他情况下至少有两个连续的因数，2*3
			//当已经有2个因数后，接下来只需要求3个因数的情况，在连续3个因数的情况下，满足要求的最大值是1287*1288*1289，所以取边界值1290
			//当已经有3个连续因素后，接下来只需要求4个因数的情况，在连续4个因素的情况下，满足要求的最大值是211*212*213*214，所以取边界值215
			//其他同理
			vector<int> maxFactor = { INT_MAX, n, (int)((double)sqrt(n) + 1), 1290, 215, 73, 35, 21, 14, 10, 0 };//3~13
			vector<int> factor(0);
			vector<vector<int>>ans(0);
			int factorSize = 0;

			for (long long i = 1; i <= min(n, maxFactor[factorSize + 1]); i++)
			{
				if (n % (i + 1) == 0)
				{
					dfsFactor(n, i, factor, ans, factorSize);
					factor.clear();
				}
			}
			sort(ans.begin(), ans.end(), cmp);
			cout << ans[0].size() << endl;
			for (int i = 0; i < ans[0].size(); i++)
			{
				cout << ans[0][i];
				if (i != ans[0].size() - 1)
					cout << "*";
			}
			cout << endl;
		}
	return 0;
}

1095. Cars on Campus (30)

1.事件模拟。

2.首先读取所有的汽车记录数据，筛选出合理的进入和离开时间，放到一个vector里面，对这个vector进行排序处理，进入时间早的放在前面。

3.对每一秒进行模拟，已经进入的车辆用一个小根堆进行存储维护，离开时间早的，排在堆顶。

3.取下一次进入校园车辆的时间，下一次离开校园车辆的时间，下一次查询的时间，取三者的最小值，直接跳那个时间点，进行处理，优化时间复杂度。

4.一开始第4个例子超时，后来采用了第3点中提到的优化方法，结果还是超时，考虑到查询量较大，于是把查询的cout改为printf，就通过了。

Each input file contains one test case. Each case starts with two positive integers N (<= 10000), the number of records, and K (<= 80000) the number of queries. Then N lines follow, each gives a record in the format。

1）最原始的一秒一秒进行模拟：

2）采用第3点的方法进行优化，还是超时

3）不进行时间事件模拟处理，仅输入数据，各测试点耗费时间：

4）最后把cout改为printf，通过：

时间限制

220 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

Zhejiang University has 6 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.

Input Specification:

Each input file contains one test case. Each case starts with two positive integers N (<= 10000), the number of records, and K (<= 80000) the number of queries. Then N lines follow, each gives a record in the format

plate_number hh:mm:ss status

where plate_number is a string of 7 English capital letters or 1-digit numbers; hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59; and status is either in or out.

Note that all times will be within a single day. Each “in” record is paired with the chronologically next record for the same car provided it is an “out” record. Any “in” records that are not paired with an “out” record are ignored, as are “out” records not paired with an “in” record. It is guaranteed that at least one car is well paired in the input, and no car is both “in” and “out” at the same moment. Times are recorded using a 24-hour clock.

Then K lines of queries follow, each gives a time point in the format hh:mm:ss. Note: the queries are given in ascending order of the times.

Output Specification:

For each query, output in a line the total number of cars parking on campus. The last line of output is supposed to give the plate number of the car that has parked for the longest time period, and the corresponding time length. If such a car is not unique, then output all of their plate numbers in a line in alphabetical order, separated by a space.

Sample Input:

16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00

Sample Output:

1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09

AC代码：

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

struct CarNode{
	vector<pair<string, bool>> record;
	vector<pair<string, string>> validRecord;
	CarNode() :record(0), validRecord(0){};
};
struct RecordNode{

	string id, in, out;
	RecordNode() :id(""), in(""), out(""){};
	RecordNode(string i,string a,string b) :id(i), in(a), out(b){};

};
bool cmpRecord(const pair<string, bool>&a, const pair<string, bool>&b)
{
	return a.first < b.first;
}
bool cmpAllRecord(const RecordNode&a, const RecordNode&b)
{
	return a.in < b.in;
}
int char2int(char a)
{
	return a - '0';
}
int time2sec(string str)
{
	return (char2int(str[0]) * 10 + char2int(str[1])) * 60*60 + (char2int(str[3]) * 10 + char2int(str[4])) * 60 + char2int(str[6]) * 10 + char2int(str[7]);
}
struct cmp
{
	bool operator()(const RecordNode&a, const RecordNode&b)
	{
		return time2sec(a.out) > time2sec(b.out);
	}
};
bool cmpPark(const pair<string, int>&a, const pair<string, int>&b)
{
	if (a.second > b.second) return true;
	else if (a.second == b.second&&a.first < b.first) return true;
	else return false;
}
string sec2str(int a)
{
	int hour = a / 3600;
	int min = (a - hour * 3600) / 60;
	int sec = a - hour * 3600 - min * 60;

	char c1 = hour / 10 + '0';
	char c2 = hour % 10 + '0';
	string ans = "";
	ans += c1;
	ans += c2;
	ans += ":";
	c1 = min / 10 + '0';
	c2 = min % 10 + '0';
	ans += c1;
	ans += c2;
	ans += ":";
	c1 = sec / 10 + '0';
	c2 = sec % 10 + '0';
	ans += c1;
	ans += c2;
	return ans;

}
int main(void)
{
	int recordSum,querySum;
	cin >> recordSum >> querySum;

	map<string, CarNode> car;//建立car 哈希表
	for (int i = 0; i < recordSum; i++)
	{//输入记录
		string id, time, flag;
		cin >> id >> time >> flag;
		//0为进入，1为出去
		if (flag == "in")
			car[id].record.push_back({ time, 0 });
		else
			car[id].record.push_back({ time, 1 });
	}
	vector<RecordNode> allRecord(0);
	for (map<string, CarNode>::iterator ite = car.begin(); ite != car.end(); ite++)
	{//筛选出有效记录，统一发到allRecord容器中
		sort(ite->second.record.begin(), ite->second.record.end(), cmpRecord);
		for (int i = 0; i < ite->second.record.size() - 1; i++)
		{
			if (!ite->second.record[i].second && ite->second.record[i + 1].second)
			{//相邻的两条记录，第一条为进入，第二条为离开，则合理
				allRecord.push_back(RecordNode(ite->first, ite->second.record[i].first, ite->second.record[i + 1].first));
			}
		}
	}
	//根据进入时间，对有效记录进行排序
	sort(allRecord.begin(), allRecord.end(), cmpAllRecord);
	
	//输入查询记录
	vector<string> queryRecord(querySum);
	for (int i = 0; i < querySum; i++)
	{
		cin >> queryRecord[i];
	}
	sort(queryRecord.begin(), queryRecord.end());

	int parkCar = 0;
	int next = 0;
	int queryIdx = 0;
	map<string, int> parkTime;

	//优先队列，记录了在校园内的车，以离开时间大小建立小根堆
	priority_queue<RecordNode, vector<RecordNode>, cmp> inCampus;
	int maxTime = 0;
	string maxID = "";
	vector<pair<string, int>> maxTimeCar(0);
	for (int i = 0; i < 24 * 3600; i++)
	{
		while (next<allRecord.size() && time2sec(allRecord[next].in) == i)
		{//查看当前是否有车进入校园
			inCampus.push(allRecord[next]);
			next++;
			parkCar++;
		}
		while (!inCampus.empty() && time2sec(inCampus.top().out) == i)
		{//查看当前是否有车离开校园
			//记录停车时间
			parkTime[inCampus.top().id] += time2sec(inCampus.top().out) - time2sec(inCampus.top().in);

			if (parkTime[inCampus.top().id] >= maxTime)
			{
				maxTimeCar.push_back({ inCampus.top().id, parkTime[inCampus.top().id] });
				maxTime = parkTime[inCampus.top().id];
				maxID = inCampus.top().id;
			}

			inCampus.pop();
			parkCar--;
		}
		if (queryIdx<queryRecord.size() && time2sec(queryRecord[queryIdx]) == i)
		{
			queryIdx++;
			printf("%d\n",parkCar);//刚开始采用了cout输出，结果超时，改为printf后不超时
		}
		int inTime = 24 * 3600, outTime = 24 * 3600, queryTime = 24 * 3600;
		if (next < allRecord.size())//记录下一个需要处理的时间点
			inTime = time2sec(allRecord[next].in);
		if (!inCampus.empty())//记录下一个需要处理的时间点
			outTime = time2sec(inCampus.top().out);
		if (queryIdx < queryRecord.size())//记录下一个需要处理的时间点
			queryTime = time2sec(queryRecord[queryIdx]);

		int nextTime = min(min(inTime,outTime),queryTime);
		i = nextTime - 1;//因为for循环里面有i++，所以这里不需要直接达到nextTime

	}
	//对最大停车的车辆数组进行排序
	sort(maxTimeCar.begin(), maxTimeCar.end(), cmpPark);
	for (int i = 0; i < maxTimeCar.size(); i++)
	{
		if (maxTimeCar[i].second == maxTime)
		{//停车时间等于最大值，则输出
			cout << maxTimeCar[i].first << " ";//输出ID
		}
		else//不等，则直接跳出循环
			break;
	}
	cout << sec2str(maxTime) << endl;
	return 0;
}