热门标签
热门文章
当前位置: article > 正文
CSP-J/S2022第二轮游记_游记csp-j
作者：weixin_40725706 | 2024-04-20 10:52:15
赞
踩
游记csp-j
Day -5
物理分数出来了，考了个寄。
罚自己不能搞OI，刷物理卷子励志了一晚。
（好像下一次的物理考试也没考多少（？））
Day -4
正文开始。
这天我在搞OI，学了一下Floyd和dijkstra，打了几道模板题。
其实我还是太蒻了，打了好久。
Day -3
同 Day -4，做最短路，同时也刷了几道DP水题。
突然感觉很慌，特别慌。
Day -2
做了一下2019的题，我甚至J组都调了好久。。。
想着到时候不会抱灵了吧，一个晚上没睡。
Day -1
测了1000m，没满分就对了。
一回到家就累死了，啥也没干。
Day 0
试机日，考试在二中考。
去了一下二中，环境很好（赞赏。
键盘很好打，就是有点平了。
win10系统很流畅，比linux要好点。
（暗自祝福自己rp++）
Day 1
考试日。
（要不是有二中人指路，我真的不知道怎么走）
对着电脑罚座30min。
开考。
一看T1，这是什么lj题目？
当时感觉有点DP，但有感觉DP行不通，我就想着先打打看。
存了图，大概过去了6min。
继续思考。
感觉可以先求一下全源最短路，然后再来树形DP。
开始打最短路了。
发现大问题！，Floyd怎么打来着？
打了三个for，没屁用。
开始想其他方法。
想了一下，感觉对每个点都进行堆优化的dijkstra和Floyd差不多，于是手搓了了一个dijkstra。
然后想怎么写dfs()
思路：
dfs(p,sum,num)
其中，p是当前节点，sum是当前分数，num是当前为第几个节点。
接下来就好写了：
#include <bits/stdc++.h> using namespace std; vector<int> V[2505]; int n, m, k; unsigned long long ans = 0; unsigned long long s[2505] = {0}; int dis[2505][2505] = {0}; bool v[10000] = {0}; bool b[10000] = {0}; const int INF = 0x7fffffff; struct Node { int p; long long jul; }; bool operator < (Node a, Node b) { return a.jul > b.jul; } priority_queue<Node> q; void dijkstra(int s) { for (int i = 1; i <= n; i++) v[i] = 0; for (int i = 1; i <= n; i++) dis[s][i] = INF; dis[s][s] = 0; q.push((Node){s, 0}); while (!q.empty()) { Node t = q.top(); q.pop(); int p = t.p; long long o = t.jul; if (v[p]) continue; v[p] = 1; for (int i = 0; i < V[p].size(); i++) { int k = V[p][i]; if (v[k]) continue; if (o + 1 < dis[s][k]) dis[s][k] = o + 1, q.push((Node){k, dis[s][k]}); } } for (int i = 1; i <= n; i++) dis[s][i] -= 1; } void dfs(int p, unsigned long long sum, int num) { if (num == 5) { if (sum > ans) ans = sum; return; } if (num == 4) { if (dis[p][1] > k) return; dfs(1, sum, num + 1); return; } for (int i = 2; i <= n; i++) { if (b[i]) continue; if (dis[p][i] > k) continue; b[i] = 1; dfs(i, sum + s[i], num + 1); b[i] = 0; } } int main() { freopen("holiday.in", "r", stdin); freopen("holiday.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m >> k; for (int i = 2; i <= n; i++) cin >> s[i]; for (int i = 1, x, y; i <= m; i++) { cin >> x >> y; V[x].push_back(y); V[y].push_back(x); } for (int i = 1; i <= n; i++) dijkstra(i); dfs(1, 0, 0); cout << ans; return 0; }
- 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
预计得分：40pts
自测得分：70pts
实际得分：？pts
思路来到T2，最开始没看懂，发现会出现负数，感觉好麻烦，跳到T3。
被T3的题面唬住了，跳到T2。
想了一下，感觉T2不是不可做，把他初始化成一个矩阵，然后在所有行中取其最小数最大的行，然后在当前行中取最小数。
感觉市STable的变式，但！是！我！不！会！
于是我只能打暴力。
代码很快打出来了。
但总是写挂，调了1.5h。
最终Code：
#include <bits/stdc++.h> using namespace std; int n, m, q; long long a[100500]; long long b[100500]; long long ans = 0; int main() { freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m >> q; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) cin >> b[i]; while (q--) { int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2; long long Min = -1; bool f = 0; int x, y; for (int i = l1; i <= r1; i++) { bool m = 0; long long awa; for (int j = l2; j <= r2; j++) { if (!m) awa = a[i] * b[j], m = 1; else { if (a[i] * b[j] < awa) { awa = a[i] * b[j]; } } } if (!f) Min = awa, x = i, f = 1; else { if (awa > Min) { Min = awa; x = i; } } } long long Max; f = 0; for (int i = l2; i <= r2; i++) { if (!f) Max = a[x] * b[i], y = i, f = 1; else { if (a[x] * b[i] < Max) { Max = a[x] * b[i]; y = i; } } } ans = a[x] * b[y]; cout << ans << endl; } return 0; }
- 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
预计得分：60pts
自测得分：60pts
实际得分：？pts
看了看T3，懂了题目，花0.5h打了个模拟，结果大挂了。
Why？
首先建立两个数组啊a[]和b[]， a i a_i ai 表示从 i i i 点出发的边的个数， b i b_i bi 相反。
1操作简单，遍历一遍，然后f=0，break。
3同一。
我的2操作和4操作多加了两个break;，自此40pts->0pts
最终Code：
#include <bits/stdc++.h> using namespace std; int n, m, q; int c[500005] = {0}; int r[500005] = {0}; int a[500005] = {0}; int b[500005] = {0}; int z; struct Edge { int u; int v; bool f; } e[500005]; int cnt = 0; int main() { freopen("galaxy.in", "r", stdin); freopen("galaxy.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; z = m; for (int i = 1, x, y; i <= m; i++) { cin >> x >> y; c[x]++, r[y]++; a[x]++, b[y]++; cnt++; e[cnt].u = x; e[cnt].v = y; e[cnt].f = 1; } cin >> q; while (q--) { int t, u, v; cin >> t; if (t == 1) { cin >> u >> v; for (int i = 1; i <= cnt; i++) { if (e[i].u == u && e[i].v == v) { e[i].f = 0; break; } } a[u]--, b[v]--; z--; } else if (t == 2) { cin >> u; for (int i = 1; i <= cnt; i++) { if (e[i].f && e[i].v == u) { e[i].f = 0; a[e[i].u]--, b[u]--; z--; break; } } } else if (t == 3) { cin >> u >> v; for (int i = 1; i <= cnt; i++) { if (e[i].u == u && e[i].v == v) { e[i].f = 1; break; } } a[u]++, b[v]++; z++; } else { cin >> u; for (int i = 1; i <= cnt; i++) { if (!e[i].f && e[i].v == u) { e[i].f = 1; a[e[i].u]++, b[u]++; z++; break; } } } bool f = 1; if (z == n) { for (int i = 1; i <= n; i++) { if (a[i] != 1) { f = 0; break; } } if (f) cout << "YES" << endl; else cout << "NO" << endl; } else cout << "NO" << endl; } return 0; }
- 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
可以40pts的Code：
#include <bits/stdc++.h> using namespace std; int n, m, q; int c[500005] = {0}; int r[500005] = {0}; int a[500005] = {0}; int b[500005] = {0}; int z; struct Edge { int u; int v; bool f; } e[500005]; int cnt = 0; int main() { freopen("galaxy.in", "r", stdin); freopen("galaxy.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; z = m; for (int i = 1, x, y; i <= m; i++) { cin >> x >> y; c[x]++, r[y]++; a[x]++, b[y]++; cnt++; e[cnt].u = x; e[cnt].v = y; e[cnt].f = 1; } cin >> q; while (q--) { int t, u, v; cin >> t; if (t == 1) { cin >> u >> v; for (int i = 1; i <= cnt; i++) { if (e[i].u == u && e[i].v == v) { e[i].f = 0; break; } } a[u]--, b[v]--; z--; } else if (t == 2) { cin >> u; for (int i = 1; i <= cnt; i++) { if (e[i].f && e[i].v == u) { e[i].f = 0; a[e[i].u]--, b[u]--; z--; } } } else if (t == 3) { cin >> u >> v; for (int i = 1; i <= cnt; i++) { if (e[i].u == u && e[i].v == v) { e[i].f = 1; break; } } a[u]++, b[v]++; z++; } else { cin >> u; for (int i = 1; i <= cnt; i++) { if (!e[i].f && e[i].v == u) { e[i].f = 1; a[e[i].u]++, b[u]++; z++; } } } bool f = 1; if (z == n) { for (int i = 1; i <= n; i++) { if (a[i] != 1) { f = 0; break; } } if (f) cout << "YES" << endl; else cout << "NO" << endl; } else cout << "NO" << endl; } return 0; }
- 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
预计得分：40pts
自测得分：0pts
实际得分：？pts
T4我直接没做了。。。
Day 2
拿到了考场代码，寄了。
THE END
这件事情告诉我们，一定不要乱加break，不然会170pts->130pts！
Think Twice,Code Once.
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/456934
推荐阅读
相关标签
