PAT (Advanced Level)-1009. Product of Polynomials (25)

PAT (Advanced Level)-1009. Product of Polynomials (25)

1009. Product of Polynomials (25)

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


This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

解读

从多项式乘法的法则出发,就是对每一项相乘之后求和。然后再将对应的结果放入存储的位置中去。

实现方法和思维与加法类似。用顺序表来存放最终结果,病输出系数不为零的项。

完整代码

#include<iostream>  
#include<iomanip> 
#include<vector>  
#include<algorithm>  
using namespace std;

typedef struct Node
{
	double sum;
	int e;
}Node;
#define MAX 3000  
int main()
{
	int n1, n2;
	cin >> n1;

	std::vector<Node> a(n1);
	for (int i = 0; i < n1; ++i)
	{
		cin >> a[i].e;
		cin >> a[i].sum;
	}
			
	cin >> n2;
	std::vector<Node> b(n2);
	for (int i = 0; i < n2; ++i)
	{
		cin >> b[i].e;
		cin >> b[i].sum;
	}
	//product  
	std::vector<double> p;
	p.assign(MAX + 1, 0.0);
	for (int i = 0; i < n1; ++i)
	{
		for (int j = 0; j < n2; ++j)
		{
			Node tmp;
			tmp.e = a[i].e + b[j].e;
			tmp.sum = a[i].sum*b[j].sum;
			p[tmp.e] += tmp.sum;
		}
	}
	//output  
	int cnt = 0;
	for (int i = MAX; i >= 0; --i)
	{
		if (std::fabs(p[i]) > 1e-6)
			cnt++;
	}
	printf("%d", cnt);
	for (int i = MAX; i >= 0; --i)
	{
		if (std::fabs(p[i]) > 1e-6)
			cout << fixed << setprecision(1) << " " << i << " " << p[i];
	}
	printf("\n");
	
	return 0;
}

PAT (Advanced Level)-1008. Elevator (20)

PAT (Advanced Level)-1008. Elevator (20)

1008. Elevator (20)

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


The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.

For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100.

Output Specification:

For each test case, print the total time on a single line.

Sample Input:

3 2 3 1

Sample Output:

41



解读

完整代码

#include<iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;
	int now = 0, next = 0, totalTime = 0;
	while (N--) 
	{
		cin >> next;
		if (next > now) 
		{
			totalTime += (next - now) * 6 + 5;
		}
		else
		{
			totalTime += (now - next) * 4 + 5;
		}
		now = next;
	}
	cout << totalTime;
	return 0;
}

PAT (Advanced Level)-1006. Sign In and Sign Out (25)

PAT (Advanced Level)-1006. Sign In and Sign Out (25)

1006. Sign In and Sign Out (25)

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


At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:

Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:

ID_number Sign_in_time Sign_out_time where times are given in the format HH:MM:SS, and ID number is a string with no more than 15 characters.

Output Specification:

For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.
Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

Sample Input:

3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40

Sample Output:

SC3021234 CS301133

解读

读完题目后,应该可以发现,这其实就是一个关于字符串大小比较的问题。 (将时间信息当做字符串处理)

因为采用了标准的24小时制时间输入,所以在比较两段时间时候,就是从第一位逐位进行大小比较,小的时间小,大的时间大,相同则比较下一位。

看到这块,应该能类比到字符串大小的比较吧,两者的处理方式是相同的。

也是采用从第一位开始,逐位比较大小,ASCII值小则字符串小,,ASCII值大则字符串大,相同则比较下一位。

又因为C++中的string类型可以直接使用<,>判断符进行string字符串的比较,所以我们在创建变量时候考虑这一点,在比较过程中可以更方便。

完整代码

#include<iostream>
#include<string>

using namespace std;

//创建结构体,来存储每次输入的员工记录ID和登入时间和登出时间
struct Record
{
	char id[15];
	string signInTime;
	string signOutTime;
};

int main()
{
    //题目中要求的变量M
	int M;
	cin >> M;

    //动态申请大小为M的结构体数组(数组的每个元素都是一个结构体)
	Record *recordList = new Record[M];
	
	//标记开门和关门的ID
	int unlockID=0, lockID=0;
	
	//比较大小时的临时变量
	string unlock, lock;
	
	//输入和比较同时进行
	for (int i = 0; i < M; i++)
	{
		cin >> recordList[i].id;
		cin >> recordList[i].signInTime;
		cin >> recordList[i].signOutTime;

		
        //初次赋值时候,初始化用来比较大小的临时量
		if (i == 0)
		{
			unlock = recordList[i].signInTime;
			lock = recordList[i].signOutTime;
		}
        
        //比较开门时间
		if (unlock > recordList[i].signInTime)
		{
			unlock = recordList[i].signInTime;
			unlockID = i;
		}
        
        //比较关门时间
		if (lock < recordList[i].signOutTime)
		{
			lock = recordList[i].signOutTime;
			lockID = i;
		}
	}

	cout << recordList[unlockID].id << " " << recordList[lockID].id;
	
	return 0;
}

PAT (Advanced Level)-1005. Spell It Right (20)

PAT (Advanced Level)-1005. Spell It Right (20)

1005. Spell It Right (20)

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


Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.


Input Specification:

Each input file contains one test case. Each case occupies one line which contains an N (<= 10100).

Output Specification:

For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.

Sample Input:

12345

Sample Output:

one five

解读

这道题目要求我们从输入的一串数字中对每个数字进行加和,这就要明确一点:
这样的一串数字累加定然和int型操作不一样。
我们首先需要能将这一串数字逐位进行拆分并单独操作。
故而我们有char字符数组和string类型可以实现这样的功能。

但是我们在这个问题中需要处理的一点就是:字符型的0123456789和作为数值的0123456798是有区别的,两者需要依照ASCII码制进行转化,比如字符型的’1’要变为1就需要进行如下的操作

'1'-'0'

两者的ASCII码制的差值,即为字面数字值。

还有一个需要注意的问题就是,int和char数组和string的互换需要熟记
sstream流的功能

完整代码

#include<iostream>
#include<cstring> //注意PAT用的C++环境为linux下的g++,string为C语言中的string.h头文件,与C++的string头文件有区别。C++中使用cstring
#include<sstream>

using namespace std;

char spell[10][10] = { "zero","one","two","three","four","five","six","seven","eight","nine" };

int main()
{
	char inputnum[101];//10的100次方,一共是101位数,切记
	cin >> inputnum;
	
	int sum_temp = 0;//记载数目总和
	int len = 0;//记载长度

	len = strlen(inputnum);
	for (int i = 0; i < len; i++)
		sum_temp += (inputnum[i] - '0');//转化为int数据进行累加
    
    //int转string的方法
	string resultNum;
	stringstream ss;
	ss << sum_temp;
	ss >> resultNum;
	
	//输出string
	len = resultNum.length();

	for (int i = 0; i < len; i++)
	{
		cout << spell[((int)resultNum[i] - '0')];
		//让我们注意一下这里spell为存储英文的数组,
		//(int)resultNum[i]是强制将string中的字符转化为int
		//(这里的int转化后是ASCII中对应的码制)与字符'0'相减才能得到字面的int数值
		
		if (i < len - 1)//最后的末尾不加空格
		{
			cout << " ";
		}
	}

	return 0;
}

PAT (Advanced Level)-1003. Emergency (25)

PAT (Advanced Level)-1003. Emergency (25)

1003. Emergency (25)

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


As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

作为一个城市的紧急救援队长,你会得到一个你所在地区的特制地图。这张地图表示由一些道路连接的几个分散的城市。每个城市拥有的救援队数量和任何两城市之间的道路的长度在地图上标出。当有来自其他城市的紧急呼叫时,您的工作是尽可能快地将您的人带到该地方,同时尽可能多地从途径的地区带上更多的人。


Input

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) – the number of cities (and the cities are numbered from 0 to N-1), M – the number of roads, C1 and C2 – the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

每次输入即一个测试案例。对于每个测试案例,第一行包含4个正整数:
N(<= 500)是城市的数量(城市从0到N-1编号), M 表示道路数量, C1和C2 分别是你目前所在的城市和你将要去救援的城市编号。
下一行包含N个整数,其中第i个整数表示第i个城市中的救援队伍的数量。
随后的M行,每行用c1,c2和L描述一条道路,它们分别是道路连接的两个城市城市和该道路的长度。
保证从C1到C2至少存在一条通畅的路径。

Output

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

对于每个测试案例,在一行中打印两个数字:C1和C2之间不同的最短路径的数量,以及在前往救援过程中可能收集到的最大救援队伍。
一行中的所有数字必须以正好一个空格分隔,并且在行末尾不允许有额外的空格。

Sample Input

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

Sample Output

2 4

解读

这道题目很显然的在考察“最短路径”算法,但是需要注意的是,题目中的最短路径并不只有一条,所以需要对原有算法进行稍微修改,以存储多条最短路径及路径信息。

完整代码

#include<iostream>       
#include<cstring>    
#include<algorithm>    
using namespace std;
const int MAX = 500;

//创建题目条件中所有输入用的变量
int N, M, C1, C2, startCity, endCity, length;
//定义存储救援队数目、距离、地图(邻接矩阵)、条件判断标注数组、输出结果数组
int v[MAX], dis[MAX], map[MAX][MAX], vis[MAX], ans[MAX];
//定义存储路径数组
long long cnt[MAX];

int main()
{
    //输入题目中的N、M、C1、C2
	cin >> N >> M >> C1 >> C2;

    //存储救援队数量
	for (int i = 0; i < N; i++) cin >> v[i];

    //初始化地图(邻接矩阵)为-1
	for (int i = 0; i < MAX; i++)
		for (int j = 0; j < MAX; j++)
			map[i][j] = -1;

    //初始化路径距离数组为-1
	for (int i = 0; i < MAX; i++)
		dis[i] = -1;

    //输入地图(邻接矩阵)信息
	while (M--)
	{
		cin >> startCity >> endCity >> length;
		map[startCity][endCity] = map[endCity][startCity] = length;
	}

    
	ans[C1] = v[C1]; dis[C1] = 0;  cnt[C1] = 1;

    //Dijkstra算法
	while (true)
	{
		int now = -1;
		for (int i = 0; i < N; i++)
		{
			if (!vis[i] && dis[i] != -1)
			{
				if (now == -1)
					now = i;
				else
					now = dis[now] < dis[i] ? now : i;
			}
		}

		if (now == -1) break;
		vis[now] = 1;

		for (int i = 0; i < N; i++)
		{
			if (map[now][i] != -1)
			{
				if (dis[i] == -1 || dis[i] > dis[now] + map[now][i])
				{
					dis[i] = dis[now] + map[now][i];
					cnt[i] = cnt[now]; 
					ans[i] = ans[now] + v[i];
				}
				else if (dis[i] == dis[now] + map[now][i])
				{
					cnt[i] += cnt[now];
					ans[i] = max(ans[i], ans[now] + v[i]);
				}
			}
		}
	}

	cout<<cnt[C2]<<" "<<ans[C2];
	return 0;
}