月度归档：2018年11月

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一起上滤的做法，必须插入一个，上滤一次，这种算法很辣鸡。

洛谷 P1022 计算器的改良

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int ratio = 0, constant = 0;
#define IfLetter if (ch <= 'Z'&&ch >= 'A' || ch <= 'z'&&ch >= 'a')
#define IfNumber if (ch >= '0'&&ch <= '9' || ch=='+' || ch=='-')
int main() {
    char letter;
    char ch;
    int num = 0;
    bool flag = true;
    while ((ch = getchar()) != '\n') {
        IfNumber{ // number(maybe with variable)
            ungetc(ch, stdin);
            int re = scanf("%d", &num); //specially prepared for the testcase form like "-a"
            if (re == 0) {
                getchar();
                ratio -= (flag ? 1 : -1);
            }
            ch = getchar();
            IfLetter{
                ratio += num * (flag ? 1 : -1);
                letter = ch;
            }
            else {
                constant += num * (flag ? 1 : -1);
                ungetc(ch, stdin);
            }
            num = 0;
        }
        else IfLetter{ //pure variable without ratio
            letter = ch;
            ratio+=(flag ? 1 : -1);
        }
        else if (ch == '=') {
            flag = false;
        }
    }
    printf("%c=%.3lf", letter, -1.0*constant / ratio);
}

洛谷 P2114 [NOI2014]起床困难综合症

发表评论

参看题解：
https://www.luogu.org/blog/user17941/solution-p2114
https://www.luogu.org/blog/user25845/solution-p2114

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int n, m, t[100005];
string s[100005];
int zero = 0, one = 0x7fffffff;
int ans = 0;
void process(int & x) {
    for (int i = 1; i <= n; i++) {
        switch (s[i][0]) {
        case 'A':
            x &= t[i];
            break;
        case 'O':
            x |= t[i];
            break;
        case 'X':
            x ^= t[i];
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> s[i] >> t[i];
    process(zero);
    process(one);
    for (int i = 31; i >= 0; i--) {
        if (ans + (1 << i) > m)continue;
        if (!(zero&(1<<i))&&(one&(1 << i)))ans |= (1 << i);
    }
    process(ans);
    cout << ans;
}