Powered by:NEFU AB_IN
2021 ICPC网络赛第一场
A
-
题意
有 k k k个点（ j = 0 , 1... k j=0,1...k j=0,1...k）， n n n个任务（ i = 0 , 1... n i =0,1...n i=0,1...n），每个任务有到达时间和持续时间，第 i i i个任务从 i % k i\%k i%k的点开始往后找有没有空闲的点，如果没有找到则任务作废，问 k k k个点谁接的任务最多
-
思路
如果暴力查找，从第二个点开始找，找完一遍发现是第一个点，碰到多个这种数据这样肯定会 T T T，所以考虑在查找方面减少复杂度，这里采取线段树+二分+set
- 线段树维护 k k k个点结束的区间最小值，单点修改，区间查询
- 二分查找最小值
- s e t set set维护 k k k个点结束的最小值，判断是否任务需要遗弃
-
代码
/* * @Author: NEFU AB-IN * @Date: 2021-09-19 13:03:13 * @FilePath: \Contest\a.cpp * @LastEditTime: 2021-09-19 19:27:05 */ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N << 2], tr[N << 3], cnt[N]; set<int> s; map<int, int> m; void bulid(int i, int l, int r) { if (l == r) { tr[i] = 0x3f3f3f3f; return; } int mid = l + r >> 1; bulid(i << 1, l, mid); bulid(i << 1 | 1, mid + 1, r); tr[i] = min(tr[i << 1], tr[i << 1 | 1]); } void update(int i, int l, int r, int x, int y) { if (l > x || x > r) return; if (l == r && l == x) { tr[i] = y; return; } int mid = l + r >> 1; update(i << 1, l, mid, x, y); update(i << 1 | 1, mid + 1, r, x, y); tr[i] = min(tr[i << 1], tr[i << 1 | 1]); } int query(int i, int l, int r, int x, int y) { if (y < l || x > r) return 0x3f3f3f3f; if (l >= x && r <= y) return tr[i]; int mid = l + r >> 1; return min(query(i << 1, l, mid, x, y), query(i << 1 | 1, mid + 1, r, x, y)); } int f(int l, int r, int x, int k) { if (l == r) return l; int mid = (l + r) / 2; if (query(1, 1, 2 * k, l, mid) < x) f(l, mid, x, k); else f(mid + 1, r, x, k); } int main() { int k, n; cin >> k >> n; bulid(1, 1, 2 * k); s.insert(0); m[0] = k; for (int i = 0; i < n; ++i) { int l, time; cin >> l >> time; if (*s.begin() >= l) continue; if (a[i % k] < l) { cnt[i % k]++; m[a[i % k]]--; if (m[a[i % k]] == 0) s.erase(a[i % k]); a[i % k] = l + time - 1; if (s.find(a[i % k]) == s.end()) s.insert(a[i % k]); m[a[i % k]]++; update(1, 1, 2 * k, (i % k) + 1, l + time - 1); update(1, 1, 2 * k, (i % k) + k + 1, l + time - 1); } else { int id = f(i % k + 1, i % k + k, l, k); id--; id %= k; cnt[id]++; m[a[id]]--; if (m[a[id]] == 0) s.erase(a[id]); a[id] = l + time - 1; if (s.find(a[id]) == s.end()) s.insert(a[id]); m[a[id]]++; update(1, 1, 2 * k, id + 1, l + time - 1); update(1, 1, 2 * k, id + k + 1, l + time - 1); } } int minx = 0, ans = 0; for (int i = 0; i < k; i++) minx = max(minx, cnt[i]); for (int i = 0; i < k; i++) { if (cnt[i] == minx) { if (ans) printf(" "); printf("%d", i); ans++; } } return 0; }
F
-
题意
几何
-
代码
/* * @Author: NEFU AB-IN * @Date: 2021-09-19 12:04:27 * @FilePath: \Contest\f.cpp * @LastEditTime: 2021-09-19 12:28:19 */ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N]; int main() { int t; cin >> t; for (int i = 1; i <= t; ++i) { double a, b, r; cin >> a >> b >> r; if (r >= b) { printf("Case #%d: %.2f\n", i, 2 * a - r); } else { printf("Case #%d: %.2f\n", i, 2 * sqrt(a * a + (b - r) * (b - r)) - r); } } return 0; }
H
-
题意
队友出的，贴一下
-
代码
/* * @Author: NEFU AB-IN * @Date: 2021-09-19 14:44:27 * @FilePath: \Contest\h.cpp * @LastEditTime: 2021-09-19 15:01:14 */ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m; set<int> s1[N], s2[N]; map<int, int> map1; void insert111(int a, int b) { if (s1[map1[a]].find(b) == s1[map1[a]].end()) s1[map1[a]].insert(b); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; int id, biao, a, b, c; double x, y, z; for (int i = 1; i <= n; i++) { cin >> id; map1[id] = i; cin >> x >> y >> z; // printf("%lf %lf %lf\n", x, y, z); } for (int i = 1; i <= m; i++) { cin >> id >> biao; switch (biao) { case 102: cin >> a >> b; insert111(a, b); s2[map1[a]].insert(id); insert111(b, a); s2[map1[b]].insert(id); break; case 203: cin >> a >> b >> c; insert111(a, b); insert111(a, c); insert111(b, c); insert111(b, a); insert111(c, a); insert111(c, b); s2[map1[a]].insert(id); s2[map1[b]].insert(id); s2[map1[c]].insert(id); } } int t; cin >> t; while (t--) { cin >> id; if (map1[id] == 0) { printf("%d\n[]\n[]\n", id); } else { printf("%d\n[", id); for (auto i : s1[map1[id]]) { if (i != *s1[map1[id]].begin()) printf(","); printf("%d", i); } printf("]\n["); for (auto i : s2[map1[id]]) { if (i != *s2[map1[id]].begin()) printf(","); printf("%d", i); } printf("]\n"); } } return 0; }
I
-
题意
签到题，数据范围也不给，考验选手读入能力，点赞
-
代码
''' Author: NEFU AB-IN Date: 2021-09-19 12:10:49 FilePath: \Contest\i.py LastEditTime: 2021-09-19 12:12:43 ''' lst = list(map(int, input().split())) x = int(input()) r = int(input()) lst.sort() flag = 0 for i in range(len(lst) - 1, -1, -1): if abs(lst[i] - x) <= r: print(lst[i], end=" ") flag = 1 if flag == 0: print()
K
-
题意
模拟即可
-
代码
/* * @Author: NEFU AB-IN * @Date: 2021-09-19 15:03:00 * @FilePath: \Contest\k.cpp * @LastEditTime: 2021-09-19 19:55:10 */ #include <bits/stdc++.h> using namespace std; int n, m; const int N = 1e5 + 50; vector<int> v[N]; int main() { int t; scanf("%d", &t); for (int k = 1; k <= t; k++) { scanf("%d%d", &n, &m); int xx, u; for (int i = 1; i <= n; i++) { v[i].clear(); cin >> xx; for (int j = 1; j <= xx; j++) { scanf("%d", &u); v[i].push_back(u); } } printf("Case #%d: \n", k); for (int j = 1; j <= m; j++) { bool flag = 0; scanf("%d %d", &u, &k); int vv = u, id; for (int i = 1; i <= k; i++) { scanf("%d", &id); if (id > v[vv].size() || id == 0) flag = 1; if (flag == 1) continue; vv = v[vv][id - 1]; } if (flag) printf("Packet Loss\n"); else { printf("%d\n", vv); } } } return 0; }
明天补题。。