CF346E-Doodle Jump【类欧】
2024-10-19 02:35:16
正题
题目链接:https://www.luogu.com.cn/problem/CF346E
题目大意
给出\(a,n,p,h\),在每个\(ax\%p(x\in[0,n])\)的位置有一个关键点,询问是否所有相邻关键点之间的距离都不超过\(h\)。
解题思路
没怎么写过类欧,这个题还是很坑的,需要考虑求一下\(h\)需要的最小值(相邻关键点直接距离的最大值)
首先第一个循环肯定都是\(ax\)的位置有关键点了,然后第二个循环开始是\(\lceil\frac{p}{a}\rceil a-p+ax\),然后每个循环的起点加一个\(\lceil\frac{p}{a}\rceil a-p\)。好像就可以用类欧把一个大问题缩减成一个小问题了。
考虑一下细节,首先是末尾那一段,也就是\(a\lfloor\frac{p}{a}\rfloor+1\sim p\)这一段是没有用的,因为如果这一段无法到达最末尾处,那么一定存在某个\(k\)使得\(ka\)无法到达\((k+1)a\)。
然后考虑有多少个可行的循环,简单的看是\(\lfloor\frac{an}{p}\rfloor\),但是这样可能会有某些周期没有跑完的情况,那么后面那些间隔是没有变小的,考虑到我们求的是最大间隔,肯定是取后面的,所以此时要减一。
然后当\(an\leq p\)的时候就可以取答案了。
时间复杂度\(O(\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll a,n,p,h,T;
ll solve(ll a,ll n,ll p){
if(a*n<p)return max(a,p-a*n);
ll z=a*n/p;
if(a*n%p<p/a*a-a)z--;
return solve((p+a-1)/a*a-p,z,a);
}
signed main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld%lld%lld%lld",&a,&n,&p,&h);
a%=p;
if(a<=h){puts("YES");continue;}
if(a*n<=p){puts(h>=a?"YES":"NO");continue;}
puts((solve(a,n,p)<=h)?"YES":"NO");
}
return 0;
}
最新文章
- Android基础总结(八)
- Windows出现带空格文件名无法删除
- PPTP-VPN第三章——用户流量与并发数限制
- ORA-12520: TNS: 监听程序无法为请求的服务器类型找到可用的处理程序
- Web前端开发面试题
- C# 对Excel文档打印时的页面设置
- MSP430主系统时钟以及430的低功耗设置
- apk,task,android:process与android:sharedUserId的区别
- 《think in python》学习-5
- JQuery的stop()属性
- go time模块
- Linux常用命令汇总(一)
- JAVA核心技术I---JAVA基础知识(知识回顾)
- 基于Python的机器学习实战:AadBoost
- MCU PWM DAC OP Voltage Output
- <;<;APUE>;>; 线程的分离状态
- GoodUserInterface 模仿页面功能
- 【转载】基于MFC的ActiveX控件开发(2)
- iframe 同域下父子页面的通信
- C语言 &#183; 身份证号码升级
热门文章
- asp.net core 搭建WebAPI微服务-----cosnul服务
- C#设计模式---单例模式(Singleton Pattern)
- linux的一般命令------附加
- 线程池ExecutorService的使用
- vue+vant实现购物车的全选和反选业务,带你研究购物车的那些细节!
- ES6扩展——箭头函数
- linux-解决/usr/bin/which: no ssh-copy-id in 和ssh: Could not resolve hostname问题
- 快速入门PaddleOCR,并试用其开发一个搜题小工具
- Kubernetes-kubectl介绍
- [源码解析] 深度学习流水线并行 PipeDream(3)--- 转换模型