想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全
| 试题编号： | 202309-4 | ||||||||||||||||||||||||||||||
| 试题名称： | 阴阳龙 | ||||||||||||||||||||||||||||||
| 时间限制： | 2.0s | ||||||||||||||||||||||||||||||
| 内存限制： | 1.0GB | ||||||||||||||||||||||||||||||
| 问题描述： |
问题描述西西艾弗岛的下方是一个庞大的遗迹群，神兽“阴阳龙”栖居在这个遗迹群中。 为了得到这件宝物，西西艾弗遗迹探索有限公司（以下简称“公司”）派遣了 p 名员工前往遗迹群，这些员工依次编号为 1 到 p。 遗迹可以视为一个大小为 n×m 的网格，左下角坐标 (1,1)，右上角坐标 (n,m)。初始时，第 i 名员工所在的位置是 (xi,yi)。保证所有员工初始所在的位置两两不同。 作为神兽，阴阳龙有着特殊之处。当其在 p=(u,v) 位置以强度 t∈[1,7] 现身时，会导致遗迹群的环境发生阴和阳的变转，从而导致在遗迹中的人的位置发生变化。 具体来说，阴阳龙首先观察右、右上、上、左上、左、左下、下和右下这八个方向，并在这八个方向找到和阴阳龙“距离”最近的员工（不包括 p）的“距离”。 记 d0 到 d7 依次为向量 (1,0),(1,1),(0,1),(−1,1),(−1,0),(−1,−1),(0,−1),(1,−1)，令： 其中：
若 K=K1⋂K2=∅，则令 k=0；否则令 k=minK>0。 例如，参考下图中的例子，其中左下角为 (1,1)，右上角为 (7,7)，共有 8 名员工，位置如图。 若 p=(4,4)，那么员工 1 刚好在阴阳龙所在位置，不计入；员工 3 不在阴阳龙的 8 个方向上，不计入；员工 2、4、5、6 与阴阳龙“距离”是 2；员工 7、8、9 与阴阳龙“距离”是 3，因此有 K1=2,3。由于与阴阳龙“距离”为 3 就到达了遗迹的边界，所以有 K2=1,2,3。因此 k=2。 若 p=(2,2)，那么员工 2、3、7、8、9都不在阴阳龙的 8 个方向上，不计入；员工 1、6 与阴阳龙的“距离”是 2；员工 4、5 与阴阳龙的“距离”是 4，因此有 K1=2,4。由于与阴阳龙“距离”为 1 时，就在向下、向左、向左下三个方向上到达了遗迹的边界，所以有 K2=1。因此 k=0。
如果 k>0，则将八个方向上的距离为 k 的位置上的员工以 p 为中心逆时针旋转 t 倍的八分之一个圆周的角度。形式化地：
易知在所有员工移动结束后，每个位置上仍至多有一个员工。例如，在上图所示的例子中取 p=(4,4),t=1，则变化后各员工所在位置如下图所示。
在全部员工进入遗迹群后，西西艾弗遗迹探索有限公司总共探测到 q 次阴阳龙的现身。很不幸的是，由于来自东方神秘力量的干扰，这 q 次阴阳龙的现身后，西西艾弗遗迹探索有限公司失去了所有员工的位置信息，因此他希望你帮他计算出所有员工的位置。 输入格式从标准输入读入数据。 第一行四个正整数 n,m,p,q； 接下来 p 行，第 i 行两个正整数 (xi,yi) 表示第 i 名员工的初始位置。 保证所有员工初始所在的位置两两不同。 接下来 q 行，第 i 行三个正整数 ui,vi,ti 表示西西艾弗遗迹探索有限公司探测到的第 i 次阴阳龙现身的位置和强度。 输出格式输出到标准输出中。 为了减少输出量，设 q 次阴阳龙的现身后所有员工的位置为 (x1,y1),…,(xp,yp)，则你只需要输出： 样例输入
样例输出
样例说明阴阳龙现身前，每个员工所在的位置如下：
阴阳龙现身一次后，每个员工所在位置如下：
评测用例规模与约定
对于全部数据： 1≤n,m≤10^9,1≤p,q≤1×10^5,1≤xi,u≤n,1≤yi,v≤m,1≤ti≤7。 保证所有员工初始所在的位置两两不同。 |
真题来源：阴阳龙
感兴趣的同学可以如此编码进去进行练习提交
c++满分题解：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, p, q;
cin >> n >> m >> p >> q;
vector<array<int, 2>> pos(p);
unordered_map<int, set<array<int, 2>>> row, col, ld, rd;
auto insert = [&](int id){
int x = pos[id][0], y = pos[id][1];
row[x].insert({y, id});
col[y].insert({x, id});
ld[x + y].insert({y, id});
rd[x - y].insert({y, id});
};
auto remove = [&](int id){
int x = pos[id][0], y = pos[id][1];
row[x].erase({y, id});
col[y].erase({x, id});
ld[x + y].erase({y, id});
rd[x - y].erase({y, id});
};
for(int i = 0; i < p; ++ i){
cin >> pos[i][0] >> pos[i][1];
insert(i);
}
for(int i = 0; i < q; ++ i){
int u, v, t;
cin >> u >> v >> t;
vector<array<int, 3>> candidate;
auto search = [&](const set<array<int, 2>>& people, int d, int dirr, int dirl){
auto pos = people.lower_bound(array<int, 2>{d, p});
if (pos != people.end()){
candidate.push_back({(*pos)[0] - d, (*pos)[1], dirr});
}
if (pos != people.begin()){
pos = prev(pos);
if ((*pos)[0] == d && pos != people.begin())
pos = prev(pos);
if ((*pos)[0] != d){
candidate.push_back({d - (*pos)[0], (*pos)[1], dirl});
}
}
};
search(row[u], v, 2, 6);
search(col[v], u, 0, 4);
search(ld[u + v], v, 3, 7);
search(rd[u - v], v, 1, 5);
if (candidate.empty())
continue;
sort(candidate.begin(), candidate.end(), [&](const array<int, 3>& a, const array<int, 3>& b){
return a[0] < b[0];
});
int mindis = min({u - 1, n - u, v - 1, m - v});
if (candidate[0][0] > mindis)
continue;
mindis = candidate[0][0];
for(int i = 0; i < candidate.size(); ++ i){
if (candidate[i][0] != mindis)
break;
int dis = candidate[i][0];
int id = candidate[i][1];
remove(id);
int dir = (candidate[i][2] + t) % 8;
pos[id][0] = u + dis * dx[dir];
pos[id][1] = v + dis * dy[dir];
insert(id);
}
}
LL ans = 0;
for(int i = 0; i < p; ++ i){
ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);
}
cout << ans << '\n';
return 0;
}运行结果：
文章出处登录后可见！
