PAT (Advanced Level)-1041. Be Unique (20)

PAT (Advanced Level)-1041. Be Unique (20)

1041. Be Unique (20)

时间限制
100 ms
内存限制
65536 kB
代码长度限制 16000 B
判题程序 Standard
作者
CHEN, Yue


Being unique is so important to people on Mars that even their lottery is designed in a unique way. The rule of winning is simple: one bets on a number chosen from [1, 104]. The first one who bets on a unique number wins. For example, if there are 7 people betting on 5 31 5 88 67 88 17, then the second one who bets on 31 wins.


Input Specification:

Each input file contains one test case. Each case contains a line which begins with a positive integer N (<=105) and then followed by N bets. The numbers are separated by a space.

Output Specification:

For each test case, print the winning number in a line. If there is no winner, print “None” instead.

Sample Input 1:

7 5 31 5 88 67 88 17

Sample Output 1:

31

Sample Input 2:

5 888 666 666 888 888

Sample Output 2:

None

解读

遍历寻找重复。 用map的捆绑对应,可以将一个数字和它本身出现的次数绑定起来。减少搜索量。

完整代码

#include<iostream>
#include<vector>
#include<map>

int main()
{
	int N;
	std::cin >> N;
	std::vector<int> record_num;
	std::map<int, int> record_unique;
	for (int i = 0; i < N; i++)
	{
		int num;
		std::cin >> num;
		record_unique[num]++;
		record_num.push_back(num);
	}

	bool flag_num = false;
	int result;
	for (int i = 0; i < record_num.size(); i++)
	{
		if (record_unique[record_num[i]] == 1)
		{
			flag_num = true;
			result = record_num[i];
			break;
		}
	}

	if (flag_num == false)
	{
		std::cout << "None" << std::endl;
	}
	else
	{
		std::cout << result << std::endl;
	}
	return 0;
}

PAT (Advanced Level)-1027. Colors in Mars (20)

PAT (Advanced Level)-1027. Colors in Mars (20)

1027. Colors in Mars (20)

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序 Standard
作者 CHEN, Yue


People in Mars represent the colors in their computers in a similar way as the Earth people. That is, a color is represented by a 6-digit number, where the first 2 digits are for Red, the middle 2 digits for Green, and the last 2 digits for Blue. The only difference is that they use radix 13 (0-9 and A-C) instead of 16. Now given a color in three decimal numbers (each between 0 and 168), you are supposed to output their Mars RGB values.


Input

Each input file contains one test case which occupies a line containing the three decimal color values.

Output

For each test case you should output the Mars RGB value in the following format: first output “#”, then followed by a 6-digit number where all the English characters must be upper-cased. If a single color is only 1-digit long, you must print a “0” to the left.

Sample Input

15 43 71

Sample Output

#123456

解读

单纯的一道十进制转换十三进制的题目。而且十三进制下不超过两位数。
进制转换的方式不做累述,PAT (Advanced Level)-1019. General Palindromic Number (20)的解读部分。

由于只有两位数的十三进制数,且有ABC这样的字符出现,所以最终我选择使用string字符串处理所有的火星数,0-9,A-C全部存入mars_base中直接做返回调用。可以减少此题中的额外处理。

完整代码

#include<iostream>
#include<string>
#include<cstring>

std::string mars_base[] = { "0","1","2","3","4","5","6","7","8","9","A","B","C" };

std::string transform_to_mars(int n)
{
	std::string RGB_mars;
	int base = 0, higher = 0;
	base = n % 13;
	higher = n / 13;

	RGB_mars = mars_base[higher] + mars_base[base];

	return RGB_mars;
}

int main()
{
	int R, G, B;
	std::cin >> R >> G >> B;

	std::string mR, mG, mB;
	mR = transform_to_mars(R);
	mG = transform_to_mars(G);
	mB = transform_to_mars(B);

	std::cout << "#" << mR << mG << mB << std::endl;

	return 0;
}

PAT (Advanced Level)-1100. Mars Numbers (20)

PAT (Advanced Level)-1100. Mars Numbers (20)

1100. Mars Numbers (20)

时间限制
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

解读

本题实际上是一道进制转换的问题,13进制。麻烦之处在于,mars数字需要用字符串来表示,所以应该做好转化进制时的数字和字符串的对应。
另外就是输出格式 火星数的整两位数,后面没有空格,所以对于整两位数和其他两位数需要区分处理。

完整代码

#include<iostream>
#include<string>
#include<sstream>
#include<cstring>
#include<vector>

// [mars_base] records the 0-12 on the mars
std::string mars_base[] = { "tret","jan","feb","mar","apr","may","jun","jly","aug","sep","oct","nov","dec" };
// [mars_higher] records the next higher digit on the mars
std::string mars_higher[] = { "tam","hel","maa","huh","tou","kes","hei","elo","syy","lok","mer","jou" };
//using namespace std;

std::string earth_to_mars(int x)
{
	if (x / 13 == 0)// 0-12
	{
		return mars_base[x];
	}
	else if (x / 13 != 0 && x%13 == 0)// 13 26 39 ....146 except 0, because 0 is in the [mars_base]
	{
		return mars_higher[x / 13 - 1];
	}
	else// the rest of double_digit which uses " "(space)
	{
		return mars_higher[x / 13 - 1] + " " + mars_base[x % 13];
	}
}

int mars_to_earth(std::string x)
{
	int num_0 = x.find(" ");// find out whether there is a " "(space) in the string 
	if (num_0 == std::string::npos)
	{
		for (int i = 0; i < 13; i++)
		{
			if (mars_base[i] == x)
			{
				return i;
			}
			else if (mars_higher[i] == x)
			{
				return (i + 1) * 13;
			}
		}
	}
	else
	{
		// to split the string in two with " "(space)
		std::string str1, str2;
		std::istringstream is(x);
		is >> str1 >> str2;

		int high=0, base=0;
		for (; high < 12; high++)
		{
			if (str1 == mars_higher[high])
				break;
		}
		for (; base < 13; base++)
		{
			if (str2 == mars_base[base])
			{
				break;
			}
		}
		return (high + 1) * 13 + base;
	}
}

int main()
{
	int N;
	std::cin >> N;
	getchar();// handle the ENTER in the cin after you input N
	std::vector<std::string> input(N);
	for (int i = 0; i < N; i++)
	{
		getline(std::cin,input[i]);
	}

	for (int j = 0; j < N; j++) 
	{
		if (input[j][0] <= '9' && input[j][0] >= '0') // earth
		{  
			std::cout << earth_to_mars(std::stoi(input[j])) << std::endl;
		}
		else // mars
		{
			std::cout << mars_to_earth(input[j]) << std::endl;
		}
	}
	return 0;
}

PAT (Advanced Level)-1035. Password (20)

PAT (Advanced Level)-1035. Password (20)

1035. Password (20)

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue


To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.


Input Specification:

Each input file contains one test case. Each case contains a positive integer N (<= 1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.

Output Specification:

For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line “There are N accounts and no account is modified” where N is the total number of accounts. However, if N is one, you must print “There is 1 account and no account is modified” instead.

Sample Input 1:

3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa

Sample Output 1:

2
Team000002 RLsp%dfa
Team000001 R@spodfa

Sample Input 2:

1
team110 abcdefg332

Sample Output 2:

There is 1 account and no account is modified

Sample Input 3:

2
team110 abcdefg222
team220 abcdefg333

Sample Output 3:

There are 2 accounts and no account is modified

解读

本题目考查点在于对字符串的检索处理,同时也考查对于输入数据的保存。
易忽视的地方: C++中,开数组存储的数组大小,cin缓冲流存在 特殊情况N=0的时候。

另外想吐槽的一句是:这个输出结束之后为什么没有句号啊!!我带了句号为什么还对了三个检查点!!!害我检查问题查了好久才注意到句末不带标点的!!!!

完整代码

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

typedef struct user
{
	bool legal;
	char Account[11];
	char Password[11];
}User_info;

//determind if the password is legal, and modify it if illegal.
bool Is_legal(user& User_info)
{
	bool legal = true;
	int len = strlen(User_info.Password);

	for (int i = 0; i < len; ++i)
	{
		if (User_info.Password[i] == '1')
		{
			User_info.Password[i] = '@';
			legal = false;
		}
		if (User_info.Password[i] == '0')
		{
			User_info.Password[i] = '%';
			legal = false;
		}
		if (User_info.Password[i] == 'l')
		{
			User_info.Password[i] = 'L';
			legal = false;
		}
		if (User_info.Password[i] == 'O')
		{
			User_info.Password[i] = 'o';
			legal = false;
		}
	}
	return legal;
}

int main()
{
	int N;
	cin >> N;
	vector<User_info> User_infoVec(N);

	int legal = 0;
	for (int i = 0; i < N; ++i)
	{
		cin >> User_infoVec[i].Account;
		cin >> User_infoVec[i].Password;
		if (Is_legal(User_infoVec[i]))
		{
			User_infoVec[i].legal = true;
			legal++;
		}
		else
		{
			User_infoVec[i].legal = false;
		}
	}

	//Output
	if (legal == N)
	{
		if (N <= 1)
		{
			cout << "There is " << N << " account and no account is modified" << endl;
		}
		else
		{
			cout << "There are " << N << " accounts and no account is modified" << endl;
		}
	}
	else
	{
		cout << N - legal << endl;
		for (int i = 0; i < N; ++i)
		{
			if (User_infoVec[i].legal == false)
			{
				cout << User_infoVec[i].Account << " " << User_infoVec[i].Password << endl;
			}
		}
	}
	return 0;
}

PAT (Advanced Level)-1004. Counting Leaves (30)

PAT (Advanced Level)-1004. Counting Leaves (30)

1004. Counting Leaves (30)

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue


A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.


Input

Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

Output

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line.

Sample Input

2 1
01 1 02

Sample Output

0 1

解读

题目条件无非就是构建并存储树,但是如何处理题目中输入的父节点和子节点是一个算法中的关键。

采用map容器,把每一个节点和存储它的子节点容器进行关联,可以方便操作。

对于存储之后的统计每层级的叶子数,可以采用深度优先的算法,通过临时变量level,在迭代中不干扰其他支线的统计,保证同级的叶子最终均会统计入LeavesOfLevel数组中。

但是这样做会有一个麻烦,由于迭代的过程level在不同的环节是不同的值,无法直接知晓探索到最深时候level的值,所以我们通过辅助统计的变量LeavesCount记录每一级的叶子数,并在输出时候进行累加,直到LeavesCount与总叶子数Leaves相同,即可停止对LeavesOfLevel数组的输出。

完整代码

#include<iostream>
#include<vector>
#include<map>

using namespace std;

map<int, vector<int>> List;

void DFS(int, int, int[]);

int main()
{
	int N, M;
	int LeavesOfLevel[101] = { 0 };//统计每级上面的叶子节点

	//输入部分
	cin >> N >> M;	
	for (int i = 0; i < M; i++)
	{
		int ID, K, ID_Son;
		cin >> ID >> K;
		for (int j = 0; j < K; j++)
		{
			cin >> ID_Son;
			List[ID].push_back(ID_Son);
		}
	}

	int Leaves = N - M;//统计总叶子数
	//深度优先搜索
	DFS(1, 0, LeavesOfLevel);

	//输出部分
	int LeavesCount = LeavesOfLevel[0];//辅助记录
	cout << LeavesOfLevel[0];
	for (int i = 1; LeavesCount < Leaves; i++)
	{
		cout << " " << LeavesOfLevel[i];
		LeavesCount += LeavesOfLevel[i];
	}
	
	return 0;
}

//深度优先,统计每层级的叶子数
void DFS(int id, int level,int LeavesOfLevel[])
{
	if (List[id].empty())
	{
		LeavesOfLevel[level]++;
		return;
	}

	vector<int>::iterator item = List[id].begin();

	for (; item != List[id].end(); item++)
	{
		DFS(*item, level+1, LeavesOfLevel);
	}
}