【题解】CCPC 2024 Jinan Site [J] Temperance

题目链接

CCPC 2024 Jinan Site [J] Temperance

题目大意

题干看上去很复杂，但是我们可以发现，一个植物如果合法，那一定意味着它对应的 \(xy\) \(yz\) \(xz\)平面中，至少有一个平面整个平面合法，如果一个点不合法，那么意味着三个平面都不合法，即使删去也不会影响哪些本来合法的平面，故可以翻译题干如下：

在一个 三维空间内有 \(n\) 个点，第 \(i\) 个点有坐标 \((x_i, y_i, z_i) \in \mathbb{N_+}^3\) ， 记 \(cnt_{x=a}\) 为 \(x=a\) 的点的数量，\(y\) \(z\)同理，对于指定 \(k\) ，计算有多少个点满足 \(max(cnt_{x=x_i}， cnt_{y=y_i}， cnt_{z=z_i}) < k\) ，输出所有 \(k \in {0, 1, 2 ... n-1}\) 的答案。

思路

根据题干翻译即可，开三个 \(unordered_map\) 或类似数据结构统计 \(cnt_{x=x_i}\)， \(cnt_{y=y_i}\)， \(cnt_{z=z_i}\)，显然当 \(max(cnt_{x=x_i}， cnt_{y=y_i}， cnt_{z=z_i}) < k\) 时，对于任意一个 $ k'>=k $ 也成立，故原问题可以视为一个前（后）缀区间修改问题，可以在统计的时候先维护差分，然后 \(O(n)\) 累加输处，注意多组数据刷0即可，时间复杂度 \(O(\Sigma_{i=1}^T n_i)\)。

AC代码

#include <iostream>
#include <unordered_map>
using namespace std;
const int N= 100005;unordered_map<long long, int> X, Y, Z;int x[N], y[N], z[N];
int ans[N];int main() {int T;cin>>T;while(T--) {int n;X.clear();Y.clear();Z.clear();ans[0] = 0;cin>>n;for(int i=1;i<=n;i++) {cin>>x[i]>>y[i]>>z[i];X[x[i]] +=1;Y[y[i]] += 1;Z[z[i]] += 1;ans[i] = 0;}for(int i=1;i<=n;i++) {int maxi = max(X[x[i]], max(Y[y[i]], Z[z[i]]))-1;ans[maxi]++;}for(int i=n-1;i>=0;i--) {ans[i] += ans[i+1];}for(int i=0;i<n;i++) {cout<<n-ans[i]<<" ";}cout<<endl;}
}