http://codeforces.com/contest/1293
D. Aroma’s Search
题意：平面上有几个数据点，(ax⋅xi−1+bx,ay⋅yi−1+by)，且 (x0,y0) ,ax,ay,bx,by 给定，问在给定总距离内从起始点最多走过几个数据点，距离为曼哈顿距离。
可以发现 (xi,yi) 是指数级增长的，所以总的点数一定不多，试一下发现只有几十个，那就直接暴力枚举从起始点先走到一个数据点，再从这个数据点走向其它点，由于是曼哈顿距离，所以如果两个数据点能互相到达，那么一定可以经过所有中间点。
则枚举起始数据点，和终止数据点，若两者可达，则经过点数为两者中间所有点。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll, ll> pii;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 1e18;
const ll mod = 1000000007;
ll X0, Y0, ax, ay, bx, by, Xs, Ys, t;
vector<pii>vc;
ll dis(ll x1, ll y1, ll x2, ll y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int main() {
cin >> X0 >> Y0 >> ax >> ay >> bx >> by >> Xs >> Ys >> t;
ll nx = X0, ny = Y0;
while (nx <= 5e16&&ny <= 5e16) {
vc.push_back(pii(nx, ny));
nx = ax * nx + bx;
ny = ay * ny + by;
}
int ans = 0;
int n = (int)vc.size();
for (int i = 0; i < n; i++) {
ll tmp = dis(Xs, Ys, vc[i].first, vc[i].second);
for (int j = 0; j < n; j++) {
if (tmp + dis(vc[i].first, vc[i].second, vc[j].first, vc[j].second) <= t) {
ans = max(ans, abs(j - i) + 1);
}
}
}
cout << ans << endl;
return 0;
};
|
E. Xenon’s Attack on the Gangs
题意：有一棵树，2≤n≤3000，要求给每条边赋值 0 到 n−2，定义两个点的贡献为这两点的路径上边的集合的 mex 值，求所有点对的贡献和 S，集合的 mex 值为第一个未在集合中出现的非负整数。
S=1≤u<v≤n∑mex(u,v)
首先，只有两点的路径经过0时，两点才有贡献，且两点的贡献为0开始最长连续数列长度。
问题就是要求 ∑k=1n∑mex(u,v)=kk
这又是个熟悉的问题，由于mex为k的点对的路径上一定包含0到k-2，0到k-3，等等，所以可以变成 ∑k=1n∑mex(u,v)≥k1，变成了求mex值大于等于k的数对个数。
接下来可以枚举所有链，将它上的边设定为从零开始的连续序列。
则只有在这条链两端的点之间才会有贡献（其它点对不经过0），链的最外侧的两团点之间贡献为k，往内贡献逐渐变小最终变成1，则可以累加数对个数。
记忆化dfs深搜枚举的链向内的mex值从k到1的最优解。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
vector<int>G[maxn];
int fa[3010][3010], siz[3010][3010];
void dfs1(int u, int _fa, int rt) {
fa[rt][u] = _fa;
siz[rt][u] = 1;
for (int v : G[u]) {
if (v == _fa)continue;
dfs1(v, u, rt);
siz[rt][u] += siz[rt][v];
}
}
ll dp[3010][3010];
ll dfs2(int u, int v) {
if (u == v)return 0;
if (dp[u][v] != -1)return dp[u][v];
return dp[u][v] = 1ll * siz[v][u] * siz[u][v] + 1ll * max(dfs2(u, fa[u][v]), dfs2(v, fa[v][u]));
}
ll ans;
int main() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
dfs1(i, 0, i);
}
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ans = max(dfs2(i, j), ans);
}
}
cout << ans << endl;
return 0;
}
|
