5.1 简单数学

2019-09-16 17:12 255人阅读评论(0)

2019年9月PAT - 练习笔记——5.1

以下页码标注的是阅读器中实际页码，而不是书本身自印的页码。

第5章入门篇（3）——数学问题

5.1 简单数学

注意

答案错误时考虑溢出的可能性

B1003 我要通过！
B1019 / A1069 数字黑洞
B1049 / A1104 数列的片段和
A1008 Elevator
A1049 Counting Ones

B1003 我要通过！

“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。

得到“答案正确”的条件是：
1. 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。
现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。

输入格式：

每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

输出格式：

每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

输入样例：
```
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
```
输出样例：
```
YES
YES
YES
YES
NO
NO
NO
NO
```
1. 我的
```
#include <iostream>
#include <string>

using namespace std;

bool Judge(const string&str, const int left, const int right)
{
	for (int i = left;i < right;++i) {
		if (str[i] != 'A') return false;
	}
	return true;
}

int main(void)
{
	int n = 0;
	cin >> n;
	
	string str = "";
	for (int ii = 0;ii < n;++ii) {
		cin >> str;
		
		int len = str.size();
		if (len < 3) {
			cout << "NO" << endl;
			continue;
		}
		int i = str.find('P', 0);
		if (i == string::npos) cout << "NO" << endl;
		else {
			if (i + 2 < len && str[i + 1] == 'A') {
				bool flaga = Judge(str, 0, i);
				if (!flaga) cout << "NO" << endl;
				// PAT APATA AAPATAA AAAPATAAA
				else if (str[i + 2] == 'T' && flaga && str.substr(0, i) == str.substr(i + 3, i)) cout << "YES" << endl;
				// xPATx -> xPAATxx -> xPAAATxxx……
				// PAT PAAT PAAAT…… 
				// APATA APAATAA APAAATAAA…… 
				else if (str[i + 2] == 'A') {
					int j = i + 3, count = 2;
					for (;j < len && str[j] == 'A';++j) ++count;
					if (j == len || str[j] != 'T') {
						cout << "NO" << endl;
						continue;
					}
					
					string a = str.substr(0, i);
					string aa = "";
                    		for (;count;--count) aa += a;
                   		if (str.substr(j + 1, len - (j + 1)) == aa) cout << "YES" << endl;
                    		else cout << "NO" << endl;
				}
                		else cout << "NO" << endl;
			}
			else cout << "NO" << endl;
		}
	}
	
	return 0;
}
```
  我发现测试点没有考虑到“PAX”这样的情况
  
  这题重点在要找出并且找准规律
2. 《算法笔记》P197
  1. “
    
    对给出的字符串，先判断其是否通过条件1的检验。之后，记录P左边A的个数为x、P和T中间A的个数为y、T右边A的个数为z。考虑到条件3得到新字符串的过程是在PT中间加一个A、字符串后面加上P前面的所有A，因此可以知道，每使用条件3一次，x不变、y变为y + 1、z变为z + x。反过来，如果沿着箭头逆回去，每逆一次，x不变、y变为y - 1，x变为z - x。这样可以一直逆回去，直到y==1时（即P和T中间只有一个A时）判断x和z是否相等：如果x == z。则输出“YES”；否则，输出“NO”。
    
    ……进一步分析可以发现一些规律，从而更快解出答案：
    
    这里x、y、z的含义和上面一样，由于y每次回退的步骤中都减1，因此从初始字符串回退到PT之间只剩一个A，需要进行y - 1次回退。而T右边A的个数z在经过y - 1次回退后（z每次减x）将变为z - x * (y - 1)。这时，判断条件2成立的条件是z - x * (y - 1)是否等于左边A的个数x（因为条件2中P左边和T右边的A的个数是相等的，且在回退过程中x不发生变化）：如果z - x * (y - 1) == x，则输出“YES”；否则，输出“NO"。
    
    ”
    
    通过观察其实可以直接看出：z == x * y，化简上面的等式得到的也是这个结果
  2. “下面再给出几组数据以便读者测试：“
```
PPPAAATTT			//NO
TAP					//NO
AAPTAA				//NO
AAPAATAAAAAA		//NO
AAAPAATAAAAAA		//YES
AAAPAAATAAAAAAAAA	//YES
```
B1019 / A1069 数字黑洞

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。

例如，我们从6767开始，将得到
```
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...
```
现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。

输入格式：

输入给出一个 (0,104) 区间内的正整数 N。

输出格式：

如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。

输入样例 1：
```
6767
```
输出样例 1：
```
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
```
输入样例 2：
```
2222
```
输出样例 2：
```
2222 - 2222 = 0000
```
1. 我的
```
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
	string n = "";
	cin >> n;
	
	bool flag = true;
	for (int i = 1;i < 4;++i) {
		if (n[i] != n[i - 1]) flag = false;
	}
	
	if (flag) printf("%04s - %04s = 0000", n.c_str(), n.c_str());
	else {
		do {
			while (n.size() < 4) n = "0" + n;
			sort(n.begin(), n.end(), greater<char>());
			int num1 = atoi(n.c_str());
			reverse(n.begin(), n.end());
			int num2 = atoi(n.c_str());
			int num = num1 - num2;
			printf("%04d - %04d = %04d\n", num1, num2, num);
			n = to_string(num);
		} while (n != "6174");
	}
	
	return 0;
}
```
  注意得到不足4位的数时需要在高位补0
  
  注意处理n=6174的情况，我是使用do-while来解决这个问题
2. 《算法笔记》P200
B1049 / A1104 数列的片段和

给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列 { 0.1, 0.2, 0.3, 0.4 }，我们有 (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这 10 个片段。

给定正整数数列，求出全部片段包含的所有的数之和。如本例中 10 个片段总和是 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。

输入格式：

输入第一行给出一个不超过 105 的正整数 N，表示数列中数的个数，第二行给出 N 个不超过 1.0 的正数，是数列中的数，其间以空格分隔。

输出格式：

在一行中输出该序列所有片段包含的数之和，精确到小数点后 2 位。

输入样例：
```
4
0.1 0.2 0.3 0.4
```
输出样例：
```
5.00
```
1. 我的
```
#include <iostream>

using namespace std;

int main(void)
{
	long long n = 0;
	cin >> n;
	
	double sum = 0;
	for (long long i = n, j = 1;i >= 1;--i, ++j) {
		double num = 0;
		cin >> num;
		sum += i * j * num;
	}
	printf("%.2lf", sum);
	
	return 0;
}
```
  一定要用long long + double，否则测试点3、4答案错误。
  
  通过样例找规律就好：
```
0.1
0.1 + 0.2               0.2
0.1 + 0.2 + 0.3         0.2 + 0.3           0.3
0.1 + 0.2 + 0.3 + 0.4   0.2 + 0.3 + 0.4     0.3 + 0.4   0.4
```
2. 《算法笔记》P202
A1008 Elevator

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
```
1. 我的
```
#include <iostream>

using namespace std;

int main(void)
{
	int n = 0;
	cin >> n;
	int pre = 0, total = 0;
	for (int i = 0;i < n;++i) {
		int now = 0;
		cin >> now;
		if (pre < now) total += (now - pre) * 6 + 5;
		else total += (pre - now) * 4 + 5;
		pre = now;
	}
	cout << total;
	
	return 0;
}
```
2. 《算法笔记》P204
A1049 Counting Ones

The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive N (≤230).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input:
```
12
```
Sample Output:
```
5
```
1. 我的
```
这题当初完全懵掉，牛客网的题解看了好久才看明白
现在记得不太清楚了，直接看的书
```
2. 《算法笔记》P205
  
  令n = 30710，并记从最低位0到最高位3的位号分别为1号位、2号位、3号位、4号位及5号位。
  1. 考虑1号位在1~n的过程中在该位可能出现的1的个数
    
    注意到n在1号位的左侧是3071。
    
    由于1号位为0（小于1），因此在1~n中，仅在高四位为0000 ~ 3070的过程中，1号位才可取到1……
  2. 考虑2号位……
    
    注意到n在2号位左侧是307，在2号位右侧是0。
    1. 由于2号位为1（等于1），因此在1~n中，仅在高三位为000 ~ 306的过程中，对任意的低一位（即0 ~ 9），2号位才总可以取到1（而使整个数不超过n），……
    2. 上面高三位最大只考虑到306，接下来考虑高三位为307的情况，当然此时还得保持2号位为1，那么也就是计算30710 ~ n有多少2号位为1的数。……
  3. 考虑3号位……
    
    注意到n在3号位左侧是30，在3号位右侧是10。
    
    由于3号位为7（大于1），因此在1 ~ n中，在高二位为00 ~ 30的过程中，对任意的低二位（即00 ~ 99），3号位均可取到1（而使整个数不超过n）……
  4. 考虑4号位……
  5. 考虑5号位……
  ……
  
  上面这个例子看似复杂，但是实际上是遵循了下面这个简洁的计算规则。……
  1. 步骤1：以ans表示1的个数，初值为0。设需要计算的数为n，且是一个m位（十进制）的数。从低到高枚举n的每一位（具体可以参看参考代码，控制一个a，每次乘10表示进一位）对每一位计算1~n中该位为1的数的个数，细节见步骤2。
  2. 步骤2：设当前处理至第k位，那么记left为第k位的高位所表示的数，now为第k位数，right为第k位的低位所表示的数，然后根据当前第k位（now）的情况分为三类讨论：
    1. 若now == 0，则ans += left * a
    2. 若now == 1，则ans += left * a + right + 1
    3. 若now >= 2，则ans += (left + 1) * a
```
#include <cstdio>

int main()
{
    int n, a = 1, ans = 0;
    int left, now, right;
    scanf("%d", &n);
    
    while (n / a != 0) {
        left = n / (a * 10);
        now = n / a % 10;
        right = n % a;
        
        if (now == 0) ans += left * a;
        else if (now == 1) ans += left * a + right + 1;
        else ans += (left + 1) * a;
        
        a *= 10;
    }
    printf("%d\n", ans);
    
    return 0;
}
```

转载：https://blog.csdn.net/weixin_44073967/article/details/100822685

查看评论

小言_互联网的博客

小言_互联网的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章

5.1 简单数学

第5章入门篇（3）——数学问题

5.1 简单数学

B1003 我要通过！

输入格式：

输出格式：

输入样例：

输出样例：

B1019 / A1069 数字黑洞

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

B1049 / A1104 数列的片段和

输入格式：

输出格式：

输入样例：

输出样例：

A1008 Elevator

Input Specification:

Output Specification:

Sample Input:

Sample Output:

A1049 Counting Ones

Input Specification:

Output Specification:

Sample Input:

Sample Output:

* 以上用户言论只代表其个人观点，不代表本网站的观点或立场

小言_互联网的博客

小言_互联网的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章

5.1 简单数学

第5章 入门篇（3）——数学问题

5.1 简单数学

B1003 我要通过！

输入格式：

输出格式：

输入样例：

输出样例：

B1019 / A1069 数字黑洞

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

B1049 / A1104 数列的片段和

输入格式：

输出格式：

输入样例：

输出样例：

A1008 Elevator

Input Specification:

Output Specification:

Sample Input:

Sample Output:

A1049 Counting Ones

Input Specification:

Output Specification:

Sample Input:

Sample Output:

* 以上用户言论只代表其个人观点，不代表本网站的观点或立场

第5章入门篇（3）——数学问题