Codeforces Round 952 (Div. 4)

A. Creating Words

void solve() {
	string a, b;
	cin >> a >> b;
	swap(a[0], b[0]);
	cout << a  << ' ' << b << '\n';
}

B. Maximum Multiple Sum

总结：作为一个等差数列，快速的找到最高次系数，以及快速求和..C = n / x, sum = (c * x + x) * c / 2;

void solve() {
	int n;
	cin >> n;

	int maxn = 0;
	int ans = 0;
	for (int x = 2; x <= n; ++x){
		int t = n / x;
		int sum = (t * x + x) * t / 2;
		if (checkMax(maxn, sum)){
			ans = x;
		}
	}

	cout << ans << '\n';
}

C. Good Prefixes

题意：数组中一个数是其他所有数的和，则数组为good。求给定数组中前缀good数组的数量。

思路：每次新增一个数，分情况讨论。该数=prefix，该数<prefix, 该数>prefix。

总结：思维题吧，一开始没想到分情况讨论，卡了一小会。

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (auto& x : a){
        cin >> x;
    }

    int last = -1;
    long long sum = 0;
    int ans = 0;   
    int maxn = 0;
    for (int i = 0; i < n; ++i){
        if (a[i] == sum || (!a[i] && i - 1 == last)){
            ans ++;
            last = i;
        }
        else if (a[i] < sum && sum + a[i] == 1ll * 2 * maxn){
            ans ++;
            last = i;
        }
        sum += a[i];
        maxn = max(maxn, a[i]);
    }

    cout << ans << '\n';
}

D. Manhattan Circle
题意：矩阵中有一个左右对阵的形状，找到形状的中心坐标。

思路：一次遍历，找到上下左右四个端点，取中心即可。

void solve() {
	int n, m;
	cin >> n >> m;

	vector<string> mat(n);
	constexpr int inf = 0x3f3f3f3f;
	int up = inf, left = inf, down = -inf, right = -inf;
	for (int i = 0; i < n; ++i){
		cin >> mat[i];
		int p = mat[i].find_first_of('#');
		int q = mat[i].find_last_of('#');
		if (p != -1){
			up = min(up, i + 1);
			left = min(left, p + 1);
			right = max(right, q + 1);
			down = max(down, i + 1);
		}
	}
	cout << (up + down) / 2  << ' ' << (left + right) / 2 << '\n';
}

E. Secret Box

题意：给定一个长方体xyz，代表3个维度长度，再给定一个体积k，问任何可能的形状（体积为k），在长方体内部可以放置的方式最多有多少个。

思路：x, y, z <= 2000。 暴力选择前两条边，然后可以得出每个维度可以移动的距离，相乘就是最大的放置方式。

总结：看到三维有点没理解，仔细分析后发现最后的答案就是在每个维度上能移动的距离，只要暴力选择边就好。选择边复杂度是(O(1e4))。可以加一些剪枝的优化操作进去。

void solve() {
	array<int, 3> a;
	for (int i = 0; i < 3; ++i){
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	long long k;
	cin >> k;

	long long ans = 0;
	for (int i = 1; i <= a[0]; ++i){
		for (int j = 1; j <= a[1]; ++j){
			long long cur = 1ll * i * j;
			if (cur > k){
				break;
			}
			if (k % cur || k / cur > a[2]){
				continue;
			}
			int p = k / (1ll * i * j);
			ans = max(ans, (1ll * (a[0] - i + 1) * (a[1] - j + 1) * (a[2] - p + 1)));
		}
	}

	cout << ans << '\n';
}

F. Final Boss
题意：给定2个长度为n的数组a和c,和一个h，a代表能量，c代表使用该能量后冷却时间。每轮操作可以使用所有未在冷却时间中的能量攻击h，问最少多少轮可以让h <= 0。如果所有的能量都在冷却，则该轮只能干等。

思路：如果能量总和>=h，那么1次就可以i，否则二分，每个二分点上可以精确的计算出可以攻击的次数。

总结：一开始没读懂题，以为一轮操作只能释放一个能量，于是写了个小顶堆，但是测试样例不过才发现一次可以使用所有的能量。。
求攻击次数时要向上取余。

void solve() {
	int n, h;
	cin >> h >> n;

	vector<int> a(n), c(n);
	for (auto& x : a){
		cin >> x;
	}
	for (int i = 0; i < n; ++i){
		cin >> c[i];
	}
	if (accumulate(a.begin(), a.end(), 0ll) >= h){
		cout << 1 << '\n';
		return;
	}
	long long l = 1, r = (long long)1e18;
	while (l < r){
		long long mid = (l + r) >> 1;
		long long sum = 0;
		for (int i = 0; i < n; ++i){
			sum += 1ll * ((mid + c[i] - 1) / c[i]) * a[i];
			if (sum >= h){
				break;
			}
		}
		if (sum >= h){
			r = mid;
		}
		else{
			l = mid +1;
		}
	}

	cout << l << '\n';
}

G. D-Function

题意：D(n)代表了n的数位和，求给定的区间内，k * D(n) = D(k * n)的数量。

思路：观察样例后发现，满足条件的数每个数位上的数 * K都不会进位，所以每个数位上的数的选择有q = 9 / k + 1中（不包括最高位），从[l, r)每个区间有(q - 1) * pow(q, l) + (q - 1) * pow(q, l + 1) + .. + (q - 1) * pow(q, r - 1) => (q - 1) *(pow(q, l) + pow(q, l + 1) + .. + pow(q, r - 1)) = (q - 1) * pow(q, l) * (pow(q, r - l) - 1) / (q - 1) = pow(q, l) * (pow(q, r - l) - 1)

void solve() {
    long long l, r, k;
    cin >> l >> r >> k;

    if (k >= 10){
        cout << 0 << '\n';
        return;
    }

    MInt q = 9 / k + 1;

    cout << fastPower(q, l) * (fastPower(q, r - l) - 1) << '\n';
}

后面还剩不少时间，有点困了，准备补剩下的题