当前位置：网站首页>PTA class a simulated 8th bomb: 1164-1167
PTA class a simulated 8th bomb: 1164-1167
2022-06-26 01:43:00 【Republic cake】
1. Summary of knowledge points
Last shot , Just kidding （ There are still many debts ahead ）
at present 1140-1167 What it feels like to me is —— The whole is not particularly difficult （ This refers to the difficulty ≥ The subject of , Of course, the food is still the same , Home efficiency is really …… It's hard to say ）, And as the number of questions increases , The feeling of routine questions has not changed , Should the template be or should it be , It is best to be able to use flexibly , Because one of the general four topics is about strain （ Be commonly called “ Card score question ”）
Feeling pta Can lay the foundation ~ But the knowledge involved is still incomplete , Preparing for the machine test still requires extensive practice …… Otherwise, it will be for nothing
| Question no | difficulty | Knowledge point |
|---|---|---|
| 1164 | string manipulation + matrix | |
| 1165 | Linked list | |
| 1166 | Simple applications of graphs | |
| 1167 | Middle preface + Pile up （ Binary tree simple application ） |
2. Sub topic solution
2.1 The first question is 1164 Good in C (20 branch )
String processing and basic use of matrix , Keep your mind steady ~
The format is strictly in accordance with the meaning of the title ( Don't be rash )
The difficulty lies in sentence segmentation , involves string Substring function uses
#include<bits/stdc++.h>
using namespace std;
string sentence;
vector<string>words;// Segment sentences
struct Alpha{
char matrix[7][5];
};
Alpha alpha[26];
void Cut(){
// Segment sentences
int len=sentence.length();
int left=0,right=0;
string word;
bool flag=false;
int i;
for(i=0;i<len;i++){
if(sentence[i]<='Z'&&sentence[i]>='A'){
if(!flag){
flag=true;
left=i;
}
}else{
// There are consecutive letters in front
if(flag){
word=sentence.substr(left,i-left);
words.push_back(word);
flag=false;
}
}
}
if(flag&&i-left>0){
word=sentence.substr(left,i-left);
words.push_back(word);
}
}
void Print(string word){
int len=word.length();
for(int row=0;row<7;row++){
if(row){
printf("\n");
}
for(int col=0;col<len;col++){
// Print every letter
if(col!=0)printf(" ");
for(int i=0;i<5;i++){
int id;
if(word[col]<='Z'&&word[col]>='A'){
id=word[col]-'A';
}else{
id=word[col]-'a';
}
printf("%c",alpha[id].matrix[row][i]);
}
}
}
}
int main(){
for(int i=0;i<26;i++){
for(int row=0;row<7;row++){
for(int column=0;column<5;column++){
cin>>alpha[i].matrix[row][column];
}
}
}
getchar();
getline(cin,sentence);
Cut();
for(int i=0;i<words.size();i++){
if(i)printf("\n\n");
Print(words[i]);
}
return 0;
}
2.2 The second question is 1165 Block Reversing (25 branch )
Static list basic questions , Not very hard , Pay attention to the details of the output
But it needs to be revised
The first edition :24/25
#include<bits/stdc++.h>
using namespace std;
int L,N,num;
int head;
struct Node{
int val;
int addr;
int next;
};
map<int,Node>nodes;
int addr,val,next_node;
vector<Node>list1;
int main(){
scanf("%d%d%d",&head,&N,&L);
for(int i=0;i<N;i++){
scanf("%d%d%d",&addr,&val,&next_node);
Node temp;
temp.addr=addr;
temp.val=val;
temp.next=next_node;
nodes[addr]=temp;
}
// First
int p=head;
while(p!=-1){
list1.push_back(nodes[p]);
p=nodes[p].next;
}
//list1 In the store : How to output
//0 1 2 3 4 5 6 7
int n=N/L+(N%L==0?0:1);
int res=N%L;
int fid;
bool flag=false;
for(int i=n;i>=1;i--){
if(res){
num=res;
fid=(i-1)*L;
}else{
num=L;
fid=(i-1)*L;
}
if(res)res=0;
for(int j=fid;j<fid+num;j++){
if(!flag){
flag=true;
}else{
printf(" %05d\n",list1[j].addr);
}
printf("%05d %d",list1[j].addr,list1[j].val);
}
}
printf(" -1");
return 0;
}
The second edition ：AC
#include<bits/stdc++.h>
using namespace std;
int head,n,block;
int arr,val,nex;
struct Node{
int arr;
int val;
int next;
};
map<int,Node>nodes;
vector<Node>list0;
int main(){
scanf("%d%d%d",&head,&n,&block);
for(int i=0;i<n;i++){
scanf("%d%d%d",&arr,&val,&nex);
Node temp;
temp.arr=arr;
temp.val=val;
temp.next=nex;
nodes[arr]=temp;
}
int p=head;
while(p!=-1){
list0.push_back(nodes[p]);
p=nodes[p].next;
}
// change , Output : 0 1 2 3 4 5 6 7
//1 2 3 4 5 6 7 8
bool flag=false;
int len=list0.size();
int res=len%block;
int times=len/block;
if(res!=0)times++;
//printf(" need %d Time \n",times);
for(int i=1;i<=times;i++){
int first=(times-i)*block;
//printf("first=%d\n",first);
int num=block;
if(i==1&&res)num=res;
//printf("num=%d\n",num);
// Output
for(int j=0;j<num;j++){
if(!flag){
flag=true;
}else{
printf(" %05d\n",list0[first+j].arr);
}
printf("%05d %d",list0[first+j].arr,list0[first+j].val);
}
}
printf(" -1");
return 0;
}
/* A test point ： 00100 8 4 71120 7 88666 00000 4 99999 00100 1 12309 68237 6 71120 33218 3 00000 99999 5 68237 88666 8 -1 12309 2 33218 need 2 Time 00100 1 12309 12309 2 33218 33218 3 00000 00000 4 -1 */
2.3 Third question 1166 Summit (25 branch )
Basic problems of graph theory ：
Adjacency graph , No time and memory card , Feel free to write
#include<bits/stdc++.h>
using namespace std;
int n,m;
int k,l;
int a ,b;
vector< vector<int> >relation;
vector<int>q;
vector<int>visnum;
vector<bool>isin;
int main(){
scanf("%d%d",&n,&m);
relation.resize(n+1);
visnum.resize(n+1);
isin.resize(n+1);
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
if(a==b)continue;
relation[a].push_back(b);
relation[b].push_back(a);
}
scanf("%d",&k);
for(int cnt=1;cnt<=k;cnt++){
fill(visnum.begin(),visnum.end(),0);
fill(isin.begin(),isin.end(),false);
scanf("%d",&l);
q.resize(l);
for(int i=0;i<l;i++){
scanf("%d",&q[i]);
isin[q[i]]=true;
}
for(int i=0;i<l;i++){
int id=q[i];
for(int j=0;j<relation[id].size();j++){
int fid=relation[id][j];
visnum[fid]++;
}
}
// Calculation 1 illegal 2 Someone forgot to invite
int flag=0;
int ans=n+1;
for(int id=1;id<=n;id++){
if(isin[id]&&visnum[id]!=l-1){
flag=1;
printf("Area %d needs help.\n",cnt);
break;
}else if(!isin[id]&&visnum[id]==l){
ans=min(ans,id);
flag=2;
}
}
if(flag==2){
printf("Area %d may invite more people, such as %d.\n",cnt,ans);
} else if(flag==0){
printf("Area %d is OK.\n",cnt);
}
}
return 0;
}
2.4 Fourth question 1167 Cartesian Tree (30 branch )
Simple questions , It belongs to the middle order + A class of problems of reconstructing tree structure by heap sorting （ Similar middle order + In the following order || Middle preface + Preface ）, The difficulty should be simple , Sequence each time from the middle (inL,inR) Find the smallest as the root node , The left-right sequence recurses to the next left-right subtree
#include<bits/stdc++.h>
using namespace std;
int N;
const int INF=99999999;
// The result of sequence traversal output in the small top heap ----> Sequence traversal output
struct Node{
int val;
Node*left=NULL;
Node*right=NULL;
};
vector<int>in;
Node*build(int inL,int inR){
if(inR<inL){
return NULL;
}
// Find the root node
int min_num=INF;
int min_id=-1;
for(int k=inL;k<=inR;k++){
if(in[k]<min_num){
min_num=in[k];
min_id=k;
}
}
Node *root=new Node;
root->val=min_num;
root->left=build(inL,min_id-1);
root->right=build(min_id+1,inR);
return root;
}
// Level traversal
void levelTravel(Node *root){
queue<Node*>q;
q.push(root);
bool flag=false;
while(!q.empty()){
Node*top=q.front();
Node*temp;
q.pop();
if(top->left!=NULL){
temp=top->left;
q.push(temp);
}
if(top->right!=NULL){
temp=top->right;
q.push(temp);
}
if(!flag){
flag=true;
}else{
printf(" ");
}
printf("%d",top->val);
}
return;
}
int main(){
scanf("%d",&N);
in.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&in[i]);
}
Node *root=build(0,N-1);
levelTravel(root);
return 0;
}
twitter , This year's exam questions are quite easy~
3. Reference link
边栏推荐
猜你喜欢
随机推荐
如何为政企移动办公加上一道“安全锁”？
Postman斷言對應脚本的解釋
Abnova丨CMV CISH 探头解决方案
Shell regular expression
Perfdog
Oracle数据库完全卸载步骤（暂无截图）
Laravel basic course routing and MVC - controller
web测试
JSON实例（一）
Web Testing
Install tensorflow GPU miscellaneous
UN make (6) makefile的条件执行
Have you considered going or staying in graduation season
[excel knowledge and skills] Excel data type
王老吉药业“关爱烈日下最可爱的人”公益活动在杭启动
缓冲
"Hot post" Statistics
Remote incremental synchronization artifact Rsync
RT thread project engineering construction and configuration - (Env kconfig)
Maze walking