Codeforces 1292B/1293D - Aroma's Search
2024-10-08 20:04:51
题目大意:
Aroma想要找数据
第0个数据再x0,y0这个点
其后所有数据所在的坐标点满足
x[i]=x[i-1]*ax+bx
y[i]=y[i-1]*ay+by
Aroma一开始在点(xs,ys),她最多只能走t步
两点间的距离用Δx+Δy表示
问Aroma最多能走到多少个点(找到多少个数据)?
解题思路:
因为ax和ay是大于等于2的整数
所以序号越大点越离散
所以最多只有log1e16约等于60个点
贪心枚举第一步要去的点i,然后从i开始先往点的序号小的点走 i-1, i-2 ,... 0
如果步数t还有剩余再考虑i+1以上的点
记录每次枚举可以到达的点的个数,取最大输出
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll e16=1e16;
ll x[],y[];
void solve(){
ll x0,y0,ax,ay,bx,by,xs,ys,t;
cin>>x0>>y0>>ax>>ay>>bx>>by>>xs>>ys>>t;
x[]=x0;
y[]=y0;
ll i,j,mxn,ans,ansd,td;
for(i=;x[i-]<=e16&&y[i-]<=e16;i++){
x[i]=x[i-]*ax+bx;
y[i]=y[i-]*ay+by;
}
mxn=i-;
ans=;
for(i=;i<=mxn;i++){
ansd=;
td=t;
if((td=td-abs(xs-x[i])-abs(ys-y[i]))>=)
ansd++;
for(j=i-;j>=&&td>;j--){
if((td=td-abs(x[j+]-x[j])-abs(y[j+]-y[j]))>=)
ansd++;
}
if(td>&&(td=td-abs(x[i+]-x[])-abs(y[i+]-y[]))>=)
ansd++;
for(j=i+;j<=mxn&&td>;j++){
if((td=td-abs(x[j]-x[j-])-abs(y[j]-y[j-]))>=)
ansd++;
}
ans=max(ans,ansd);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio();
cin.tie();cout.tie();
solve(); return ;
}
最新文章
- C#互斥体——Mutex
- ASP.NET Core 1.0 入门——了解一个空项目
- 清除浮动类的css
- QQ音乐无损歌曲接口api
- C#基础(二)
- JdbcTemplate查询数据 三种callback之间的区别
- 《Python 学习手册4th》 第十二章 if测试和语法规则
- 算法优化(动态规划):COGS 2009. [USACO Mar09]餐厅清扫
- prim模板题
- PhiloGL学习(6)——深情奉献:快乐的一家
- 忘记Jenkins管理员密码的解决办法
- 14 fragment传值
- IntelliJ Idea 第一次使用
- c++ 开源库介绍和安装
- Android popupMenu
- eclipse热部署配置
- 树结构数据的展示和编辑-zTree树插件的简单使用
- CSS深入理解之float(HTML/CSS)
- Unity3D游戏开发最佳实践20技巧(三)
- Ubuntu下gcc的简单使用