题解：P11372 「CZOI-R2」加训
题目大意
机房被看作维正方体，有
解题思路
- 方向与人数上限：因
k 维空间，教练最多有2k 个观察方向，理论最多发现2k 个摸鱼。 - 预处理最近障碍：将教练当作障碍，遍历所有障碍与教练比较。对满足
k-1 维坐标差异的障碍，依其与教练坐标大小关系，更新对应方向最近障碍信息。 - 处理学生：对每个学生，先查是否满足
k-1 维坐标差异条件，不符则跳过。符合时，对比学生与对应方向最近障碍到教练距离，更近则更新学生为新最近对象，标记并统计。 - 统计结果：统计各方向最近为学生的方向数，即教练发现摸鱼数量。
注释非常详细！
#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1e3 + 5;
// 机房空间（看作k维正方体）的边长
int n;
// 机房空间的维数
int dt;
// OIer（正在摸鱼的人员）的数量
int ot;
// 原本障碍的数量
int oc;
// 教练的数量
int ct;
// os数组用于存储OIer的坐标信息，第一维表示第几个OIer，第二维表示坐标维度
int os[MAX_SIZE][5];
// all数组用于存储障碍（包含后面当作障碍处理的教练）的坐标信息，第一维表示第几个障碍（教练也算在内了），第二维表示坐标维度
int all[2 * MAX_SIZE][5];
// cs数组用于单独存储教练的坐标信息，方便后续处理时区分使用，第一维表示第几个教练，第二维表示坐标维度
int cs[MAX_SIZE][5];
// nr数组用于存储每个方向上到教练最近的障碍相关信息，nr[0][i]表示在某个维度上坐标小于教练坐标方向（可理解为“左”方向）的最近障碍坐标
// nr[1][i]表示在某个维度上坐标大于教练坐标方向（可理解为“右”方向）的最近障碍坐标
int nr[2][5];
// vis数组用于标记每个方向上到教练最近的是不是学生，vis[0][i]对应“左”方向，vis[1][i]对应“右”方向
bool vis[2][5];
// solve函数用于处理单个教练能发现的摸鱼OIer的数量，参数now表示当前处理的是第几个教练
void solve(int now) {
int fn = 0;
// 初始化nr数组，将nr[0]各元素置为0，通常用于记录较小值（类似左方向）时的初始比较基础
memset(nr[0], 0, sizeof(nr[0]));
// 初始化nr[1]各元素为一个较大值（0x7f在本题情境下可当作一个相对很大的值用于后续比较更新）
// 用于记录较大值（类似右方向）时的初始比较基础，方便后续找到更小的更近的值来更新
memset(nr[1], 0x7f, sizeof(nr[1]));
// 初始化vis数组，将所有标记都置为false，表示初始时各方向上最近的都不是学生
memset(vis, 0, sizeof(vis));
// 预处理障碍（这里的障碍包含了当作障碍处理的教练），遍历所有的障碍
for (int i = 1; i <= oc; i++) {
int solve = 0; // solve用于记录当前障碍与教练有几个维度的坐标是相同的，初始化为0
int dif = -1; // dif用于记录第一个不同的维度编号，初始化为 -1，表示未找到不同维度
// 遍历每个维度，判断当前障碍与当前教练在该维度上的坐标是否相同
for (int j = 1; j <= dt; j++) {
if (all[i][j]!= cs[now][j]) {
dif = j; // 如果坐标不同，记录下这个不同的维度编号
} else {
solve++; // 如果坐标相同，相同维度数量加1
}
}
// 如果相同维度数量不等于dt - 1，说明不满足发现摸鱼条件里关于坐标维度差异的要求，直接跳过该障碍
if (solve!= dt - 1) continue;
// 如果在某个维度上，当前障碍的坐标小于教练在该维度的坐标，更新对应“左”方向上的最近障碍坐标
if (all[i][dif] < cs[now][dif])
nr[0][dif] = max(nr[0][dif],
all[i][dif]);
else
// 如果在某个维度上，当前障碍的坐标大于教练在该维度的坐标，更新对应“右”方向上的最近障碍坐标
nr[1][dif] = min(nr[1][dif],
all[i][dif]);
}
// 对每个学生进行处理，遍历所有的学生
for (int i = 1; i <= ot; i++) {
int solve = 0;
int dif = -1;
// 同样遍历每个维度，判断当前学生与当前教练在各维度上的坐标异同情况
for (int j = 1; j <= dt; j++) {
if (os[i][j]!= cs[now][j]) {
dif = j;
} else {
solve++;
}
}
// 如果不满足有且仅有dt - 1维坐标不同的条件，跳过该学生
if (solve!= dt - 1) continue;
// 如果学生在某个维度上的坐标小于教练坐标，且大于该维度“左”方向上已记录的最近障碍坐标
if (os[i][dif] < cs[now][dif] && os[i][dif] > nr[0][dif]) {
// 更新“左”方向上的最近坐标为该学生的坐标
nr[0][dif] = os[i][dif];
// 如果该方向上之前最近的不是学生，说明发现了新的可被发现摸鱼的学生，数量加1，并标记该方向最近的是学生
if (!vis[0][dif]) {
fn++;
vis[0][dif] = 1;
}
}
// 如果学生在某个维度上的坐标大于教练坐标，且小于该维度“右”方向上已记录的最近障碍坐标
if (os[i][dif] > cs[now][dif] &&
os[i][dif] < nr[1][dif]) {
// 更新“右”方向上的最近坐标为该学生的坐标
nr[1][dif] = os[i][dif];
// 如果该方向上之前最近的不是学生，说明发现了新的可被发现摸鱼的学生，数量加1，并标记该方向最近的是学生
if (!vis[1][dif]) {
fn++;
vis[1][dif] = 1;
}
}
}
// 输出当前教练能发现的摸鱼OIer的数量
cout << fn <<' ';
}
int main() {
// 输入机房空间的边长、维数、OIer的数量、原本障碍的数量以及教练的数量
cin >> n >> dt >> ot >> oc >> ct;
// 循环读取每个OIer的坐标信息，外层循环控制第几个OIer，内层循环控制坐标维度
for (int i = 1; i <= ot; i++)
for (int j = 1; j <= dt; j++)
cin >> os[i][j];
// 循环读取每个障碍的坐标信息，外层循环控制第几个障碍，内层循环控制坐标维度
for (int i = 1; i <= oc; i++)
for (int j = 1; j <= dt; j++)
cin >> all[i][j];
// 循环读取每个教练的坐标信息，外层循环控制第几个教练，内层循环控制坐标维度
// 同时将教练的坐标信息添加到障碍坐标数组all中，将教练当作障碍处理，方便后续统一处理
for (int i = 1; i <= ct; i++)
for (int j = 1; j <= dt; j++) {
cin >> cs[i][j];
all[oc + i][j] = cs[i][j];
}
// 更新障碍的总数，将教练数量加到原本的障碍数量上，因为教练已经当作障碍看待了
oc += ct;
// 对每个教练调用solve函数，统计并输出每个教练能发现的摸鱼OIer的数量
for (int i = 1; i <= ct; i++)
solve(i);
return 0;
}