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将博客内容html导出为Markdown格式

《Python将博客内容html导出为Markdown格式》Python将博客内容html导出为Markdown格式,通过博客url地址抓取文章,分析并提取出文章标题和内容,将内容构建成html,再转... 目录一、为什么要搞?二、准备如何搞?三、说搞咱就搞!抓取文章提取内容构建html转存markdown

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专