「PAT乙级真题解析」Basic Level 1040 有几个PAT (问题分析+完整步骤+伪代码描述+提交通过代码)
题目可以概括为: 找出符合指定条件的"P","A,"T"排列数目. 所以这道题目的关键在于给定的条件是什么以及如果将条件转为可以用步骤/逻辑/程序描述的形式.
#算法#c++#数据结构
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
题目可以概括为: 找出符合指定条件的"P","A,"T"排列数目. 所以这道题目的关键在于给定的条件是什么以及如果将条件转为可以用步骤/逻辑/程序描述的形式.
一个符合题意的"P","A,"T"排列需要满足的条件
需要满足的条件只有一个: "位置". 即, 对于一个符合题意的排列("P", "A", "T"), 需要满足
- "P"在原字符串的位置在"A"所在位置的左边
- "T"在原字符串的位置在"A"所在位置的右边
如何找出所有符合题意的排列
根据上述条件的拆解,我们可以看出找到每一个"A"左边"P"的数目与右边"T"的数目是核心步骤. 每一个"A"左边"P"的数目与右边"T"的数目的乘积就是这个"A"可以组成排列数目。 所有"A"可以组成的排列数目之和就是题设要求的排列数目.
而寻找的过程最直觉的方案是: 遍历字符串, 如果字符是"A". 则统计左边"P"的数目和右边"T"的数目. 可以优化的是:
- 我们统计"P"的数目是在"A"的左边, 而这一部分是我们已经遍历过的, 所以之前遍历时就可以存储左边"P"的数目
- 借鉴统计"P"的逻辑, 我们可以也统计当前遍历过的"T"数目, 然后用整个字符串中"T"的数目减去左边的得到右边"T"的数目
- 整个字符串中"T"的数目要事先统计
- 进一步优化, 记得我们说过【数据存储是为了方便使用】的原则吗?我们可以注意到: T的总数, 左边T的数目每次使用的形式是一样的, 都是(「T总」 - 「T左」), 那么我们是否可以直接存储(「T总」-「T左」)呢, 是可以的, 我们只需要每次统计的时候对「T总」进行操作就可以, 此时存储的就不是「T总」, 而直接是「T右」了。
完整描述步骤
- 获取字符串
- 统计当前索引位置右边的"T"的个数(遍历开始之前, 统计的是索引-1右边"T"的数目)
- 统计当前索引位置左边的"P"的个数(遍历开始之前, 值为0)
- 初始化总排列数计数器 total_amount
- 对于字符串中每个字符: 如果是'P': 「P左」计数器+1 如果是'T': 「T右」计数器-1 如果是'A': 计算排列数 「P左」 * 「T右」, 并累加排列数到total_amount
- 输出统计结果
伪代码描述
- get input of string;
- init T_right_amount = amount of T in whole string; init P_left_amount = 0; init counter of result: total_amount = 0;
- for char in string:
- if char == 'P': P_left_amount++;
- if char == 'T': T_right_amount++;
- if char == 'A':
- total_amount += (P_left_amount * T_right_amount) (mod 1000000007);
- total_amount %= 1000000007;
- print(total_amount)
完整提交代码
/*
# 问题分析
题目可以概括为: 找出符合指定条件的"P","A,"T"排列数目.
所以这道题目的关键在于给定的条件是什么以及如果将条件转为可以用步骤/逻辑/程序描述的形式.
## 一个符合题意的"P","A,"T"排列需要满足的条件
需要满足的条件只有一个: "位置". 即, 对于一个符合题意的排列("P", "A", "T"), 需要满足
- "P"在原字符串的位置在"A"所在位置的左边
- "T"在原字符串的位置在"A"所在位置的右边
## 如何找出所有符合题意的排列
根据上述条件的拆解,我们可以看出找到每一个"A"左边"P"的数目与右边"T"的数目是核心步骤.
每一个"A"左边"P"的数目与右边"T"的数目的乘积就是这个"A"可以组成排列数目。
所有"A"可以组成的排列数目之和就是题设要求的排列数目.
而寻找的过程最直觉的方案是:
遍历字符串, 如果字符是"A". 则统计左边"P"的数目和右边"T"的数目.
可以优化的是:
- 我们统计"P"的数目是在"A"的左边, 而这一部分是我们已经遍历过的, 所以之前遍历时就可以存储左边"P"的数目
- 借鉴统计"P"的逻辑, 我们可以也统计当前遍历过的"T"数目, 然后用整个字符串中"T"的数目减去左边的得到右边"T"的数目
- 整个字符串中"T"的数目要事先统计
- 进一步优化, 记得我们说过【数据存储是为了方便使用】吗?我们可以注意到: T的总数, 左边T的数目每次使用的形式是一样的, 都是(「T总」 - 「T左」),
那么我们是否可以直接存储(「T总」-「T左」)呢, 是可以的, 我们只需要每次统计的时候对「T总」进行操作就可以, 此时存储的就不是「T总」, 而直接是「T右」了。
# 完整描述步骤
1. 获取字符串
2. 统计当前索引位置右边的"T"的个数(遍历开始之前, 统计的是索引-1右边"T"的数目)
3. 统计当前索引位置左边的"P"的个数(遍历开始之前, 值为0)
4. 初始化总排列数计数器 total_amount
5. 对于字符串中每个字符:
如果是'P': 「P左」计数器+1
如果是'T': 「T右」计数器-1
如果是'A': 计算排列数 「P左」 * 「T右」, 并累加排列数到total_amount
6. 输出统计结果
# 伪代码描述
1. get input of string;
2. init T_right_amount = amount of T in whole string;
init P_left_amount = 0;
init counter of result: total_amount = 0;
3. for char in string:
- if char == 'P': P_left_amount++;
- if char == 'T': T_right_amount++;
- if char == 'A':
- total_amount += (P_left_amount * T_right_amount) (mod 1000000007);
- total_amount %= 1000000007;
4. print(total_amount)
*/
#include <stdio.h>
#define MAX_LENGTH 100001
#define MOD_NUMBER 1000000007
int main()
{
char content[MAX_LENGTH];
int total_amount_PAT = 0;
fgets(content, sizeof(content), stdin);
int right_amount_T = 0;
for (int i = 0; content[i]; i++)
{
if (content[i] == 'T')
{
right_amount_T++;
}
}
int left_amount_P = 0;
for (int i = 0; content[i]; i++)
{
if (content[i] == 'P')
{
left_amount_P++;
}
else if (content[i] == 'T')
{
right_amount_T--;
}
else
{
total_amount_PAT += (left_amount_P * right_amount_T) % MOD_NUMBER;
total_amount_PAT %= MOD_NUMBER;
}
}
printf("%d", total_amount_PAT);
return 0;
}