https://atcoder.jp/contests/agc044/tasks

A - Pay to Win

 

题意：初始有数0，给定目标数字N，1≤N≤10181\le N\le 10^{18}，有四种操作：花费 AA，乘2；花费 BB，乘3；花费 CC ，乘5；花费 DD，加减1。问达到目标数字的最小花费。

考虑从N操作到0，则操作变为除，且必定整除时操作。

操作序列显然是类似DDDDADDBDDDBBDDCC，即一段D然后有ABC，再循环，所以要考虑D到什么时候可能要ABC了，然后dfs下一个状态。

结论是下一个状态为 ⌊N2⌋\lfloor \frac{N}{2}\rfloor 或 ⌈N2⌉\lceil \frac{N}{2}\rceil，或⌊N3⌋\lfloor \frac{N}{3}\rfloor 或 ⌈N3⌉\lceil \frac{N}{3}\rceil，或⌊N5⌋\lfloor \frac{N}{5}\rfloor 或 ⌈N5⌉\lceil \frac{N}{5}\rceil.

下一个状态显然是在ABC操作后得到的，并且ABC之前必须全是D，其它都是中间状态，要剪掉。

如果状态 y<⌊Nk⌋y<\lfloor \frac{N}{k}\rfloor，则如果一直D到y，最后再除一次k，D的花费为 N−kyN-ky。但是如果先D到 k⌊Nk⌋k\lfloor \frac{N}{k}\rfloor，再除k，再一直D到y，则D的花费为 N−k⌊Nk⌋+⌊Nk⌋−yN-k\lfloor \frac{N}{k}\rfloor+\lfloor \frac{N}{k}\rfloor-y，两个花费减一下就能发现第二种操作序列更好。所以不应该把y作为下一个的状态。

而如果状态 y>⌈Nk⌉y>\lceil \frac{N}{k} \rceil，同理，第一种D花费为 ky−Nky-N。第二种D花费为 k⌈Nk⌉−N+y−⌈Nk⌉k\lceil \frac{N}{k} \rceil-N+y-\lceil \frac{N}{k} \rceil，还是第二种更好。

⌊Nk⌋\lfloor \frac{N}{k}\rfloor 和 ⌈Nk⌉\lceil \frac{N}{k} \rceil 之间没有其它状态了，所以得证。

所以在到达其它状态y之前，一定要经过ABC到达 ⌊Nk⌋\lfloor \frac{N}{k}\rfloor 或 ⌈Nk⌉\lceil \frac{N}{k}\rceil，所以下一个状态应该为 ⌊Nk⌋\lfloor \frac{N}{k}\rfloor 或 ⌈Nk⌉\lceil \frac{N}{k}\rceil。

这样只枚举必然到达的状态，也就减少了复杂度。

还要注意由于这里指定必须进行一次ABC，所以还有一种可能一路D到0没有考虑到，所以应该另外处理一下。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int T;
ll n, a, b, c, d;
map<ll, ll>mp;
ll dfs(ll n) {
	if (n == 0)return 0;
	if (n == 1ll)return d;
	if (mp.count(n))return mp[n];
	ll res = inf;
	if (n < res / d)res = n * d;
	ll l2 = n / 2, r2 = l2 + (n & 1);
	ll l3 = n / 3, r3 = l3 + (n % 3 != 0);
	ll l5 = n / 5, r5 = l5 + (n % 5 != 0);
	res = min(res, abs(l2*2 - n)*d + a + dfs(l2));
	res = min(res, abs(r2*2 - n)*d + a + dfs(r2));
	res = min(res, abs(l3*3 - n)*d + b + dfs(l3));
	res = min(res, abs(r3*3 - n)*d + b + dfs(r3));
	res = min(res, abs(l5*5 - n)*d + c + dfs(l5));
	res = min(res, abs(r5*5 - n)*d + c + dfs(r5));
	mp[n] = res;
	return res;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		mp.clear();
		scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d);
		printf("%lld\n", dfs(n));
	}
	return 0;
}

 

B - Joker

 

题意：n*n的01矩阵，初始全为1，给定操作序列，按照顺序每次从该位置找到一条到达矩阵外的的最短路径，路径长度定义为路径上1的个数，然后把该位置置为0。问所有操作结束后总花费。

不同操作间没有影响，所以每次独立操作。

每个位置到达矩阵外的最短路可以由周围四个位置的最短路得到，所以考虑维护每个位置的最短路，每次操作时直接取四周的最小值，操作后更新维护。

操作后该位置为0，所以在该位置的最短路就为四周的最小值。再用得到的新的值bfs更新周围，扩散直到某个位置没有变化。

由于所有位置的最短路初始是最大的，而最大值约为 N36\frac{N^3}{6}，之后每次更新时被更新到的每个位置至少-1，而最终所有位置的最短路都是0，所以所有操作总的更新的位置数一定小于等于 N36\frac{N^3}{6}，那么复杂度也就够了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int n;
typedef pair<int, int>pii;
pii id(int x) {
	return pii((x - 1) / n + 1, (x - 1) % n + 1);
}
int dx[]{ 0,0,-1,1 };
int dy[]{ -1,1,0,0 };
int d[510][510], gg[510][510];
bool ilg(int x, int y) {
	return x<1 || y<1 || x>n || y>n;
}
void bfs(pii p) {
	queue<pii>q;
	q.push(p);
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (ilg(nx, ny) || d[nx][ny] <= d[x][y] + gg[x][y])continue;
			d[nx][ny] = d[x][y] + gg[x][y];
			q.push(pii(nx, ny));
		}
	}
}
int main() {
	scanf("%d", &n);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			d[i][j] = min(min(n - i, n - j), min(i - 1, j - 1)), gg[i][j] = 1;
	for (int i = 0; i < n*n; i++) {
		int x, y;
		scanf("%d", &x);
		pii p = id(x);
		x = p.first, y = p.second;
		int tmp = INF;
		for (int j = 0; j < 4; j++) {
			int nx = x + dx[j], ny = y + dy[j];
			tmp = min(tmp, d[nx][ny] + gg[nx][ny]);
		}
		ans += tmp;
		d[x][y] = tmp;
		gg[x][y] = 0;
		bfs(p);
	}
	printf("%d\n", ans);
	return 0;
}