codeforces 50题精选训练

本章节参考:2020,2021 年 CF 简单题精选 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

T1:

首先，很容易观察到点的一些特征:

- 都在第一象限；
- 点的分布越来越稀疏。

以样例为例：

还有无限个点没有画出来。

根据点的分布越来越稀疏的特性，能不能发现收集点的规律呢？
比如我们可以先枚举一个点 \(i\)，直接从 \((x_s, y_s)\) 出发去收集 \(\text P_i\)。

然后呢？如果往 \(\text P_0\) 的方向收集，点会非常密集；如果往 \(\text P_\infty\) 的方向收集，点就会非常稀疏。

当然，我们往 \(\text P_0\) 的方向收集！

但是，这边的点是有限的，如果全部收集完了时间还绰绰有余呢？

那就原路返回，再往 \(\text P_\infty\) 的方向收集！

有人可能会疑惑，为什么这里都原路返回了，答案还是最优呢？

首先，因为随着 \(j\) 的增大，\(x_j, y_j\) 都在增大，所以 \(\sum_{j = 1}^{i}\operatorname{dist}(\text P_{j-1}, \text P_j)\)（也就是从 \(\text P_i\) 收集到 \(\text P_0\) 的总距离）就等于 \(\operatorname{dist}(\text P_0 ,\text P_i)\)（\(\operatorname{dist}\) 表示曼哈顿距离）。

下面为了分析方便只看 \(x\) 坐标（\(\operatorname{Xdist}\) 表示 \(x\) 坐标之差）。

点最密集的时候应该是什么时候？很显然，\(a_x\) 和 \(b_x\) 都最小的时候，也就是 \(a_x = 2, b_x = 0\)。

\[ \operatorname{Xdist}(\text P_{i+1}, \text P_{i}) = (a_x \cdot x_{i} + b_x) - x_{i} = (a_x - 1)\cdot x_{i} + b_x = x_i \]

\[ \operatorname{Xdist}(\text P_{0}, \text P_{i}) = x_i - x_0 \]

\(\because x_0 \ge 1 \quad \therefore \operatorname{Xdist}(\text P_{i+1}, \text P_{i}) > \operatorname{Xdist}(\text P_{0}, \text P_{i})\)

现在 \(y\) 坐标也加进来，就可以得到 \(\operatorname{dist}(\text P_{i+1}, \text P_{i}) > \operatorname{dist}(\text P_{0}, \text P_{i})\)。

这说明什么？收集 \(\text P_0 \sim \text P_{i - 1}\) 的时间比只收集一个 \(\text P_{i + 1}\) 的时间还要少！

如果当初选择向右走，那再去收集 \(\text P_{i + 2}\) 的时候，显然 \(\operatorname{dist}(\text P_{i+1}, \text P_{i +2}) > \operatorname{dist}(\text P_{i}, \text P_{i+1})\)，那么 \(\operatorname{dist}(\text P_{i+1}, \text P_{i +2}) + \operatorname{dist}(\text P_{i}, \text P_{i+1}) > 2 \operatorname{dist}(\text P_{0}, \text P_{i})\)。说明向 \(\text P_{\infty}\) 方向收集 \(2\) 个点的时候，\(\text P_0\) 方向已经回来了，并收集了 \(i\) 个点，如果 \(i \ge 2\) 那么直接可以知道答案更优了，还剩两种情况：

- \(i=0\)，这时没什么左右之分，那不影响答案；
- \(i=1\)，直接带入算一算，\(x_1 = 2 x_0\)，\(x_2 = 4 x_0\)，那么左边加上返回的时间是 \(2 x_0\)，直接去 \(\text P_2\) 的时间也是 \(2 x_0\)，因为越往后点越稀疏，而两种方案当前耗时相同，起点不同，所以 \(\text P_0\) 方向还是更优。

还有一个小问题，就是数组开多大，因为 \(2^{64} > 10^{18}\)，所以数组开到 \(70\) 就绰绰有余了。

时间复杂度 \(\mathcal O(n^2)\)，\(n\) 是要用到的点数，算到 \(x_n > x_s, y_n > y_s, \operatorname{dist}(\text P_n, \text S) > t\) 即可。

//https://codeforces.com/contest/1292/problem/B

/*
    38 70 2 2 67 88
6838924170055088 456766390500883 9176106261147424

调了半天,最终还是A了
由数据范围可知道,由于数据点是以指数级增长的,所以最多有2^64>=10^16,也就是顶多64个
然后 由于数据点一共就64个,不难想到暴力枚举,我认为比较难的地方就在于如何去枚举,如果
我们真的是纯暴力的话,每个点有选或不选,那么就是2^64,肯定不行
由于数据点是指数级爆炸增长,所以说可以这样想,假设原点在某两点之间,那么我们要先把左边的遍历完再遍历右边
可以想 2^0+2^1+....2^n-1相加,他们的和 是不如 2^n大的,所以说我们走2^n这个点不如走n-1所有点 
*/
//3,144,565,100,727,795
//5,102,364,399,534,485
#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N=2e5+10;
int res;
//bool cmp(pair<int,int>a,pair<int,int>b)
//{
//    return a.first<b.first;
//}
signed main()
{
    int x0,y0,ax,ay,bx,by,xs,ys,t,f=0,pos;
    cin>>x0>>y0>>ax>>ay>>bx>>by>>xs>>ys>>t;
    vector<pair<int,int>>point;
    point.push_back({x0,y0});
    for(int i=1;i<=61;i++){
        int x=x0*ax+bx,y=y0*ay+by;
        if(x<0||y<0) break;
        if(x0*ax+bx>=1e17||y0*ay+by>=1e17) break;
        point.push_back({x,y}),x0=x,y0=y;
    }
//    sort(point.begin(),point.end(),cmp);
//    int vis=0; 
//    for(int i=0;i<point.size();i++)
//        if(point[i]==make_pair(xs,ys)) pos=i,vis++;
//        
//    cout<<pos<<endl;
//    for(auto i:point) cout<<i.first<<' '<<i.second<<endl;
//    
//    for(int i=pos;i<point.size();i++){
//        int ans=0,nowx=xs,nowy=ys,t_=t;
////        cout<<"右: "<<endl;
//        for(int j=pos+1;j<=i;j++){
////            cout<<t_<<endl;
////            cout<<j<<' '<<point[j].first<<' '<<point[j].second<<endl; 
//            if(point[j]==make_pair(xs,ys)) continue;
//            int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy));
//            if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second;
//            else break;
//        } 
////        cout<<"左: "<<endl;
//        for(int j=pos;j>=0;j--){
////            cout<<t_<<endl;
////            cout<<j<<' '<<point[j].first<<' '<<point[j].second<<' '<<endl; 
//            if(point[j]==make_pair(xs,ys)) continue;
//            int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy));
//            if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second;
//        }
////        cout<<ans<<endl;
//        res=max(res,ans);
//    }
    for(int i=0;i<point.size();i++){
        int t_=t,nowx=xs,nowy=ys,ans=0;
        for(int j=i;j>=0;j--){
            int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy));
            if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second;
        }
        for(int j=i+1;j<point.size();j++){
            int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy));
            if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second;
            else break;
        }
        res=max(res,ans);
    }
//    if(vis>=2) res++;
    cout<<res;
    return 0;
}