当前位置：网站首页>PTA class a simulated second bullet: 1136-1139
PTA class a simulated second bullet: 1136-1139
2022-06-26 01:43:00 【Republic cake】
emm These are data structure related topics , In recent years, the difficulty is certainly greater than these problems ~, The sequence of machine test exercises ：PTA->LeetCode, The revolution has not yet succeeded , Rookies still have to work hard
- Mainly for the convenience of future disk recovery , So the first three questions AC Code at the end , Put the wrong question first （ I am used to overturning , I always think it will be used again in the future ）
- The most important thing is to examine the topic , English is very important
| Question no | difficulty | Inspection point |
|---|---|---|
| 1136 | string Handle | |
| 1137 | Sort simulation | |
| 1138 | In the sequence traversal + The previous sequence traverses the recovery tree structure （ Post order traversal output ） | |
| 1139 | simulation + chart （ Pay attention to weight removal ） |
1139 First Contact (30 branch )
24/30: The simulation is very redundant , In fact, several plates are not sealed , So it looks complicated , In fact, the idea is still more violent and has no skills
#include<bits/stdc++.h>
using namespace std;
int n,m;
int k;
int a,b;
/*24/30zhong*/
const int maxn=20000;//0 0000-0 9999 schoolboy ** 1 0000 1 9999 girl student
vector< vector<int> >graph(maxn);
struct Ans{
int f1;
int f2;
};
vector<Ans>ans;
bool hasConnect(int id1,int id2){
for(int i=0;i<graph[id1].size();i++){
if(graph[id1][i]==id2)return true;
}
return false;
}
int Find(int sex,int id,int tid){
int sum=0;
Ans temp;
if(sex==1){
// schoolboy
for(int i=0;i<graph[id].size();i++){
int id2=graph[id][i];
if(id2>=10000)continue;// The first one is boys
for(int j=0;j<graph[id2].size();j++){
int id3=graph[id2][j];
if(id3<10000)continue;// The second is a girl
if(hasConnect(id3,tid)){
sum++;
temp.f1=id2;
temp.f2=id3;
ans.push_back(temp);
}
}
}
}else if(sex==0){
for(int i=0;i<graph[id].size();i++){
int id2=graph[id][i];
if(id2<10000)continue;// The first is a girl
for(int j=0;j<graph[id2].size();j++){
int id3=graph[id2][j];
if(id3>=10000)continue;// The second is a boy
if(hasConnect(id3,tid)){
sum++;
temp.f1=id2;
temp.f2=id3;
ans.push_back(temp);
}
}
}
}else if(sex==2){
//2 girl student
for(int i=0;i<graph[id].size();i++){
int id2=graph[id][i];
if(id2<10000)continue;// The first is girl student
for(int j=0;j<graph[id2].size();j++){
int id3=graph[id2][j];
if(id3<10000)continue;// The second is a girl
if(hasConnect(id3,tid)){
sum++;
temp.f1=id2;
temp.f2=id3;
ans.push_back(temp);
}
}
}
}else{
for(int i=0;i<graph[id].size();i++){
int id2=graph[id][i];
if(id2>=10000)continue;// The first one is boys
for(int j=0;j<graph[id2].size();j++){
int id3=graph[id2][j];
if(id3>=10000)continue;// The second is a boy
if(hasConnect(id3,tid)){
sum++;
temp.f1=id2;
temp.f2=id3;
ans.push_back(temp);
}
}
}
}
return ans.size();
}
int sum;
// schoolboy girl student
bool cmp(Ans a,Ans b){
if(a.f1!=b.f1){
return a.f1<b.f1;
}else{
return a.f2<b.f2;
}
}
char aa[10];
char bb[10];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
// Friendship
cin>>aa>>bb;
if(aa[0]=='-'){
a=10000-atoi(aa);
}else{
a=atoi(aa);
}
if(bb[0]=='-'){
b=10000-atoi(bb);
}else{
b=atoi(bb);
}
//printf("############################ a=%d b=%d\n",a,b);
graph[a].push_back(b);
graph[b].push_back(a);
}
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%d%d",&a,&b);
// schoolboy - girl student
if(a<0&&b>=0){
a=10000-a;
// girl student
sum=Find(0,a,b);
//printf("ANS:\n");
printf("%d\n",sum);
sort(ans.begin(),ans.end(),cmp);
for(int i=0;i<sum;i++){
printf("%04d %04d\n",ans[i].f1%10000,ans[i].f2%10000);
}
}else if(b<0&&a>=0){
b=10000-b;
// schoolboy
sum=Find(1,a,b);
//printf("ANS:\n");
printf("%d\n",sum);
sort(ans.begin(),ans.end(),cmp);
for(int i=0;i<sum;i++){
printf("%04d %04d\n",ans[i].f1%10000,ans[i].f2%10000);
}
}else if(a<0&&b<0){
// Same sex : Duplicate check
a=10000-a;
b=10000-b;
sum=Find(2,a,b);
//printf("ANS:\n");
//printf("%d\n",sum);
sort(ans.begin(),ans.end(),cmp);
int diff=0;
for(int i=0;i<sum;i++){
bool flag=true;
for(int j=i+1;j<sum;j++){
if(ans[i].f1==ans[j].f2&&ans[i].f2==ans[j].f1){
flag=false;
break;
}
}
if(flag)diff++;
}
printf("%d\n",diff);
for(int i=0;i<sum;i++){
bool flag=true;
for(int j=i+1;j<sum;j++){
if(ans[i].f1==ans[j].f2&&ans[i].f2==ans[j].f1){
flag=false;
break;
}
}
if(flag){
printf("%04d %04d\n",ans[i].f1%10000,ans[i].f2%10000);
}
}
} else if(a>=0&&b>=0){
sum=Find(3,a,b);
//printf("ANS:\n");
sort(ans.begin(),ans.end(),cmp);
int diff=0;
for(int i=0;i<sum;i++){
bool flag=true;
for(int j=i+1;j<sum;j++){
if(ans[i].f1==ans[j].f2&&ans[i].f2==ans[j].f1){
flag=false;
break;
}
}
if(flag)diff++;
}
printf("%d\n",diff);
for(int i=0;i<sum;i++){
bool flag=true;
for(int j=i+1;j<sum;j++){
if(ans[i].f1==ans[j].f2&&ans[i].f2==ans[j].f1){
flag=false;
break;
}
}
if(flag){
printf("%04d %04d\n",ans[i].f1%10000,ans[i].f2%10000);
}
}
}
ans.clear();
}
return 0;
}
Revision ：
This inscription has been written for a long time , The first three sample points are relatively simple , Note that the output is 04d And the same-sex situation , Then you can't enter directly int, Otherwise -0 Classified as male （ If you don't believe it, you can try ）
Refer to Liu Shen's code and find the error factors as follows ：
- Without considering the same sex A-B-A-B The situation of （ Two more test points can be passed after the revision ~+2 branch ）
- There is also a test point where I don't know what is wrong , So violence absorbs the thought of Liu Shen's code ed
- The overall thinking time complexity is high , You should first find out all and A Friends of the same sex , Find out and B Friends of the same sex , In these two sets, find friends to output
emmm then AC The code is much simpler
#include<bits/stdc++.h>
using namespace std;
int n,m;
int k;
const int maxn=20000;//0 0000 0 9999 1 0000 1 9999
struct Ans{
int a;
int b;
};
vector<vector<int> >graph(maxn);
char a[10];
char b[10];
int aa,bb;
vector<int>fa;//a Friends of the same sex
vector<int>fb;//b Friends of the same sex
vector<Ans>ans;
bool cmp(Ans a,Ans b){
if(a.a!=b.a){
return a.a<b.a;
}else{
return a.b<b.b;
}
}
bool hasConnect(int a,int b){
for(int i=0;i<graph[a].size();i++){
if(graph[a][i]==b){
return true;
}
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
cin>>a>>b;
if(a[0]=='-'){
aa=10000-atoi(a);
}else{
aa=atoi(a);
}
if(b[0]=='-'){
bb=10000-atoi(b);
}else{
bb=atoi(b);
}
graph[aa].push_back(bb);
graph[bb].push_back(aa);
}
scanf("%d",&k);
while(k--){
cin>>a>>b;
if(a[0]=='-'){
aa=10000-atoi(a);
}else{
aa=atoi(a);
}
if(b[0]=='-'){
bb=10000-atoi(b);
}else{
bb=atoi(b);
}
// find A Friends of the same sex
for(int i=0;i<graph[aa].size();i++){
if(graph[aa][i]/10000==aa/10000&&graph[aa][i]!=bb){
fa.push_back(graph[aa][i]);
}
}
// find B Friends of the same sex
for(int i=0;i<graph[bb].size();i++){
if(graph[bb][i]/10000==bb/10000&&graph[bb][i]!=aa){
fb.push_back(graph[bb][i]);
}
}
// Find a common link between two friends
int sum=0;
for(int i=0;i<fa.size();i++){
for(int j=0;j<fb.size();j++){
if(hasConnect(fa[i],fb[j])){
sum++;
Ans temp;
temp.a=fa[i];temp.b=fb[j];
ans.push_back(temp);
}
}
}
// Output the answer
printf("%d\n",sum);
sort(ans.begin(),ans.end(),cmp);
for(int i=0;i<sum;i++){
printf("%04d %04d\n",ans[i].a%10000,ans[i].b%10000);
}
ans.clear();
fa.clear();
fb.clear();
}
return 0;
}
1136 A Delayed Palindrome
#include<bits/stdc++.h>
using namespace std;
bool isok(string num){
int len=num.length();
if(len==1){
return true;
}else{
for(int i=0;i<len/2;i++){
if(num[i]!=num[len-i-1]){
return false;
}
}
return true;
}
}
string Add(string a,string b){
int len=a.length();
string ans="";
int s,c=0;
int temp=0;
for(int i=len-1;i>=0;i--){
temp=a[i]+b[i]-2*'0'+c;
s=temp%10;
c=temp/10;
ans+=to_string(s);
}
while(c){
ans+=to_string(c%10);
c/=10;
}
reverse(ans.begin(),ans.end());
return ans;
}
string num;
string renum;
int main(){
cin>>num;
int cnt=0;
while(!isok(num)&&cnt<10){
cnt++;
cout<<num<<" + ";
renum=num;
reverse(num.begin(),num.end());
cout<<num<<" = ";
num=Add(num,renum);
cout<<num<<endl;
}
if(isok(num)){
cout<<num<<" is a palindromic number.";
}else{
cout<<"Not found in 10 iterations.";
}
return 0;
}
1137 Final Grading
#include<bits/stdc++.h>
using namespace std;
int p,m,f;
struct Student{
int Gp=-1;
int Gf=-1;
int G;
int Gm=-1;
string id;
};
map<string,Student>mp;
string id;
int score;
vector<Student>stu;
bool cmp(Student a,Student b){
if(a.G!=b.G){
return a.G>b.G;
}else{
return a.id<b.id;
}
}
int main(){
scanf("%d%d%d",&p,&m,&f);
for(int i=0;i<p;i++){
cin>>id>>score;
mp[id].id=id;
mp[id].Gp=score;
}
for(int i=0;i<m;i++){
cin>>id>>score;
mp[id].id=id;
mp[id].Gm=score;
}
for(int i=0;i<f;i++){
cin>>id>>score;
mp[id].id=id;
mp[id].Gf=score;
}
for(map<string,Student>::iterator it=mp.begin();it!=mp.end();it++){
Student temp=it->second;
if(temp.Gm>temp.Gf){
temp.G=0.4*temp.Gm+0.6*temp.Gf+0.5;
}else{
temp.G=temp.Gf;
}
stu.push_back(temp);
}
sort(stu.begin(),stu.end(),cmp);
for(int i=0;i<stu.size();i++){
if(stu[i].Gp<200||stu[i].G<60)continue;
cout<<stu[i].id<<" ";
printf("%d %d %d %d\n",stu[i].Gp,stu[i].Gm,stu[i].Gf,stu[i].G);
}
return 0;
}
1138 Postorder Traversal
This kind of personal feeling is a template question , I did it yesterday , Today is the day for blind typing
The idea is not difficult to understand , The key is that if you don't do it for a long time …… It's really hard to adjust （ What do you say if you recite it …… It is this inscription that is written faster than the first question ）
// In the sequence traversal + The former sequence traversal -----> The first number of postorder traversal
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>pre;
vector<int>mid;
struct Node{
int value;
Node*lchild=NULL;
Node*rchild=NULL;
};
Node*build(int preL,int preR,int inL,int inR){
if(preL>preR){
return NULL;
}
int value=pre[preL];
Node *node=new Node();
node->value=value;
int k;
for(k=inL;k<=inR;k++){
if(mid[k]==value){
break;
}
}
int left_num=k-inL;
node->lchild=build(preL+1,preL+left_num,inL,k-1);
node->rchild=build(preL+left_num+1,preR,k+1,inR);
return node;
}
bool flag=false;
void posT(Node *root){
if(root==NULL){
return ;
}
posT(root->lchild);
posT(root->rchild);
if(!flag){
printf("%d",root->value);
flag=true;
}
}
int main(){
scanf("%d",&n);
pre.resize(n);
mid.resize(n);
for(int i=0;i<n;i++){
scanf("%d",&pre[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&mid[i]);
}
Node *root=NULL;
root=build(0,n-1,0,n-1);
posT(root);
return 0;
}
边栏推荐
- 正则表达式
- 27. template match
- 2022 explosion proof electrical operation certificate examination question bank and simulation examination
- 阳光男孩陈颢天 受邀担任第六季完美童模全球总决赛代言人
- Log4j2 vulnerability
- Remote incremental synchronization artifact Rsync
- Worthington胶原蛋白酶的多类型研究
- 热血男孩滕文泽 受邀担任第六季完美童模全球总决赛形象大使
- MySQL example - comprehensive case (multi condition combined query)
- Interpretation of script corresponding to postman assertion
猜你喜欢
Reading notes on how to connect the network - hubs, routers and routers (III)
Simple making of master seal
通过电脑获取WIFI密码（只能连接过的WiFi）
Cross validation -- a story that cannot be explained clearly
Shengxin weekly issue 34
清甜女孩李斯霞 受邀担任第六季完美童模全球总决赛小主持人
28. contour discovery
Abnova丨抗GBA单克隆抗体解决方案
23. histogram equalization
物联网亿万级通信一站式解决方案EMQ
随机推荐
readv ＆ writev
Can bus transceiver principle
24. histogram calculation
Some summary of sequence model
RT thread project engineering construction and configuration - (Env kconfig)
easyexcel读取文件
GUN make (7) 执行make
Install tensorflow GPU miscellaneous
"Hot post" Statistics
[visual studio code] vscode shortcut keys
2021 - 1 - 15 notes de pêche Ctrl + C / V
Simple making of master seal
木瓜蛋白酶的特点及相关特异性介绍
王老吉药业“关爱烈日下最可爱的人”公益活动在杭启动
Several methods of JQ obtaining objects
App test (I)
The overall process of adding, deleting, modifying and querying function items realized by super detailed SSM framework
28. contour discovery
STM32GPIO
Postman斷言對應脚本的解釋