CF Round #822 题解

Un1quAIoid · 2022-09-24 13:25:43 · 个人记录

A

题目大意

给定 n 个数 a_i，一次操作可以选一个数使其 +1 或 -1，问使得能够选出三个相等的数的最小操作数。

sol.

首先最终选出的三个数的值一定是三个数初始值的中位数，比较显然，然后就只需要给 a_i 排序，枚举中位数 a_i，对 a_{i+1}-a_{i-1} 取 \min 即可。

时间复杂度 O(n \log n)。

B

题目大意

有一个金字塔，第 i 层有 i 个房间，房间 (i,j) 可以通向房间 (i+1,j),(i+1,j+1)，在房间 (i,j) 放置火把可以给所有它能到达的房间增加 1 的亮度值，你现在可以在若干个房间放置火把，给定 n，求出使得房间 (1,1),(2,1) \dots (n,1) 的亮度值之和最大、对于 [1,n] 每一层内的房间都有相同亮度值的方案。

sol.

首先第 i 层所有房间的最大亮度值是 i，因为只有 i 个房间能够到达 (i,1)，然后只需要在每一层的第一个和最后一个房间放置火把即可达到这个上界并满足限制。

C

题目大意

初始你有一个集合 S，包含 1 \dots n 的 n 个正整数，每次操作你可以选择一个正整数 k，删掉 S 中最小的 k 的倍数，并花费 k 的代价，求出使得 S 变成 T 的最小代价。

sol.

考虑贪心，从 1 到 n 枚举 k，把能删的数全删掉。从小到大依次枚举 k 的倍数 i，若 i 需要保留，说明不能再用 k 删数，直接枚举下一个 k，否则若 i 没有被删过，则将总代价加上 k。

时间复杂度为调和级数 O(n \log n)。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e6+5;

int n;
char s[MAXN];
bool use[MAXN];
ll ans;

void solve() {
    for (int i = 1; i <= n; i++) use[i] = 0;

    scanf("%d", &n);
    scanf(" %s", s + 1);

    ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            if (s[j] == '1') break;
            if (!use[j]) use[j] = 1, ans += i;
        }
    }

    printf("%lld\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

D

题目大意