题目大意:

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

最新文章

  1. C#互斥体——Mutex
  2. ASP.NET Core 1.0 入门——了解一个空项目
  3. 清除浮动类的css
  4. QQ音乐无损歌曲接口api
  5. C#基础(二)
  6. JdbcTemplate查询数据 三种callback之间的区别
  7. 《Python 学习手册4th》 第十二章 if测试和语法规则
  8. 算法优化(动态规划):COGS 2009. [USACO Mar09]餐厅清扫
  9. prim模板题
  10. PhiloGL学习(6)——深情奉献:快乐的一家
  11. 忘记Jenkins管理员密码的解决办法
  12. 14 fragment传值
  13. IntelliJ Idea 第一次使用
  14. c++ 开源库介绍和安装
  15. Android popupMenu
  16. eclipse热部署配置
  17. 树结构数据的展示和编辑-zTree树插件的简单使用
  18. CSS深入理解之float(HTML/CSS)
  19. Unity3D游戏开发最佳实践20技巧(三)
  20. Ubuntu下gcc的简单使用

热门文章

  1. sqli-labs注入lesson1-2闯关秘籍
  2. python利用百度云接口实现车牌识别
  3. Mac 终端命令使用自动补全时忽略大小写设置
  4. POJ 1942:Paths on a Grid
  5. JZOJ823PJ-C, TG-B
  6. NRF24L01多对一、多通道通讯关键代码
  7. cos改ip
  8. js对象属性名和属性值生成新数组时都作为属性值
  9. ansible删除目录下所有内容
  10. Linux-线程引入