当前位置：网站首页>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;
}
边栏推荐
- The overall process of adding, deleting, modifying and querying function items realized by super detailed SSM framework
- Abnova丨CSV 单克隆抗体解决方案
- 俏皮少女王艺璇 受邀担任第六季完美童模全球总决赛推广大使
- JSON实例（一）
- 手机卡开户的流程是什么？网上开户是否安全么？
- 快速生成1~20自然数，并轻松复制
- 热血男孩滕文泽 受邀担任第六季完美童模全球总决赛形象大使
- Eight principles of element positioning
- 正则表达式
- 2022 explosion proof electrical operation certificate examination question bank and simulation examination
猜你喜欢
--都市修炼手册之SQL-- 第一章 基础复习
Log4j2 vulnerability
Cross validation -- a story that cannot be explained clearly
GNN (graph neural network) introduction vernacular
Oracle database startup backup preparation
Textcnn paper Interpretation -- revolutionary neural networks for sense classification
23. histogram equalization
MySQL图书借阅系统项目数据库建库表语句（组合主键、外键设置）
CYCA少儿形体礼仪 乐清市培训成果考核圆满落幕
26. histogram back projection
随机推荐
Accumulation and summary of activation function
判定积分给业务带来价值的两个指标
浅谈接口测试（二）
集合集合！！快来复习--mysql增删改查，内、左右连接 复习笔记
Assertion of postman interface test
缓冲
NLP enhanced technology
GUN make (5) makefile中的变量
STM32GPIO
【Visual Studio Code】vscode快捷键大全
Difference between app test and web test
阳光男孩陈颢天 受邀担任第六季完美童模全球总决赛代言人
Abnova丨CSV 单克隆抗体解决方案
recvmsg ＆ sendmsg
“热帖”统计
Common deep learning optimizers
**MySQL例题一（根据不同问题，多条件查询）**
Perfdog
[visual studio code] vscode shortcut keys
Maze walking