PAT 甲级真题题解（121-155）
2024-08-30 06:22:53
1121 Damn Single
模拟
// 1121 Damn Single
#include <map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; map<int, int> m, vis;
vector<int> p;
const int N = 1e4 + ;
int a[N]; int main() {
int n, x, y;
scanf("%d", &n);
while (n--) {
scanf("%d %d", &x, &y);
x++; y++;
m[x] = y;
m[y] = x;
}
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
a[i]++;
vis[a[i]] = ;
}
for (int i = ; i <= n; i++) {
if (vis[ m[a[i]] ]) continue;
p.push_back(a[i]);
}
sort(p.begin(), p.end());
printf("%d\n", p.size());
for (int i = ; i < p.size(); i++) {
if (i != ) printf(" ");
printf("%05d", p[i] - );
}
return ;
}
1122 Hamiltonian Cycle
模拟
// 1122 Hamiltonian Cycle
#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = ;
int MAP[N][N];
set<int> s; int main() {
memset(MAP, -, sizeof(MAP));
int n, m, k;
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
MAP[u][v] = ; MAP[v][u] = ;
}
scanf("%d", &k);
while (k--) {
bool f = ;
int u, v, root;
scanf("%d", &m);
scanf("%d", &root);
s.insert(root);
u = root;
for (int i = ; i < m; i++) {
scanf("%d", &v);
s.insert(v);
if (MAP[u][v] == -) f = ;
u = v;
}
if (root != u || s.size() != n || m != n + ) f = ;
if (!f) printf("NO\n");
else printf("YES\n");
s.clear();
}
return ;
}
1124 Raffle for Weibo Followers
MAP标记
// 1124 Raffle for Weibo Followers
#include <map>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; map<string, int> vis;
string str; int main() {
bool f = ;
int n, m, s, cnt;
cin >> n >> m >> s;
cnt = m;
for (int i = ; i < s; i++) cin >> str;
for (int i = s; i <= n; i++) {
cin >> str;
if (cnt == m && !vis[str]) {
f = ;
cout << str << endl;
cnt = ;
vis[str] = ;
}
if (!vis[str]) cnt++;
}
if (!f) cout << "Keep going..." << endl;
return ;
}
1125 Chain the Ropes
思维
// 1125 Chain the Ropes
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e4 + ;
int a[N]; int main() {
int n, ans = ;
cin >> n;
for (int i = ; i <= n; i++) cin >> a[i];
sort(a + , a + + n);
ans = a[];
for (int i = ; i <= n; i++) {
ans += a[i];
ans /= ;
}
cout << ans << endl;
return ;
}
1126 Eulerian Path
给定m条边关系，判断是欧拉回路还是半欧拉回路或者不是欧拉回路。
如果一个连通图，具有0个奇度顶点为欧拉回路，具有2个奇度顶点为半欧拉，其他均不为欧拉图。
#include <bits/stdc++.h>
using namespace std; const int N = 1e5 + ;
int cnt[N], fa[N]; void init() {
for (int i = ; i < N; i++) fa[i] = i;
} int fi(int x) {
return fa[x] == x ? fa[x] : fa[x] = fi(fa[x]);
} void Union(int x, int y) {
int fx = fi(x), fy = fi(y);
if (fx != fy) {
fa[fx] = fy;
}
} int main() {
init();
int n, m, ans = , s = ;
scanf("%d %d", &n, &m);
for (int i = ; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
Union(u, v);
cnt[u]++; cnt[v]++;
}
for (int i = ; i <= n; i++) {
if (cnt[i] % ) ans++;
if (fa[i] == i) s++;
if (i != ) printf(" ");
printf("%d", cnt[i]);
}
printf("\n");
if (s == && ans <= ) {
if (ans == ) printf("Eulerian\n");
else if (ans == ) printf("Semi-Eulerian\n");
else printf("Non-Eulerian\n");
} else printf("Non-Eulerian\n");
return ;
}
1127 ZigZagging on a Tree
中序后序建树，层次遍历。（参考了柳神的做法，简洁多了。）
#include <queue>
#include <vector>
#include <iostream>
using namespace std; vector<int> in, post, result[];
int n, tree[][], root; struct node {
int index, depth;
}; void dfs(int &index, int inLeft, int inRight, int postLeft, int postRight) {
if (inLeft > inRight) return;
index = postRight;
int i = ;
while (in[i] != post[postRight]) i++;
dfs(tree[index][], inLeft, i - , postLeft, postLeft + (i - inLeft) - );
dfs(tree[index][], i + , inRight, postLeft + (i - inLeft), postRight - );
} void bfs() {
queue<node> q;
q.push(node{root, });
while (!q.empty()) {
node temp = q.front();
q.pop();
result[temp.depth].push_back(post[temp.index]);
if (tree[temp.index][] != )
q.push(node{tree[temp.index][], temp.depth + });
if (tree[temp.index][] != )
q.push(node{tree[temp.index][], temp.depth + });
}
} int main() {
cin >> n;
in.resize(n + ), post.resize(n + );
for (int i = ; i <= n; i++) cin >> in[i];
for (int i = ; i <= n; i++) cin >> post[i];
dfs(root, , n, , n);
bfs();
printf("%d", result[][]);
for (int i = ; i < ; i++) {
if (i % == ) {
for (int j = ; j < result[i].size(); j++)
printf(" %d", result[i][j]);
} else {
for (int j = result[i].size() - ; j >= ; j--)
printf(" %d", result[i][j]);
}
}
return ;
}
1128 N Queens Puzzle
同行，同列，同斜判断下即可。
// 1128 N Queens Puzzle
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 1e5 + ;
bool vis1[N], vis2[N]; int main() {
int t, n, x;
cin >> t;
while (t--) {
bool ok = ;
cin >> n;
for (int i = ; i <= * n; i++) vis1[i] = vis2[i] = ;
for (int i = ; i <= n; i++) {
cin >> x;
if (vis1[x] || vis2[x + i]) {
ok = ;
}
vis1[x] = ;
vis2[x + i] = ;
}
if (ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return ;
}
1129 Recommendation System
STL set应用
// 1129 Recommendation System
#include <set>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 5e4 + ;
struct node {
int id, time;
friend bool operator < (node x,node y){
if(x.time == y.time) return x.id < y.id;
return x.time > y.time;
}
}; int cnt[N];
set<node> se;
set<node> ::iterator it; int main() {
int n, k, x;
cin >> n >> k;
for (int i = ; i <= n; i++) {
cin >> x;
if(i == ) {
cnt[x]++;
se.insert({x, cnt[x]});
continue;
}
else {
cout << x << ":";
int c = ;
for (auto y : se) {
c++;
if(c > k) break;
cout << " " << y.id;
}
cout << endl;
}
if (se.find({x, cnt[x]}) != se.end()) {
it = se.find({x, cnt[x]});
se.erase(it);
}
cnt[x]++;
se.insert({x, cnt[x]});
}
return ;
}
1130 Infix Expression
给定中缀表达式二叉树，输出中缀表达式。（记得CSP也考过，当时是直接暴力A的。）
#include <bits/stdc++.h>
using namespace std; #define N 21
int n, Root;
int vis[N]; struct Node {
string s;
int l, r;
} node[N]; void dfs(int root) {
if (root == -) return ;
if (root != Root && (node[root].l != - || node[root].r != -)) cout << "(";
dfs(node[root].l);
cout << node[root].s;
dfs(node[root].r);
if ( root != Root && (node[root].l != - || node[root].r != -)) cout<<")";
} int main() {
scanf("%d", &n);
memset(vis, , sizeof(vis));
for (int i = ; i <= n; i++) {
cin >> node[i].s >> node[i].l >> node[i].r;
vis[node[i].l] = vis[node[i].r] = ;
}
Root = ;
while (vis[Root]) Root++;
dfs(Root);
return ;
}
1131 Subway Map
DFS暴力找最短路。同时保证题目中的那些要求。
#include <bits/stdc++.h>
using namespace std; #define MAX 10005
#define INF 0x3f3f3f3f int N, M, K;
int S, E; struct Stop {
int line;
int id;
} stops[MAX]; vector<Stop> stopVec[MAX];
int flag[MAX];
int cntMax = INF;
vector<Stop> stopAns, stopsVec;
int subMin = ; void dfs(int x, int cnt) {
if(x == E) {
int sub = ;
if(cntMax > cnt) {
stopAns = stopsVec;
cntMax = cnt;
for(int i = ; i < stopsVec.size(); i++) {
if(stopsVec[i].line != stopsVec[i-].line) {
sub++;
}
}
subMin = sub;
}
if(cntMax == cnt) {
for(int i = ; i < stopsVec.size(); i++) {
if(stopsVec[i].line != stopsVec[i-].line) {
sub++;
}
}
if(sub < subMin) {
stopAns = stopsVec;
subMin = sub;
}
}
return;
}
for(int i = ; i < stopVec[x].size(); i++) {
if(flag[stopVec[x][i].id] == ) {
flag[stopVec[x][i].id] = ;
stopsVec.push_back(stopVec[x][i]);
dfs(stopVec[x][i].id, cnt+);
stopsVec.pop_back();
flag[stopVec[x][i].id] = ;
}
}
} int main()
{
cin>>N;
for(int i = ; i <= N; i++) {
scanf("%d", &M);
for(int j = ; j < M; j++) {
scanf("%d", &stops[j].id);
stops[j].line = i;
if(j != ) {
stopVec[stops[j].id].push_back(stops[j-]);
stopVec[stops[j-].id].push_back(stops[j]);
}
}
}
cin>>K;
for(int i = ; i < K; i++) {
scanf("%d%d", &S, &E);
cntMax = INF;
dfs(S, );
printf("%d\n", cntMax);
int line = stopAns[].line;
int id = S;
for(int i = ; i < stopAns.size(); i++) {
if(line != stopAns[i].line) {
printf("Take Line#%d from %04d to %04d.\n", line, id, stopAns[i-].id);
line = stopAns[i].line;
id = stopAns[i-].id;
}
}
printf("Take Line#%d from %04d to %04d.\n", line, id, E);
}
return ;
}
1132 Cut Integer
注意判断拆开后是否有0。
#include <iostream>
using namespace std; int cal(string s) {
int res = ;
for (int i = ; i < s.size(); i++) {
res = res * + (s[i] - '');
}
return res;
} int main() {
int n;
cin >> n;
while (n--) {
string m;
int a, b, c;
cin >> m;
c = cal(m);
a = cal(m.substr(, m.size() / ));
b = cal(m.substr(m.size() / , m.size() / ));
if (a * b != && c % (a * b) == ) cout << "Yes" << endl;
else cout << "No" << endl;
}
return ;
}
1133 Splitting A Linked List
从root开始，保存小于0的，大于等于0小于等于K的和大于K的链表，最后按顺序输出结果即可。
#include <bits/stdc++.h>
using namespace std; const int INF = 0x3f3f3f3f; struct Node {
int data, next;
} node[]; int root, a, N, K;
vector<int> v[]; int main() {
scanf("%d%d%d", &root, &N, &K);
for (int i = ; i < N; i++) {
scanf("%d", &a);
scanf("%d %d", &node[a].data, &node[a].next);
}
while (root != -) {
if (node[root].data < ) v[].push_back(root);
else if (node[root].data <= K) v[].push_back(root);
else v[].push_back(root);
root = node[root].next;
}
int f = ;
for (int i = ; i < ; i++) {
for (int j = ; j < v[i].size(); j++) {
if (!f) printf("%05d %d",v[i][j],node[v[i][j]].data), f = ;
else printf(" %05d\n%05d %d",v[i][j],v[i][j],node[v[i][j]].data), f = ;
}
}
printf(" -1\n");
return ;
}
最新文章
- 基于HTML5实现3D热图Heatmap应用
- [转]vb socket通信（TCP/UDP）一对一、多对一
- 安卓CPU性能测试
- LDAP客户端
- 关于android的一些基础知识
- vim——打开多个文件、同时显示多个文件、在文件之间切换
- 微信支付接口 H5
- 六个创建模式之工厂方法模式(Factory Method Pattern)
- DLL输入和输出函数—dllinport与dllexport
- thinkphp G方法的华丽升级
- iOS8 UITableView 分割条设置separator intent = 0 不起作用
- EasyUI - Combo组件
- Nutch+HBase
- 开始的iOS编程之前的准备
- 浅析Content Negotation在Nancy的实现和使用
- strval
- 探索 Python 学习
- linux下 vi命令编辑/etc/my.cnf
- python读取文件时提示"UnicodeDecodeError: 'gbk' codec can't decode
- 05 Zabbix4.0触发器表达式Trigger expression支持的函数