2022.9 PAT甲级题解

2022.9 PAT甲级题解

听说PAT可能可以抵浙软机试，于是一小时速通PAT甲级（笑

题目名字不记得，就不写了。

第一题

数轴上若干个点，给一个长度，求这个长度最多能框住多少点并求出此时这个长度左端点的最小值。排序后双指针一下就行。$\mathcal{O}(n\log n)$

#include 
typedef long long ll;
const int MAXN = 1e5 + 10;
int a[MAXN];
int main()
{
    int n, h; scanf("%d%d", &n, &h);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    std::sort(a + 1, a + 1 + n);
    int ans = 0, l;
    for (int i = 1, j = 0; i <= n; ++i)
    {
        while (j + 1 <= n && a[j + 1] - a[i] <= h) ++j;
        if (j - i + 1 > ans) ans = j - i + 1, l = a[j] - h;
    }
    printf("%d %d\n", l, ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二题

给一个数组，问这个数组是否可以通过某个数组快排两趟后得到。注意到pivot有一个很显然的性质即右边的数都大于等于它，左边的数都小于等于它。因此从前往后扫一趟最大值，从后往前扫一趟最小值，若某个位置的最大值和最小值都等于本身则说明这个位置可以成为pivot。统计一下这种数的个数，如果大于等于3则可以。注意特判边界，如果一个pivot是边界的话则剩下只要一个就行。$\mathcal{O}(n)$

#include 
typedef long long ll;
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int a[MAXN], l[MAXN], r[MAXN];
int main()
{
    int t; scanf("%d", &t);
    while (t--)
    {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        int mini = INF;
        for (int i = n; i >= 1; --i)
        {
            mini = std::min(mini, a[i]);
            r[i] = mini;
        }
        int maxi = -INF;
        for (int i = 1; i <= n; ++i)
        {
            maxi = std::max(maxi, a[i]);
            l[i] = maxi;
        }
        int ans = 0, f = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (r[i] == a[i] && l[i] == a[i])
            {
                ++ans;
                if (i == 1 || i == n) ++f;
            }
        }
        if (ans + f >= 3) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

第三题

没啥好说的，按题意模拟一下。

#include 
typedef long long ll;
const int MAXN = 1e4 + 10, MAXM = 1e2 + 10;
int lst[MAXN][MAXM];
int m[MAXN], din[MAXN], dout[MAXN];
int main()
{
    int n, t; scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &m[i]);
        for (int j = 1; j <= m[i]; ++j)
        {
            scanf("%d", &lst[i][j]);
            din[lst[i][j]]++; dout[i]++;
        }
    }
    std::vector < int > oli;
    for (int i = 1; i <= n; ++i)
        if (din[i] >= dout[i] * t)
            oli.push_back(i);
    memset(din, 0, sizeof din);
    for (auto &i : oli)
    {
        for (int j = 1; j <= m[i]; ++j)
            ++din[lst[i][j]];
    }
    int ans = 0;
    for (auto &i : oli)
        ans = std::max(ans, din[i]);
    int cnt = 0;
    for (auto &i : oli)
        if (din[i] == ans)
        {
            if (cnt++) printf(" %d", i);
            else printf("%d", i);
        }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

第四题

给二叉树中序和前序遍历，输出后续遍历，同时判断这棵二叉树的类型。建树典中典，建出来之后模拟判断一下就可以，也没什么说的，只不过模拟稍微有点难写。我写得很丑。

#include 
typedef long long ll;
const int MAXN = 2e3 + 10;
int l[MAXN], r[MAXN], v[MAXN], id[MAXN], idx, root;
int a[MAXN], b[MAXN];
int depth[MAXN];
std::vector < int > post;
int build(int al, int ar, int bl, int br)
{
    if (al > ar) return -1;
    if (bl > br) return -1;
    int now = ++idx;
    v[now] = b[bl];
    int i = al;
    std::set < int > st;
    for ( ; i <= ar; ++i)
    {
        if (a[i] == v[now])
            break;
        st.insert(a[i]);
    }
    int j = bl + 1;
    for ( ; j <= br; ++j)
        if (st.find(b[j]) == st.end())
            break;
    l[now] = build(al, i - 1, bl + 1, j - 1);
    r[now] = build(i + 1, ar, j, br);
    return now;
}
void scan(int now)
{
    if (now == -1) return;
    scan(l[now]); scan(r[now]);
    post.push_back(v[now]);
}
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &b[i]);
    root = build(1, n, 1, n);
    scan(root);
    // for (int i = 1; i <= idx; ++i)
    //     printf("%d %d %d\n", v[i], l[i], r[i]);
    std::queue < int > que;
    que.push(root);
    while (!que.empty())
    {
        int i = que.front(); que.pop();
        if (l[i] != -1) depth[l[i]] = depth[i] + 1, que.push(l[i]);
        if (r[i] != -1) depth[r[i]] = depth[i] + 1, que.push(r[i]);
    }
    bool f = 0;
    int d = -1, tot = 0;
    for (int i = 1; i <= idx; ++i)
        if (l[i] == -1 && r[i] == -1)
        {
            if (d == -1) d = depth[i];
            else if (depth[i] != d) f = 1; 
        }
        else ++tot;
    if (!f && tot == (1 << d) - 1) printf("1\n");
    else
    {
        d = -1;
        for (int i = 1; i <= idx; ++i)
            d = std::max(d, depth[i]);
        int td = -1; f = 0; tot = 0;
        for (int i = 1; i <= idx; ++i)
        {
            if (depth[i] == d - 1 || (l[i] == -1 && r[i] == -1 && depth[i] != d))
            {
                if (td == -1) td = depth[i];
                else if (depth[i] != td) f = 1;
            }
            if (depth[i] != d) ++tot;
        }
        if (f || tot != (1 << td + 1) - 1) printf("0\n");
        else
        {
            id[root] = 1;
            std::queue < int > que;
            que.push(root);
            while (!que.empty())
            {
                int i = que.front(); que.pop();
                if (l[i] != -1) id[l[i]] = id[i] * 2, que.push(l[i]);
                if (r[i] != -1) id[r[i]] = id[i] * 2 + 1, que.push(r[i]);
            }
            // for (int i = 1; i <= idx; ++i)
            //     printf("%d ", id[i]);
            // printf("\n");
            std::vector < int > x;
            for (int i = 1; i <= idx; ++i)
                if (depth[i] == d)
                    x.push_back(i);
            std::sort(x.begin(), x.end(), [&](int a, int b){
                return id[a] < id[b];
            });
            if (id[x[0]] != 1ll << d) printf("3\n");
            else
            {
                for (int i = 1; i < x.size(); ++i)
                    if (id[x[i]] - 1 != id[x[i - 1]])
                    {
                        printf("3\n");
                        goto NXT;
                    }
                printf("2\n");
                NXT:;
            }
        }
    }
    for (int i = 0; i < post.size(); ++i)
        if (i) printf(" %d", post[i]);
        else printf("%d", post[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

PAT什么时候能加SPJ啊，天天PE，人麻了。

最近在忙保研，928之后大概会写一篇小作文。

以及最近出的题比较多，大概等今年迎新赛或者绍兴那边的比赛供题结束后会专门开篇文章写一下出的题。