当前位置：网站首页>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
边栏推荐
- Loss function of depth model
- 俏皮少女王艺璇 受邀担任第六季完美童模全球总决赛推广大使
- 2022 documenter general basic (documenter) exam simulation 100 questions and online simulation exam
- 微信朋友圈测试点
- Postman断言对应脚本的解释
- What happens from entering a web address in the browser's input box to seeing the contents of the web page?
- 图文大师印章简易制作
- JQ获取对象的几种方式
- Fasttext knowledge points summary
- Some summary of model compression
猜你喜欢
随机推荐
recv ＆ send
从在浏览器的输入框输入一个网址，到看到网页的内容，这个过程中发生了什么？
Oracle数据库完全卸载步骤（暂无截图）
STM32 key development foundation
2022 explosion proof electrical operation certificate examination question bank and simulation examination
元素定位的八大法则
Oracle database startup backup preparation
大周建议自媒体博主前期做这4件事
论文阅读 Exploring Temporal Information for Dynamic Network Embedding
Accumulation of some knowledge points in machine learning
“热帖”统计
Embedded c learning notes
判定积分给业务带来价值的两个指标
图文大师印章简易制作
弹性蛋白酶的用途和化学性质
Quickly generate 1~20 natural numbers and easily copy
王老吉药业“关爱烈日下最可爱的人”公益活动在杭启动
Test questions and answers for the 2022 baby sitter (Level 5) examination
手机卡开户的流程是什么？网上开户是否安全么？
readv ＆ writev