PAT（甲级）2017年秋季考试
2024-09-01 17:50:59
PAT（甲级）2017年秋季考试
D题红黑树待补21/30
大佬的代码，看着想哭，这才是艺术啊
A Cut Integer
模拟题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int getLen(ll x){
int len = 0;
while(x){
len++;
x/=10;
}
return len;
}
int main(){
cin>>n;
while(n--){
ll x;
cin>>x;
int len = getLen(x);
ll temp = x;
int t = 0;
ll right = 0;
ll rightTemp = 0;
ll left = 0;
while(t<len/2){
rightTemp = rightTemp * 10 + temp%10;
temp/=10;
t++;
}
while(rightTemp){
right = right * 10 + rightTemp%10;
rightTemp/=10;
}
left = temp;
if(left == 0 || right == 0){
puts("No");
}else{
if(x%(left*right) == 0) puts("Yes");
else puts("No");
}
}
return 0;
}
B Splitting A Linked List
链表题
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxm = 100000;
struct node{
int address;
int data;
int next;
}nod[maxm];
vector<node> vec;
vector<node> ans;
int Head,n,k;
int vis[maxm];
int main(){
cin>>Head>>n>>k;
for(int i=1;i<=n;i++){
int add,dat,nex;
cin>>add>>dat>>nex;
nod[add].address = add;
nod[add].data = dat;
nod[add].next = nex;
}
for(int head = Head;head!=-1;head=nod[head].next){
vec.push_back(nod[head]);
}
for(int i=0;i<vec.size();i++){
if(vec[i].data < 0 && !vis[vec[i].address]){
ans.push_back(vec[i]);
vis[vec[i].address] = 1;
}
}
for(int i=0;i<vec.size();i++){
if(vec[i].data >= 0 && vec[i].data <= k && !vis[vec[i].address]){
ans.push_back(vec[i]);
vis[vec[i].address] = 1;
}
}
for(int i=0;i<vec.size();i++){
if(!vis[vec[i].address]){
ans.push_back(vec[i]);
vis[vec[i].address] = 1;
}
}
if(ans.size() == 1){
printf("%05d %d -1",ans[0].address,ans[0].data);
return 0;
}
for(int i=0;i<ans.size()-1;i++){
printf("%05d %d %05d\n",ans[i].address,ans[i].data,ans[i+1].address);
}
if(ans.size() > 1) printf("%05d %d -1",ans[ans.size()-1].address,ans[ans.size()-1].data);
return 0;
}
C Vertex Cover
简单图论，最小覆盖，邻接表存图
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10000;
int n,m,k;
int g[maxn][maxn];
int vis[maxn][maxn];
vector<int> vec;
void init(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
vis[i][j] = 0;
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
g[u][v] = 1;
g[v][u] = 1;
}
cin>>k;
for(int t=0;t<k;t++){
init();
int nv;
cin>>nv;
for(int i=0;i<nv;i++) {
int d;
cin>>d;
vec.push_back(d);
}
for(int i=0;i<=nv-1;i++){
for(int j=0;j<n;j++){
if(g[vec[i]][j] == 1){
vis[vec[i]][j] = 1;
vis[j][vec[i]] = 1;
}
}
}
bool flag = true;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(g[i][j] == 1 && (vis[i][j] == 0 || vis[j][i] == 0)){
flag = false;
break;
}
}
if(flag == false) break;
}
if(flag) puts("Yes");
else puts("No");
vec.clear();
}
return 0;
}
D Is It A Red-Black Tree
判断是否红黑树 21分/30分 待补
#include<bits/stdc++.h>
using namespace std;
/*
21分
*/
const int maxn = 1010;
int k,n;
int pre[maxn];
int rb[maxn];
int xb[maxn];
//bool childFlag = true;
struct node{
int v;
int cnt;
node *l;
node *r;
};
void insert(node *root,int pos){
if(root == NULL) return;
if(rb[pos] == 0){
root->cnt++;
}
if(root->v > pre[pos]){
if(root->l == NULL){
root->l = new node();
root->l->v = pre[pos];
root->l->l = NULL;
root->l->r = NULL;
if(rb[pos] == 0) root->l->cnt = 1;
}else{
insert(root->l,pos);
}
}else{
if(root->r == NULL){
root->r = new node();
root->r->v = pre[pos];
root->r->l = NULL;
root->r->r = NULL;
if(rb[pos] == 0) root->r->cnt = 1;
}else{
insert(root->r,pos);
}
}
}
bool checkChild(node *Root){
if(Root->l){
if(rb[Root->v] < 0 && rb[Root->l->v] <0){
return false;
}else{
return checkChild(Root->l);
}
}
if(Root->r){
if(rb[Root->v] < 0 && rb[Root->r->v] <0){
return false;
}else{
return checkChild(Root->r);
}
}
return true;
}
void init(){
for(int i=0;i<=n;i++){
rb[i] = 0;
xb[i] = 0;
pre[i] = 0;
}
}
void bfs(node *root){
if(root == NULL) return;
cout<<root->v<<" "<<root->cnt<<endl;
if(root->l) bfs(root->l);
if(root->r) bfs(root->r);
}
bool can = true;
void travel(node *root){
if(can == false) return;
if(root->v == 15){
int ddd = 1;
}
if(root->l && root->r){
if(root->l->cnt != root->r->cnt) {
can = false;
return;
}
}
if(root->l) {
travel(root->l);
}
if(root->r) {
travel(root->r);
}
}
int main(){
cin>>k;
while(k--){
cin>>n;
init();
for(int i=1;i<=n;i++) {
int d;
cin>>d;
if(d < 0 ){
xb[-d] = 1;
rb[i] = 1;
pre[i] = -d;
}else{
rb[i] = 0;
pre[i] = d;
}
}
node *Root = new node();
Root->l = NULL;
Root->r = NULL;
Root->v = pre[1];
Root->cnt = 1;
for(int i=2;i<=n;i++) insert(Root,i);
if(rb[1] == 1) puts("No");
else if(checkChild(Root) == false) puts("No");
else{
//bfs(Root);
can = true;
travel(Root);
if(can == false) puts("No");
else puts("Yes");
}
}
return 0;
}
最新文章
- Android开发-之监听button点击事件
- exynos4412中断编程
- ROW_NUMBER() OVER的用法
- 1.SpringMVC的简介和环境搭建
- Linux下bash: scp: command not found问题 或者装ssh包时报错 Requires: libedit.so.0()(64bit)
- 利用Arduino快速制作Teensy BadUSB
- 使用 SharedPreferences 实现数据的存储和读取
- hdu 5747 Aaronson
- linux env
- POJ 1661 Help Jimmy （dijkstra，最短路）
- [HIHO1039]字符消除(字符串，枚举，模拟)
- 网络A、B、C类IP地址的区别
- MP4(一)-结构
- 等待事件--db file sequential read
- 机器学习笔记——K-means
- android ndk通过遍历和删除文件
- 第27篇 重复造轮子---模拟IIS服务器
- 用JavaScript实现图片剪切效果
- 2017年最新15个漂亮的 HTML 摄影网站模板
- 咬碎STL空间配置器