当前位置：网站首页>PTA class a simulated sixth bomb: 1156-1159
PTA class a simulated sixth bomb: 1156-1159
2022-06-26 01:43:00 【Republic cake】
title: Class a simulation 1156-1159
date: 2022-02-02 11:44:50
categories:
- Algorithm and data structure
tags: - Programming practice
- PTA
1. Summary of knowledge points
There is no time today （ It should be ……） The only one that doesn't have AC The test point of is 1158, So be careful with the last two questions , Hold your mind ~
The knowledge points involved in this assignment are ：
- Simple mathematics
- string manipulation + Structure ordering +STL（ Optional ）
- Union checking set
- STL Use + Trees
| Question no | difficulty | Knowledge point |
|---|---|---|
| 1156 | Simple mathematics （ Prime judgment ） | |
| 1157 | string manipulation + Structure ordering | |
| 1158 | Union checking set +STL | |
| 1159 | Trees （ The difficulty is OK , Although the code length is quite …… But the basis of investigation , No card time ） |
2. Sub topic solution
2.1 The first question is ：PTA Class A 1156
Look at simple mathematics ：
Given a N, If
N+6 and N Simultaneously primeperhapsN-6 and N Simultaneously primeThink it is sexy The number of
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int x){
if(x<=1)return false;
if(x==2||x==3||x==5||x==7)return true;
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
int x;
int ans;
bool isSexy(int x){
if(isPrime(x)&&isPrime(x+6))return true;
if(isPrime(x)&&isPrime(x-6))return true;
return false;
}
int main(){
scanf("%d",&x);
if(isSexy(x)){
printf("Yes\n");
if(isPrime(x-6)){
printf("%d",x-6);
}else{
printf("%d",x+6);
}
}else{
printf("No\n");
ans=x+1;
while(!isSexy(ans)){
ans++;
}
printf("%d",ans);
}
return 0;
}
2.2 The second question is ：PTA Class A 1157
string manipulation ＋ Structure ordering ： Simple questions
#include<bits/stdc++.h>
using namespace std;
int N;
int M;
map<string,bool>alumni;
vector<string>comer;
vector<string>ans;
string temp;
bool cmp(string a,string b){
if(a.length()!=b.length()){
return a.length()>b.length();
}else{
string tempa=a.substr(6,8);
string tempb=b.substr(6,8);
return tempa<tempb;// The date of birth is small
}
}
int main(){
scanf("%d",&N);
for(int i=0;i<N;i++){
cin>>temp;
alumni[temp]=true;
}
scanf("%d",&M);
comer.resize(M);
for(int i=0;i<M;i++){
cin>>comer[i];
if(alumni[comer[i]]==true){
ans.push_back(comer[i]);
}
}
int cnt=ans.size();
printf("%d\n",cnt);
if(cnt==0){
sort(comer.begin(),comer.end(),cmp);
cout<<comer[0];
}else{
sort(ans.begin(),ans.end(),cmp);
cout<<ans[0];
}
return 0;
}
2.3 Third question ：PTA Class A 1158
A magic question ：
It's not hard to think , Just pay attention to the details ~
Ideas 1： Bypass and look up the set （ Because I forgot ）…… Then the cup came out
When I comment out 61 That's ok , The second test point is just
When I comment out 60 That's ok , The fourth test point is just
Open the door to the absurd …… It's ridiculous （ Good , Food is original sin ）
Ideas 2：
And look up the set output gang
Train of thought ：
During the review, I found that there was no way to get around the problem （a-b b-c Under the circumstances ……a And c Or a nest of ）, The following code does not solve this problem
#include<bits/stdc++.h>
using namespace std;
//
int k,m,n;
int caller,receiver,duration;
vector<int>suspects;
const int maxn=1009;
int hasConnect[maxn][maxn];
bool vis[maxn];
// Print out the criminal gang
int main(){
scanf("%d%d%d",&k,&n,&m);
memset(hasConnect,-1,sizeof(hasConnect));
memset(vis,false,sizeof(vis));
for(int i=0;i<m;i++){
scanf("%d%d%d",&caller,&receiver,&duration);
if(hasConnect[caller][receiver]==-1){
hasConnect[caller][receiver]=duration;
}else{
hasConnect[caller][receiver]+=duration;
}
}
for(int i=1;i<=n;i++){
int cnt=0;// Short call , Call out
int back=0; // reply
for(int j=1;j<=n;j++){
if(hasConnect[i][j]==-1)continue;// I haven't played
if(hasConnect[i][j]<=5&&hasConnect[j][i]==-1){
cnt++;
} else if(hasConnect[i][j]<=5&&hasConnect[j][i]!=-1){
cnt++;
back++;
}
}
if(cnt>k&&back<=0.2*cnt){
suspects.push_back(i);
}
}
int len=suspects.size();
// There's nothing wrong with it
if(len==0){
printf("None");
}else{
// They belong to the same criminal group
sort(suspects.begin(),suspects.end());
for(int i=0;i<len;i++){
// Output leader
if(!vis[suspects[i]]){
printf("%d",suspects[i]);
vis[suspects[i]]=true;
}else{
continue;
}
// Output attendant
for(int j=i+1;j<len;j++){
// Call each other
//if((hasConnect[suspects[i]][suspects[j]]!=-1&&hasConnect[suspects[j]][suspects[i]]!=-1)&&!vis[suspects[j]]){
if((hasConnect[suspects[i]][suspects[j]]!=-1||hasConnect[suspects[j]][suspects[i]]!=-1)&&!vis[suspects[j]]){
printf(" %d",suspects[j]);
vis[suspects[j]]=true;
}else{
continue;
}
}
printf("\n");
}
}
return 0;
}
Train of thought two ：
There's nothing to say , And look it up and review it , More basic
Pay attention to is , First filter to get suspects Array , And then when you do it and look it up , It was used map<int,int> Store the parent node
For positive order output , It was used
map<int,set<int> >Store answers , Default ascending order
The reference blog gives DFS And joint search set , For the time being, we will consolidate and search the collection
#include<bits/stdc++.h>
using namespace std;
// And look up the set solution
int k,m,n;
int caller,receiver,duration;
vector<int>suspects;
const int maxn=1009;
int hasConnect[maxn][maxn];
bool vis[maxn];
// Print out the criminal gang
// And look up the template
map<int,int>f;
int Find(int x){
int a=x;
while(x!=f[x]){
x=f[x];
}
// Reduce time complexity
int temp;
while(a!=f[a]){
temp=a;
a=f[a];
f[temp]=x;
}
return x;
}
void Union(int a,int b){
int fa=Find(a);
int fb=Find(b);
if(fa<fb){
f[fb]=fa;
}else{
f[fa]=fb;
}
}
int main(){
scanf("%d%d%d",&k,&n,&m);
memset(hasConnect,-1,sizeof(hasConnect));
memset(vis,false,sizeof(vis));
for(int i=0;i<m;i++){
scanf("%d%d%d",&caller,&receiver,&duration);
if(hasConnect[caller][receiver]==-1){
hasConnect[caller][receiver]=duration;
}else{
hasConnect[caller][receiver]+=duration;
}
}
for(int i=1;i<=n;i++){
int cnt=0;// Short call , Call out
int back=0; // reply
for(int j=1;j<=n;j++){
if(hasConnect[i][j]==-1)continue;// I haven't played
if(hasConnect[i][j]<=5&&hasConnect[j][i]==-1){
cnt++;
} else if(hasConnect[i][j]<=5&&hasConnect[j][i]!=-1){
cnt++;
back++;
}
}
if(cnt>k&&back<=0.2*cnt){
suspects.push_back(i);
}
}
int len=suspects.size();
// There's nothing wrong with it
if(len==0){
printf("None");
}else{
// Union checking set
for(int i=0;i<len;i++){
f[suspects[i]]=suspects[i];// initialization
}
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
if(hasConnect[suspects[i]][suspects[j]]!=-1&&hasConnect[suspects[j]][suspects[i]]!=-1){
Union(suspects[i],suspects[j]);
}
}
}
map<int,set<int> >ans;
for(int i=0;i<len;i++){
int id=suspects[i];
int fid=Find(id);
ans[fid].insert(id);
}
// Output the answer
for(map<int,set<int> >::iterator it=ans.begin();it!=ans.end();it++){
set<int>temp=it->second;
bool flag=false;
for(set<int>::iterator it2=temp.begin();it2!=temp.end();it2++){
if(!flag){
flag=true;
}else{
printf(" ");
}
printf("%d",*it2);
}
printf("\n");
}
}
return 0;
}
2.4 Fourth question ：PTA Class A 1159
No time card …… therefore , Although the code is long , But it's all basic ：
- In the sequence traversal + Post order traversal to build the tree
- Application of sequence traversal （ Basics ）
- STL in map Reduce coding difficulty
- string in sscanf Use
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Node{
int val;
int level;
Node*left=NULL;
Node*right=NULL;
};
vector<int>post;
vector<int>in;
// The template , Need to be familiar with
Node*build(int postL,int postR,int inL,int inR){
if(postL>postR){
return NULL;
}
Node *root=new Node;
root->val=post[postR];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==post[postR]){
break;
}
}
int left_num=k-inL;
root->left=build(postL,postL+left_num-1,inL,k-1);
root->right=build(postL+left_num,postR-1,k+1,inR);
return root;
}
int isFull(Node*root){
// Except for the leaf nodes , Both have two children
if(root==NULL){
return 1;
}
if(root->right==NULL&&root->left==NULL){
return 1;
}
if(root->right==NULL&&root->left!=NULL){
return 0;
}
if(root->right!=NULL&&root->left==NULL){
return 0;
}else{
return isFull(root->left)*isFull(root->right);
}
}
string temp;
map<int,bool>exist;// Record whether there is
map<int,int>levels;// Record the number of layers
map<int,int>father;
map<int,int>rchild;
map<int,int>lchild;
void levelTravel(Node*root){
queue<Node*>q;
root->level=1;
q.push(root);
while(!q.empty()){
Node *top=q.front();
levels[top->val]=top->level;// The layer number
q.pop();
Node*left=top->left;
Node*right=top->right;
if(left!=NULL){
lchild[top->val]=left->val;
left->level=top->level+1;
q.push(left);
father[left->val]=top->val;
}else{
lchild[top->val]=-1;
}
if(right!=NULL){
rchild[top->val]=right->val;
right->level=top->level+1;
q.push(right);
father[right->val]=top->val;
}else{
rchild[top->val]=-1;
}
}
}
int main(){
scanf("%d",&n);
post.resize(n);
in.resize(n);
for(int i=0;i<n;i++){
scanf("%d",&post[i]);
exist[post[i]]=true;
}
for(int i=0;i<n;i++){
scanf("%d",&in[i]);
}
Node *root=NULL;
root=build(0,n-1,0,n-1);
int isfull=isFull(root);
levelTravel(root);
scanf("%d",&m);
m++;
while(m--){
getline(cin,temp);
int len=temp.length();
if(temp=="It is a full tree"){
if(isfull){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(temp[len-1]=='t'){
//---is the root
int ask=-1;
const char *p= temp.c_str();
sscanf(p,"%d is the root",&ask);
if(root!=NULL&&root->val==ask){
printf("Yes\n");
}else{
printf("No\n");
}
}else if(temp[len-1]=='s'){
//-- and -- are siblings
int a,b;
const char *p= temp.c_str();
sscanf(p,"%d and %d are siblings",&a,&b);
if(exist[a]&&exist[b]){
if(a==b||father[a]&&father[b]&&father[a]==father[b])
printf("Yes\n");
else{
printf("No\n");
}
}else{
printf("No\n");
}
}else if(temp[len-1]=='l'){
//-- and -- are on the same level
int a,b;
const char *p= temp.c_str();
sscanf(p,"%d and %d are on the same level",&a,&b);
if(exist[a]&&exist[b]){
if(levels[a]==levels[b]){
printf("Yes\n");
}else{
printf("No\n");
}
}else{
printf("No\n");
}
}else if(temp.find('p')!=string::npos){
//32 is the parent of 11
int a,b;
const char *p= temp.c_str();
sscanf(p,"%d is the parent of %d",&a,&b);
if(exist[a]&&exist[b]){
if(father[b]&&father[b]==a){
printf("Yes\n");
}else{
printf("No\n");
}
}else{
printf("No\n");
}
}else if(temp.find('r')!=string::npos){
//28 is the right child of 2
int a,b;
const char *p= temp.c_str();
sscanf(p,"%d is the right child of %d",&a,&b);
if(exist[a]&&exist[b]){
if(rchild[b]&&rchild[b]==a){
printf("Yes\n");
}else{
printf("No\n");
}
}else{
printf("No\n");
}
}else if(temp.find('l')!=string::npos){
//28 is the left child of 2
int a,b;
const char *p= temp.c_str();
sscanf(p,"%d is the left child of %d",&a,&b);
if(exist[a]&&exist[b]){
if(lchild[b]&&lchild[b]==a){
printf("Yes\n");
}else{
printf("No\n");
}
}else{
printf("No\n");
}
}
}
return 0;
}
3. Reference material
边栏推荐
- JSON简介
- 2021-1-15 fishing notes ctrl+c /v
- Is it safe to open a securities account online
- Viwi interface
- Longitude and latitude multipoint acquisition center point has been solved
- 2021-1-15 摸鱼做的笔记Ctrl+c /v来的
- How to search papers in a certain field
- 17.11 std::atomic续谈、std::async深入谈
- easyexcel读取文件
- Talking about interface test (2)
猜你喜欢
![[flower carving experience] 11 start esp32c3](/img/ff/d7c266893ef4ef70c6536085927e0e.jpg)
随机推荐
Android system startup security
Perfdog
图文大师印章简易制作
shell正则表达式
Assertion of postman interface test
正则表达式
Maze walking
Common deep learning optimizers
21. Hoff circle transformation
Web Testing
Data arrangement of machinetranslation
Explication du script correspondant à l'assertion Postman
蒟蒻初学单片机的一丢丢笔记
浅谈接口测试（二）
Talking about interface test (I)
Several methods of JQ obtaining objects
浅谈接口测试（一）
论文阅读 Exploring Temporal Information for Dynamic Network Embedding
CYCA少儿形体礼仪 乐清市培训成果考核圆满落幕
easyexcel读取文件