[数据结构与算法]PAT甲级1031~1033

前言：距离四级考试剩26天，PAT甲级考试剩27天
对PAT甲级练习题做总结

• 2021/11/22

1031 1032 1033

1031 Hello World for U (20 分)

• 题目大意：
  给一个字符串，按找U形输出，左n1下n2右n3，其中n1和n3取相同的值，并且小于等于n2，n1+n2+n3=N+2

• 题目解析：

• n1=n3=(N+2)/3

• n2=(N+2)/3+(N+2)%3

英语单词：

vertical 垂直的，竖直

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair<int,int> pii;


char str[N][N];

int main(){
    string s;cin>>s;
    int n = s.size(),cnt = 0;
    n+=2;
    int row = n/3,col = n/3+n%3;
    for(int i = 0; i < row; i ++ ){
        for(int j = 0; j < col; j ++ ){
            str[i][j] = ' ';    
        }
    }
    //cout<<n<<" "<<row<<" "<<col<<endl;
    int i = 0;
    while(i < row) str[i++][0] = s[cnt++];
    cnt --, i = 0;
    while(i < col) str[row-1][i++] = s[cnt++];
    cnt --,i = row-1;
    while(i >= 0) str[i--][col-1] = s[cnt++];
    for(int i = 0; i < row; i ++ ){
        for(int j = 0; j < col; j ++ ){
            cout<<str[i][j];
        }
        puts("");
    }
    return 0;
}

1032 Sharing (25 分)

• 题目大意：
  找出两个链表共同的后缀
• 题目解析：
  模拟链表操作

英语单词：

suffix 后缀
sublist 子表

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
const int inf = 0x3f3f3f3f;

#define x first
#define y second

typedef pair<int,int> pii;

/*
11111 - 00001 - 00010 - 12345 - 67890 - 00002 
- 00003 -1 
2222 - 23456 - 67890 - 00002 -  00003 -1
*/

int n1,n2,m;
int ne[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n1 >> n2 >> m;
    while(m --){
        int a,b;char c;
        cin >> a >> c >> b;
        ne[a] = b;
    }
    map<int,int> hs;
    while(n1 != -1) hs[n1] = true,n1 = ne[n1];
    int ans = -1;
    while(n2 != -1){
        if(hs[n2]) {ans = n2;break;}
        n2 = ne[n2];
    }
    if(ans == -1) cout<<"-1";
    else printf("%05d",ans);
    return 0;
}

1033 To Fill or Not to Fill (25 分)

• 题目大意：

• 题目解析：
  贪心，比较难写，看的柳神代码，先往后写着，鸽一下

英语单词：

tank 罐，桶
gas station 加油站
route 路线

代码如下：

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+10;
const int inf = 0x3f3f3f3f;

#define dis first
#define pri second

typedef pair<int,int> pii;
typedef double db;

/*
*/

int n;
db cmx,finald,davg;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> cmx >> finald >> davg >> n;
    vector<pair<db,db>> v;
    v.push_back({finald,0});
    for(int i = 0; i < n; i ++ ){
        db pri,dis;cin>>pri>>dis;
        v.push_back({dis,pri});
    }
    sort(v.begin(),v.end());
    db nowdis = 0,mxdis = 0,nowpri = 0,totpri = 0,leftdis = 0;
    if(!v[0].dis) nowpri = v[0].pri;
    else {printf("The maximum travel distance = 0.00\n");return 0;}
    while(nowdis < finald){
        mxdis = davg*cmx + nowdis;
        db mipridis = 0,mipri = inf;
        bool ok = false;
        for(int i = 1; i <= n && v[i].dis <= mxdis; i ++ ){
            if(v[i].dis <= nowdis) continue;
            if(v[i].pri < nowpri){
                totpri += (v[i].dis - nowdis - leftdis)*nowpri/davg;
                leftdis = 0;
                nowpri = v[i].pri;
                nowdis = v[i].dis;
                ok = true;
                break;
            }
            if(v[i].pri < mipri){
                mipri = v[i].pri;
                mipridis = v[i].dis;
            }
        }
        if(!ok && mipri != inf){
            totpri += (nowpri * (cmx - leftdis/davg));
            leftdis = cmx*davg - (mipridis-nowdis);
            nowpri = mipri;
            nowdis = mipridis;
        }
        if(!ok && mipri == inf){
            nowdis += cmx*davg;
            printf("The maximum travel distance = %.2f\n",nowdis);
            return 0;
        }
    }
    printf("%.2f\n",totpri);
    return 0;
}