【CSP】阴阳龙_(拆解问题,构建方案,思考发散)

2024-08-27 16:36
文章标签 问题 构建 思考 csp 方案 阴阳 拆解 发散

本文主要是介绍【CSP】阴阳龙_(拆解问题,构建方案,思考发散)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 问题背景与任务概述

背景：在题目中，我们面临一个庞大的遗迹群，神兽“阴阳龙”在其中移动。当阴阳龙现身时，遗迹中的员工可能会因阴阳龙的力量被移动到新的位置。任务的目标是模拟阴阳龙多次现身后，所有员工最终的位置，并通过这些位置计算出一个最终的异或值。

任务：核心任务是根据阴阳龙的现身位置及方向，计算出员工的新位置，并最终计算异或值。这涉及大量的二维坐标变换及判断操作。

2. 总任务划分与子问题分析

整个问题可以分为以下几个子问题：

  1. 数据输入与初始化。
  2. 员工坐标的插入和删除操作。
  3. 寻找最短距离的员工。
  4. 更新员工位置。
  5. 计算异或结果。

2.1 数据输入与初始化

处理的问题：需要从标准输入中读取遗迹的大小、员工的初始位置、以及阴阳龙的现身次数和每次的具体参数。

代码逻辑：采用自定义的快速输入函数read()以提高读取效率。该方法使用缓冲区，能够一次性读取大量数据，从而减少I/O操作的次数。

实现思路：通过快速输入读取数据，能够显著提升数据读取的速度，尤其是在竞赛环境下。

选择的理由：通过 read 一次性读取大块数据，并在缓冲区中处理，能显著减少 I/O 操作的次数，提高输入效率。适合处理大规模数据的输入任务。 

推广性：快速输入法适用于任何需要处理大规模数据输入的场景，特别是在I/O操作成为瓶颈时。

char buf[1 << 24], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2) ? EOF : *p1++)inline int read() {int x = 0;char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x;
}

2.2 员工坐标的插入和删除操作

处理的问题：员工的坐标存储与删除，便于在阴阳龙现身时快速查找需要移动的员工。

代码逻辑：采用unordered_map和set的数据结构，利用哈希表实现员工坐标的快速查找与更新。set结构用于保证同一行、列或对角线上的员工有序（基于位置排序），便于范围查询。

实现思路：unordered_map结合set提供了高效的查找与插入操作，同时保持员工在各个方向上的顺序。由于哈希表的平均时间复杂度为O(1)，这一设计能显著提升性能。

选择的理由：unordered_map 提供了平均 O(1) 的查找和插入效率，set 保证了元素的有序性，便于进行区间查询和有序访问。两者的结合适合处理频繁插入、删除及有序访问的场景。

推广性：这种组合结构适用于任何需要频繁插入、删除以及有序访问的场景，如区间管理、事件调度等。

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

2.3 寻找最短距离的员工

处理的问题：阴阳龙现身后，需要确定在各个方向上距离阴阳龙最近的员工，以决定其是否需要被移动。

代码逻辑：通过搜索函数search实现员工的查找，利用lower_bound快速定位员工，并根据距离判断是否需要更新位置。

实现思路：lower_bound能够在有序容器中以O(log n)的复杂度找到第一个不小于目标值的元素，这使得查找最近员工的操作十分高效。结合unordered_map和set的组合，能够在复杂度上取得良好的平衡。

选择的理由：lower_bound 提供了 O(log n) 的复杂度，结合 unordered_map 和 set，实现了高效的查找与记录操作。该方法推广性强，适用于其他动态维护最小值或最大值的场景。

推广性：这一思想可以推广到任何需要动态维护最小值或最大值的场景，如优先队列问题、区间最值查询等。

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

2.4 更新员工位置

处理的问题：在找到最近的员工后，需要根据阴阳龙的力量将其位置更新。

代码逻辑：通过计算最小距离mindis和方向向量dx, dy来确定新位置，避免超出地图边界。

实现思路：根据方向向量和最小距离，使用模运算实现旋转操作，确保位置的更新符合题目要求。

选择的理由：利用方向向量和模运算，简化了坐标更新的逻辑。方向向量是一种通用方法，可以推广到其他方向变换问题。

推广性：这一思想可以应用于任何需要基于方向和距离进行位置更新或变换的场景，如旋转操作、图形变换等。

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

2.5 计算异或结果

处理的问题：题目要求计算所有员工最终位置的异或值，以此作为最后的答案。

代码逻辑：遍历所有员工的位置，通过异或操作计算最终结果。

实现思路：异或操作具有交换律和结合律，能够有效处理多个数值的累积问题，并且异或操作的时间复杂度为O(1)，非常高效。

选择的理由：异或操作具有良好的去重与组合性质，在许多竞赛题目中都能派上用场。通过这种方式，可以快速合并多个值的特性。

推广性：异或操作适用于任何需要多值累积、去重或组合的场景，如密码学应用、哈希函数设计等。

LL ans = 0;
for (int i = 0; i < p; ++i) {ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);
}

3.最终方案

3.1代码和注释

#include <iostream>
#include <vector>
#include <unordered_map>
#include <array>
#include <set>
#include <algorithm>
#include <cstring>using namespace std;
typedef long long LL;const int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };  // 定义八个方向的x坐标变化量
const int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };  // 定义八个方向的y坐标变化量// 快速输入的全局变量与方法定义
char buf[1 << 24], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 24, stdin), p1 == p2) ? EOF : *p1++)inline int read() {int x = 0;char ch = getchar();while (ch < '0' || ch > '9') ch = getchar();while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x;
}int main() {ios::sync_with_stdio(false);  // 关闭同步，加速IOcin.tie(0);  // 解除cin与cout的绑定cout.tie(0);  // 解除cin与cout的绑定int n = read(), m = read(), p = read(), q = read();  // 读取网格大小、员工数量和阴阳龙出现次数vector<array<int, 2>> pos(p);  // 存储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) {pos[i][0] = read();pos[i][1] = read();insert(i);}// 处理每次阴阳龙现身的影响for (int i = 0; i < q; ++i) {int u = read(), v = read(), t = read();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, INT_MAX });  // 查找最近的员工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()) {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) {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];  // 更新员工x坐标pos[id][1] = v + dis * dy[dir];  // 更新员工y坐标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;
}

3.2代码结构说明

  1. 快速输入处理：通过自定义的read()函数处理输入，使用fread读取大块数据，减少I/O操作时间，从而加快输入速度。

  2. 数据结构选择：

    • unordered_map<int, set<array<int, 2>>>：分别存储员工在行、列、主对角线、副对角线上的位置，使得查找与更新操作效率更高。
    • vector<array<int, 2>> pos：用于存储所有员工的初始坐标位置。

  3. 员工位置的更新：阴阳龙现身时，根据阴阳龙位置与员工的最小距离及旋转方向，动态更新员工的位置。

  4. 最终结果计算：对所有员工的最终位置进行异或操作，得到结果。

3.3结论与建议

  • 优点：该方案利用了快速输入方法与高效的数据结构，使得程序在处理大规模数据时具有较高的执行效率，适合竞赛环境。
  • 改进建议：在处理更加复杂的场景时，可以考虑进一步优化数据结构的内存占用，或者通过多线程并行处理提高程序的执行速度。

如果能帮到你,给作者点个赞吧~

后续还有更多精彩内容和详细思考过程分享

                                                     -- 认真写作 提升思考 --

这篇关于【CSP】阴阳龙_(拆解问题,构建方案,思考发散)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1112207。

相关文章

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

无人叉车3d激光slam多房间建图定位异常处理方案-墙体画线地图切分方案

墙体画线地图切分方案 针对问题：墙体两侧特征混淆误匹配，导致建图和定位偏差，表现为过门跳变、外月台走歪等 ·解决思路：预期的根治方案IGICP需要较长时间完成上线，先使用切分地图的工程化方案，即墙体两侧切分为不同地图，在某一侧只使用该侧地图进行定位 方案思路 切分原理：切分地图基于关键帧位置，而非点云。 理论基础：光照是直线的，一帧点云必定只能照射到墙的一侧，无法同时照到两侧实践考虑：关
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

高效+灵活，万博智云全球发布AWS无代理跨云容灾方案！

摘要 近日，万博智云推出了基于AWS的无代理跨云容灾解决方案，并与拉丁美洲，中东，亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础，将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合，为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日，万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频，介绍了
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
Retrieval-based-Voice-Conversion-WebUI模型构建指南

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI（简称 RVC）模型是一个基于 VITS（Variational Inference with adversarial learning for end-to-end Text-to-Speech）的简单易用的语音转换框架。 具有以下特点 简单易用：RVC 模型通过简单易用的网页界面，使得用户无需深入了
阅读更多...
Android平台播放RTSP流的几种方案探究（VLC VS ExoPlayer VS SmartPlayer）

Android平台播放RTSP流的几种方案探究（VLC VS ExoPlayer VS SmartPlayer）

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候，不知道如何选的好，本文针对常用的方案，做个大概的说明： 1. 使用VLC for Android VLC Media Player（VLC多媒体播放器），最初命名为VideoLAN客户端，是VideoLAN品牌产品，是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式，并支持DVD影音光盘，VCD影
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...
缓存雪崩问题

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库，瞬间耗尽数据库资源，导致数据库无法使用。 解决方案： 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内，大量缓存数据同时失效，导致所有请求直接涌向数据库，瞬间增加数据库的负载压力，可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2