分类: pat - CheaSim Blog

[pat1139]First Contact 前导零

First Contact

题意

给定一个图,图中的点只有男的点或者女的点。给定两个不同的点AB,问他们第一个点通过两个不同的点找到第二个点,并且A找到的点和A同性,B连接的点跟B同性,这样的点对有多少对。

题解

暴力枚举即可,找到所有相邻的同性点,之后同性点之间有连接就是一对点对。

  • wa点 前导零输出,-0000输入
  • 中间的点不能是两边的点,必须是不同的四个点

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
100
101
102
103
104
105
#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
map<int,int> mx;
const int maxn = 3e2+10;
int vis[maxn][maxn];
int idx[maxn];
int gender[maxn];
void output(int x){
char ch[10];
ch[0] = '0';
ch[1] = '0';
ch[2] = '0';
ch[3] = '0';
ch[4] = '\0';
int cnt = 3;
while(x){
ch[cnt--] = (x%10)+'0';
x /= 10;
}
printf("%s",ch);
}
int trans(string x,int &sign){
int a = 0;
int sz = x.size();
if(x[0] == '-'){
rep(i,1,sz){
a += pow(10,4-i) * (x[i] - '0');
}
sign = 1;
}else{
rep(i,0,sz){
a += pow(10,3-i) * (x[i] - '0');
}
}
return a;
}
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int n,m;
scanf("%d%d",&n,&m);
int cnt = 1;
rep(i,0,m){
string a,b; cin>>a>>b;
int x,y;
int sign1 = 0,sign2 = 0;
x = trans(a,sign1) ; y = trans(b,sign2);
if(mx[x] == 0){
mx[x] = cnt++;
if(sign1) gender[mx[x]] = 1;
idx[mx[x]] = x;
}
if(mx[y] == 0){
mx[y] = cnt++;
if(sign2) gender[mx[y]] = 1;
idx[mx[y]] = y;
}
int id1 = mx[x];
int id2 = mx[y];
vis[id1][id2] = vis[id2][id1] = 1;
}
int k;scanf("%d",&k);
rep(i,0,k){
int x,y; scanf("%d%d",&x,&y);
x = max(-1*x,x);
y = max(-1*y,y);
int id1 = mx[x]; int id2 = mx[y];
vector<int> xx;vector<int> yy;
if(id1 == 0 || id2 == 0){
puts("0");
continue;
}
rep(j,1,cnt+1)
if(j != id2 && vis[id1][j] && (gender[id1]^gender[j]) == 0)
xx.push_back(j);
rep(j,1,cnt+1)
if(j != id1 && vis[id2][j] && (gender[id2]^gender[j]) == 0)
yy.push_back(j);
vector<pair<int,int>> ans;
for(auto x:xx){
for(auto y:yy){
if(vis[x][y] == 1){
ans.push_back(make_pair(idx[x],idx[y]));
}
}
}
sort(ans.begin(),ans.end());
printf("%d\n",ans.size());
for(auto x:ans){
output(x.fi); printf(" "); output(x.se);
puts("");
//printf("%d %d\n",x.fi,x.se);
}
}
return 0;
}

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