热门标签
热门文章
- 1（附源码）ssm基于Html+css的音乐网站的设计与实现 毕业设计181627_html音乐网站框架设计
- 2vrchat模型房_vrchat人物模型 1.0 官方版
- 3盘点百度、阿里、腾讯、华为自动驾驶战略
- 4python 全栈开发，Day75(Django与Ajax,文件上传,ajax发送json数据,基于Ajax的文件上传,SweetAlert插件)...
- 5Android5.0之NavigationView的使用
- 6全球首个AI女主播上岗了！太惊艳了！
- 7魔兽世界私服架设教程——如何搭建魔兽世界私服
- 8蓝桥杯备考冲刺必刷题（Python） | 549 扫雷
- 9Java –将值附加到Object []数组中
- 10torch.cuda.OutOfMemoryError: CUDA out of memory. Tried to allocate 86.00 MiB (GPU 0； 31.74 GiB total
当前位置: article > 正文
CCF-CSP202303C题LDAP【100分】（结构清晰）_ldap csp
作者：不正经 | 2024-03-09 17:15:42
赞
踩
ldap csp
非递归写法（栈）
参考了
①CCF-CSP认证 202303 500分题解；
②bitset的基本用法
③表达式求值
自认代码结构相对清晰，给卡在这题的同学参考。
#include <bits/stdc++.h> using namespace std; const int N = 2510; typedef bitset<N> STATE; typedef pair<int, int> PII; int n, m; vector<PII> p; map<PII, STATE> d; map<int, STATE> S; stack<STATE> num; stack<char> op; void eval(){ STATE b = num.top(); num.pop(); STATE a = num.top(); num.pop(); char c = op.top(); op.pop(); STATE res; if (c == '&') res = a & b; else res = a | b; num.push(res); } STATE solve(string str){ stack<STATE>().swap(num), stack<char>().swap(op); for (int i = 0; i < str.size(); i ++ ){ char c = str[i]; if (isdigit(c)){ int x = 0, j = i; while (j < str.size() && isdigit(str[j])) x = x * 10 + str[j] - '0', j ++ ; char oper = str[j]; j ++ ; int y = 0; while (j < str.size() && isdigit(str[j])) y = y * 10 + str[j] - '0', j ++ ; i = j - 1; if (oper == ':') num.push(d[{x, y}]); else num.push(~d[{x, y}] & S[x]); } else if (c == '(') op.push(c); else if (c == ')'){ while (op.top() != '(') eval(); op.pop(); } else{ while (op.size() && op.top() != '(') eval(); op.push(c); } } while (op.size()) eval(); return num.top(); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i < n; i ++ ){ int t; cin >> t; p.push_back({t, i}); int cnt; cin >> cnt; while (cnt -- ){ int x, y; cin >> x >> y; d[{x, y}][i] = 1; S[x][i] = 1; } } sort(p.begin(), p.end()); cin >> m; while (m -- ){ string str; cin >> str; STATE state = solve(str); vector<int> res; for (int i = 0; i < n; i ++ ){ int x = p[i].first, y = p[i].second; if (state[y]) res.push_back(x); } for (int i = 0; i < res.size(); i ++ ) cout << res[i] << " \n"[i == res.size() - 1]; if (res.empty()) cout << endl; } return 0; } /* 2 1 2 1 2 2 3 2 2 2 3 3 1 4 1:2 3~1 &(1:2)(2:3) |(1:2)(3:1) */
- 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
运行时间也还行
递归写法
另外，有个很凑巧的递归写法，考场上试出来的。利用了scanf的机制，用%d读字符，会将读取的字符自动退回输入缓冲区，原用于接收的int变量tmp值未改变。
参考C语言使用%d读入字符会发生什么
#include <bits/stdc++.h> using namespace std; const int N = 2510; typedef bitset<N> STATE; typedef pair<int, int> PII; int n, m; vector<PII> p; map<PII, STATE> d; map<int, STATE> S; STATE get(){ int tmp = 0; scanf("%d", &tmp); if (tmp){ int x = tmp, y; char op; cin >> op >> y; if (op == ':') return d[{x, y}]; else return ~d[{x, y}] & S[x]; } char op; scanf("%c", &op); getchar(); STATE x = get(); getchar(); getchar(); STATE y = get(); getchar(); if (op == '&') return x & y; else return x | y; } int main(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ){ int t; scanf("%d", &t); p.push_back({t, i}); int cnt; scanf("%d", &cnt); while (cnt -- ){ int x, y; scanf("%d %d", &x, &y); d[{x, y}][i] = 1; S[x][i] = 1; } } sort(p.begin(), p.end()); scanf("%d", &m); while (m -- ){ STATE state = get(); getchar(); vector<int> res; for (int i = 0; i < n; i ++ ){ int x = p[i].first, y = p[i].second; if (state[y]) res.push_back(x); } for (int i = 0; i < res.size(); i ++ ) printf(" %d" + !i, res[i]); puts(""); } return 0; } /* 2 1 2 1 2 2 3 2 2 2 3 3 1 4 1:2 3~1 &(1:2)(2:3) |(1:2)(3:1) */
- 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
时间慢了1s
更正常一点的写法
#include <bits/stdc++.h> using namespace std; const int N = 2510; typedef bitset<N> STATE; typedef pair<int, int> PII; int n, m; vector<PII> p; map<PII, STATE> d; map<int, STATE> S; string str; STATE state; int get(int u){ if (isdigit(str[u])){ int x = 0, y = 0; while (u < str.size() && isdigit(str[u])) x = x * 10 + str[u] - '0', u ++ ; char op = str[u]; u ++ ; while (u < str.size() && isdigit(str[u])) y = y * 10 + str[u] - '0', u ++ ; if (op == ':') state = d[{x, y}]; else state = ~d[{x, y}] & S[x]; return u; } char op = str[u]; u ++ ; u = get(u + 1); STATE x = state; u ++ ; u = get(u + 1); STATE y = state; if (op == '&') state = x & y; else state = x | y; return u + 1; } int main(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ){ int t; scanf("%d", &t); p.push_back({t, i}); int cnt; scanf("%d", &cnt); while (cnt -- ){ int x, y; scanf("%d %d", &x, &y); d[{x, y}][i] = 1; S[x][i] = 1; } } sort(p.begin(), p.end()); scanf("%d", &m); while (m -- ){ cin >> str; get(0); vector<int> res; for (int i = 0; i < n; i ++ ){ int x = p[i].first, y = p[i].second; if (state[y]) res.push_back(x); } for (int i = 0; i < res.size(); i ++ ) printf(" %d" + !i, res[i]); puts(""); } return 0; } /* 2 1 2 1 2 2 3 2 2 2 3 3 1 4 1:2 3~1 &(1:2)(2:3) |(1:2)(3:1) */
- 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
可能更好想到的做法，属性值直接存储，每位单独进行判断。不用unorder_map则70分。
#include <bits/stdc++.h> using namespace std; const int N = 2510; typedef pair<int, int> PII; int n, m; vector<PII> p; unordered_map<int, int> v[N]; string str; bool flag; int aim; int get(int u){ if (isdigit(str[u])){ int x = 0, y = 0; while (u < str.size() && isdigit(str[u])) x = x * 10 + str[u] - '0', u ++ ; char op = str[u]; u ++ ; while (u < str.size() && isdigit(str[u])) y = y * 10 + str[u] - '0', u ++ ; if (!v[aim].count(x)) flag = false; else if (op == ':' && v[aim][x] == y) flag = true; else if (op == '~' && v[aim][x] != y) flag = true; else flag = false; return u; } char op = str[u]; u ++ ; u = get(u + 1); bool x = flag; u ++ ; u = get(u + 1); bool y = flag; if (op == '&') flag = x && y; else flag = x || y; return u + 1; } int main(){ scanf("%d", &n); for (int i = 0; i < n; i ++ ){ int t; scanf("%d", &t); p.push_back({t, i}); int cnt; scanf("%d", &cnt); while (cnt -- ){ int x, y; scanf("%d %d", &x, &y); v[i][x] = y; } } sort(p.begin(), p.end()); scanf("%d", &m); while (m -- ){ cin >> str; vector<int> res; for (int i = 0; i < n; i ++ ){ int x = p[i].first, y = p[i].second; aim = y; get(0); if (flag) res.push_back(x); } for (int i = 0; i < res.size(); i ++ ) printf(" %d" + !i, res[i]); puts(""); } return 0; } /* 2 1 2 1 2 2 3 2 2 2 3 3 1 4 1:2 3~1 &(1:2)(2:3) |(1:2)(3:1) */
- 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
时间慢了很多
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/215710
推荐阅读
相关标签
