1. 知识点总结
100/100,压着点写完的,中途打断了一下但是计时没终止,心惊肉跳的模拟……呜呜呜,加油加油,只希望最后不要爆零就好。
这次的题目总体平缓,没有特别难的,也没有那种很轻松一下子就过的。尤其最后一题还是考察的蛮碎的。
题目 | 难度 | 知识点 |
---|---|---|
1156 Sexy Primes | 🎯 | 数学 |
1157 Anniversary | 🎯 | 结构体STL |
1158 Telefraud Detection | 🎯 | 并查集 |
1159 Structure of a Binary Tree | 🎯🎯 | 二叉树,遍历,字符串操作 |
2. 分题题解
2.1 PAT 1156 Sexy Primes
数学+简单的条件限制时间复杂度,条件限制不加的话会超时几个测试点;
关键词:素数判别
#include<bits/stdc++.h>
using namespace std;
int num1,num2;
bool isPrime(int x){
if(x<=1)return false;
if(x==2||x==3||x==5||x==7||x==11){
return true;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
return false;
}
}
return true;
}
bool flag=false;
int main(){
scanf("%d",&num1);
if(isPrime(num1)){
if(isPrime(num1-6)){
printf("Yes\n%d",num1-6);
flag=true;
}else if(isPrime(num1+6)){
printf("Yes\n%d",num1+6);
flag=true;
}
}
if(!flag){
while(1){
num1++;
if(isPrime(num1)&&(isPrime(num1+6)||isPrime(num1-6))){
printf("No\n%d",num1);
break;
}
}
}
return 0;
}
2.2 PAT 1157 Anniversary
基础的结构体,不能完全说是水题,考察的是英语阅读理解,没错,卡在了English上,但是还是机智的很快反应过来(偶吼吼~
#include<bits/stdc++.h>
using namespace std;
int N;//id个数
int M;//参会id个数
map<string,bool>isAl;
string id;
struct Vistor{
string id;
string birth;
int isok=0;
};
vector<Vistor>vis;
bool cmp(Vistor a,Vistor b){
if(a.isok!=b.isok){
return a.isok>b.isok;
}else{
return a.birth<b.birth;
}
}
int ans=0;
int main(){
scanf("%d",&N);
for(int i=0;i<N;i++){
cin>>id;
isAl[id]=true;
}
scanf("%d",&M);
vis.resize(M);
for(int i=0;i<M;i++){
cin>>id;
vis[i].id=id;
vis[i].birth=id.substr(6,8);
if(isAl.find(id)!=isAl.end()){
vis[i].isok=1;
ans++;
}
}
printf("%d\n",ans);
sort(vis.begin(),vis.end(),cmp);
printf("%s",vis[0].id.c_str());
return 0;
}
2.3 PAT 1158 Telefraud Detection
这题题解写得不是很漂亮,主要是数据量不大,否则我觉得我的解法好像开的空间有点多了……
基本的并查集板子,外面套了一层判断,也就是需要先排除可疑人物再对可疑人物的关系网做一个并查集
#include<bits/stdc++.h>
using namespace std;
//首先筛出可疑人员,再找到gang
int K,N,M;//K是阈值,N是人数,M是电话数
vector<vector<int>>graph;
vector<int>suspect;
vector<bool>isSus;
vector<int>f;
vector<set<int>>ans;
void init(){
for(int i=1;i<=N;i++){
f[i]=i;
ans[i].insert(i);
}
}
int Find(int a){
int x=a;
while(a!=f[a]){
a=f[a];
}
int temp;
while(x!=f[x]){
temp=f[x];
f[x]=a;
x=temp;
}
return a;
}
int Union(int a,int b){
int fa=Find(a);
int fb=Find(b);
if(fa<fb){
f[fb]=fa;//B合并给A
//printf("以%d为根的合并到%d\n",fb,fa);
for(set<int>::iterator it=ans[fb].begin();it!=ans[fb].end();it++){
ans[fa].insert(*it);
}
ans[fb].clear();
}else if(fb<fa){
f[fa]=fb;//A合并给B
//printf("以%d为根的合并到%d\n",fa,fb);
for(set<int>::iterator it=ans[fa].begin();it!=ans[fa].end();it++){
ans[fb].insert(*it);
}
ans[fa].clear();
}
}
int u,v,d;
int main(){
scanf("%d%d%d",&K,&N,&M);
graph.resize(N+1);
isSus.resize(N+1);
ans.resize(N+1);
f.resize(N+1);
fill(isSus.begin(),isSus.end(),false);
for(int i=1;i<=N;i++){
graph[i].resize(N+1);
fill(graph[i].begin(),graph[i].end(),0);
}
for(int i=0;i<M;i++){
scanf("%d%d%d",&u,&v,&d);
//call-receive
graph[u][v]+=d;
}
//首先筛查出可疑人员:A->B的短电话<K且20%的短电话得到了回复
for(int i=1;i<=N;i++){
int call=0;//打出去的短电话个数
int callback=0;//回复的电话
for(int j=1;j<=N;j++){
if(j==i||graph[i][j]==0){
continue;
}else if(graph[i][j]<=5){
call++;
if(graph[j][i]){
callback++;
}
}
}
if(call>K&&callback<=call*0.2){
suspect.push_back(i);
isSus[i]=true;
}
}
if(suspect.size()==0){
printf("None");
}else{
//下面并查集求犯罪集合
init();
int len=suspect.size();
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
int a=suspect[i];
int b=suspect[j];
if(graph[a][b]&&graph[b][a]){
Union(a,b);
}
}
}
//输出结果
for(int i=0;i<len;i++){
int id=suspect[i];
if(ans[id].size()){
bool flag=false;
for(set<int>::iterator it=ans[id].begin();it!=ans[id].end();it++){
if(flag){
printf(" ");
}else{
flag=true;
}
printf("%d",*it);
}
printf("\n");
}
}
}
return 0;
}
2.4 PAT 1159 Structure of a Binary Tree
重新复习了字符串的输入和提取值操作~总体不难,dullTree的定义注意读题,和书上定义有区别嗷!
关键词:二叉树构建,层次遍历
#include<bits/stdc++.h>
using namespace std;
int N,M;
vector<int>post,in;
string str;
struct Node{
int val;
Node*left=NULL,*right=NULL;
int level=0;
Node*parent=NULL;
};
map<int,Node*>mp;
//构建二叉树
bool isFull=true;
Node* build(int inL,int inR,int postL,int postR){
if(inL>inR||postL>postR||inL<0||inR>=N||postL<0||postR>=N){
return NULL;
}
Node *root=new Node;
root->val=post[postR];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==root->val){
break;
}
}
int num=k-inL;
root->left=build(inL,k-1,postL,postL+num-1);
root->right=build(k+1,inR,postL+num,postR-1);
return root;
}
//层序遍历
vector<int>cnt;//每一层的结点个数
int max_level=0;
void levelTravel(Node*root){
queue<Node*>q;
q.push(root);
while(!q.empty()){
Node*top=q.front();
int l=top->level;
mp[top->val]=top;
cnt[l]++;
max_level=top->level;
//printf("level:%d val:%d\n",l,top->val);
q.pop();
if(top->left==NULL&&top->right!=NULL){
isFull=false;
}
if(top->left!=NULL&&top->right==NULL){
isFull=false;
}
if(top->left){
q.push(top->left);
top->left->parent=top;
top->left->level=l+1;
}
if(top->right){
q.push(top->right);
top->right->parent=top;
top->right->level=l+1;
}
}
}
int main(){
scanf("%d",&N);
post.resize(N);
in.resize(N);
cnt.resize(N+1);
fill(cnt.begin(),cnt.end(),0);
for(int i=0;i<N;i++){
scanf("%d",&post[i]);
}
for(int i=0;i<N;i++){
scanf("%d",&in[i]);
}
//构建树
Node *root=build(0,N-1,0,N-1);
levelTravel(root);
scanf("%d",&M);
getchar();
for(int i=0;i<M;i++){
getline(cin,str);
int len=str.length();
if(str[len-1]=='t'){
//A is the root
int val;
sscanf(str.c_str(),"%d is the root",&val);
if(root->val==val){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(str[len-1]=='s'){
//A and B are siblings
int a,b;
sscanf(str.c_str(),"%d and %d are siblings",&a,&b);
if(mp[a]->parent!=NULL&&mp[b]->parent!=NULL&&mp[a]->parent->val==mp[b]->parent->val){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(str[len-1]=='l'){
//A and B are on the same level
int a,b;
sscanf(str.c_str(),"%d and %d are on the same level",&a,&b);
if(mp[a]->level==mp[b]->level){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(str[len-1]=='e'){
//It is a full tree
//满二叉树的定义?
if(isFull){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(find(str.begin(),str.end(),'p')!=str.end()){
//A is the parent of B
int a,b;
sscanf(str.c_str(),"%d is the parent of %d",&a,&b);
if(mp[b]->parent!=NULL&&mp[b]->parent->val==a){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(find(str.begin(),str.end(),'g')!=str.end()){
//A is the right child of B
int a,b;
sscanf(str.c_str(),"%d is the right child of %d",&a,&b);
if(mp[b]->right!=NULL&&mp[b]->right->val==a){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(find(str.begin(),str.end(),'f')!=str.end()){
//A is the left child of B
int a,b;
sscanf(str.c_str(),"%d is the left child of %d",&a,&b);
if(mp[b]->left!=NULL&&mp[b]->left->val==a){
printf("Yes\n");
}else{
printf("No\n");
}
}
}
return 0;
}
3. 参考资料
无,闭卷