专栏文章

题解：CF2157F Git Gud

WWilliamFranklin
CF2157F题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min1f099
此快照首次捕获于
2025/12/01 18:59
3 个月前
此快照最后确认于
2025/12/01 18:59
3 个月前
查看原文

Solution

以下 N=250000N = 250000。
首先第一反应是分块，设每 BB 个一组，组内从大到小排序，组内代价总和就是 B(B+1)2\frac{B(B + 1)}{2}。这样贡献就是 1000NB+B2(B+1)2\frac{1000N}{B} + \frac{B^2(B + 1)}{2}，这个显然是很劣的。但这个分组，且组内从大到小的想法自然且十分重要。
接着我们考虑，每一次组内的一个数 XX，加上一个它的代价后，跳到 YY，那么需要满足 YY 的位置在 XX 后，且我们还希望分的组较少，每个数的代价也少。
从这个向后跳的过程中，有无感觉出树状数组的影子，就是每一次 X+lowbit⁡(X)X + \operatorname{lowbit}(X)。这启示我们可以按照 lowbit⁡(X)\operatorname{lowbit}(X) 分组。这样一共有 log⁡2N\log_2{N} 组，总贡献写个程序算一下，可以达到 22382482238248。
还是不可以，但我们想到，我们分的组还是太少了，才不到 2020 个。那就从这个地方入手，考虑若以 mm 为底，那么组数将会是 (m−1)log⁡mN(m - 1)\log_mN，并且这个是单增的。然后对于一个数 XX，设它在 mm 进制下一共从最低位开始连续 00 的个数为 xx，那么定义其代价就是 mxm^x。这样整体代价随 mm 增长越平均，其平均数也显然是一个凸函数，求个导什么的应该就能证。
懒得算了，手动二分以下，m=100m = 100 即可通过，总代价为 956000956000。但最小的时候应该是 m=63m = 63，总代价为 923093923093。但 CodeForces 的题解评论区中，还有神仙达到了 8.5×1058.5 \times 10^5，很神秘，很智慧，很无敌，很是非人类。
对于 n=4n = 4，直接输出样例就可以了。
AC Code (m=100m = 100)CPP
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 250005;
pair<int, pair<int, int> > a[N];
bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
	if (a.x == b.x) return a.y.x > b.y.x;
	return a.x < b.x;
}
int calc() {
	long long ans = 0;
	For(i, 1, 250000) ans += min(a[i].y.y, 250000 - a[i].y.x);
	cout << 249999 << '\n';
	For(i, 1, 250000) if (a[i].y.x != 250000)cout << a[i].y.x << ' ' << min(a[i].y.y, 250000 - a[i].y.x) << '\n';
	For(i, 2, 250000) if (a[i].y.x != 250000) if (a[i].y > a[i - 1 - (a[i - 1].y.x == 250000)].y) ans += 1000;
	return ans;
}
int work(int B) {
	For(i, 1, 250000) {
		int last = 1;
		int x = i;
		while (x % B == 0) {
			last = last * B;
			x /= B;
		}
		a[i].x = last * (x % B);
		a[i].y.x = i;
		a[i].y.y = last;
	}
	sort(a + 1, a + 250000 + 1, cmp);
	long long ans = calc();
	return ans;
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	if (n == 4) {
		cout << "4\n";
		cout << "1 4\n";
		cout << "3 1\n";
		cout << "2 1\n";
		cout << "3 1\n";
		return 0;
	}
	int B = 100;
	int ans = work(B);
	//cout << ans;
	return 0; 
}
AC Code (m=63m = 63)CPP
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 250005;
pair<int, pair<int, int> > a[N];
bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
	if (a.x == b.x) return a.y.x > b.y.x;
	return a.x < b.x;
}
int calc() {
	long long ans = 0;
	For(i, 1, 250000) ans += min(a[i].y.y, 250000 - a[i].y.x);
	cout << 249999 << '\n';
	For(i, 1, 250000) if (a[i].y.x != 250000)cout << a[i].y.x << ' ' << min(a[i].y.y, 250000 - a[i].y.x) << '\n';
	For(i, 2, 250000) if (a[i].y.x != 250000) if (a[i].y > a[i - 1 - (a[i - 1].y.x == 250000)].y) ans += 1000;
	return ans;
}
int work(int B) {
	For(i, 1, 250000) {
		int last = 1;
		int x = i;
		while (x % B == 0) {
			last = last * B;
			x /= B;
		}
		a[i].x = last * (x % B);
		a[i].y.x = i;
		a[i].y.y = last;
	}
	sort(a + 1, a + 250000 + 1, cmp);
	long long ans = calc();
	return ans;
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	if (n == 4) {
		cout << "4\n";
		cout << "1 4\n";
		cout << "3 1\n";
		cout << "2 1\n";
		cout << "3 1\n";
		return 0;
	}
	int B = 63;
	int ans = work(B);
	//cout << ans;
	return 0; 
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...