「CF1237X」Codeforces Global Round 5
A. Balanced Rating Changes
先把所有奇数除二下取整，再任选一些加一
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, sum; int even[20005], a[20005], b[20005]; int main() { n = read(); for(int i = 1; i <= n; i++) { a[i] = read(); if(a[i] % 2 == 0) { even[i] = 1; b[i] = a[i] / 2; } else if(a[i] > 0) b[i] = a[i] / 2; else b[i] = - ((-a[i]) / 2) - 1; sum += b[i]; } int k = -sum; for(int i = 1; i <= n; i++) if(!even[i] && k > 0) { b[i]++; k--; } for(int i = 1; i <= n; i++) printf("%d\n", b[i]); return 0; } |
B. Balanced Tunnel
按进入顺序排序，依次考虑，维护出站顺序的最大值
直观理解就是，比一辆车先进站的，如果在它之后出站，它肯定插队了
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n, ans; struct data{ int x, y; }a[100005]; bool cmp(data a, data b) { return a.x < b.x; } int main() { n = read(); for(int i = 1; i <= n; i++) { int t = read(); a[t].x = i; } for(int i = 1; i <= n; i++) { int t = read(); a[t].y = i; } sort(a + 1, a + n + 1, cmp); int mx = 1; for(int i = 1; i <= n; i++) { if(a[i].y < mx) ans++; mx = max(mx, a[i].y); } printf("%d\n", ans); return 0; } |
C2. Balanced Removals (Harder)
先考虑二维情况，按 x，y 排序，可以把所有点看成一列一列的点，先再每一列上两两配对。这样每一列最多剩下一个，再把相邻列配对即可。
三维情况先按 z 排序，每个平面按二维做法做完以后最多剩一个点，再把相邻列配对即可。
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; struct data{ int x, y, z, id, vis; }a[50005]; bool cmp(data a, data b) { if(a.z != b.z) return a.z < b.z; if(a.x != b.x) return a.x < b.x; return a.y < b.y; } void solve(int x, int y) { for(int i = x; i <= y; i++) if(a[i].x == a[i + 1].x && i + 1 <= y && !a[i].vis) { a[i].vis = a[i + 1].vis = 1; printf("%d %d\n", a[i].id, a[i + 1].id); } int last = 0; for(int i = x; i <= y; i++) if(!a[i].vis) { if(!last)last = i; else { printf("%d %d\n", a[i].id, a[last].id); a[i].vis = a[last].vis = 1; last = 0; } } } int main() { n = read(); for(int i = 1; i <= n; i++) { a[i].x = read(), a[i].y = read(), a[i].z = read(); a[i].id = i; } sort(a + 1, a + n + 1, cmp); for(int i = 1, j = 0; i <= n; i = j) { j = i; while(a[j].z == a[i].z && j <= n)j++; solve(i, j - 1); } int last = 0; for(int i = 1; i <= n; i++) if(!a[i].vis) { if(!last)last = i; else { printf("%d %d\n", a[i].id, a[last].id); a[i].vis = a[last].vis = 1; last = 0; } } return 0; } |
D. Balanced Playlist
先用数据结构（线段树或单调栈），处理出每一个 track_x，预处理往后小于其 1 / 2 的 track 是哪个，记为 b_x
再对于每个 track 为左端点，找一个右端点，满足这个区间的 b 的最小值在这个区间内
这两步我都是用二分线段树实现的
由于题目中是一个环，从一个曲子出发，答案最多是 2n，所以把序列复制三遍维护
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int a[300005], b[300005]; int mn[1200005], mx[1200005], l[1200005], r[1200005]; void build(int k, int x, int y) { int mid = (x + y) >> 1; l[k] = x; r[k] = y; if(x == y) { mn[k] = mx[k] = a[x]; return; } build(k << 1, x, mid); build(k << 1 | 1, mid + 1, y); mn[k] = min(mn[k << 1], mn[k << 1 | 1]); mx[k] = max(mx[k << 1], mx[k << 1 | 1]); } int querymn(int k, int x, int y) { int L = l[k], R = r[k], mid = (L + R) >> 1; if(L == x && y == R) return mn[k]; int ans = inf; if(x <= mid) ans = min(ans, querymn(k << 1, x, min(y, mid))); if(y > mid) ans = min(ans, querymn(k << 1 | 1, max(mid + 1, x), y)); return ans; } int main() { n = read(); for(int i = 1; i <= n; i++) a[i] = a[i + n] = a[i + n + n] = read(); build(1, 1, 3 * n); for(int i = 1; i <= 3 * n; i++) { int l = i, r = 3 * n, ans = inf; while(l <= r) { int mid = (l + r) >> 1; int t = querymn(1, i, mid); if(t <= (a[i] - 1) / 2) { ans = mid; r = mid - 1; } else l = mid + 1; } b[i] = ans; } for(int i = 1; i <= 3 * n; i++) { a[i] = b[i]; } build(1, 1, 3 * n); for(int i = 1; i <= n; i++) { int l = i, r = i + 2 * n, ans = -1; while(l <= r) { int mid = (l + r) >> 1; int t = querymn(1, i, mid); if(t <= mid) { ans = mid; r = mid - 1; } else l = mid + 1; } // cout << ans << endl; if(ans != -1)printf("%d ", ans - i); else printf("-1 "); } return 0; } |
Subscribe
计数器 9328696
OI 课件=>
OI 课件=>