PAT 1108_1111复盘

1108

这个题一开始直报运行时错误，后来定位在stoi函数，有可能那个数很大，加了个特判以后好了（测试点二）

但是变成了答案错误，，我看其他小伙伴都说这个题测试点2是个count=1要输出number的问题，我寻思我也注意了QAQ
真不知道问题了

#include 
#include
#include
#include
#include
#include
#include 
#include
#include
using namespace std;
string s[102];
bool vis[102];
int ct=0;
double num=0;
bool igel(string s) {int len = s.length();int have_dian = 0;int dian_pos = 0;for (int i = 0; i < len; ++i) {//先判断合法的特殊符号if (i == 0 && s[i] == '-') continue;if (s[i] == '.' && !have_dian) {have_dian = 1;dian_pos = i;continue;}if (s[i] < '0' || s[i] > '9') return false;}if(have_dian && s[len-1]!='.') {double d = stod(s);if(dian_pos<len-1-2) return false;else if(d>=-1000 && d<=1000  ){ct++;num+=d;return true;}return false;}else {if(s.length()>7) return false;int in = stol(s);if (in >= -1000 && in <= 1000) {ct++;num += in;return true;}return false;}
}
int main(){int n;cin>>n;for (int i = 0; i < n; ++i) {string temp;cin>>temp;s[i]=temp;vis[i]=igel(temp);}for (int i = 0; i < n; ++i) {if(!vis[i]){cout<<"ERROR: " <<s[i]<< " is not a legal number"<<endl;}}if(ct==0){cout<<"The average of 0 numbers is Undefined"<<endl;}else if(ct==1){cout<<"The average of 1 number is "<<num<<endl;}else{cout<<"The average of "<<ct<<" numbers is ";printf("%.2lf\n",num/ct);}}

1109 Group Photo (25 分)

#include 
#include
#include
#include
#include
#include
#include 
using namespace std;
struct People{string name;int hei;
}people[10101];
int n,k;
int row;
int rows[101][10010];
bool cmp(People a,People b){if(a.hei!=b.hei) return a.hei>b.hei;else{return a.name<b.name;}
}
int main(){cin>>n>>row;for (int i = 0; i < n; ++i) {string na;int h;cin>>na>>h;people[i].name=na;people[i].hei=h;}sort(people,people+n,cmp);//最后一排先搞好int num=0;k=floor(n/row);//一共几排int num_of_the_last=(n-row*k)+k;rows[row][num_of_the_last/2+1]=num++;if(num_of_the_last%2==0){for (int i = 1; i <= num_of_the_last/2; ++i) {rows[row][num_of_the_last/2+1-i]=num++;if(i<=num_of_the_last/2-1)rows[row][num_of_the_last/2+1+i]=num++;}}else{for (int i = 1; i <= num_of_the_last/2; ++i) {rows[row][num_of_the_last/2+1-i]=num++;rows[row][num_of_the_last/2+1+i]=num++;}}for (int i = 1; i <=num_of_the_last ; ++i) {cout<<people[rows[row][i]].name;if(i!=num_of_the_last) cout<<" ";}cout<<endl;//其他行for (int j = row-1; j > 0 ; --j) {num_of_the_last=k;rows[j][num_of_the_last/2+1]=num++;if(num_of_the_last%2==0){for (int i = 1; i <= num_of_the_last/2; ++i) {rows[j][num_of_the_last/2+1-i]=num++;if(i<=num_of_the_last/2-1)rows[j][num_of_the_last/2+1+i]=num++;}}else{for (int i = 1; i <= num_of_the_last/2; ++i) {rows[j][num_of_the_last/2+1-i]=num++;rows[j][num_of_the_last/2+1+i]=num++;}}}for (int i = row-1; i > 0 ; --i) {for (int j = 1; j <= k ; ++j) {cout<<people[rows[i][j]].name;if(j!=num_of_the_last) cout<<" ";}cout<<endl;}}

这个题注意审题就好了，k是行数！！！！！

1110 Complete Binary Tree (25 分)

//
// Created by Arc on 2021/9/1.
//
#include 
#include
#include
#include
#include
#include 
#include
#include 
using namespace std;
struct tree{int left=-1;int right=-1;
}Tree[25];
int father[25];
int main(){memset(father,-1,sizeof(father));int n;cin>>n;for (int i = 0; i < n; ++i) {string l,r;cin>>l>>r;if(l!="-") {Tree[i].left = stoi(l);father[  stoi(l)]=i;}if(r!="-") {Tree[i].right = stoi(r);father[ stoi(r)]=i;}}int root=-1;//cout<<"father[0]"<for (int i = 0; i < n; ++i) {if(father[i]==-1&&root==-1){root=i;}}int no_chi=0;int flag=1;int record=-1;queue<int> q;q.push(root);while(!q.empty()){int temp=q.front();q.pop();record=temp;if(Tree[temp].left!=-1 && no_chi==0){q.push(Tree[temp].left);}else if(Tree[temp].left==-1 && no_chi==0){no_chi=1;}else if(Tree[temp].left!=-1 && no_chi){flag=0;break;}if(Tree[temp].right!=-1 && no_chi==0){q.push(Tree[temp].right);}else if(Tree[temp].right==-1 && no_chi==0){no_chi=1;}else if(Tree[temp].right!=-1 && no_chi){flag=0;break;}}if(flag==0) cout<<"NO "<<root<<endl;else{cout<<"YES "<<record<<endl;}}

这个题一开始错了三个点，，因此还写了一堆样例，，实际上就是，一开始把输入定义成char了，但是可能是两位数，，，之前犯过一遍的错误！

那就把样例贴出来吧！

6
1 2
3 -
4 5
- -
- -
- -9 
7 8
2 3
- -
- -
0 1
- -
4 5
- -
- -5
1 2
3 4
- -
- -
- -5
1 2
- -
3 4
- -
- -4
1 -
2 3
- -
- -

1111 Online Map (30 分)

这个题思路很简单（甚至我one try)，但是！！！！！这代码也太长看吧！两个dij，然后还写了一个dfs

其实最后这个题就是看你码代码的速度的，，三个小时的话，，，你这个题肯定必须上手就来啊！！！！

//
// Created by Arc on 2021/9/1.
//
#include 
#include
#include
#include
#include
#include 
#include
#include 
using namespace std;
int Length[520][520];
int Time[520][520];
int d1[520];
int w1[520];
int w2[520];
int vis1[520];
int vis2[520];
int d2[520];
int n,m;
int INF=100000;
int pre1[520];
vector<int> pre2[520];
int source,dest;
void init(){for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {Length[i][j]=INF;Time[i][j]=INF;}d1[i]=INF;d2[i]=INF;vis1[i]=0;vis2[i]=0;pre1[i]=-1;w1[i]=INF;w2[i]=INF;}
}
void dij1(int start){d1[start]=0;for (int i = 0; i < n; ++i) {int u=-1,MIN=INF;for (int j = 0; j < n; ++j) {if(vis1[j]==0 && d1[j]<MIN){u=j;MIN=d1[j];}}if(u==-1) return ;vis1[u]=1;for (int j = 0; j < n; ++j) {if(vis1[j]==0 && Length[u][j]!=INF ){if(d1[u]+Length[u][j]<d1[j]){d1[j]=d1[u]+Length[u][j];w1[j]=Time[u][j]+w1[u];pre1[j]=u;}else if(d1[u]+Length[u][j]==d1[j]&&w1[j]>Time[u][j]+w1[u]){w1[j]=Time[u][j]+w1[u];pre1[j]=u;}}}}};
//
void dij2(int start){d2[start]=0;for (int i = 0; i < n; ++i) {int u=-1,MIN=INF;for (int j = 0; j < n; ++j) {if(vis2[j]==0 && d2[j]<MIN){u=j;MIN=d2[j];}}if(u==-1) return ;vis2[u]=1;for (int j = 0; j < n; ++j) {if(vis2[j]==0 && Time[u][j]!=INF ){if(d2[u]+Time[u][j]<d2[j]){d2[j]=d2[u]+Time[u][j];pre2[j].clear();pre2[j].push_back(u);}else if(d2[u]+Time[u][j]==d2[j]){pre2[j].push_back(u);}}}}};
int MINX=INF;
vector<int> ans;
vector<int> temp;
void dfs(int start,int num){if(start==source){if(num<MINX){MINX=num;ans=temp;}return ;}int len=pre2[start].size();for (int i = 0; i < len; ++i) {temp.push_back(pre2[start][i]);dfs(pre2[start][i],num+1);temp.pop_back();}}
int main(){cin>>n>>m;init();for (int i = 0; i < m ; ++i) {int a,b;int one_way;int length;int time;cin>>a>>b>>one_way>>length>>time;// scanf("%d %d %d %d %d",&a,&b,&one_way,&length,&time);Length[a][b]=length;Time[a][b]=time;if(!one_way){Length[b][a]=length;Time[b][a]=time;}}
//    for (int i = 0; i 
//        for (int j = 0; j < n; ++j) {
//            cout<
//        }
//        cout<
//
//    }cin>>source>>dest;// cout<dij1(source);//cout<//dij2(source);//cout<temp.push_back(dest);dfs(dest,0);shuchu:int q=dest;vector<int> v1;while(q!=-1){v1.push_back(q);q=pre1[q];}reverse(v1.begin(),v1.end());int len=ans.size();// cout<<"len"<reverse(ans.begin(),ans.end());if(v1!=ans) {cout << "Distance = " << d1[dest] << ": ";int len_v1 = v1.size();for (int i = 0; i < len_v1; ++i) {cout << v1[i];if (i != len_v1 - 1) {cout << " -> ";}}cout << endl;cout << "Time =" << d2[dest] << ": ";for (int i = 0; i < len; ++i) {cout << ans[i];if (i != len - 1) {cout << " -> ";}}}else{cout << "Distance = " << d1[dest] << "; ";cout << "Time =" << d2[dest] << ": ";for (int i = 0; i < len; ++i) {cout << ans[i];if (i != len - 1) {cout << " -> ";}}}}

以后还是得注意一下做题速度，三个小时四个题可能确实有点多，但是这个，多练练，把一些比较固定的思路记住！加油呀！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！