2021PAT甲级秋季考试题解

#include
using namespace std;
const int N = 1e4+10;
struct L{
    int address;
    int len;
}link[N];
int sum[N];
int main()
{
    int n,k;
    int total = 0;
    cin >> n >> k;
    for(int i = 0 ; i < n ; i ++)
    {
        cin >> link[i].address >> link[i].len;
        total+=link[i].len;
    }
    sum[0] = link[0].len-1;
    for(int i = 1 ; i < n ; i++) sum[i] = sum[i-1] + link[i].len;
    total -= 1;
    int q;
    int cnt = 1;
    for(int i = 0 ; i < k ; i ++)
    {
        cin >> q;
        if(q>total) puts("Illegal Access");
        else
        {
            int l = 0,r=n-1;
            while(l 
7-2 Stack of Hats 
 
#include
using namespace std;
const int N = 1e4+10;
unordered_map ord;// 表示帽子的大小顺序
unordered_map pos;// 表示人先后到来顺序
int a[N];
int b[N];
int n;
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(a+1,a+n+1,greater()); //从大到小排序
    for(int i = 1 ; i <= n ; i ++) ord[a[i]] = i; //记录帽子大小顺序
    for(int i = 1 ; i <= n ; i ++)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }

    sort(a+1,a+n+1,greater()); //从大到小排序
    for(int i = n ; i >= 2 ; i--)
    {
        cout< 
7-3 Playground Exploration 
 
#include
using namespace std;
const int N = 110;
bool st[N];
vector g[N];
int n,m;
int dfs(int u)
{
    int len = 1 ;
    for(int i = 0 ; i < g[u].size() ; i ++)
    {
        if(!st[g[u][i]])
        {
//            cout<> n >> m;
    for(int i = 1 ; i <= m ; i ++)
    {
        int a,b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1 ; i <= n ; i ++)
    {
        sort(g[i].begin(),g[i].end());
    }
    int cnt = 0;
    int idx = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        memset(st,0,sizeof st);
        st[i] = true;
        int len = dfs(i);
        if(len > cnt) {
            idx = i;
            cnt = len;
        }
    }
    cout< 
7-4 Sorted Cartesian Tree 
 
#include
using namespace std;
typedef pair PII;
const int N = 35;
PII a[N];
unordered_map le,rt;//记录左右子树
int n;
vector ans;
bool cmp(PII a,PII b)
{
    return a.first < b.first;
}
int build(int l,int r)
{
    int minn = a[l].second; //priority值进行比较
    int root = l;
    if(l>r) return -1;
    for(int i = l; i <= r; i ++){
        if(a[i].second l ) le[root] = build(l,root-1);
    if( root < r ) rt[root] = build(root+1,r);
    return root;
}
void bfs(int root)
{
    queue q;
    q.push(root);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        PII now = a[t];
        ans.push_back(now);
        if(le.count(t)) q.push(le[t]);
        if(rt.count(t)) q.push(rt[t]);
    }
}
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++ ){
        cin >> a[i].first >> a[i].second;
    }
    sort(a+1,a+n+1,cmp); //根据Key值排序,得到中序遍历序列
    int root = build(1,n); //建树
    bfs(root);
    for(int i = 0 ; i < ans.size()-1 ; i ++) cout<