作者归档：Jack

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;
}

Openjudge BJUTACM 2018 周末集训 1005:Largest Rectangle in a Histogram

发表评论

可以说是非常不好想也非常不好做的一道题了……大佬的提示是单调栈，自己随便想了想就开始写，结果就挂掉了，然后看题解，也没太大用，最后是单步调试让我差不多搞清楚了。Solve()函数里的每一行都博大精深，有很多用。我也实在讲不清楚，把AC代码发上来，再贴几个题解连接参考一下吧。

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
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
long long solve(vector<long long> & heights) {
    long long remax = 0;
    stack<long long> spos;
    heights.push_back(0);
    for (int i = 0; i < heights.size(); i++) {
        while (!spos.empty() && heights[spos.top()] >= heights[i]) {
            int curpos = spos.top();
            spos.pop();
            remax = max(remax, heights[curpos] * (spos.empty() ? i : ((i - 1) - (spos.top() + 1) + 1))); //这里大部分题解写的是i-spos.top()-1，我搞明白之后把这里写成了易于理解的形式
        }
        spos.push(i);
    }
    return remax;
}
int main() {
    do {
        int n;
        scanf("%d", &n);
        if (n == 0)break;
        vector<long long> v;
        for (int i = 1; i <= n; i++) {
            long long x;
            scanf("%lld", &x);
            v.push_back(x);
        }
        printf("%lld", solve(v));
    } while (1);
}

此题为LeetCode原题：https://leetcode.com/problems/largest-rectangle-in-histogram/description/
该题BJUTACM地址：http://bjutacm.openjudge.cn/bjut2018/1005/
（数据范围有可能会不相同）
题解：
https://www.cnblogs.com/grandyang/p/4322653.html
https://blog.csdn.net/princexiexiaofeng/article/details/79652003
https://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html
https://tech.pic-collage.com/algorithm-largest-area-in-histogram-84cc70500f0c
我个人看题解是没看懂的，单步调试拯救了我。。如果看不懂就单步吧。。有的地方我没解释清楚，从网上搜搜题解就好。
强烈建议这道题单步跟，多跟几个样例，不单步你看不懂其中的逻辑。。
我按照雪花大佬做法写的，经我垃圾的改编加了一堆cruft：不要问我怎么回事我也搞不清楚

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
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
struct P {
    long long h, i;
};
long long solve(vector<long long> & heights) {
    long long remax = 0;
    stack<P> s;
    heights.push_back(0);
    for (int i = 0; i < heights.size(); i++) {
        long long l = i;
        while (!s.empty() && s.top().h > heights[i]){
            l = s.top().i;
            remax = max(remax, s.top().h * ( (i - 1) - s.top().i + 1));
            s.pop();
        }
        s.push(P{ heights[i],l });
    }
    return remax;
}
int main() {
    do {
        int n;
        scanf("%d", &n);
        if (n == 0)break;
        vector<long long> v;
        for (int i = 1; i <= n; i++) {
            long long x;
            scanf("%lld", &x);
            v.push_back(x);
        }
        printf("%lld\n", solve(v));
    } while (1);
}

雪花大佬的不cruft的代码

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
#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;

struct Candidate { // candidate rectangle. area = height * (end_pos - start_pos)
  ll h; // the height
  ll i; // the start position;
        // end position is implied
};

Candidate monostack[100100];
ll size = 0;

ll max_area = 0;

void monostack_push(ll h, ll i) {
  ll pos = i; // start pos

  while (size > 0 && monostack[size - 1].h >= h) { // equality is optional
    Candidate const & p = monostack[--size]; // pop

    pos = p.i; // update start pos

    max_area = max(max_area, p.h * (i - p.i));
  }

  monostack[size++] = {h, pos}; // push
}

int main() {
  // init
  size = 0;
  max_area = 0;

  // for each input
  //   monostack_push(height, pos);
  // monostack_push(0, last pos + 1); // another trick

  // output max_area
}

Openjudge BJUTACM 1036:括号画家

发表评论

智障的一开始竟然想用递归/记忆化做。。。老T。后来猛然醒悟是栈。。。

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
void E() {
    cout << "No";
    exit(0);
}
void S() {
    cout << "Yes";
    exit(0);
}
stack<char> s;
int main() {
    char c;
    while (cin >> c) {
        switch (c) {
        case '(':case '[':case '{':
            s.push(c);
            break;
        case ')':case ']':case '}':
            if (s.empty())E();
            switch (c) {
            case ')':
                if (s.top() == '(')s.pop();
                else E();
                break;
            case ']':
                if (s.top() == '[')s.pop();
                else E();
                break;
            case '}':
                if (s.top() == '{')s.pop();
                else E();
                break;
            }
        }
    }
    S();
}

http://bjutacm.openjudge.cn/lianxi/1036/

Openjudge BJUTACM 1018:简单计算器

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int t;
stack<double> si;
stack<char> sc;
inline bool execute() {
    if (sc.empty()) return false;
    double x2 = si.top();
    si.pop();
    double x1 = si.top();
    si.pop();
    char symbol = sc.top();
    sc.pop();
    switch (symbol) {
    case '+':si.push(x1 + x2); break;
    case '-':si.push(x1 - x2); break;
    case '*':si.push(x1 * x2); break;
    case '/':si.push(x1 / x2); break;
    }
    return true;
}
int main() {
    scanf("%d", &t);
    do {
        char c = getc(stdin);
        if (c == -1)break;
        if (c == '\n') {
            while (execute());
            if (si.empty())continue;
            double v = si.top();
            while (!si.empty())si.pop();
            while (!sc.empty())sc.pop();
            printf("%.2lf\n", v);
            continue;
        }
        if (c <= '9' && c >= '0') {
            ungetc(c, stdin);
            double v;
            scanf("%lf", &v);
            if (sc.empty())si.push(v);
            else if (sc.top() == '-') {
                si.push(-v);
                sc.pop();
                sc.push('+');
            }
            else if (sc.top() == '/') {
                si.push(1.0 / v);
                sc.pop();
                sc.push('*');
            }
            else si.push(v);
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!sc.empty() && (c == '+' || c == '-') && (sc.top() == '*' || sc.top() == '/')) {
                execute();
            }
            sc.push(c);
        }
    } while (1);
}

http://bjutacm.openjudge.cn/lianxi/1018/

Openjudge BJUTACM 181A:素数和

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int n, m;
bool isprime[10000005];
int prime[10000005];
vector<int> primeList;
inline void genPrime() {
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= 10000000; i++) {
        if (!isprime[i])continue;
        primeList.push_back(i);
        for (int j = 2 * i; j <= 10000000; j += i) {
            isprime[j] = false;
        }
    }
}
inline void putIn(int v) {
    for (int i = 0; i < primeList.size() && v >= primeList[i] && v != 1; i++) {
        if (v%primeList[i] == 0) {
            prime[primeList[i]]++;
            while (v%primeList[i] == 0)v /= primeList[i];
        }
        if (isprime[v]) {
            prime[v]++;
            break;
        }
    }
}
int main() {
    genPrime();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d", &v);
        putIn(v);
    }
    for (int i = 1; i <= 10000000; i++) {
        prime[i] += prime[i - 1];
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        if (r > 10000000)r = 10000000;
        if (l > 10000000)l = 10000000;
        printf("%d\n", prime[r] - prime[l - 1]);
    }
}

http://bjutacm.openjudge.cn/lianxi/181A/

C++指针

发表评论

仅做保留参考个人使用，谁要是能看懂，那就是C++大神了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<typeinfo>
using namespace std;
char s[2010][2010];
int * func1(int a, int b) { return 0; }
int *(*func)(int, int) = func1;
int main() {
    cout << typeid(func1).name() << endl;
    cout << typeid(func).name() << endl;
    auto ptr = &s;
    cout << typeid(&ptr).name() << " " << sizeof(&ptr) << " " << (int)(&ptr + 1) - (int)(&ptr) << endl;
    cout << typeid(ptr).name() << " " << sizeof(ptr) << " " << (int)(ptr + 1) - (int)(ptr) << endl;
    cout << typeid(&s).name() << " " << sizeof(&s) << " " << (int)(&s + 1) - (int)(&s) << endl;
    cout << typeid(s).name() << " " << sizeof(s) << " " << (int)(s + 1) - (int)(s) << endl;
    cout << typeid(*s).name() << " " << sizeof(*s) << " " << (int)(*s + 1) - (int)(*s) << endl;
    cout << typeid(&s[0]).name() << " " << sizeof(&s[0]) << " " << (int)(&s[0] + 1) - (int)(&s[0]) << endl;
    cout << typeid(s[0]).name() << " " << sizeof(s[0]) << " " << (int)(s[0] + 1) - (int)(s[0]) << endl;
    cout << typeid(*s[0]).name() << " " << sizeof(*s[0]) << endl;
    cout << typeid(&s[0][0]).name() << " " << sizeof(&s[0][0]) << " " << (int)(&s[0][0] + 1) - (int)(&s[0][0]) << endl;
    cout << typeid(s[0][0]).name() << " " << sizeof(s[0][0]) << endl;
}

输出结果（找一个好点的编译器，别用g++，输出的Typeinfo没法看）：

1
2
3
4
5
6
7
8
9
10
11
12
int * __cdecl(int,int)
int * (__cdecl*)(int,int)
char (* *)[2010][2010] 4 4
char (*)[2010][2010] 4 4040100
char (*)[2010][2010] 4 4040100
char [2010][2010] 4040100 2010
char [2010] 2010 1
char (*)[2010] 4 2010
char [2010] 2010 1
char 1
char * 4 1
char 1

总结：对某类型做sizeof运算，返回的是本类型本身的大小；对某类型指针做加减操作，数值为n，是对其绝对地址加减：对该指针解除引用后的类型的sizeof运算的数值乘以n。