Aroma’s Search
Created by LXC on Sat May 6 10:16:40 2023
https://codeforces.com/problemset/problem/1292/B
ranting: 1700
tag: brute force, constructive algorithms, geometry, greedy, implementation
题意
在一个无限的二维平面上，有无限个数据节点。
这些节点的分布为：
- 第一个节点在位置$(x_0,y_0)$
- 其余节点$(x_i, y_i) = (a_x*x_{i-1}+b_x, a_y * y_{i-1}+b_y)$
你初始位置在(xs, ys)，然后每秒钟可以向上/下/左/右移动一单位距离。
请问t秒钟能最多到达多少数据节点。
题解
显然第i个数据节点的位置的x和y都是指数增长的。
所以我们考虑x坐标以及y坐标分别不超过xs+t和ys+t的所有数据节点，这些节点的个数是log数量级的
然后对于访问数据节点i到数据节点j这个区间的所有数据节点，所需要的时间是节点i和节点j曼哈顿距离。
我们可以暴力枚举，(xs,ys)到任意区间的一端所需的时间+访问该区间的所有节点的时间，在不超过t的情况下，维护最大的节点数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;
void sol() {
ll x0, y0, ax, ay, bx, by, xs, ys, t;
cin >> x0 >> y0 >> ax >> ay >> bx >> by >> xs >> ys >> t;
vector<pair<ll,ll>> p;
ll cx = x0, cy = y0;
while (cx<=xs+t && cy<=ys+t) {
p.emplace_back(cx, cy);
cx = cx*ax+bx;
cy = cy*ay+by;
}
ll ans = 0;
for (int i=0; i<p.size(); i++) {
ll px = xs, py = ys, d = 0, tans = 0;
for (int j=i; j<p.size(); j++) {
ll x = p[j].first, y = p[j].second;
d += abs(px-x)+abs(py-y);
if (d<=t) tans++;
else break;
px = x, py = y;
}
ans = max(ans, tans);
}
for (int i=0; i<p.size(); i++) {
ll px = xs, py = ys, d = 0, tans = 0;
for (int j=i; j>=0; j--) {
ll x = p[j].first, y = p[j].second;
d += abs(px-x)+abs(py-y);
if (d<=t) tans++;
else break;
px = x, py = y;
}
ans = max(ans, tans);
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}
|