Codeforces Round 844(id 1782) 题解

Posted on In ,

比赛链接

可以参考这篇题解.

A - Parallel Projection

题意: 给一个长宽高分别为 \(w, d, h\) 的长方体, 并给出下底面上一点 \((a, b)\) 和上底面上一点 \((f, g)\), 求沿着长方体表面两点间的最短距离.

展开题解

一道初中题. 容易发现, 仅经过一个侧面最佳, 那就分别沿着四个方向展开, 算出展开后顶面那点到底面的投影, 再求曼哈顿距离即可, 取四个中的最小值. 时间复杂度 \(O(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
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int INF = 0x3f3f3f3f;
int w, d, h, a, b, f, g;
int Dist(int a, int b, int x, int y) {
    return abs(a - x) + abs(b - y);
}
void work() {
    cin >> w >> d >> h >> a >> b >> f >> g;
    int ans = INF;
    ans = min(ans, Dist(a, b, f, -h-g));
    ans = min(ans, Dist(a, b, -h-f, g));
    ans = min(ans, Dist(a, b, f, d+h+d-g));
    ans = min(ans, Dist(a, b, w+h+w-f, g));
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
        work();
    return 0;
}

B - Going to the Cinema

题意: 有 \(n\) 个人, 每个人有个 \(a_i\). 每人说一句断言: 我去电影院当且仅当除我以外去的人不少于 \(a_i\) 个. 现在要使全部人说的断言均为真(请注意到这是一句双蕴含的命题, 这个人本身不一定要去), 则请问有几种去的人的选择?

展开题解

我们把 \(a_i\) 从小到大排序, 即保证 \(a_1\le a_2\le \cdots \le a_n\). 设 \(i\) 去而 \(j\) 不去, 一共去了 \(t\) 人, 根据上面的断言我们有: 一方面, \(i\) 去, 那么 \(t\ge a_i+1\); 另一方面, \(j\) 不去, 则 \(t < a_j\), 可知 \(a_i+1<a_j\), 一必要条件是 \(i<j\). 所以我们发现, 这相当于把序列分成两部分, 前一部分全去, 后一部分全不去. 枚举 \(i\), 设 \(1\) 到 \(i(0\le i\le n)\) 去, \(i+1\) 到 \(n\) 不去, 则要求不等式 \(a_i+1\le i<a_{i+1}\) 满足, 验证即可. 注意处理一下边界. 时间复杂度 \(O(n\log n)\), 瓶颈在于排序.

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
#include <iostream>
#include <algorithm>
using namespace std;


constexpr int MAXN = 2e5 + 5;
int n, a[MAXN];
void work() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    a[0] = -1; a[n+1] = n+1;
    int ans = 0;
    for(int i = 0; i <= n; i++)
        if(a[i] + 1 <= i && i <= a[i+1] - 1)
            ++ans;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
        work();
    return 0;
}

C - Equal Frequencies

题意: 给一个长度为 \(n\) 的字符串, 只能含小写字母, 问最少的替换操作, 使得里面所有出现过的字符一样多.

展开题解

首先, 我们枚举一下, 最终串中出现的字母种类 \(s\), 可知 \(1\le s\le 26\) 且 \(s\mid n\), 则最终每种字符要出现 \(n/s\) 次. 我们贪心地选择原串中出现次数前 \(s\) 多的字母最后变成 \(n/s\) 种. 这里可以简单证明一下这个贪心为什么是对的:

设 \(i\) 和 \(j\) 两种字符出现次数分别是 \(c_i\) 和 \(c_j\), 则选 \(i\) 不选 \(j\) 的代价是 \(c_j+\max\lbrace 0, c_i-n/s\rbrace\), 选 \(j\) 不选 \(i\) 的代价是 \(c_i+\max\lbrace 0, c_j-n/s\rbrace\). 则选 \(i\) 的理由是 \(c_j+\max\lbrace 0, c_i-n/s\rbrace \le c_i+\max\lbrace 0, c_j-n/s\rbrace\), 简单化简一下可知 \(c_i\ge c_j\).

于是排个序后, 把需要减少的字符(对于前 \(s\) 种要保留的字符, 则它比 \(n/s\) 多的次数; 对于后 \(26-s\) 种不保留的字符, 则它比 \(0\) 多的次数)的次数记录下来, 把需要增加的字符(前 \(s\) 种中比 \(n/s\) 少的次数)放进一个队列中. 最后, 扫一边原串, 如果当前位置原来的字符需要减少, 那么从队列中拿一个新的字符替换.

总时间复杂度 \(O(s(s\log s + n))\), 此处 \(s\) 为字符集大小 \(26\).

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
constexpr int INF = 0x3f3f3f3f;
int n;
string s;
vector<int> snum, id;
vector<int> add, mns;

bool cmp(int a, int b) {
    return snum[a] > snum[b];
}

void work() {
    cin >> n >> s;
    int ans = INF;
    string ansstring;
    snum = vector<int>(26);
    for(auto ch : s)
        snum[ch - 'a']++;
    for(int ty = 1; ty <= 26; ty++)
        if(n % ty == 0) {
            id = vector<int>(26);
            for(int i = 0; i < 26; i++)
                id[i] = i;
            int eve = n / ty;
            sort(id.begin(), id.end(), cmp);
            add = vector<int>();
            mns = vector<int>(26);
            for(int i = 0; i < ty; i++) {
                int c = id[i];
                if(snum[c] < eve) {
                    for(int k = snum[c]; k < eve; k++)
                        add.push_back(c);
                } else if(snum[c] > eve) {
                    for(int k = snum[c]; k > eve; k--)
                        mns[c]++;
                }
            }
            for(int i = ty; i < 26; i++) {
                int c = id[i];
                for(int k = snum[c]; k > 0; k--)
                    mns[c]++;
            }
            int ret = 0;
            string retstring = s;
            for(auto &ch : retstring) {
                int c = ch - 'a';
                if(mns[c]) {
                    ch = add.back() + 'a';
                    add.pop_back();
                    mns[c]--;
                    ret++;
                }
            }
            if(ret < ans) {
                ans = ret;
                ansstring = retstring;
            }
        }
    cout << ans << '\n' << ansstring << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
        work();
    return 0;
}

D - Many Perfect Squares

给 \(n\) 个互不相同的数 \(a_i\), 对于所有的 \(x\) 满足 \(0\le x\le 10^{18}\), 求序列 \(\lbrace a_i+x\rbrace\) 中完全平方数的个数的最大值.

数据范围: \(1\le n\le 50, 1\le a_1<a_2<\cdots < a_n\le 10^9\).

展开题解

首先显然, 答案至少为 \(1\).

我们接下来看答案是否可以 \(\ge 2\).

在这种情况下, 必然存在两个数 \(a_p, a_q\)(不妨设 \(p<q\)), 满足 \(a_p+x=f^2, a_q+x=g^2\), 那么 \(a_q-a_p=g^2-f^2=(g-f)(g+f)\). 我们枚举 \(a_q-a_p\) 的小的那个因数 \(t:t\mid (a_q-q_p)\ \textnormal{and}\ t^2\le a_q-a_p\), 则令 \(g-f=t, g+f=(a_q-a_p)/t\), 求出 \(g\), 从而求出这种情况的 \(x\) 来. 接下来, 只需要枚举一遍序列看看这个 \(x\) 的情况的答案了.

也许你会对这个做法的时间复杂度有疑问. 首先, \(O(n^2)\) 的枚举是必要的. 接下来, 我们会使用 \(O(\sqrt V)\) 枚举因数. 如果枚举到因子, 还需要多一个 \(O(n)\). 时间复杂度为 \(O(n^2\sqrt V+n^3\operatorname{Maxd}(V))\), 其中 \(\operatorname{Maxd}(V)\) 表示 \(1\sim V\) 范围内因数个数函数 \(d(n)\) 的最大值. 这个上界还算松. 其中 \(n\) 取 \(\le 50\), \(V\) 取 \(\le 10^9\).

关于该函数的一些结论:

OEIS A066150 列出了对于 \(1\le x< 10^n\) 的数, \(d(x)\) 的最大值, 几近可以认为数列第 \(n\) 项 \(a_n\) 就等于 \(\operatorname{Maxd}(10^n)\).

查表我们发现, 这个函数 比 \(t^{\lg 2}\) 增长还慢)

比较有用的结论是, \(a_9=\operatorname{Maxd}(10^9)=1344, a_{18}=\operatorname{Maxd}(10^{18})=103680\).

更加具体的问题可以去看 这道题

有上面的分析后, 一通计算, 我们发现这个时间复杂度确实可以接受...

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
55
56
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
constexpr int MAXN = 55;
int n, a[MAXN], ans;

ll sqr(ll x) {
    return x * x;
}
bool issquare(ll x) {
    return sqr(ll(sqrt((double)x) + 0.5)) == x;
}
int gett(ll t) {
    int ret = 0;
    for(int i = 1; i <= n; i++)
        if(issquare(a[i] + t))
            ret++;
    //cerr << '(' << t << ' ' << ret << ')' << endl;
    return ret;
}
void check(int p, int q) {
    int val = a[q] - a[p];
    for(int i = 1; 1ll * i * i <= val; i++)
        if(val % i == 0) {
            int xny = i, xpy = val / i;
            if(xny % 2 != xpy % 2)
                continue;
            int x = (xpy - xny) / 2;
            ll t = 1ll * x * x - a[p];
            if(t < 0)
                continue;
            ans = max(ans, gett(t));
        }
}
void work() {
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    ans = 1;
    for(int i = 1; i <= n; i++)
        for(int j = i+1; j <= n; j++)
            check(i, j);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
        work();
    return 0;
}