题解 CF1237C2 【Balanced Removals (Harder)】

Nemlit

2019-10-18 10:20:34

Solution

这么妙的题怎么没人发题解啊 首先这是三维的,~~我们可以对其进行降维打击~~ 先考虑一维怎么做? 我们可以对其该维坐标进行排序,按照顺序输出,可能会多余一个 那拓展到二维呢? 我们可以把它转化成一维,分成很多个一维后执行上述操作,把一维中多的一些点存下来,可以保证这些点的一维值两两不等,于是按照另一维坐标输出就行了 那三维呢? 其实和二维是一样的,用类似操作转化成二维即可 ## $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define maxn 100005 struct node { int x, y, z, id; }e[maxn], p[maxn], q[maxn], a[maxn], b[maxn]; //e用来存储三维坐标,p用来存储第三维相等时的二维坐标,q用来存储第二三维都相等的一维坐标 //a用来存储二维操作中剩余点的坐标,b则是用来存储三位操作中剩余点的坐标 int n, c2D, c3D; il bool cmp(node a, node b) { return a.z < b.z; } il bool cmp1(node a, node b) { return a.y < b.y; } il bool cmp2(node a, node b) {return a.x < b.x; } il void solve1D(int x) { sort(q + 1, q + x + 1, cmp2); for(re int i = 1; i < x; i += 2) printf("%d %d\n", q[i].id, q[i + 1].id); if(x & 1) a[++ c2D] = q[x]; } il void solve2D(int x) { sort(p + 1, p + x + 1, cmp1); int now = 1, cnt = 0; c2D = 0; rep(i, 1, x) { now = i; while(now <= x && p[i].y == p[now].y) q[++ cnt] = p[now ++]; i = now - 1, solve1D(cnt), cnt = 0; } for(re int i = 1; i < c2D; i += 2) printf("%d %d\n", a[i].id, a[i + 1].id); if(c2D & 1) b[++ c3D] = a[c2D]; } il void solve3D() { sort(e + 1, e + n + 1, cmp); int now = 1, cnt = 0; rep(i, 1, n) { now = i; while(now <= n && e[i].z == e[now].z) p[++ cnt] = e[now ++]; i = now - 1, solve2D(cnt), cnt = 0; } for(re int i = 1; i < c3D; i += 2) printf("%d %d\n", b[i].id, b[i + 1].id); } int main() { n = read(); rep(i, 1, n) e[i].id = i, e[i].x = read(), e[i].y = read(), e[i].z = read(); solve3D(); return 0; } ```