温州网站快速排名,wordpress可以添加字段吗,郑州做茶叶的网站,苍南最新发布请配合想查看其他题的真题及题解的同学可以前往查看#xff1a;CCF-CSP真题附题解大全 试题编号#xff1a;202309-4试题名称#xff1a;阴阳龙时间限制#xff1a;2.0s内存限制#xff1a;1.0GB问题描述#xff1a; 问题描述 西西艾弗岛的下方是一个庞大的遗迹群#xff0c;神… 想查看其他题的真题及题解的同学可以前往查看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的“距离”。 其中垂直和水平方向的“距离”是指员工和阴阳龙连线的长度斜线方向的“距离”是指员工和阴阳龙连线在水平方向上投影的长度。设想从阴阳龙的位置同时出发 分别向这 8 个方向前进每一单位时间运动 1 个“距离”。如果在某一时刻在某一方向刚好遇到一位员工则此时前进的距离即被记为 k否则如果在某一时刻 在某一方向上刚好到达遗迹的边界但是在此之前任何方向上都没有遇到员工则令 k0。形式化描述上述确定 k 的方法是 记 d0 到 d7 依次为向量 (1,0),(1,1),(0,1),(−1,1),(−1,0),(−1,−1),(0,−1),(1,−1)令 K1{k∈N∣∃i∈[0,7],j∈[1,p],s.t.(xj,yj)pkdi} K2{k∈N∣∀i∈[0,7],(pkdi)∈[1,n]×[1,m]} 其中 (xi,yi) 为第 i 名员工在此次阴阳龙现身前的位置这个位置可能和其初始位置不同但为了方便起见我们使用同一个记号K1 为所有员工到阴阳龙距离组成的集合K2 为从阴阳龙出发直至在某一方向抵达边界所包括全部的距离组成的集合。若 KK1⋂K2∅则令 k0否则令 kminK0。 例如参考下图中的例子其中左下角为 (1,1)右上角为 (7,7)共有 8 名员工位置如图。 若 p(4,4)那么员工 1 刚好在阴阳龙所在位置不计入员工 3 不在阴阳龙的 8 个方向上不计入员工 2、4、5、6 与阴阳龙“距离”是 2员工 7、8、9 与阴阳龙“距离”是 3因此有 K12,3。由于与阴阳龙“距离”为 3 就到达了遗迹的边界所以有 K21,2,3。因此 k2。 若 p(2,2)那么员工 2、3、7、8、9都不在阴阳龙的 8 个方向上不计入员工 1、6 与阴阳龙的“距离”是 2员工 4、5 与阴阳龙的“距离”是 4因此有 K12,4。由于与阴阳龙“距离”为 1 时就在向下、向左、向左下三个方向上到达了遗迹的边界所以有 K21。因此 k0。 变化前各员工位置 如果 k0则将八个方向上的距离为 k 的位置上的员工以 p 为中心逆时针旋转 t 倍的八分之一个圆周的角度。形式化地 若 k0则什么也不会发生。 否则∀i∈[0,7]若 pkdi 位置上有员工那么其该员工会被移动到 pkd(it)mod8。 易知在所有员工移动结束后每个位置上仍至多有一个员工。例如在上图所示的例子中取 p(4,4),t1则变化后各员工所在位置如下图所示。 变化后各员工位置 在全部员工进入遗迹群后西西艾弗遗迹探索有限公司总共探测到 q 次阴阳龙的现身。很不幸的是由于来自东方神秘力量的干扰这 q 次阴阳龙的现身后西西艾弗遗迹探索有限公司失去了所有员工的位置信息因此他希望你帮他计算出所有员工的位置。 输入格式 从标准输入读入数据。 第一行四个正整数 n,m,p,q 接下来 p 行第 i 行两个正整数 (xi,yi) 表示第 i 名员工的初始位置。 保证所有员工初始所在的位置两两不同。 接下来 q 行第 i 行三个正整数 ui,vi,ti 表示西西艾弗遗迹探索有限公司探测到的第 i 次阴阳龙现身的位置和强度。 输出格式 输出到标准输出中。 为了减少输出量设 q 次阴阳龙的现身后所有员工的位置为 (x1,y1),…,(xp,yp)则你只需要输出 ⨁i1pi×xiyi 其中 ⨁ 表示按位异或即 C/C 中的 ^ 运算符。 样例输入 3 3 9 1 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 2 2 1 样例输出 20 样例说明 阴阳龙现身前每个员工所在的位置如下 3 6 9 2 5 8 1 4 7 阴阳龙现身一次后每个员工所在位置如下 6 9 8 3 5 7 2 1 4 评测用例规模与约定 子任务编号n≤m≤p≤q≤子任务分值1100010001051054021091091000100015310510510510525410910910510520对于全部数据 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;vectorarrayint, 2 pos(p);unordered_mapint, setarrayint, 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;vectorarrayint, 3 candidate;auto search [](const setarrayint, 2 people, int d, int dirr, int dirl){auto pos people.lower_bound(arrayint, 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 arrayint, 3 a, const arrayint, 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;
}
运行结果
