这次PAT据说是最简单的一次，不过我是第一次参加，考场上紧张的一逼- -
而且差点给这个T1把心态搞炸了，不知道有多少人跟我一样T1 WA了几十次的人呢，真就把编程考试做成了阅读理解- -

T1 Arrays and Linked Lists

T1大意是，有很多数组分散在内存的各个地方，保证数组没有相交的部分，每个数组有自己的首地址以及长度，给出n个数组的首地址和长度，以及k个查询，每个查询要给出对于给定的数组下标，这个下标对应的内存地址是多少，并在最后输出，一共有多少个数组被声明了，数组是int型的，每个元素占4B；

打个比方，数组A0首地址为2048，长度为5，那么如果我们想查询下标为3的地址，显然他就在A0内，因此输出2048+3x4=2060;
如果还有两个数组A1和A2（0 1 2是按顺序排下去的），A1首地址为128，长度为6，A2首地址为4016，长度为10。那么如果我们想查询下标为5的地址,他应该在数组A1中，对应地址128+0x4=128；类似地，如果想查询下标为15的地址，那么它应该在A2中；如果查询的下标超出了所有数组的总长，则输出Illegal Access；

有些细节：
1、若我们查询的下标所在的数组是第 T 个，那么第 T 个数组及其之前的数组应全部被声明；
2、如果查询超出了所有数组总长，则本次查询不会声明任何数组；

3、最坑的一点，就是数组A0是默认已经被声明的，也就是说哪怕所有查询都超出了数组总长，A0也是已被声明的，这句话是在第二段的第一句，不知道有多少人因为没注意到这不起眼的一句话而痛失满分；

抛开上面那些坑，这其实就是道简单的模拟题，直接做就好了

C++代码

#include<bits/stdc++.h>
using namespace std;

long long n,k,used[100010];
long long start[100010],len[100010];

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>start[i]>>len[i];
    }
    for(int i=1;i<=k;i++){
        long long a;
        cin>>a;
        long long flag=0;
        for(int j=1;j<=n;j++){
            if(flag==0&&a<len[j]) {
                flag=1;
                cout<<start[j]+4*a<<endl;
                used[j]=1;
                break;
            }
            else if(flag==0) a-=len[j];
        }
        if(flag==0) cout<<"Illegal Access"<<endl;
    }
    int tot=1;
    for(int i=n;i>=1;i--) {
        if(used[i]==1) {
            tot=i;
            break;
        }
    }
    cout<<tot<<endl;
    return 0;
}

T2 Stack of Hats

T2的大意是，一共有n顶帽子，对应了n个人，每个人都有自己的体重，每个帽子也有自己的大小，帽子大小和人的体重对应的，意思是假如一个人的体重是第3大的，那么他的帽子大小也应该是第三大的（所以头大和体重有关系么）；输入第一行给出n顶帽子的大小，这些帽子从下到上按顺序叠在一起的，第一个在最下面；输入第二行给出n个人的体重；要求按帽子从上至下的顺序输出：这顶帽子对应的人在输入第二行中的下标是多少，例如：最上面一顶帽子大小是20，同时这顶帽子也是所有帽子中最大的，最重的体重是180，180的这位老铁在输入第二行中是第三个，因此输出的第一个数字是3，后续同理；
n<=10^4，帽子大小不超过10^5，体重不超过10^6;

我的做法是哈希表，不过鉴于我这数组命名极其辣眼睛，还得说明一下：sz[ i ]表示第 i 大的帽子的大小，f[ i ]表示从下至上的第 i 顶帽子，slev[ i ]表示大小为 i 的帽子是第几大的，w[ i ]表示第 i 重的人体重是多少，loc[ i ]表示体重为 i 的人，他在输入序列中的下标；
这么套一遍娃，就能得到这顶帽子对应的主人的下标了，套n遍就得到结果了
（之前说看到群里有人用二分，我想了下，感觉应该是我看错了TAT）

C++代码

#include<bits/stdc++.h>
using namespace std;

int sz[1000010],w[1000010];
int n,loc[1000010],slev[1000010],f[1000010],fw[1000010];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sz[i];
        f[i]=sz[i];
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
        loc[w[i]]=i;
    }
    sort(w+1,w+n+1);
    sort(sz+1,sz+n+1);
    for(int i=n;i>=1;i--){
        slev[sz[i]]=i;
    }
    for(int i=n;i>=1;i--){
        cout<<loc[w[slev[f[i]]]];
        if(i>1) cout<<" ";
    }
    return 0;
}

T3 Playground Exploration

T3的大意是，给出一张无向图，一共有n个结点(n<=100)，现在有些小孩子，他们可以从任意一个结点出发，每次离开当前结点前往相邻结点时，都会选择一个可以走的（他们不会重复经过一个结点）编号最小的结点，问从哪个结点出发，可以使得经过的结点数最多，要求输出这个结点编号以及经过的结点数；

直接暴搜就好了

C++代码

#include<bits/stdc++.h>
using namespace std;

int n,m,vis[110];
vector<int>edges[110];
int res=0,len=0;

void dfs(int start,int now,int dis){
    if(vis[now]==1) return;
    vis[now]=1;
    if(dis>len) res=start,len=dis;
    for(int i=0;i<edges[now].size();i++){
        int t=edges[now][i];
        if(vis[t]==1) continue;
        dfs(start,t,dis+1);
        break;
    }
    vis[now]=0;
}

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        sort(edges[i].begin(),edges[i].end());
    }
    for(int i=1;i<=n;i++){
        dfs(i,i,1);
    }
    cout<<res<<" "<<len;
    return 0;
}

T4 Sorted Cartesian Tree

这个据说是原题？不过我也不清楚，往年真题我是一题都没刷过；
题目大意是：有这样一种树，他的每个结点有一个键值key以及一个优先值priority。其中键值应符合二叉搜索树的要求，优先值应符合小根堆的要求，现在给出这棵树上所有结点的键值以及优先值，要求给出这颗树的层序遍历，输出时，第一行给出键值的层序遍历结果，第二行输出优先值的遍历结果；

我看群里有人说用的平衡树，写了三百多行，我只觉得他们好厉害…为什么这也能做到，太强了orz；

我的做法是，既然键值要符合二叉搜索树，那么可以先对键值排个序，这就相当于得到了这棵树的中序遍历，然后我们完全可以按照（前序–中序）或者（后序–中序）非常类似的建树方法：先用一个哈希表（ys）存键值到优先级的映射，用一个数组（inorder）存键值排好序后的序列（也就是中序序列）。然后我们就可以通过dfs开始建树了，这里的dfs参数只需要当前中序序列的左边界（li）和右边界（ri）就够了。

在dfs中，对于当前区间 [li,ri] ，我们创立一个临时数组temp，通过哈希表（ys）找到这个区间内的所有键值对应的优先值，将其加入这个数组中，然后找到这个数组中的最小值，将这个最小优先值对应的结点作为根即可（因为优先级要满足小根堆要求，因此当前中序区间中，优先值最小的一个应该作为当前子树的根结点）这样我们就把这棵树建了出来，然后跑一边层序遍历就ok，如果有人好奇300行的平衡树是咋写的，请来甲级辅导群群里问问那些大佬，我也想开开眼界。

C++代码

#include<bits/stdc++.h>
using namespace std;

int n,idx=0,root,cnt=0;
vector<int>child[100];
int key[100],pr[100],inorder[100];
unordered_map<int,int>ys;
vector<int>res1,res2;

int dfs(int li,int ri){
    if(li>ri) return 0;
    int res,minp=0x3f3f3f3f;
    vector<int>temp;
    for(int i=li;i<=ri;i++){
        temp.push_back(ys[inorder[i]]);
    }
    for(int i=0;i<temp.size();i++) minp=min(minp,temp[i]);
    for(int i=li;i<=ri;i++){
        if(minp!=ys[inorder[i]]) continue;
        res=i;
        child[res].push_back(dfs(li,i-1));
        child[res].push_back(dfs(i+1,ri));
    }
    if(li==1&&ri==n) root=res;
    return res;
}

void bfs(){
    queue<int>nodes;
    nodes.push(root);
    while(!nodes.empty()){
        int temp=nodes.front();
        nodes.pop();
        res1.push_back(inorder[temp]);
        res2.push_back(ys[inorder[temp]]);
        for(int i=0;i<child[temp].size();i++){
            if(child[temp][i]!=0) nodes.push(child[temp][i]);
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>key[i]>>pr[i];
        inorder[i]=key[i];
        ys[key[i]]=pr[i];
    }
    sort(inorder+1,inorder+1+n);
    dfs(1,n);
    bfs();
    for(int i=0;i<res1.size();i++) {
        cout<<res1[i];
        if(i!=res1.size()-1) cout<<" ";
    }
    cout<<endl;
    for(int i=0;i<res2.size();i++) {
        cout<<res2[i];
        if(i!=res2.size()-1) cout<<" ";
    }
    return 0;
}