阴阳龙
计算机软件能力认证考试系统
心力交瘁的一集。但是也是收获满满吧。从这一题中，可以学到：点相当于线的位置确定、1ll的使用、使用set找最近的点、特殊线满足的关系、点的旋转。看起来有很多，这里我们慢慢讲解。
按照从易到难来讲，首先是1ll的使用：1LL是为了在计算时，把int类型的变量转化为long long，然后再赋值给long long类型的变量。主要用于运算过程中的时候。
特殊线满足的关系：本题中出现了8个方向，其实就是4条线。过龙点的水平、竖直、主副对角线。横线上面的点都满足y相等；竖线上面的点都满足x相等；主对角线上面的点都满足x+y相等；副对角线上面的点都满足x-y相等。所以，我们通过对比对应线的关键值，就能区分他是不是在这条线上。
点的旋转：只能说，幸好题目给了公式，但同样也给了坑。我们需要将那八个点剔除不在位置上的（也就是之前发现k的含义其实是最近的距离），将大于k的那些点给pass掉。还需要使用erase将该点从四条线的map中抹除，最后将根据公式写出新的坐标，同时插入新的线条信息。
点相当于线的位置确定：题目一开始就给我们设置了一个难题——判断点是否在龙的八方上。我们如果一个个去判断点和龙的位置关系的话，就一定会超时。最好的方式，就是一边存的时候，就一边将过该点的四条线的信息存进去。满足相同键值的点一定在同一直线上，比如水平的，点a(2,3)，b(8,3)，他们水平线的键值都是3，所以他们的水平线是同一条。这也就是我们insert函数做的操作。我们构建 map<int, set<pii>> heng, shu, zhu, fu;表示4条线。pii表示pair<int,int>，存放的是用于判断距离的一个坐标。map中的int存放关键值，用于区分不同的线条。
使用set找最近的点：这是本题的重中之重。本题还需要理解的一点就是k的实际含义。本题用了大量的篇幅去介绍k是怎么来的，就是为了让我们忽视，k其实本质上就是最近的那个点到龙的距离。所以，如何高效地求这个点，成为了重点。理解了这个之后，我们就不需要去求K1、K2的集合，大大省略了计算过程和代码。我们首先否定全部遍历一遍点的想法，而将视线聚焦于这四条线上。我们最后保留的是这四条线上的点，所以我们可以先把这八条线上的最近的点提取出来，然后再从这8个点中找最近中的最近。使用set自带的upper_bound和lower_bound，快速定位到第一个在线上大于龙坐标的点，或者龙的坐标。注意lower_bound是定位到龙的坐标，所以我们还需要--it来找到位置小于龙的点。
AC：
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N=1e5+3; //最多的人数
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define ll long longstruct Position
{int x,y;
};int n, m, t, k, p, q;
int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
map<int, set<pii>> heng, shu, zhu, fu; //四条线
Position pt[N],cur; //存放人的坐标位置 和 龙的位置 void insert(int id) //我们将这个点存了4次
{int x=pt[id].x,y=pt[id].y; /*相对于龙而言的八个方向，其实就是4条线：横竖、主对角线、副对角线横线上面的点都满足y相等 竖线上面的点都满足x相等 主对角线上面的点都满足x+y相等 副对角线上面的点都满足x-y相等 所以，我们通过对比对应线的关键值，就能区分他是不是在这条线上因为龙所在的这4条线是唯一的，各线的关键值是唯一的，如果有的点不满足这个关键值，说明就不在这线上 */ heng[y].insert({x,id});shu[x].insert({y,id});zhu[x+y].insert({x,id});fu[x-y].insert({x,id});
} void erase(int id) //存4次，就要删4次
{int x=pt[id].x,y=pt[id].y; heng[y].erase({x,id});shu[x].erase({y,id});zhu[x+y].erase({x,id});fu[x-y].erase({x,id});
}int dis(int id) //用于返回水平或竖直上于龙的最大距离
{ //其实如果在对角线上，水平和竖直上相对龙的距离是一样的//这里之所以取最大距离，是为了在水平竖直上，非关键距离=0，影响判断 return max(abs(cur.x-pt[id].x),abs(cur.y-pt[id].y));
} int main()
{cin>>n>>m>>p>>q;for(int i=1;i<=p;i++){cin>>pt[i].x>>pt[i].y; insert(i); //将对应位置的关键值进行记录 }while(q--){cin>>cur.x>>cur.y>>t; //当前龙的位置和强度//先要计算k才能知道旋转参数 //计算k，就是要计算K1、K2 //其实根本不需要真的要算K1K2这俩集合，因为最后得到的k本质上就是最近的距离！//我悟了！怪不得答案里要先计算出八个方向上最近的id！因为如果k值存在，那么就是其P+kdi得到的位置//其实就是最近的那几个点！ //所以，我们只需要提前将8个方向上的点给弄出来，然后再进行比较和旋转，就方便很多。 //还是有很多细节的：lower的时候，需要比较的第二个值为0，还有后面的it要--//lower和upper都会考虑到第二个值，所以在比较的时候，我们要将第二个值统一换成 都大于 都小于 的值 vector<int>point(8,0); //存8个最近的点的id //注意，这个顺序不能换！按照题目中要求的顺序来 auto it = heng[cur.y].upper_bound({cur.x, inf});point[0] = it != heng[cur.y].end() ? it->second : 0;it = fu[cur.x - cur.y].upper_bound({cur.x, inf});point[1] = it != fu[cur.x - cur.y].end() ? it->second : 0;it = shu[cur.x].upper_bound({cur.y, inf});point[2] = it != shu[cur.x].end() ? it->second : 0;it = zhu[cur.x + cur.y].lower_bound({cur.x, 0});point[3] = it != zhu[cur.x + cur.y].begin() ? (--it)->second : 0;it = heng[cur.y].lower_bound({cur.x, 0});point[4] = it != heng[cur.y].begin() ? (--it)->second : 0;it = fu[cur.x - cur.y].lower_bound({cur.x, 0});point[5] = it != fu[cur.x - cur.y].begin() ? (--it)->second : 0;it = shu[cur.x].lower_bound({cur.y, 0});point[6] = it != shu[cur.x].begin() ? (--it)->second : 0;it = zhu[cur.x + cur.y].upper_bound({cur.x, inf});point[7] = it != zhu[cur.x + cur.y].end() ? it->second : 0;//确定k值//k值，说白了，就是如果员工和龙的最短距离 和 龙到边界的最短距离 比较//如果前者小，那k=员工和龙的最短距离，否则，k=0 //龙到边界的最短距离k=min(min(cur.x-1,cur.y-1),min(n-cur.x,m-cur.y));//通过遍历这八个最近的点找最近距离for(auto it:point)if(it!=0) //仅处理存在的点k=min(k,dis(it));//下面开始旋转。旋转分为3部分，1.选择 2.删除原点 3.插入新点 for(auto &it:point) //选择，将那些距离不达标的给从8大点中剔除 if(it!=0 && dis(it)>k) //如果距离龙太远，就要把这个点剔除it=0; //不可能出现dis<k的情况，因为k就是最近中的最近//删除for(auto it:point)if(it!=0)erase(it); //插入for(int i=0;i<8;i++) //因为旋转要用到i，就不用auto了 {if(point[i]==0) continue;pt[point[i]].x=cur.x + k*dx[(i+t)%8];pt[point[i]].y=cur.y + k*dy[(i+t)%8]; //修改了坐标位置insert(point[i]); //插入线的位置 }} ll ans=0;for(int i=1;i<=p;i++) //遍历所有点，进行题目中的加工输出ans^=1ll*i*pt[i].x+pt[i].y;cout<<ans<<endl; return 0;} 参考代码：CCF-CSP认证考试 202309-4 阴阳龙 100分题解_csp 阴阳龙-CSDN博客
