1. 知识点总结
100/100,2h10min
本次的题目涉及很多经典数据结构，但是模板用的不多，基本的暴力+STL即可解决
| 题目 | 难度 | 知识点 |
|---|---|---|
| 1132 Cut Integer | 🎯 | 字符串 |
| [**1133 Splitting A Linked List**](题目详情 - 1133 Splitting A Linked List (pintia.cn)) | 🎯 | 链表 |
| 1134 Vertex Cover | 🎯 | 图论 |
| 1135 Is It A Red-Black Tree | 🎯🎯 | 红黑树判断 |
2. 分题题解
2.1 PAT 1132 Cut Integer
字符串处理,基础的基础哈
#include<bits/stdc++.h>
using namespace std;
int N;
string Z;
int main(){
scanf("%d",&N);
while(N--){
cin>>Z;
int len=Z.length();
int a=stoi(Z.substr(0,len/2));
int b=stoi(Z.substr(len/2,len));
if(a*b&&stoi(Z)%(a*b)==0){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
} 2.2 PAT 1133 Splitting A Linked List
链表基础题，其实简单的写法最后用merge或者insert合并可能看起来更简洁
#include<bits/stdc++.h>
using namespace std;
//将负数单独拎出来提到前面去
struct Node{
int addr;
int val;
int next=-1;
};
int N,K,head;
map<int,Node>mp;
Node temp;
vector<Node>a,b,c,d; //负数 小于等于K 大于等于K
int main(){
scanf("%d%d%d",&head,&N,&K);
for(int i=0;i<N;i++){
scanf("%d%d%d",&temp.addr,&temp.val,&temp.next);
mp[temp.addr]=temp;
}
int p=head;
while(p!=-1){
temp=mp[p];
p=temp.next;
if(temp.val<0){
a.push_back(temp);
}else if(temp.val<=K){
b.push_back(temp);
}else{
c.push_back(temp);
}
}
//输出答案
for(int i=0;i<a.size();i++){
d.push_back(a[i]);
}
for(int i=0;i<b.size();i++){
d.push_back(b[i]);
}
for(int i=0;i<c.size();i++){
d.push_back(c[i]);
}
int lend=d.size();
for(int i=0;i<lend;i++){
printf("%05d %d ",d[i].addr,d[i].val);
if(i+1<lend){
printf("%05d\n",d[i+1].addr);
}
}
printf("-1");
return 0;
} 2.3 PAT 1134 Vertex Cover
图论，关键是理解题目的意思：需要使得给的sets包含图中所有边涉及到的两个结点之一
#include<bits/stdc++.h>
using namespace std;
int N,M,K,u,v,num,a;
vector<bool>has;
struct Edge{
int u,v;
};
vector<Edge>edges;
Edge temp;
int main(){
scanf("%d%d",&N,&M);
for(int i=0;i<M;i++){
scanf("%d%d",&temp.u,&temp.v);
edges.push_back(temp);
}
scanf("%d",&K);
has.resize(N);
for(int i=0;i<K;i++){
scanf("%d",&num);
fill(has.begin(),has.end(),false);
for(int j=0;j<num;j++){
scanf("%d",&a);
has[a]=true;
}
bool flag=true;
for(int x=0;x<M;x++){
temp=edges[x];
if(has[temp.u]||has[temp.v]){
continue;
}else{
printf("No\n");
flag=false;
break;
}
}
if(flag){
printf("Yes\n");
}
}
return 0;
}2.4 PAT 1135 Is It A Red-Black Tree
判断涉及到重新构建树（根据in和pre数组），层次遍历（为每个叶子结点跟踪到父节点做准备）;
需要理解题意的基础上掌握一定的二叉树模板进行解题，难点在于：
(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.的判断。
具体代码如下，自认为注释还是可以的~
#include<bits/stdc++.h>
using namespace std;
int K,N;
vector<int>pre,in;
struct Node{
int val;
Node*left=NULL;
Node*right=NULL;
Node*parent=NULL;
int cnt=-1;
};
bool r1b2;
Node *build(int preL,int preR,int inL,int inR){
if(preL<0||preR>=N||inL<0||inR>=N||preL>preR||inL>inR){
return NULL;
}
Node*root=new Node;
root->val=pre[preL];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==root->val){
break;
}
}
int num=k-inL;
root->left=build(preL+1,preL+num,inL,k-1);//num
root->right=build(preL+num+1,preR,k+1,inR);
if(root->val<0){
//如果结点为红色，子节点需要为黑
if((root->left!=NULL&&root->left->val<0)||(root->right!=NULL&&root->right->val<0)){
r1b2=false;
}
}
return root;
}
bool cmp(int a,int b){
return abs(a)<abs(b);
}
bool isok;
void levelTravel(Node*root){
queue<Node*>q;
q.push(root);
while(!q.empty()){
Node*top=q.front();
q.pop();
if(top->left!=NULL){
top->left->parent=top;
q.push(top->left);
}
if(top->right!=NULL){
top->right->parent=top;
q.push(top->right);
}
if((top->left==NULL||top->right==NULL)&&isok){
//遍历其根结点
int cnt=1;
while(top!=NULL){
if(top->val>0){
cnt++;
}
if(top->cnt==-1){
top->cnt=cnt;
}else if(top->cnt!=cnt){
isok=false;
break;
}
top=top->parent;
}
}
}
}
int main(){
scanf("%d",&K);
while(K--){
r1b2=true;
isok=true;
scanf("%d",&N);
pre.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&pre[i]);
}
in=pre;
sort(in.begin(),in.end(),cmp);
Node*root=build(0,N-1,0,N-1);
if(root->val<0||!r1b2){
printf("No\n");//根节点不为黑
}else{
//每个结点到其降序输出的叶子结点经过的黑色结点都相同数目
levelTravel(root);
if(!isok){
printf("No\n");
}else{
printf("Yes\n");
}
}
}
return 0;
}3. 参考资料
无
