分类目录归档:数据结构

CSP 201903-2 二十四点

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
using namespace std;
int calculate(int n1, int n2, char op)
{
    switch (op)
    {
    case '+':
        return n1 + n2;
        break;
    case '-':
        return n1 - n2;
        break;
    case 'x':
        return n1 * n2;
        break;
    case '/':
        return n1 / n2;
        break;
    }
    return -1;
}
bool solve(string s)
{
    deque<int> si;
    deque<char> sop;
    for (int i = 0; i < 7; i++)
    {
        if (i % 2 == 0)
        { // Inttop
            int t = s[i] - '0';
            si.push_back(t);
            if (sop.empty()) continue;
            if (sop.back() == 'x' || sop.back() == '/')
            {
                int t2 = si.back();
                si.pop_back();
                int t1 = si.back();
                si.pop_back();
                int t = calculate(t1, t2, sop.back());
                sop.pop_back();
                si.push_back(t);
            }
        }
        else
        { // Op
            char op = s[i];
            sop.push_back(op);
        }
    }
    while (!sop.empty())
    {
        int t1 = si.front();
        si.pop_front();
        int t2 = si.front();
        si.pop_front();
        int t = calculate(t1, t2, sop.front());
        sop.pop_front();
        si.push_front(t);
    }
    return si.front()==24;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n;
    while (n--)
    {
        cin >> s;
        if (solve(s))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

CSP 202012-3 带配额的文件系统

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
import copy

file_template = {
    "isDirectory": False,
    "fileSize": 0,
    "childSize": 0,
    "childQuota": 0,
    "descendantQuota": 0,
    "descendants": {}
}
root_directory = {
    "isDirectory": True,
    "fileSize": 0,
    "childSize": 0,
    "childQuota": 0,
    "descendantQuota": 0,
    "descendants": {}
}

def filepath_resolver(filepath: str):
    fpArr = filepath.split('/')
    fpArr.pop(0)
    return fpArr

def visit(filepath):
    if filepath == '/':
        return root_directory
    fpArr = filepath_resolver(filepath)
    fileIter = root_directory
    try:
        for file in fpArr:
            fileIter = fileIter["descendants"][file]
    except KeyError:
        return None
    return fileIter

def checkQuotaLimit(fileIter, filesize, descendants = True, child = True):
    if descendants:
        if fileIter["descendantQuota"] != 0:  # 检查后代文件配额
            if fileIter["fileSize"] + filesize > fileIter["descendantQuota"]:
                return False
    if child:
        if fileIter["childQuota"] != 0:  # 检查孩子文件配额
            if fileIter["childSize"] + filesize > fileIter["childQuota"]:
                return False
    return True

def create(filepath, filesize, isDirectory = False):
    dstIter = visit(filepath)
    update_filesize = filesize
    if dstIter is not None:
         update_filesize -= dstIter["fileSize"]

    fpArr = filepath_resolver(filepath)
    fileIter = root_directory
    for i in range(len(fpArr)):
        file = fpArr[i]
        if file not in fileIter["descendants"].keys(): # 无该目录/文件
            curFile = copy.deepcopy(file_template)
            if i != len(fpArr) - 1: # 非末端文件
                if not checkQuotaLimit(fileIter, update_filesize, True, False): return False
                curFile["isDirectory"] = True
            else: # 末端文件
                if not checkQuotaLimit(fileIter, update_filesize): return False
                curFile["isDirectory"] = isDirectory
                curFile["fileSize"] = filesize
            fileIter["descendants"][file] = curFile
        else: # 存在该目录/文件
            curFile = fileIter["descendants"][file]
            if i != len(fpArr) - 1: # 非末端文件
                if not curFile["isDirectory"]: # 欲进入的新目录文件与普通文件重名
                    return False
                else:
                    if not checkQuotaLimit(fileIter, update_filesize, True, False): return False
            else: # 末端文件
                if curFile["isDirectory"] != isDirectory: # 欲创建的同名新文件与旧文件类型冲突
                    return False
                else: # 文件已存在,替换文件大小
                    if not checkQuotaLimit(fileIter, update_filesize): return False
                    curFile["fileSize"] = filesize
        fileIter = fileIter["descendants"][file]

    fileIter = root_directory
    for i in range(len(fpArr)):
        file = fpArr[i]
        fileIter["fileSize"] += update_filesize
        if i == len(fpArr) - 1:
            fileIter["childSize"] += update_filesize
        fileIter = fileIter["descendants"][file]
    return True

def remove(filepath):
    fpArr = filepath_resolver(filepath)
    dstIter = visit(filepath)
    if dstIter is None:
        return True

    fileIter = root_directory
    for file in fpArr:
        fileIter["fileSize"] -= dstIter["fileSize"]
        if fileIter["descendants"][file] == dstIter:
            if not dstIter["isDirectory"]:
                fileIter["childSize"] -= dstIter["fileSize"]
            break
        fileIter = fileIter["descendants"][file]
    fileIter["descendants"].pop(fpArr[-1])
    return True

def quota(filepath, child_quota, descendant_quota):
    dstIter = visit(filepath)
    if dstIter is None:
        return False
    if not dstIter["isDirectory"]:
        return False
    child_flag = child_quota == 0 or dstIter["childSize"] <= child_quota
    descendant_flag = descendant_quota == 0 or dstIter["fileSize"] <= descendant_quota
    if child_flag and descendant_flag:
        dstIter["childQuota"] = child_quota
        dstIter["descendantQuota"] = descendant_quota
        return True
    else:
        return False

def main():
    n = int(input())
    for loop in range(n):
        cmd = input().split()
        result = False
        if cmd[0] == "C":
            result = create(cmd[1], int(cmd[2]))
        elif cmd[0] == "R":
            result = remove(cmd[1])
        else:
            result = quota(cmd[1], int(cmd[2]), int(cmd[3]))
        if result:
            print("Y")
        else:
            print("N")
        # print(root_directory)

if __name__ == '__main__':
    main()

CSP 202012-2 期末预测之最佳阈值

这题也不知道咋回事,我想了个异想天开的做法,也不知道行不行,交上去竟然过了!哈哈哈哈哈哈。
暴力的N^2做法可以得70,我写个异想天开的排序+前缀和做法100。
感觉有必要写个题解,在这里写一下。

本题的大致意思是,给出一堆人的学习努力程度(用一个非负整数表示)和其是否挂科(并不必然成正相关,其中可能混杂学习努力程度高的人也挂科的情况)。要求找到一个学习努力程度基准分数,使得用该基准评判学生的努力程度时,判断对的最多。

我主要利用差分的思想进行解题。对于一个分数,我们其实只需要知道通过与挂科的人数的差值即可。基准分数是否应该低于或高于某一特定学习努力程度分数,在于其能否为总人数作出贡献。例如,如果一个分数有3人通过,3人挂科,则不管选择比他低的基准还是比他高的基准,则都对总的人数做出了3的贡献,可以相互抵消。但若4人通过,3人挂科,则更应该优先选择比其低的基准,因为这样的话,判断对的就多了一个。

首先建立一个map对输入的数据进行排序。由于选择指标的时候只看努力程度不看人,因此可以将同努力程度的人们聚合起来。如果该人挂科,在是否通过的数组cnt里-1,如果通过则+1.这样就产生了一个差分的数组cnt。此时,该数组cnt表示的是在选定该分数作为基准后,通过的人比挂科的人多多少。

然后,对其进行前缀和操作。借助前缀和,我们可以得到数组presum,可以计算选择任意基准分数时,通过的人比挂科的人多多少。还可计算选择任意基准分数时,挂科的人比通过的人多多少(通过对计算值取负)。这样,我们分别计算高于基准分数通过的人比挂科的人多多少,和低于基准分数时挂科的人比通过的人多多少。将他们相加,就可以得到一个判断正确的人数的差分。统计这些差分的最大值,就可以算出对应的基准分数。

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

using namespace std;

int m;
map<int, int> stat;
int arrSize = 0;
int y[100005], cnt[100005], presum[100005];

int main() {
    ios::sync_with_stdio(false);
    cin >> m;
    while (m--) {
        int y, result;
        cin >> y >> result;
        stat[y] += result ? 1 : -1;
    }
    for (auto iter = stat.begin(); iter != stat.end(); iter++) {
        int ind = iter->first, v = iter->second;
        y[arrSize] = ind;
        cnt[arrSize] = v;
        arrSize++;
    }
    presum[0]=cnt[0];
    for(int i=1;i<arrSize;i++){
        presum[i]=presum[i-1]+cnt[i];
    }
    int index=0, cmpValue=presum[arrSize-1];
    for(int i=1;i<arrSize;i++){
        int tmpV=presum[arrSize-1]-presum[i-1]*2;
        if(tmpV>=cmpValue){
            cmpValue=tmpV;
            index=i;
        }
    }
    cout<<y[index];
}

洛谷 P3369 【模板】普通平衡树

手写Splay成功。庆祝能写出来的第一个BBST!
代码如下:

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include<iostream>
#include<cassert>
using namespace std;
class Splay {
private:
    struct Node {
        int v; //值
        Node* f, * l, * r; //父,左孩子,右孩子
        int cnts; //本子树下包含自身的所有**元素**数目
        int rep; //该值重复了多少次
        Node(int v, Node* f) :v(v), f(f), l(NULL), r(NULL), cnts(1), rep(1) {}
    };
    Node* _root;
#define root _root->r
    void update(Node* p) { //更新cnts值
        p->cnts = p->rep;
        if (p->l)p->cnts += p->l->cnts;
        if (p->r)p->cnts += p->r->cnts;
    }
    bool identify(Node* s, Node* f) { //确定本节点是左孩子还是右孩子,左孩子false,右孩子true
        return !f || s == f->r;
    }
    void connect(Node* s, Node* f, bool r) { //儿子地址,父亲地址,连接到左儿子还是右儿子
        if (f)(r ? f->r : f->l) = s; //父亲更新新儿子
        if (s)s->f = f; //儿子更新新父亲
    }
    void rotate(Node* s) { //儿子节点的旋转
        Node* f = s->f, * gf = s->f->f;
        if (!identify(s, f)) { //左孩子
            connect(s->r, f, false);
            connect(f, s, true);
            connect(s, gf, identify(f, gf));
        }
        else { //右孩子
            connect(s->l, f, true);
            connect(f, s, false);
            connect(s, gf, identify(f, gf));
        }
        update(f);
        update(s);
    }
    void splay(Node* s, Node* e) { //伸展操作,将节点s旋转到节点e所在的位置
        e = e->f;
        while (s->f != e) {
            Node* f = s->f;
            if (f->f == e)rotate(s); //s是e的直系儿子,只需做单旋
            else if (identify(f, f->f) == identify(s, f)) { //Zig-Zig或Zag-Zag,需要先旋父亲节点,再旋儿子节点
                rotate(f);
                rotate(s);
            }
            else { //Zig-Zag或Zag-Zig
                rotate(s);
                rotate(s);
            }
        }
    }

public:
    Splay() {
        _root = new Node(0, NULL);
    }
    ~Splay() {
        delete _root;
    }
    Node* find(int v) {
        Node* cur = root;
        if (!cur)return NULL;
        while (1) {
            if (cur->v == v) break;
            Node* next = v < cur->v ? cur->l : cur->r;
            if (!next)break;
            cur = next;
        }
        splay(cur, root);
        root = cur;
        if (cur->v == v)return cur;
        else return NULL;
    }
    void del(int v) {
        Node* cur = find(v);
        if (!cur)return;
        if (cur->rep > 1) { //节点个数出现多于1次
            cur->rep--;
            cur->cnts--;
            return;
        }
        if (!cur->l && !cur->r) { //删除最后一个仅剩的节点
            root = NULL;
        }
        else if (!cur->l) { //无左子树时直接把右子树拼到根
            root = cur->r;
            root->f = _root;
        }
        else { //有左子树时,把左子树的最大值旋到根的左子,将根的右子放到根的左子的右子,删根后补左子树
            Node* l = cur->l;
            while (l->r)l = l->r;
            splay(l, cur->l);
            Node* r = cur->r;
            connect(r, l, true);
            root = l;
            root->f = _root;
            update(l);
        }
        delete cur;
    }
    void insert(int v) {
        Node* cur = find(v);
        if (!root) { //特判空树
            root = new Node(v, _root);
            return;
        }
        if (cur && cur->v == v) { //元素存在,直接把次数+1
            cur->rep++;
            cur->cnts++;
            return;
        }
        Node* newNode = new Node(v, _root);
        if (root->v < v) { //将v接入右侧
            connect(root, newNode, false);
            connect(root->r, newNode, true);
            root->r = NULL;
        }
        else { //将v接入左侧
            connect(root, newNode, true);
            connect(root->l, newNode, false);
            root->l = NULL;
        }
        update(root);
        update(newNode);
        root = newNode;
        newNode->f = _root;
    }
    int rank(int v) {
        Node* cur = find(v);
        if (!cur)return -1;
        int lCnts = cur->l ? cur->l->cnts : 0;
        return lCnts + 1;
    }
    int atrank(int rank) {
        Node* cur = root;
        while (cur) {
            int lCnts = cur->l ? cur->l->cnts : 0;
            if (lCnts < rank && rank <= lCnts + cur->rep) {
                splay(cur, root);
                return cur->v;
            }
            if (rank <= lCnts)cur = cur->l;
            else {
                rank -= lCnts + cur->rep;
                cur = cur->r;
            }
        }
        return -1;
    }
    int upper(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v <= v)return atrank(lCnts + root->rep + 1);
        return root->v;
    }
    int lower(int v) {
        Node* cur = find(v);
        int lCnts = root->l ? root->l->cnts : 0;
        if (root->v >= v)return atrank(lCnts);
        return root->v;
    }
#undef root
};
int main() {
    Splay splay;
    int n;
    cin >> n;
    while (n--) {
        int op1, op2;
        cin >> op1 >> op2;
        if (op1 == 1) {
            splay.insert(op2);
        }
        else if (op1 == 2) {
            splay.del(op2);
        }
        else if (op1 == 3) {
            cout << splay.rank(op2) << endl;
        }
        else if (op1 == 4) {
            cout << splay.atrank(op2) << endl;
        }
        else if (op1 == 5) {
            cout << splay.lower(op2) << endl;
        }
        else if (op1 == 6) {
            cout << splay.upper(op2) << endl;
        }
    }
}

参考资料:
https://www.luogu.com.cn/blog/user19027/solution-p3369
非常感谢rentenglong同学

洛谷 P2580 于是他错误的点名开始了

Trie树练手题,然而空间不够用最后一个点MLE,90

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<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MaxN = 5000000;
int trie[MaxN][26];
int cnts[MaxN];
int tot;
int trieInsert(string s) {
    int node = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!trie[node][s[i] - 'a'])node = trie[node][s[i] - 'a'] = ++tot;
        else node = trie[node][s[i] - 'a'];
    }
    return node;
}
int main() {
    int n,m;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        int node=trieInsert(s);
        cnts[node]=1;
    }
    cin >> m;
    while (m--) {
        cin >> s;
        int node = trieInsert(s);
        if (cnts[node] == 1){
            cout << "OK" << endl;
            cnts[node]=2;
        }
        else if (cnts[node] == 0)cout << "WRONG" << endl;
        else if (cnts[node] == 2)cout << "REPEAT" << endl;
    }
}

洛谷 P1481 魔族密码

今学习Trie树:https://blog.csdn.net/weixin_43792276/article/details/98977397

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<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MaxN = 5000;
int trie[MaxN][26];
int cnts[MaxN];
int tot;
void trieInsert(string s) {
    int node = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!trie[node][s[i] - 'a'])node = trie[node][s[i] - 'a'] = ++tot;
        else node = trie[node][s[i] - 'a'];
    }
    cnts[node]++;
}
void trieAccumulate(int node) {
    for (int i = 0; i < 26; i++) {
        if (trie[node][i]) {
            cnts[trie[node][i]] += cnts[node];
            trieAccumulate(trie[node][i]);
        }
    }
}
int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        trieInsert(s);
    }
    trieAccumulate(0);
    int result = 0;
    for (int i = 0; i <= tot; i++)result = max(result, cnts[i]);
    cout << result;
}

蓝桥杯 历届试题 小计算器

问题描述
  模拟程序型计算器,依次输入指令,可能包含的指令有

  1. 数字:’NUM X’,X为一个只包含大写字母和数字的字符串,表示一个当前进制的数
  2. 运算指令:’ADD’,’SUB’,’MUL’,’DIV’,’MOD’,分别表示加减乘,除法取商,除法取余
  3. 进制转换指令:’CHANGE K’,将当前进制转换为K进制(2≤K≤36)
  4. 输出指令:’EQUAL’,以当前进制输出结果
  5. 重置指令:’CLEAR’,清除当前数字

  指令按照以下规则给出:
  数字,运算指令不会连续给出,进制转换指令,输出指令,重置指令有可能连续给出
  运算指令后出现的第一个数字,表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
  重置指令后出现的第一个数字,表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
  进制转换指令可能出现在任何地方

  运算过程中中间变量均为非负整数,且小于2^63。
  以大写的’A’~’Z’表示10~35
输入格式
  第1行:1个n,表示指令数量
  第2..n+1行:每行给出一条指令。指令序列一定以’CLEAR’作为开始,并且满足指令规则
输出格式
  依次给出每一次’EQUAL’得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

可以说样例给的挺恶心。会让人想不到,这玩意要考虑还是不考虑优先级!?最后在测试下是不需要考虑优先级的。直接挨着个的算即可。还有一个点是我进制转换写错了(竟然’A’->11,生无可恋脸)一直在调这里。。。。其他没啥了。

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
#include<iostream>
#include<deque>
#include<algorithm>
#include<cassert>
#include<cstdlib>
#include<string>
using namespace std;
int n;
int radix = 10;
string radixS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
deque<long long> sll;
deque<string> sop;
long long value;
inline long long getCorDecimal(char c) {
    if ('0' <= c && c <= '9')return c - '0';
    if ('A' <= c && c <= 'Z')return c - 'A' + 10;
    assert(false);
    return -1;
}
long long Radix2Decimal(string s) {
    reverse(s.begin(), s.end());
    long long cntBase = 1, result = 0;
    for (int i = 0; i<s.size(); i++) {
        result += getCorDecimal(s[i])*cntBase;
        cntBase *= radix;
    }
    return result;
}
string Decimal2Radix(long long v) {
    string s = "";
    while (v) {
        s.push_back(radixS[v%radix]);
        v /= radix;
    }
    if (s == "")s = "0";
    reverse(s.begin(), s.end());
    return s;
}
bool calculate4Back() {
    if (sop.empty())return false;
    string & comm = sop.back();
    if (comm == "ADD")value += sll.back();
    else if (comm == "SUB")value = sll.back() - value;
    else if (comm == "MUL")value *= sll.back();
    else if (comm == "DIV")value = sll.back() / value;
    else if (comm == "MOD")value = sll.back() % value;
    else assert(false);
    sop.pop_back();
    sll.pop_back();
    sll.push_back(value);
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string comm, radixV;
        cin >> comm;
        if (comm == "NUM") {
            cin >> radixV;
            value = Radix2Decimal(radixV);
            if (!calculate4Back())sll.push_back(value);
            //cout<<Decimal2Radix(sll.front())<<endl;
        }
        else if (comm == "ADD" || comm == "SUB" || comm == "MUL" || comm == "DIV" || comm == "MOD") {
            sop.push_back(comm);
        }
        else if (comm == "CHANGE") {
            cin >> radix;
        }
        else if (comm == "EQUAL") {
            cout << Decimal2Radix(sll.front()) << endl;
        }
        else if (comm == "CLEAR") {
            sll.clear();
            sop.clear();
        }
    }
}

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

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
}