PAT练习

PAT练习

为了拿PAT的50元代金券,刷一刷牛客网上的PAT真题。

点我连接

Rational Sum

题意

求一百个分数的和。

题解

大整数秒了。

其实我想用python,现在acm区域赛都让用python了

ac代码

##Read Number in Chinese

题意

给定一个数字,用中文拼音输出他。

题解

模拟。

  • 如果是负数,输出”Fu”
  • 每四位分隔一下,都是一样的。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
char s[20];
string chinese[10] = {"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
ll n;
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%s",s);
int t = 0;
int sz = strlen(s);

if(s[0] == '-') t = 1;
per(i,t,sz) s[i+10-sz] = s[i];
rep(i,t,10-sz+t) s[i] = '0';
vector<string> ans;
if(s[0] == '-') ans.push_back("Fu");
bool flag = true;
int idx = 0;
rep(i,1,10) if(s[i] > '0'){
idx = i;
break;
}
rep(i,1,10) s[i] -= '0';
if(s[1] != 0){
ans.push_back(chinese[s[1]]);
ans.push_back("Yi");
}
if(s[2] != 0){
ans.push_back(chinese[s[2]]);
ans.push_back("Qian");
}else{
if(s[1] && (s[3] || s[4] || s[5])) ans.push_back("ling");
}
if(s[3] != 0){
flag = true;
ans.push_back(chinese[s[3]]);
ans.push_back("Bai");
}else{
if(s[4] != 0 || s[5] != 0) ans.push_back("ling");
}
if(s[4] != 0){
flag = true;
ans.push_back(chinese[s[4]]);
ans.push_back("Shi");
}else{
if(s[5] != 0) ans.push_back("ling");
}
if(s[5] != 0){
ans.push_back(chinese[s[5]]);
}else if((s[2] == 0 && s[3] == 0 && s[4] == 0) && (s[6] || s[7] || s[8] || s[9])) ans.push_back("ling");
if(s[2] || s[3] || s[4] || s[5]) ans.push_back("Wan");

// gewei
flag = true;


if(s[6] != 0){
ans.push_back(chinese[s[6]]);
ans.push_back("Qian");
}else{
if(idx <= 5 && (s[7] || s[8] || s[9])) ans.push_back("ling");
}
if(s[7] != 0){
ans.push_back(chinese[s[7]]);
ans.push_back("Bai");
}else{
if(s[8] != 0 || s[9] != 0) ans.push_back("ling");
}
if(s[8] != 0){
ans.push_back(chinese[s[8]]);
ans.push_back("Shi");
}else{
if(s[9] != 0) ans.push_back("ling");
}
if(s[9] != 0) ans.push_back(chinese[s[9]]);
if(ans.size() == 0) ans.push_back("ling");
bool lingling = true;
rep(i,0,ans.size()){
if(ans[i] == "ling" && lingling && ans.size()>1) {
continue;
}
if(ans[i] != "ling" && ans[i] != "Fu") lingling = false;
else lingling = true;
cout<<ans[i];
if(i==ans.size()-1) cout<<'\n';
else cout<<' ';
}
return 0;
}

List Grades (25)

题意

给定最多100个人,给他们排序,输出指定成绩区间内的人名和ID。

题解

模拟,sort

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
struct node{
string name;
string id;
int grade;
bool operator<(const node& x) const{
return grade > x.grade;
}
node(){}
node(string a,string b,int g){
name = a;
id = b;
grade = g;
}
};
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
vector<node> ve;
int n; scanf("%d",&n);
rep(i,0,n){
string a,b; int g;
cin>>a>>b>>g;
ve.push_back(node(a,b,g));
}
sort(ve.begin(),ve.end());
int st,ed;
scanf("%d%d",&st,&ed);
bool flag = false;
rep(i,0,n) if(ve[i].grade <= ed && ve[i].grade >= st) flag = true;
int cnt = 0;
while(cnt < n && ve[cnt].grade > ed) cnt++;
while(cnt < n && ve[cnt].grade >= st){
cout<<ve[cnt].name<<' '<<ve[cnt].id<<' '<<'\n';
cnt++;
}
if(!flag) puts("NONE");

return 0;
}

Tree Traversals Again (25)

题意

用栈表示一个树的先根遍历,求这颗二叉树的后跟遍历。

题解

dfs模拟一下即可。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

char s[30];
struct node{
int id;
node *left = NULL,*right = NULL;
};
void addnode(node * root,int n,int f){
if(f){
root->left = new node();
root->left->id = n;
}else{
root->right = new node();
root->right->id = n;
}
}
void dfs(node* u){
int n; scanf("%s",s);
// left
if(s[1] == 'u'){
cin>>n;
addnode(u,n,1);
dfs(u->left);
}
scanf("%s",s);
if(s[1] == 'u'){
cin>>n;
addnode(u,n,0);
dfs(u->right);
}else{
return;
}
}
void post_order(node * rt){
if(rt->left != NULL){
post_order(rt->left);
}
if(rt->right != NULL){
post_order(rt->right);
}
printf("%d ",rt->id);
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
node * root = new node();
int n;scanf("%d",&n);
scanf("%s %d",s,&n);
root->id = n;
dfs(root);
post_order(root);
return 0;
}