P9840 [ICPC2021 Nanjing R] Oops, It‘s Yesterday Twice More题解
[ICPC2021 Nanjing R] Oops, It’s Yesterday Twice More
传送门
题面翻译
有一张 n × n n\times n n×n 的网格图,每个格子上都有一只袋鼠。对于一只在 ( i , j ) (i,j) (i,j) 的袋鼠,有下面四个按钮:
- 按钮
U
:如果 i > 1 i>1 i>1,移动到 ( i − 1 , j ) (i-1,j) (i−1,j),否则,原地不动; - 按钮
D
:如果 i < n i<n i<n,移动到 ( i + 1 , j ) (i+1,j) (i+1,j),否则,原地不动; - 按钮
L
:如果 j > 1 j>1 j>1,移动到 ( i , j − 1 ) (i,j-1) (i,j−1),否则,原地不动; - 按钮
R
:如果 j < n j<n j<n,移动到 ( i , j + 1 ) (i,j+1) (i,j+1),否则,原地不动。
每次按下按钮,都会对所有的袋鼠生效。请输出一种使得所有袋鼠最终都在 ( a , b ) (a,b) (a,b) 的操作序列,并且序列的长度小于等于 3 × ( n − 1 ) 3\times(n-1) 3×(n−1)。
题目描述
After the great success in 2018, 2019, and 2020, Nanjing University of Aeronautics and Astronautics (NUAA) will host the International Collegiate Programming Contest \textit{International Collegiate Programming Contest} International Collegiate Programming Contest (ICPC) Nanjing regional for the fourth time.
Team Power of Two \textbf{\textit{Power of Two}} Power of Two and team Three Hold Two \textbf{\textit{Three Hold Two}} Three Hold Two won the champion for Tsinghua University in 2018 and 2019. In 2020, team Inverted Cross \textbf{\textit{Inverted Cross}} Inverted Cross from Peking University won the champion. In 2021, there are around 700 700 700 teams including the defending champion \textbf{the defending champion} the defending champion participating in the contest. We are so excited to see who will win this year!
Although we can’t gather in Nanjing this time due to the pandemic, we should still be grateful for the hard work done by all staff and volunteers for this contest. Thank you all for your great contribution to this contest!
In the 2018 contest, problem K, Kangaroo Puzzle \textbf{\textit{Kangaroo Puzzle}} Kangaroo Puzzle, requires the contestants to construct an operation sequence for the game:
The puzzle is a grid with n n n rows and m m m columns ( 1 ≤ n , m ≤ 20 1 \le n, m \le 20 1≤n,m≤20) and there are some (at least 2 2 2) kangaroos standing in the puzzle. The player’s goal is to control them to get together. There are some walls in some cells and the kangaroos cannot enter the cells with walls. The other cells are empty. The kangaroos can move from an empty cell to an adjacent empty cell in four directions: up, down, left, and right.
There is exactly one kangaroo in every empty cell in the beginning and the player can control the kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos will move simultaneously according to the button you press.
The contestant needs to construct an operating sequence of at most 5 × 1 0 4 5 \times 10^4 5×104 steps consisting of U, D, L, R only to achieve the goal.
In the 2020 contest, problem A, Ah, It’s Yesterday Once More \textbf{\textit{Ah, It's Yesterday Once More}} Ah, It’s Yesterday Once More, requires the contestants to construct an input map to hack the following code of the problem described before:
#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{srand(time(NULL));for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);return 0;
}
Now in the 2021 contest, Paimon prepares another version of the problem for you. You are given a grid with n n n rows and n n n columns ( 2 ≤ n ≤ 500 2 \leq n \leq 500 2≤n≤500). All cells are empty and there is one kangaroo standing in each cell.
Similarly, you can control the kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos will move simultaneously according to the button you press. Specifically, for any kangaroo located in the cell on the i i i-th row and the j j j-th column, indicated by ( i , j ) (i,j) (i,j):
- Button U: it will move to ( i − 1 , j ) (i-1,j) (i−1,j) if i > 1 i>1 i>1. Otherwise, it will stay in the same grid.
- Button D: it will move to ( i + 1 , j ) (i+1,j) (i+1,j) if i < n i<n i<n. Otherwise, it will stay in the same grid.
- Button L: it will move to ( i , j − 1 ) (i,j-1) (i,j−1) if j > 1 j>1 j>1. Otherwise, it will stay in the same grid.
- Button R: it will move to ( i , j + 1 ) (i,j+1) (i,j+1) if j < n j<n j<n. Otherwise, it will stay in the same grid.
You need to construct an operating sequence consisting only of characters U
, D
, L
, and R
. After applying it, you must make sure every kangaroo will gather at the specific cell ( a , b ) (a,b) (a,b). The length of the operating sequence cannot exceed 3 ( n − 1 ) 3(n-1) 3(n−1).
输入格式
There is only one test case in each test file.
The first and only line of the input contains three integers n n n, a a a, b b b ( 2 ≤ n ≤ 500 2 \leq n \leq 500 2≤n≤500, $ 1 \leq a,b \leq n$) indicating the size of the grid and the target cell.
输出格式
Output a string consisting only of characters U
, D
, L
and R
in one line. And its length mustn’t exceed 3 ( n − 1 ) 3(n-1) 3(n−1). It can be proved that the answer always exists.
样例 #1
样例输入 #1
3 3 3
样例输出 #1
RRDD
样例 #2
样例输入 #2
4 3 2
样例输出 #2
DLDLDLUR
以上来自洛谷 以上来自洛谷 以上来自洛谷
解题思路
你以为开始讲解了?不,先听龙吟:原神,启动!(这是伏笔)
正片开始
题目中说 若越界则不动 若越界则不动 若越界则不动,就可以利用这个条件把所有袋鼠聚在一个角上,然后统一移动至目标格子,目标格子离哪个角更近就到哪个。
就结束了?不,然后这题有SPJ,要注意命令顺序。(十分的让人不爽(*******)(<-你猜猜我想说什么。))
AC Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, a, b;
int tmp;
inline void work() {cin >> n >> a >> b;tmp = n / 2;if (a <= tmp && b <= tmp) {for (int i = 1; i < n; i++) {cout << "U";}for (int i = 1; i < n; i++) {cout << "L";}for (int i = 1; i < a; i++) {cout << "D";}for (int i = 1; i < b; i++) {cout << "R";}}if (a <= tmp && b > tmp) {for (int i = 1; i < n; i++) {cout << "U";}for (int i = 1; i < n; i++) {cout << "R";}for (int i = 1; i < a; i++) {cout << "D";}for (int i = n; i > b; i--) {cout << "L";}}if (a > tmp && b <= tmp) {for (int i = 1; i < n; i++) {cout << "D";}for (int i = 1; i < n; i++) {cout << "L";}for (int i = n; i > a; i--) {cout << "U";}for (int i = 1; i < b; i++) {cout << "R";}}if (a > tmp && b > tmp) {for (int i = 1; i < n; i++) {cout << "D";}for (int i = 1; i < n; i++) {cout << "R";}for (int i = n; i > a; i--) {cout << "U";}for (int i = n; i > b; i--) {cout << "L";}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;
}
相关文章:
P9840 [ICPC2021 Nanjing R] Oops, It‘s Yesterday Twice More题解
[ICPC2021 Nanjing R] Oops, It’s Yesterday Twice More 传送门 题面翻译 有一张 n n n\times n nn 的网格图,每个格子上都有一只袋鼠。对于一只在 ( i , j ) (i,j) (i,j) 的袋鼠,有下面四个按钮: 按钮 U:如果 i > 1 …...
OceanBase与MySQL兼容性对比
OB针对于高并发和大数据更有优势,公司的dba让我们把数据从mysql迁移到OceanBase了,这里记录一下OceanBase的MySQL模式。 OceanBase的MySQL模式兼容MySQL5.7的绝大部分功能和语法,兼容MySQL5.7版本的全量以及8.0版本的部分JSON函数。 暂不支持的功能: O…...

【linux】visudo
碎碎念 visudo命令是用来修改一个叫做 /etc/sudoers 的文件的,用来设置哪些 用户 和 组 可以使用sudo命令。并且使用visudo而不是使用 vi /etc/sudoers 的原因在于:visudo自带了检查功能,可以判断是否存在语法问题,所以更加安全 …...

Nvidia-docker的基础使用方法
安装: 安装nvidia-docker: distribution$(. /etc/os-release;echo $ID$VERSION_ID)curl -s -L https://nvidia.github.io/nvidia-docker/gpgkey | sudo apt-key add -curl -s -L https://nvidia.github.io/nvidia-docker/$distribution/nvidia-docker.l…...
uniapp一键换色
需求 : 在我们现有项目基础上, 把原来的颜色替换成另一个颜色, 同时需要为下一个项目预留出来随时更换主题色, 实现一键换色 实现 : 1. 介绍 兼容不同项目对主题色及图标的需求 主要通过以下对css颜色和icon主题色图标两个模块的切换 scss/less的css变量config/index.js中的…...
动态规划思想案例刨析
动态规划的思想 动态规划解决问题的核心思想是“重叠子问题”和“最优子结构”。 重叠子问题:在复杂问题中,往往存在许多重复的子问题。动态规划通过避免重复计算,将子问题的解保存起来,以便在需要时直接引用,从而提…...

vtk9.3 配置 visual studio 2019 运行环境 和运行实例详解
(1)包含文件配置: 项目--属性--VC目录,在包含目录中把include文件夹的地址加进去,一直要到下一级 vtk-9.3目录下, 小知识: 在Visual Studio 2019中运行项目时,如果项目中使用了第三…...

腾讯云添加SSL证书
一、进入腾讯云SSL证书: ssl证书控制台地址 选择“我的证书”,点击"申请免费证书" 2、填写域名和邮箱,点击“提交申请” 在此页面中会出现主机记录和记录值。 2、进入云解析 DNS:云解析DNS地址 进入我的解析-记录…...
CentOS下用rpm安装软件时报错error: Failed dependencies
在CentOS下用rpm安装软件时会报如下错误: 1、安装时提示: [rootdb software]# rpm -ivh ksh-20120801-254.el8.x86_64.rpm warning: ksh-20120801-254.el8.x86_64.rpm: Header V3 RSA/SHA256 Signature, key ID 8483c65d: NOKEY error: Failed depende…...

Vue3+Vite连接高德地图JS API——地图显示、输入搜索
1 开通高德地图Web端JS API服务 1、进入高德地图API官网(https://lbs.amap.com/): 2、注册登录。 3、进入控制台。 4、点击“应用管理”,点击“我的应用”,创建新应用。 5、添加Key,服务平台选择“Web端&…...

一台java服务器可以跑多少个线程?
一台java服务器可以跑多少个线程? 一台java服务器能跑多少个线程?这个问题来自一次线上报警如下图,超过了我们的配置阈值。 打出jstack文件,通过IBM Thread and Monitor Dump Analyzer for Java工具查看如下: 共计166…...
【Python 千题 —— 基础篇】猜数字小游戏
题目描述 题目描述 猜数字。利用 random 函数随机生成一个1~100之间的数并存储在变量中,然后使用条件判断以及循环方式编写一个猜数字的环节: 如果输入的数字大于随机生成的数字,则输出“猜大了”如果输入的数字小于随机生成的数字&#x…...
Android Media3 ExoPlayer 如何正确设置缓存大小
在播放音视频时,如何开启 Android Media3 ExoPlayer 缓存,请参考笔者另外一篇文章: Android Media3 Exoplayer 开启缓存功能 笔者在设置 ExoPlayer 的缓存大小时,遇到一个非常奇怪的问题,例如,设置最大缓存…...

WPF实现右键选定TreeViewItem
在WPF中,TreeView默认情况是不支持右键选定的,也就是说,当右键点击某节点时,是无法选中该节点的。当我们想在TreeViewItem中实现右键菜单时,往往希望在弹出菜单的同时选中该节点,以使得菜单针对选中的节点生…...
蓝桥杯 java 重复字符串
题目描述 * 如果一个字符串S恰好可以由某个字符串重复K次得到,我们就称S是K次重复字符串。 * 例如 abcabcabc 可以看作是 abc重复3次得到,所以 abcabcabc 是3次重复字符串。 * 同理 aaaaaa 既是2次重复字符串、又是3次重复字符串和6次重复字符串。 * 现在…...

Vue实战:两种方式创建Vue项目
文章目录 一、实战概述二、实战步骤(一)安装Vue CLI脚手架1、从Node.js官网下载LTS版本2、安装Node.js到指定目录3、配置Node.js环境变量4、查看node版本5、查看npm版本6、安装Vue Cli脚手架7、查看Vue Cli版本 (二)命令行方式构建…...

不同打包工具下的环境变量配置方式对比
本文作者为 360 奇舞团前端开发工程师 天明 前言 在现代的JavaScript应用程序开发中,环境变量的配置是至关重要的。不同的应用场景和部署环境可能需要不同的配置,例如开发、测试和生产环境。最常见的需求是根据不同的环境,配置如是否开启sour…...

5个99%的人可能不知道的实用程序库!
前言 作为一名前端开发者,这些 JavaScript 库极大地提高了我的工作效率,如格式化日期、处理 URL 参数和调试移动网页。朋友们,我想和你们分享这些库。 1. 使用 “Day.js” 来格式化日期和时间 链接 作为开发者,我已经厌倦了在 JavaScript 中操作日期和时间,因为它太麻烦了。…...
shell脚本,ADB
Linux命令行命令是系统内置的命令或用户自定义的脚本(shell 脚本,.sh扩展名结尾),可以通过终端输入命令来执行。这些命令通常存储在Linux系统的/bin、/usr/bin、/sbin、/usr/sbin等目录下,也可以在$PATH环境变量中指定…...
微服务治理:微服务安全详解
微服务安全旨在保护微服务架构中每一个独立的服务。与传统单体应用程序不同,它们在单点应用安全措施,微服务由于其独立性,需要分布式安全方法。 为何关注微服务安全? 攻击面扩大: 更多服务暴露在外,意味着攻击者拥有…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...