liuchuo – 第22页 – 我不管，反正我最萌～

L1-059 敲笨钟 (20 分)-PAT 团体程序设计天梯赛 GPLT

微博上有个自称“大笨钟V”的家伙，每天敲钟催促码农们爱惜身体早点睡觉。为了增加敲钟的趣味性，还会糟改几句古诗词。其糟改的方法为：去网上搜寻压“ong”韵的古诗词，把句尾的三个字换成“敲笨钟”。例如唐代诗人李贺有名句曰：“寻章摘句老雕虫，晓月当帘挂玉弓”，其中“虫”（chong）和“弓”（gong）都压了“ong”韵。于是这句诗就被糟改为“寻章摘句老雕虫，晓月当帘敲笨钟”。

现在给你一大堆古诗词句，要求你写个程序自动将压“ong”韵的句子糟改成“敲笨钟”。

输入格式：
输入首先在第一行给出一个不超过 20 的正整数 N。随后 N 行，每行用汉语拼音给出一句古诗词，分上下两半句，用逗号 , 分隔，句号 . 结尾。相邻两字的拼音之间用一个空格分隔。题目保证每个字的拼音不超过 6 个字符，每行字符的总长度不超过 100，并且下半句诗至少有 3 个字。

输出格式：
对每一行诗句，判断其是否压“ong”韵。即上下两句末尾的字都是“ong”结尾。如果是压此韵的，就按题面方法糟改之后输出，输出格式同输入；否则输出 Skipped，即跳过此句。

输入样例：
5
xun zhang zhai ju lao diao chong, xiao yue dang lian gua yu gong.
tian sheng wo cai bi you yong, qian jin san jin huan fu lai.
xue zhui rou zhi leng wei rong, an xiao chen jing shu wei long.
zuo ye xing chen zuo ye feng, hua lou xi pan gui tang dong.
ren xian gui hua luo, ye jing chun shan kong.
输出样例：
xun zhang zhai ju lao diao chong, xiao yue dang lian qiao ben zhong.
Skipped
xue zhui rou zhi leng wei rong, an xiao chen jing qiao ben zhong.
Skipped
Skipped

分析：用s字符串组存放每一个单词，用cnt记录单前单词是句子中的第几个，使用,和.分别判断上半句和下半句的完成。当遇到某个单词结尾是,时判断是否满足末尾为ong，是的将flag设置为1。结尾为.时也一样，并且判断flag是否为1，是的话就输出句子，并将最后三个修改为“qiao ben zhong.”～

#include <bits/stdc++.h>
using namespace std;
int cnt, flag;
string s[101];
int main() {
    cin >> s[0];
    while (cin >> s[cnt]) {
        if (s[cnt].back() == ',') {
            if ((int)s[cnt].size() >= 4 && *(s[cnt].end() - 2) == 'g' && *(s[cnt].end() - 3) == 'n' && *(s[cnt].end() - 4) == 'o') flag = 1;
        } else if (s[cnt].back() == '.') {
            if ((int)s[cnt].size() >= 4 && flag && *(s[cnt].end() - 2) == 'g' && *(s[cnt].end() - 3) == 'n' && *(s[cnt].end() - 4) == 'o') {
                for (int i = 0; i < cnt - 2; i++) cout << s[i] << ' ';
                cout << "qiao ben zhong.\n";
            } else cout << "Skipped\n";
            cnt = flag = 0;
            continue;
        }
        cnt++;
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int cnt, flag;

string s[101];

int main() {

cin >> s[0];

while (cin >> s[cnt]) {

if (s[cnt].back() == ',') {

if ((int)s[cnt].size() >= 4 && *(s[cnt].end() - 2) == 'g' && *(s[cnt].end() - 3) == 'n' && *(s[cnt].end() - 4) == 'o') flag = 1;

} else if (s[cnt].back() == '.') {

if ((int)s[cnt].size() >= 4 && flag && *(s[cnt].end() - 2) == 'g' && *(s[cnt].end() - 3) == 'n' && *(s[cnt].end() - 4) == 'o') {

for (int i = 0; i < cnt - 2; i++) cout << s[i] << ' ';

cout << "qiao ben zhong.\n";

} else cout << "Skipped\n";

cnt = flag = 0;

continue;

}

cnt++;

}

return 0;

}

L1-058 6翻了 (15 分)-PAT 团体程序设计天梯赛 GPLT

“666”是一种网络用语，大概是表示某人很厉害、我们很佩服的意思。最近又衍生出另一个数字“9”，意思是“6翻了”，实在太厉害的意思。如果你以为这就是厉害的最高境界，那就错啦 —— 目前的最高境界是数字“27”，因为这是 3 个 “9”！

本题就请你编写程序，将那些过时的、只会用一连串“6666……6”表达仰慕的句子，翻译成最新的高级表达。

输入格式：
输入在一行中给出一句话，即一个非空字符串，由不超过 1000 个英文字母、数字和空格组成，以回车结束。

输出格式：
从左到右扫描输入的句子：如果句子中有超过 3 个连续的 6，则将这串连续的 6 替换成 9；但如果有超过 9 个连续的 6，则将这串连续的 6 替换成 27。其他内容不受影响，原样输出。

输入样例：
it is so 666 really 6666 what else can I say 6666666666

输出样例：
it is so 666 really 9 what else can I say 27

#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
    getline(cin, s);
    for (int i = 0, cnt; i < (int)s.size(); i++) {
        if (s[i] != '6') cout << s[i];
        else {
            cnt = 1;
            while (i + cnt < (int)s.size() && s[i+cnt] == '6') cnt++;
            if (cnt <= 3) {
                for (int j = 0; j < cnt; j++) cout << '6';
            } else if (cnt <= 9) cout << '9';
            else cout << "27";
            i += cnt - 1;
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {

getline(cin, s);

for (int i = 0, cnt; i < (int)s.size(); i++) {

if (s[i] != '6') cout << s[i];

else {

cnt = 1;

while (i + cnt < (int)s.size() && s[i+cnt] == '6') cnt++;

if (cnt <= 3) {

for (int j = 0; j < cnt; j++) cout << '6';

} else if (cnt <= 9) cout << '9';

else cout << "27";

i += cnt - 1;

}

return 0;

}

L1-057 PTA使我精神焕发 (5 分)-PAT 团体程序设计天梯赛 GPLT

以上是湖北经济学院同学的大作。本题就请你用汉语拼音输出这句话。

输入格式：
本题没有输入。

输出格式：
在一行中按照样例输出，以惊叹号结尾。

输入样例：
无
输出样例：
PTA shi3 wo3 jing1 shen2 huan4 fa1 !

#include <iostream>
using namespace std;
int main() {
    cout << "PTA shi3 wo3 jing1 shen2 huan4 fa1 !";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

cout << "PTA shi3 wo3 jing1 shen2 huan4 fa1 !";

return 0;

}

[note]标点符号和数学符号所对应的英文

看英文文档时候会看到一些代码中标点符号的英文以前没有接触过，顺便就把键盘上所有的标点符号、常用的数学符号一起整理了一下～

`	grave accent	重音符
~	tilde	/‘tɪldə/ 波浪符号
～	swung dash	代字号，swing 摇摆
!	exclamation point	/ˌɛksklə’meʃən/ 感叹号
@	at	在…
#	① pound ②number	① 井号 ② …号
$	dollar	美元符号
%	per cent	百分比
^	caret	插入符号
…	ellipsis points	/ɪ’lɪpsɪs/ 省略号
&	ampersand = and	和
*	asterisk	/‘æstərɪsk/ 星号
( )	① parenthesis ② round brackets	/pə’rɛnθəsɪs/ 圆括号，复数parentheses
–	① hyphen ② minus	① /‘haɪfn/ 连字号 ② 减号
——	dash	破折号
_	underline	下划线
+	plus	加号
=	is equal to	等于号
[ ]	square brackets	方括号
{ }	curly brackets	花括号，大括号
\	backslash	反斜杠
\|	vertical bar，vertical virgule	竖线
\|\|	parallel	双线号
;	semicolon	分号
:	colon	冒号
‘’	quotation mark	引号
“”	double quotation mark	双引号
	apostrophe	/ə’pɑstrəfi/ 撇号
,	comma	逗号
<>	angle brackets	尖括号
<	is less than	小于号
>	is greater than	大于号
《》	French quotes	书名号；法文符号
.	period，full stop，dot	句号
/	① slash ② virgule	① 斜线 ② /‘vɝgjʊl/ 置于二字之间表示任取一字均可的短斜线
//	① slash-slash ② comment	① 双斜线 ② 注释符
?	question mark	问号

∵	since，because	因为
∴	hence，therefore	因此，所以
√	square root	平方根
∞	infinity	/ɪn’fɪnəti/ 无穷号
℃	Celsius system	/‘selsiəs/ 摄氏度
⊥	perpendicular to	垂直于
∩	intersection of	交集
∪	union of	并集
∑	summation of	总和
≡	is equivalent to	全等于号
≌	Is congruent to	全等号
≈	is approximately equal to	约等于号
~	Is similar to	相似
±	plus or minus	正负号
x	is multiplied by	乘号
÷	is divided by	除号
≠	is not equal to	不等于号
→	arrow	箭头
§	section，division	分节号
○	circumference	圆周
∷	equals，as	等于，成比例
‰	per mill	千分比
°	degree	度
≥	greater than or equal to	大于等于号
≤	less than or equal to	小于等于号
—	division / fraction	分号
mod	modulo	模运算符
Δ	① triangle ② Delta	① 三角符号 ② 第四个希腊字母Delta
≪	much less than	远小于
≫	much greater than	远大于
n!	factorial	阶乘号

first-class type 一等类型的含义

一等(first-class)类型是指可以在执行期创造，并作为参数传递给其他函数或存入一个变数。

如果一个对象是一等类型，那么它：

可以被存入变量或其他结构
可以被作为参数传递给其他函数
可以被作为函数的返回值
可以在执行期创造，而无需完全在设计期全部写出
即使没有被系结至某一名称，也可以存在

大部分语言的基本类型的数值（如int, float）等都是一等类型～

在C/C++中，函数不是一等类型，这表示函数在C/C++语言中不能在执行期创造，而必须在设计时全部写好，而在Python、Swift中函数是一等类型，这意味着函数可以作为其他函数的参数和返回值。

PAT 1155 Heap Paths （30 分）- 甲级

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

One thing for sure is that all the keys along any path from the root to a leaf in a max/min heap must be in non-increasing/non-decreasing order.

Your job is to check every path in a given complete binary tree, in order to tell if it is a heap or not.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (1<N≤1,000), the number of keys in the tree. Then the next line contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

Output Specification:
For each given tree, first print all the paths from the root to the leaves. Each path occupies a line, with all the numbers separated by a space, and no extra space at the beginning or the end of the line. The paths must be printed in the following order: for each node in the tree, all the paths in its right subtree must be printed before those in its left subtree.

Finally print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all.

Sample Input 1:
8
98 72 86 60 65 12 23 50
Sample Output 1:
98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap
Sample Input 2:
8
8 38 25 58 52 82 70 60
Sample Output 2:
8 25 70
8 25 82
8 38 52
8 38 58 60
Min Heap
Sample Input 3:
8
10 28 15 12 34 9 8 56
Sample Output 3:
10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap

题目大意：给出一颗完全二叉树，打印出从根节点到所有叶节点的路径，打印顺序先右后左，即先序遍历的镜像。然后判断该树是大顶堆、小顶堆或者不是堆～

分析：1.深搜打印出所有路径（从右往左，即先序的镜像），vector保存一路上的节点，通过push和pop回溯，维护路径，index <= n是对只有左叶节点没有右叶节点的点特判
2.判断是否为堆：从第二个节点开始遍历，如果比父节点小，就不是小顶堆，如果比父节点大，就不是大顶堆～

#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int a[1009], n, isMin = 1, isMax = 1;
void dfs(int index) {
    if (index * 2 > n && index * 2 + 1 > n) {
        if (index <= n) {
            for (int i = 0; i < v.size(); i++)
                printf("%d%s", v[i], i != v.size() - 1 ? " " : "\n");
        }
    } else {
        v.push_back(a[index * 2 + 1]);
        dfs(index * 2 + 1);
        v.pop_back();
        v.push_back(a[index * 2]);
        dfs(index * 2);
        v.pop_back();
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    v.push_back(a[1]);
    dfs(1);
    for (int i = 2; i <= n; i++) {
        if (a[i/2] > a[i]) isMin = 0;
        if (a[i/2] < a[i]) isMax = 0;
    }
    if (isMin == 1)
        printf("Min Heap");
    else 
        printf("%s", isMax == 1 ? "Max Heap" : "Not Heap"); 
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> v;

int a[1009], n, isMin = 1, isMax = 1;

void dfs(int index) {

if (index * 2 > n && index * 2 + 1 > n) {

if (index <= n) {

for (int i = 0; i < v.size(); i++)

printf("%d%s", v[i], i != v.size() - 1 ? " " : "\n");

}

} else {

v.push_back(a[index * 2 + 1]);

dfs(index * 2 + 1);

v.pop_back();

v.push_back(a[index * 2]);

dfs(index * 2);

v.pop_back();

}

int main() {

cin >> n;

for (int i = 1; i <= n; i++)

scanf("%d", &a[i]);

v.push_back(a[1]);

dfs(1);

for (int i = 2; i <= n; i++) {

if (a[i/2] > a[i]) isMin = 0;

if (a[i/2] < a[i]) isMax = 0;

}

if (isMin == 1)

printf("Min Heap");

else

printf("%s", isMax == 1 ? "Max Heap" : "Not Heap");

return 0;

}