一、PAT A1132 Cut Integer
- 就是模拟啦。注意判断分割的两个数乘积为 0 的情况。参考代码如下。
#include
#include
#include
using namespace std;int main() {string s;int n;cin >> n;while (n--) {cin >> s;int a = stoi(string(s.begin(), s.begin() + s.size() / 2));int b = stoi(string(s.begin() + s.size() / 2, s.end()));int c = stoi(s);if (a * b == 0)cout << "No" << endl;else if (c % (a * b) == 0)cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}
二、PAT A1133 Splitting A Linked List
- 先散列把整个链表存起来，然后再遍历一次链表进行分类存储，最后输出即可。参考代码如下。
#include
#include
#include
#include
#include
using namespace std;struct node {string address, next;int v;
};unordered_map mp;
vector below_zero;
vector below_k;
vector above_k;
vector ans;int main() {string st, address, next;st.resize(6);address.resize(6);next.resize(6);int n, k, v;scanf("%s%d%d", &st[0], &n, &k);for (int i = 0; i < n; i++) {scanf("%s%d%s", &address[0], &v, &next[0]);node temp;temp.address = address;temp.next = next;temp.v = v;mp[address] = temp;}while (true) {if (mp[st].v < 0)below_zero.push_back(mp[st]);else if (mp[st].v <= k)below_k.push_back(mp[st]);elseabove_k.push_back(mp[st]);if (mp[st].next[0] == '-') break;else st = mp[mp[st].next].address;}for (auto it : below_zero) ans.push_back(it);for (auto it : below_k) ans.push_back(it);for (auto it : above_k) ans.push_back(it);for (int i = 0; i < ans.size() - 1; i++)printf("%s %d %s\n", &ans[i].address[0], ans[i].v, &ans[i + 1].address[0]);printf("%s %d -1\n", &ans[ans.size() - 1].address[0], ans[ans.size() - 1].v);return 0;
}
三、PAT A1134 Vertex Cover
- 用邻接矩阵存储图，同时记录每个点的度。遍历 cover ，把 cover 内的每个点 u 及与 u 相连的点 v 的度减 1。最后若还有度大于 0 的点，说明不是 cover。参考代码如下。
#include
#include
#include
using namespace std;
const int maxn = 10010;vector adj[maxn];
int degree[maxn], temp_d[maxn];int main() {int n, m, k, u, v;scanf("%d%d", &n, &m);while (m--) {scanf("%d%d", &u, &v);adj[u].push_back(v);adj[v].push_back(u);degree[u]++;degree[v]++;}scanf("%d", &k); while (k--) {int nv;memcpy(temp_d, degree, sizeof(degree));scanf("%d", &nv);while (nv--) {scanf("%d", &u);for (int i = 0; i < adj[u].size(); i++) {v = adj[u][i];temp_d[u]--;temp_d[v]--;}}bool yes = true;for (int i = 0; i < n; i++)if (temp_d[i] > 0) {printf("No\n");yes = false;break;}if (yes) printf("Yes\n");}return 0;
}
四、PAT A1135 Is It A Red-Black Tree
- 这道题又参考了萌妹子的博客。“从任意结点到叶子结点的路径中，黑色结点的个数是否相同”，这个条件一开始理解错了，以为是任意根到叶子的路径中的黑色结点的个数相同，结果错的好惨。这里用 cnt 函数获取每个结点的左右孩子的黑高度，如果不相等则不为红黑树。这里也求出了每一条根到叶子的路径，如果路径上有连着的两个红色结点，则不为红黑树。写得比较复杂，参考代码如下。
#include
#include
#include
#include
using namespace std;struct node {int v, color;node* lchild = NULL;node* rchild = NULL;
};
vector path;
bool flag = true;void build(node* &tree, int v) {if (tree == NULL) {tree = new node;if (v > 0) tree->color = 1;else tree->color = -1;tree->v = abs(v);return;}if (abs(v) < tree->v) build(tree->lchild, v);else build(tree->rchild, v);
}
int cnt(node* tree) {if (tree == NULL) return 0;if (tree->color == -1) return max(cnt(tree->lchild), cnt(tree->rchild));else return 1 + max(cnt(tree->lchild), cnt(tree->rchild));
}
void judge(node* tree) {if (cnt(tree->lchild) != cnt(tree->rchild)) { flag = false; return; }if (tree->lchild == NULL && tree->rchild == NULL) {path.push_back(tree->color);for (int i = 0; i < path.size(); i++)if (i != 0 && path[i] == -1 && path[i - 1] == -1){flag = false; return;}path.pop_back();}path.push_back(tree->color);if (tree->lchild) judge(tree->lchild);if (tree->rchild) judge(tree->rchild);path.pop_back();
}int main() {int k, n, t;scanf("%d", &k);while (k--) {path.clear();flag = true;node* tree = NULL;scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d", &t);build(tree, t);} if (tree->color == -1) printf("No\n");else {judge(tree);if(flag) printf("Yes\n");else printf("No\n");} }return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
