分类目录归档:

PTA 团体程序设计天梯赛-练习集 L2-012 关于堆的判断

这道题里坑点很大:反而不利于深入学习过数据结构的同学做题。。
先贴代码:

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<map>
#include<string>
#include<functional>
#include<algorithm>
#include<stack>
#include<list>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
//Root is 1
//小顶堆
int n, m;
int heap[1005];
int Hsize = 0;
inline int lson(int x) {
    return x * 2;
}
inline int rson(int x) {
    return x * 2 + 1;
}
inline int father(int x) {
    return x / 2;
}
void PercolateUp(int node) {
    if (heap[node] < heap[father(node)]) {
        swap(heap[node], heap[father(node)]);
        PercolateUp(father(node));
    }
}
void insert(int x) {
    heap[++Hsize] = x;
    PercolateUp(Hsize);
}
int _findNode(int v) {
    for (int i = 1; i <= n; i++) {
        if (v == heap[i])return i;
    }
    return -1;
}
bool isRoot(int v) {
    return heap[1] == v;
}
bool isSiblings(int v1, int v2) {
    int node = _findNode(v1);
    if (node % 2 == 1)return heap[node - 1] == v2;
    else return heap[node + 1] == v2;
}
bool isParent(int C,int F){
    int node = _findNode(C);
    return heap[father(node)] == F;
}
bool isChild(int C, int F) {
    int node = _findNode(F);
    return heap[lson(node)] == C || heap[rson(node)] == C;
}
int Itype; //0 root,1 sibling,2 parent,3 child
int Ix, Iy;
char str[100];
void getInput() {
    scanf("%d", &Ix);
    scanf("%s", str);
    if (strcmp(str, "and") == 0) {
        Itype = 1;
        scanf("%d", &Iy);
        scanf("%s", str);
        scanf("%s", str);
        return;
    }
    scanf("%s", str);
    if (strcmp(str, "a") == 0) {
        Itype = 3;
        scanf("%s", str);
        scanf("%s", str);
        scanf("%d", &Iy);
        return;
    }
    scanf("%s", str);
    if (strcmp(str, "root") == 0) {
        Itype = 0;
        return;
    }
    Itype = 2;
    scanf("%s", str);
    scanf("%d", &Iy);
    return;
}
int main() {
    heap[0] = -100000;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        insert(x);
    }
    for (int i = 1; i <= m; i++) {
        getInput();
        bool flag;
        switch (Itype) {
        case 0:flag = isRoot(Ix); break;
        case 1:flag = isSiblings(Ix, Iy); break;
        case 2:flag = isParent(Iy, Ix); break;
        case 3:flag = isChild(Ix, Iy); break;
        }
        cout << (flag ? "T" : "F")<< endl;
    }
}

对我来说的坑点:一个是数据范围是有负数的!!!还有一个,儿子、父亲节点不是广义儿子、父亲节点,只是直属的,有直接相连边的,间接连接的不算,还有一个是不能使用一次全部读入到数组里从n/2下标到n一起上滤的做法,必须插入一个,上滤一次,这种算法很辣鸡。

洛谷 P1631 序列合并

思路完全同P2085,用大根堆,如果比堆顶小,就把堆顶的换下来,比堆顶大就扔掉不要break。
这种思路看起来很好用。

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<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
priority_queue<ll> pq;
stack<ll> s;
ll n, A[100005], B[100005];
int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> A[i];
    for (int i = 1; i <= n; i++)cin >> B[i];
    for (int i = 1; i <= n; i++) {
        pq.push(A[1] + B[i]);
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (pq.top() > A[i] + B[j]) {
                pq.pop();
                pq.push(A[i] + B[j]);
            }
            else break;
        }
    }
    while (!pq.empty()) {
        s.push(pq.top());
        pq.pop();
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

洛谷 P2085 最小函数值

有点不好做,先得知道二次函数的性质,最小值是x=-b/2a。然后用堆的时候要小心,要用大根堆,一次性把堆加满,探测每个二次函数轴附近的值是否比堆里的最大值大,如果是的话就把堆里的最大值取出来,不是的话就可以终止这次二次函数的循环了。最后因为是大根堆,用个栈把顺序颠倒过来再输出就行了。

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
int A[10005], B[10005], C[10005];
priority_queue<int> pq;
stack<int> s;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)pq.push(0x7fffffff);
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i] >> C[i];
        double pivot = -1.0*B[i] / 2 / A[i];
        if (pivot < 0) {
            for (int j = 1; j <= m; j++) {
                int v = A[i] * j*j + B[i] * j + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else break;
            }
        }
        else {
            int p = round(pivot);
            int v = A[i] * p * p + B[i] * p + C[i];
            if (v < pq.top()) {
                pq.pop();
                pq.push(v);
            }
            for (int j = 0; 2 * j <= m - 1; j++) {
                bool flag = true;
                v = A[i] * (p + j + 1)*(p + j + 1) + B[i] * (p + j + 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                v = A[i] * (p - j - 1)*(p - j - 1) + B[i] * (p - j - 1) + C[i];
                if (v < pq.top()) {
                    pq.pop();
                    pq.push(v);
                }
                else flag = false;
                if (!flag)break;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        s.push(pq.top());
        pq.pop();
    }
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
}

洛谷 P1801 黑匣子_NOI导刊2010提高(06)

异常清晰,自己花了好长时间想出来的,继续加油!

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
struct BlackBox {
private:
    priority_queue<ll,vector<ll>,greater<ll> > minHeap;
    priority_queue<ll> maxHeap;
public:
    void add(ll num) {
        if (maxHeap.empty())minHeap.push(num);
        else if (num < maxHeap.top()) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(num);
        }
        else minHeap.push(num);
    }
    ll get() {
        ll re = minHeap.top();
        maxHeap.push(minHeap.top());
        minHeap.pop();
        return re;
    }
}BB;
int m, n;
ll arr1[200005], arr2[200005];
ll arr2Ptr = 1;
int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) cin >> arr1[i];
    for (int i = 1; i <= n; i++)cin >> arr2[i];
    for (int i = 1; i <= m; i++) {
        BB.add(arr1[i]);
        while (arr2[arr2Ptr] == i) {
            cout << BB.get() << endl;
            arr2Ptr++;
        }
    }
}