PAT A 1108 1109 1110 1111

作者: 大美mixer | 来源:发表于2018-12-04 22:16 被阅读0次

PAT A 1108 1109 1110 1111
每日一画，更新到1111天～
福州怡山大厦房间安排表
每日一画
hashMap的底层原理
ARTS-004
1110和1111
财富小记1108-1110
2进制转16 进制
煲仔饭算个猫！

这些题都需要仔细读题，很多错误都是因为题意不清导致的。

1108 字符串

题目大意：
real numbers：实数
accurate up to：精确到
2 decimal places：两位小数
给N个实数，计算符合条件的数的平均值。
符合条件的数是范围在[-1000,1000]并且精确到两位小数的数字。
思路：
用sscanf, sprintf是个好方法，具体可以参考：柳婼の blog
scanf("%s", a);
sscanf(a, "%lf", &temp);
sprintf(b, "%.2lf",temp);
但是这样做也没啥意思了，于是平时练习用复杂的方法做一遍。

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
    int n; // n<=100
    cin>>n;
    int count = 0;
    double sum = 0.0;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        bool flag = true;
        bool exist = false;
        double num = 0.0;
        double k = 1;
        bool fuhao = true, ex_fu = false;
        for(int j=0;j<s.length();j++){
            if( (s[j]== '+' || s[j] == '-') && ex_fu == false){
                ex_fu = true;
                if(s[j]== '-'){
                    fuhao = false;
                }
            }else if( (s[j]== '+' || s[j] == '-') && ex_fu == true){
                flag = false;
                break;
            }else if(((!(s[j]>='0' && s[j]<='9')) && s[j]!='.') || (s[j] == '.' && exist == true)){
                flag = false;
                break;
            }else if(s[j] == '.' && exist == false && j != 0){
                exist = true;
            }else if(s[j] == '.' && exist == false && j == 0){// .2是不正确的 
                flag = false;
                break;
            }else{
                if(exist == false){
                    num = num*10 + s[j] - '0';
                }else{
                    k = k*0.1;
                    num = num + (s[j] - '0')*k;
                    if(k < 0.01){
                        flag = false;
                        break;
                    }
                }
            }
        }
        if(fuhao == false) num = -num;
        if(!(num>=-1000 && num<=1000) ){
            flag = false;
        }
        if(flag){
            count++;
            sum+=num;
        }else{
            cout<<"ERROR: "<<s<<" is not a legal number"<<endl;
        }
    } 
    if(count == 0){
        cout<<"The average of "<<count<<" numbers is Undefined"<<endl;
    }else if(count == 1){
        cout<<"The average of "<<count<<" number is ";
        printf("%.2lf\n", sum / count);
    }else{
        cout<<"The average of "<<count<<" numbers is ";
        printf("%.2lf\n", sum / count);
    }
    return 0;
}

1109 逻辑题

题目大意： N个人，排列成k队。
排队规则：
1、每列有n/k个人（向下取整），多余的人站最后一列
2、后排的人数必须>=前排的人数
3、最高的人站在（m/2+1）的位置
4、其他人先矮后高又矮。假设左相对于右高
5、同样的高度，根据姓名的字母表排序，姓名没有重复
见到这种很复杂的输入，又有排序。必定用vector的sort,参数多就定义结构体。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef struct node{
    string name;
    int height;
}node;

bool cmp(node a, node b){
    if(a.height == b.height){
        return a.name > b.name;
    }
    return a.height < b.height;
}

int main(){
    int n ,k;
    cin>>n>>k; 
    vector<node> v;
    for(int i=0;i<n;i++){
        string n;
        int h;
        cin>>n>>h;
        node temp;
        temp.name = n;
        temp.height = h;
        v.push_back(temp);
    }
    sort(v.begin(), v.end(), cmp);
    
    int m = n / k; //每排几个人 
    int y = n % k; //余数 
    int count = n-1;
    int hang = 0;
    
    vector< vector<string> > ans(k+1);
    
    vector<string> temp(m+y);  //最后一排 
    int p,q;
    temp[(m+y)/2] = v[count--].name;
    for(p = (m+y)/2-1, q = (m+y)/2+1; p>=0 && q<m+y; p--, q++){
        temp[p] = v[count--].name;
        temp[q] = v[count--].name;  
    } 
    if(p==0){
        temp[p] = v[count--].name;
    }
    for(int j=0;j<m+y;j++){
        ans[hang].push_back(temp[j]);
    }
    hang++;
    
    for(int i=0;i<k-1;i++){//前k-1排，没排m个人。
        vector<string> temp(m); 
        int p,q;
        temp[(m)/2] = v[count--].name;
        for(p = (m)/2-1, q = (m)/2+1; p>=0 && q<m; p--, q++){
            temp[p] = v[count--].name;
            temp[q] = v[count--].name;  
        } 
        if(p==0){
            temp[p] = v[count--].name;
        }
        for(int j=0;j<m;j++){
            ans[hang].push_back(temp[j]);
        }
        hang++;
    }
    
    for(int i = 0; i < hang; i++){
        for(int j = 0; j<ans[i].size();j++){
            if(j!=0){
                cout<<" ";
            }
            cout<<ans[i][j];
        }
        cout<<endl;
    }
    return 0;
}

1110 树

题目大意： 给一个树，求是否是是一个完全二叉树

#include<iostream>
#include<map>
#include<string.h>
#include<vector>
#include<stdlib.h>
using namespace std;

typedef struct node{
    char l,r;
}node;

int n;
map<int, node> tree;
int root = 0;
int have[25] = {0};
int num,ans;

void dfs(int r, int index){
    if(index > num){
        num = index;
        ans = r;
    }
    if(tree[r].l != -1){
        dfs(tree[r].l,index*2);
    } 
    if(tree[r].r != -1){
        dfs(tree[r].r,index*2+1);
    }
    return ;
}

int main(){
    cin>>n; // <=20
    for(int i=0;i<n;i++){
        char a[5],b[5];
        cin>>a>>b;
        node temp;
        if(a[0] == '-'){
            temp.l = -1;
        }else{
            temp.l = atoi(a);
            have[temp.l] = 1;
        }
        if(b[0] == '-'){
            temp.r = -1;
        }else{
            temp.r = atoi(b);
            have[temp.r] = 1;
        }
        tree[i] = temp;
    }
    
    //没有指向的，就是root
    while(have[root] != 0) root++;  
    
    dfs(root, 1);
    
    if(num==n) cout<<"YES "<<ans<<endl;
    else cout<<"NO "<<root<<endl;
        
    return 0;
}

1111 最短路径

题目大意： 给出起点和终点，找出最短路和最快路
一个求最短路径（如果相同求时间最短的那条），一个求最快路径（如果相同求结点数最小的那条）
思路： 两次狄更斯+DFS即可。

#include<iostream>
#include<cstdio>
#include<vector>
#define inf 99999999
using namespace std;

int n, m;
int cost[505][505],time0[505][505];
int dis[505];
bool visit[505];
vector<int> temppath,path, pathcopy;
vector<int> pre[510];
int minnode, mintime;
int s,d; 

void dfscost(int v){
    //cout<<v<<" ";
    temppath.push_back(v);
    if(v == s){
        int tempcost = 0;
        for(int i=temppath.size()-1; i>0; i--){
            int id = temppath[i], nextid = temppath[i-1];
            tempcost += time0[id][nextid];
        }
        if(tempcost < mintime){
            mintime = tempcost;
            path = temppath;
        }
        temppath.pop_back();
        return;
    }
    for(int i = 0;i<pre[v].size();i++){
        dfscost(pre[v][i]);
    }
    temppath.pop_back();
}

void dfstime(int v){
    temppath.push_back(v);
    if(v==s){
        if(temppath.size() < minnode){
            minnode = temppath.size();
            path = temppath;
        }
        temppath.pop_back();
        return ;
    }
    for(int i=0;i<pre[v].size();i++){
        dfstime(pre[v][i]);
    }
    temppath.pop_back();
}

int main(){
    
    cin>>n>>m;
    
    fill(cost[0],cost[0]+505*505,inf);
    fill(time0[0],time0[0]+505*505,inf);
    fill(dis, dis+505, inf);
    
    for(int i=0;i<m;i++){
        int u,v, flag, l,t;
        cin>>u>>v>>flag>>l>>t;
        cost[u][v] = l;
        time0[u][v] = t;
        if(flag == 0){
            cost[v][u] = l;
            time0[v][u] = t;
        }
    }   
    cin>>s>>d;
    
    pre[s].push_back(s);
    dis[s] = 0;
    for(int i=0;i<n;i++){
        int u = -1 , minn = inf;
        for(int j=0;j<n;j++){
            if(visit[j] == false && dis[j] < minn ){
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0;v<n;v++){
            if(visit[v] == false && cost[u][v]!=inf){
                if(dis[v] > dis[u] + cost[u][v]){
                    dis[v] = dis[u]+cost[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v] == dis[u] + cost[u][v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
    mintime = inf;
    dfscost(d); 
    pathcopy = path;
    int disans = dis[d];
    
    fill(dis, dis+505, inf);
    fill(visit, visit+505, false);
    for(int i=0;i<510;i++){
        pre[i].clear();
    }
    temppath.clear();
    path.clear();
    pre[s].push_back(s);
    dis[s] = 0;
    for(int i=0;i<n;i++){
        int u = -1 , minn = inf;
        for(int j=0;j<n;j++){
            if(visit[j] == false && dis[j] < minn){
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        visit[u] = true;
        for(int v = 0;v<n;v++){
            if(visit[v] == false && time0[u][v]!=inf){
                if(dis[v] > dis[u] + time0[u][v]){
                    dis[v] = dis[u] + time0[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(dis[v] == dis[u] + time0[u][v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
    minnode = inf;
    dfstime(d); 
    
    cout<<"Distance = "<<disans;
    if(pathcopy == path){
        cout<<"; ";
    }else{
        cout<<": ";
        for(int i = pathcopy.size()-1; i>=0; i--){
            if( i != pathcopy.size()-1){
                cout<<" -> ";
            }
            cout<<pathcopy[i];
        }
        cout<<endl;
    }
    
    cout<<"Time = "<<dis[d]<<": ";
    for(int i = path.size()-1; i>=0; i--){
        if( i != path.size()-1){
            cout<<" -> ";
        }
        cout<<path[i];
    }
    cout<<endl;
    
    return 0;
}

PAT A 1108 1109 1110 1111
这些题都需要仔细读题，很多错误都是因为题意不清导致的。 1108 字符串题目大意： real numbers：...
每日一画，更新到1111天～
第1109天～第1110天～一个有英文名的皇帝～第1111天
福州怡山大厦房间安排表
房间号姓名 1102 王德芳寇光辉 1107 郑文 1109 苏进何源 1110 张国炎陆香坤 1111 ...
每日一画
第1108，第1109天的唐老鸭
hashMap的底层原理
1、hashmap 计算下标的位置 1111 1111 1111 1111 1111 0000 1110 1010...
ARTS-004
Algorithm 1108. Defanging an IP Address 1109. Corporate F...
1110和1111
昨天操作，做t比亚迪，185，182.82各两手比亚迪，182.60卖出5手比亚迪，加了上汽10手，尾盘出了10手...
财富小记1108-1110
早起煮了鸡蛋，倒好牛奶，我想要保证蛋白质的摄入，就自己行动，不把希望寄托在老公身上。同时，让他感受到被照顾。按照昨...
2进制转16 进制
4位2进制转成1位16进制.例如10111011111001,我们把它从右开始4位一分10 1110 1111 1...
煲仔饭算个猫！
昨天是1111，一个可怕的日子，一个钱包减肥的日子，我知道1110那天你还是别人亲爱的男朋友，但是到1112你花光...