Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 – Elimination Round) A-D

比赛链接

A

题意

设计一条线路要贴着6个墙面走,从 ((a,b))((f,g)) ,线路长度最短。

题解

知识点:模拟。

分类取最短即可。

时间复杂度 (O(1))

空间复杂度 (O(1))

代码

#include 
#define ll long long

using namespace std;

bool solve() {
    int w, d, h;
    int a, b, f, g;
    cin >> w >> d >> h;
    cin >> a >> b >> f >> g;
    int ans = h + min(abs(a - f) + min(b + g, 2 * d - b - g), abs(b - g) + min(a + f, 2 * w - a - f));
    cout > t;
    while (t--) {
        if (!solve()) cout 

B

题意

(n) 个人要去电影院,第 (i) 个人要求至少 (a_i) 个其他人去他才去,问最终能有多少种选人去电影院的方案,保证每种方案选完后所有符合要求的都去了。

题解

知识点:贪心。

从小到大排序。如果低要求的人能去就先去,保证要求高的人去之前能去的都去。如果低要求的都去不了,换成高要求的更去不了,不如先预选低要求的,看看后面能不能补上。如此,可以得到所有方案。

因为可以都不去,所以如果第一个人就有 (geq 1) 的要求时,显然是可以都不去的。

对于 (iin[1,n)) ,如果 (a_i leq i-1)(a_{i+1} > i) ,说明 ([1,i]) 都能去,但不能直接选 (i+1) ,因为缺人需要继续安排后面的看看能不能补上,所以这里可以方案加一。

其他情况,([1,i+1]) 都能去则必须安排在一个方案;([1,i+1]) 都不能去,继续选,不能算做一个方案;([1,i]) 不能去,但 ([1,i+1]) 可以去,此时要继续往后选,让这个方案能去的人都去。

最后,上述判断包括不了全都去,因此特判方案加一。

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

空间复杂度 (O(n))

代码

#include 
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i > a[i];
    sort(a + 1, a + n + 1);
    int ans = 0;
    if (a[1] != 0) ans++;
    for (int i = 1;i  i) ans++;
    }
    ans++;
    cout > t;
    while (t--) {
        if (!solve()) cout 

C

题意

给出一个小写字母的字符串,每次修改可以使一个位置的字母替换成任意字母,求出修改的最少次数,使字符串的字母出现次数相同,并输出修改后的字符串。

题解

知识点:模拟,枚举,贪心。

注意到,直接枚举最后的个数很困难,但枚举最后有几种字母很容易,因此考虑枚举最后剩多少种字母。

接下来分两步走:

  1. 确定最少要变多少位置,同时确定最少答案情况的字母种数。
  2. 通过上一步确定的信息,遍历字符串更改。

第一步:

先将每个字母对应的出现次数记录好,同时保存字母本身的序号,方便排序后还能找到对应的字母。

枚举字母种数 (i) ,满足 (i mid n) ,则最终每种字母会有 (x = dfrac{n}{i}) 个。我们可以贪心地选择保留数量最多的前 (i) 个,这些字母中数量大于 (x) 是必须修改的,而后 (26-i) 个字母,全部都需要修改。于是,就可以求出 (i) 对应的修改次数 (delta) ,枚举取最小值,并记录最终种数 $div $ 和每种数量 (cnt),即可。

第二步:

我们此时需要遍历字符串修改,因此需要通过字母序号得到字母的排名(从 (0) 开始)和数量,所以需要遍历第一步得到的排名对应数量和序号的数组获得。

若某个位置的字母的数量大于 (cnt) 或者排名大于等于 (div) 并且字母的数量大于 (0) 则需要修改,枚举 (26) 个字母找到排名小于 (div) 且数量小于 (cnt) 的填充进去即可。

时间复杂度 (O(n))

空间复杂度 (O(n))

代码

#include 
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector> rk(26);
    for (int i = 0;i >());
    int div = 1;
    int ans = 1e9;
    for (int i = 1;i > pos(26);
    for (int i = 0;i  cnt || pos[s[i] - 'a'].second >= div && pos[s[i] - 'a'].first) {
            pos[s[i] - 'a'].first--;
            for (int j = 0;j > t;
    while (t--) {
        if (!solve()) cout 

D

题意

给出一个数组 (a_i in [1,10^9]) ,求出 (x in [0, 10^{18}])(a_1+x,cdots,a_n+x) 中完全平方数的数量的最大值。

题解

知识点:枚举,因数集合。

显然,必然存在 (x) 使得 (a+x) 是个完全平方数,答案至少为 (1) 。考虑答案为 (2) 及以上的情况。

我们可以先枚举所有两个数的组合 (a_i,a_j(i ,如果存在大于等于 (2) 的答案,必然会包括这些两个数的组合,因而我们可以通过两个数枚举出所有成立的 (x) ,对每个 (x) 在完整的数组中再跑一遍记录答案即可。

我们考虑如何得到使 (a_i+x,a_j+x) 都成为完全平方数的 (x) 。设 (a_i+x = s^2,a_j+x = t^2) ,直接枚举 (x) 复杂度是 (10^9) ,考虑枚举 (s,t) 相关的数。我们可以得到 (a_j-a_i = t^2-s^2 = (t+s)(t-s) in [1,10^9)) , 因此我们可以枚举 (t+s,t-s) ,即枚举 (a_j-a_i) 的因子即可,我们最多只需要枚举 (sqrt {10^9}) 次即可,然后再求出 (t,s) ,就可以得到 (x) 了。

时间复杂度 (O(n^2sqrt{10^9}))

空间复杂度 (O(n))

#include 
#define ll long long

using namespace std;

bool issqr(ll n) {
    ll x = sqrt(n);
    return x * x == n;
}

int a[57];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i > a[i];
    int ans = 1;
    for (int i = 1;i > t;
    while (t--) {
        if (!solve()) cout 

文章来源于互联网:Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) A-D

THE END
分享
二维码