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; }
明天補題，，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301517.html
標籤：其他
上一篇：說說QQ音樂專案的那些bug
下一篇：動態規劃之線性DP題集