CF538G (套路题)
2024-10-07 23:37:01
CF538G
题目大意
你有一个长度为\(l\)的指令序列,每个指令为向上,向下,向左,向右中的一种。
机器人会循环执行该序列,即,执行完第\(l\)个指令后,就会重新开始执行第一个指令。
现在,给你\(n\)个信息,每个信息为:在第\(t\)秒时,机器人所处的位置\((x,y)\)
请求出一个合法的序列,如无解,则输出\(No\)
\(n\le2*10^5\ l\le2*10^6\)
解题历程
一开始,真的很自闭,二维的太难考虑了。
去翻题解,题解第一行说,这样的位移可以等价于每秒独立地在\(x+y\)和\(x-y\)方向上\(+1\)或\(-1\)
豁然开朗。
于是,现在只需要考虑一维的情况了。
我们发现,它循环多次,又剩余一点。
我们就考虑这多出的一点,令:
\(t=p*l+q\)
若我们假设整个序列在当前方向上的位移为\(x\),\(q\)内的位移为\(f(q,x)\),\(t\)内的位移为\(sum\)
则\(f(q,x)=sum-px\)
我们把所有的信息按\(q\)排序,那么,需满足以下限制
\[
|f(q_i,x)-f(q_{i+1},x)|\le q_{i+1}-q_i
\]
然后,解方程,找出值域内的任意\(x\),再带回去算即可
注:可能需要考虑以下奇偶性的问题
代码
由于我是口胡选手,所以就先咕着。
最新文章
- 通过dll或def文件提取lib导入库文件
- 关于lambda表达式的一些学习——基于谓词筛选值序列
- java Iterator Fail-fast机制
- 搭建SpringMVC+MyBatis开发框架三
- BZOJ 1029 [JSOI2007] 建筑抢修(贪心)
- UIImageView旋转任意角度
- 详细讲解Android对自己的应用代码进行混淆加密防止反编译
- 使 httpClient 支持中文
- hadoop配置文件的作用
- nginx是什么nginx安装与配置之windows版
- vedio-js的视频插件用法
- C# System.Collections
- Angular2入门:TypeScript的模块
- Civil 3D 二次开发 创建AutoCAD对象—— 00 ——
- robotframework中RIDE的下载及安装
- [转] Linux shell判断文件和文件夹是否存在
- Homebrew 安装mysql
- java 路径的问题
- Report CodeForces - 631C (栈)
- 使用delphi 开发多层应用(二十四)KbmMW 的消息方式和创建WIB节点
热门文章
- UMP系统功能 资源管理
- 关于Windows10企业版的激活方法
- JZOJ[3771] 【NOI2015模拟8.15】小 Z 的烦恼
- 「题解」:[组合数学]:Perm 排列计数
- Jdk8 Hashmap ConcurrentHashMap
- JDK源码阅读--LinkedList
- 组件:基础的基础组件(Component,Portlet)
- 解决MySQL登录ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using passwor)问题
- js中控制流管理的四种方法
- (Eclipse) 安装Subversion1.82(SVN)插件