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;
}

PAT (Advanced Level)-1002. A+B for Polynomials (25)

PAT (Advanced Level)-1002. A+B for Polynomials (25)

1002. A+B for 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

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.
每次输入包含两行内容。每一行都包含一个多项式的信息:
K N1 aN1 N2 aN2 … NK aNK

K是多项式共包含几项。K满足[1, 10]
Nk是多项式项的指数。Nk满足0 <= NK < … < N2 < N1 <=1000
aNk是多项式中Nk次项的系数

程序输入默认严格按照从高次幂项到低次幂项依次输入。

Output

For each test case you should output the sum 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 to 1 decimal place.

输出的是两行多项式的和。输出格式和输入格式相同。 需要注意,系数严格保留一位小数。

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 2 1.5 1 2.9 0 3.2

解读

这个过程,用数组实现最简单。
数组的第i位刚好存第i次方幂项的系数。

所以我们创建一个1001位的double型数组(初始化为0)

  • (从第0次方项(常数项)到第1000次方项,一共1001项)
  • (系数要保留一位小数)

然后我们进行输入

  1. 第一次输入,先用一个量存输入有多少项。(比如第1次就是k1项)
  2. 然后进行对多项式信息输入的存储,一个量存指数,一个量存系数。
  3. 输入完一组指数和系数之后,向数组对应的位置存好系数就好。
  4. 待输入完后,进行第二次输入。同样的先用一个量存输入有多少项(k2)。
  5. 重复第2,3步。
  6. 需要注意的是,由于我们数组初始就全部为0,所以我们在向对应位置存入的时候,可以直接进行对应的加和(见代码)

然后输出

  1. 输出时候,先要计算一下加和之后还有多少项。
    • 这个时候我们就需要统计数组里面存入的数据有多少项不为零。计数,然后输出计数的数量。
  2. 然后我们输出多项式信息,即输出数组。
    • 由于高次项在前,而数组是升序排列的,所以我们对数组需要反着来一个个输出。
    • 输出所有不为0的项(即多项式的aNk),同时输出当前项所在数组的位数(即多项式的Nk)

完整代码

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

int main()
{
  double array[1001];// 创建数组
  //数组初始化为0
  for (int i = 0; i < 1001; i++)
  {
    array[i] = 0;
  }// 完成初始化
  
  int count = 0;// 计数变量
  
  //第一次输入开始
  int k1;
  cin >> k1;
  for (int i = 0; i < k1; i++)// 只进行k1次输入,因为只有k1项
  {
    int exponents;// 指数
    cin >> exponents;
    double coefficients;// 系数
    cin >> coefficients;

    array[exponents] += coefficients;// 等同于array[exponents] = array[exponents] + coefficients;
  }// 第一次输入结束

  // 第二次输入开始
  int k2;
  cin >> k2;
  for (int i = 0; i < k2; i++)
  {
    int exponents;
    cin >> exponents;
    double coefficients;
    cin >> coefficients;

    array[exponents] += coefficients;// 注意,这个时候就进行的两行的加和。
  }// 第二次输入结束

  //开始计算有多少项
  for(int i=0;i<1001;i++)
  {
    if (array[i] != 0)
    {
      count += 1;
    }
  }
  cout << count;//输出总项数 K
  
  //输出数组
  for (int i = 1000; i >= 0; i--)// 反序
  {
    if (array[i] != 0)
      cout <<fixed << setprecision(1) << " " << i << " " << array[i];
  }

  return 0;
}

PAT (Advanced Level)-1001. A+B Format (20)

PAT (Advanced Level)-1001. A+B Format (20)

1001. A+B Format (20)

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

Calculate a + b and output the sum in standard format — that is, the digits must be separated into groups of three by commas (unless there are less than four digits).
计算a+b并在标准格式下输出这个和。(这个和的数据应该分为三部分:前面的几位数,逗号,后三位。除非数字小于三位数)

Input

Each input file contains one test case. Each case contains a pair of integers a and b where -1000000 <= a, b <= 1000000. The numbers are separated by a space. 程序接受输入的两个数a和b,a和b都满足在区间[-1000000, 1000000]。输入的两个数用空格间隔开。

Output

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

在一行内输出a和b的和。并且这个和应该用标准格式写出。 (注意上面的题目要求,这个和应该分为三部分:后面三位,逗号,和剩下的前面的几位数。)

Sample Input

-1000000 9

Sample Output

-999,991


解读

程序有两个输入的变量a,b
计算a+b(我们记sum=a+b)
一个输出变量sum,依照格式分为三部分。

思路如下 :

  1. 判断sum是否满足大于三位数。
  2. 如果小于三位数:
    直接输出sum。
  3. 如果大于三位数,小于七位数:
    将sum拆分成两部分head(前面三位)和tail(后面三位)。
    • tail后三位我们可以直接对sum对1,000取余获得(需要取绝对值)。
    • head前三位我们可以对sum除以1,000后取余对1000获得。(因为int型变量没有小数点精度,所以sum除以1,000会舍弃后最后三位数的部分)
    • 输出head、逗号(,)、tail即可。
  4. 如果是七位数: 将sum拆分为三部分,第七位,中间三位(head),后面三位(tail)。
    • 最高位我们可以让sum除以1,000,000来舍弃后面六位数来。(原理见上面int型变量)
    • 中间三位head前三位我们可以对sum除以1,000后对1000取余获得。(需要取绝对值)
    • 后三位我们可以直接对sum对1,000取余获得。(需要取绝对值)
    • 输出第七位、逗号(,)、head、逗号(,)、tail即可。
  • 这里需注意的是,对于100,009这样的数,取后三位应该是009,但是上述办法我们计算得到的tail数值是9(自动舍弃前面的0)。这个是个需要注意的问题(对于中间三位数,也会有类似的情况),我们在cout输出的时候进行修正。
  • 修正方法,用setw(3)来限定每次输出限定的位数为3。不足位用setfill(‘0’)代码补充为0
  • 另外,不论合适对sum原始数据进行修改,都会保留负号(如果是负数的话),所以我们对于分部的部分在输出时候就需要用abs函数取绝对值。

完整代码

#include<iostream>  
#include<iomanip>  
using namespace std;  
  
int main()  
{  
    int a, b,sum;  
    int tail=0, head=0;  
    cin >> a >> b;  
    sum = a + b;  
    tail = sum % 1000;  //计算 个十百位(123位) 上的数字
    //判断是否大于三位数
    if (sum/1000==0)  //三位数之内
        cout << tail << endl;  
    else{  
        head = (sum / 1000) % 1000;  //取 千万十万位(456位) 上的数字
  
        if ((sum / 1000) /1000 == 0)  //六位数之内
            cout << head << "," << setw(3)<<setfill('0')<<abs(tail) << endl;  
        else  //七位数
            cout << sum/1000000 << "," << setw(3)<<setfill('0')<<abs(head) << "," <<setw(3)<<setfill('0')<< abs(tail) << endl;  
    }  
    return 0;  
}