CCF-CSP真题《202309-4 阴阳龙》思路+python,c++满分题解

2023-11-05 23:04

本文主要是介绍CCF-CSP真题《202309-4 阴阳龙》思路+python,c++满分题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  想查看其他题的真题及题解的同学可以前往查看: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;否则,如果在某一时刻,
在某一方向上刚好到达遗迹的边界,但是在此之前任何方向上都没有遇到员工,则令 k=0。形式化描述上述确定 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)=p+kdi}
K2={k∈N+∣∀i∈[0,7],(p+kdi)∈[1,n]×[1,m]}

其中:

  • (xi,yi) 为第 i 名员工在此次阴阳龙现身前的位置(这个位置可能和其初始位置不同,但为了方便起见,我们使用同一个记号);
  • K1 为所有员工到阴阳龙距离组成的集合;
  • K2 为从阴阳龙出发直至在某一方向抵达边界所包括全部的距离组成的集合。

若 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 倍的八分之一个圆周的角度。形式化地:

  • 若 k=0,则什么也不会发生。

  • 否则,∀i∈[0,7],若 p+kdi 位置上有员工,那么其该员工会被移动到 p+kd(i+t)mod8。

易知在所有员工移动结束后,每个位置上仍至多有一个员工。例如,在上图所示的例子中取 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),则你只需要输出:
⨁i=1pi×xi+yi
其中 ⨁ 表示按位异或,即 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≤子任务分值
11000100010510540
21091091000100015
310510510510525
410910910510520

对于全部数据:

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;
}

运行结果:

这篇关于CCF-CSP真题《202309-4 阴阳龙》思路+python,c++满分题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/353026

相关文章

利用python实现对excel文件进行加密

《利用python实现对excel文件进行加密》由于文件内容的私密性,需要对Excel文件进行加密,保护文件以免给第三方看到,本文将以Python语言为例,和大家讲讲如何对Excel文件进行加密,感兴... 目录前言方法一:使用pywin32库(仅限Windows)方法二:使用msoffcrypto-too

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

Python装饰器之类装饰器详解

《Python装饰器之类装饰器详解》本文将详细介绍Python中类装饰器的概念、使用方法以及应用场景,并通过一个综合详细的例子展示如何使用类装饰器,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. 引言2. 装饰器的基本概念2.1. 函数装饰器复习2.2 类装饰器的定义和使用3. 类装饰

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模