抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

七つの海

今日、海を見た。もう怖くない

博客

随笔

朋友

归档

关于

Codeforces Round#705 div.2 回顾

七海

题解

发布于：2021年3月11日

次浏览

补题链接：https://codeforces.com/contest/1493/

记录

很捞，ABC 选手都没有当成，属是不是很行（

a.jpg

补了题之后发现这场甚至还算比较简单的，肺都气炸（

题解

A - Anti-knapsack

给定 \(n\) 和 \(k\)，要求选出最大的子集 \(S \subset [1, n]\)，使得不存在集合 \(T \subseteq S\) 满足 \(\sum_{i \in T}i = k\)；

明明是个签到题但是我却白给一发；最开始写的是由前缀和小于 k 的数字构成小于 k 的部分，但是仔细想想就会发现这个数字集合显然不如 k / 2 大==

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt();
    while (T --)
    {
        int n, k;
        $$ n, k;
        int ans = n - k + k / 2;
        println(ans);
        for (int i = (k + 1) / 2; i < k; ++ i)
            print(i, ' ');
        for (int i = k + 1; i <= n; ++ i)
            print(i, ' ');
        println();
    }
    return 0;
}

日常脑瘫操作（

B - Planet Lapituletti

纯暴力就行

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
struct fast_read
{
    template<class name>
    fast_read operator, (name &x)
    {scanner(x); return fast_read{};}
} fastRead;
#define $$ fastRead,

char trans[] = {'0', '1', '5', '-', '-', '2', '-', '-', '8', '-'};

void mirror(const char *s, char *t)
{
    for (int i = 0; i < 5; ++ i)
        if (s[i] == ':') t[4 - i] = ':';
        else t[4 - i] = trans[s[i] - '0'];
    t[5] = 0;
}

auto turn(const char *s)
{
    int H = (s[0] - '0') * 10 + s[1] - '0',
        M = (s[3] - '0') * 10 + s[4] - '0';
    return make_pair(H, M);
}

void make(int H, int M, char *s)
{
    s[0] = H / 10 % 10 + '0';
    s[1] = H % 10 + '0';
    s[3] = M / 10 % 10 + '0';
    s[4] = M % 10 + '0';
    s[2] = ':', s[5] = 0;
}

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt(), h, m;
    const auto validator =
    [&](const char *s)
    {
        for (int i = 0; i < 5; ++ i)
            if (s[i] == '-') return false;
        auto [H, M] = turn(s);
        return H >= 0 && H < h && M >= 0 && M < m;
    };
    const auto tik =
    [&](char *s)
    {
        auto [H, M] = turn(s);
        ++ M; H = (H + M / m) % h;
        M %= m;
        make(H, M, s);
    };
    while (T --)
    {
        char s[6], t[6];
        $$ h, m, s;
        mirror(s, t);
        while (!validator(t))
            tik(s), mirror(s, t);
        println(s);
    }
    return 0;
}

但是代码有点花里胡哨

C - K-beautiful Strings

定义K-美丽的字符串：字符串中所有出现的字符的出现次数都是 k 的整数倍；

现在给 \(n \leq 10^5\) 和 \(k \leq n\)，问可以得到的字典序最小但是字典序大于等于原串的的K-美丽的字符串；如果这样的字符串不存在，输出 -1；

怎么说呢，首先需要明确以下几点：

  • 只有字符串长度为 K 的倍数的字符串才有可能成为题目要求的字符串
  • 因为满足要求的字符串字典序要比原串大，所以尽可能小的唯一方法是尽可能地保留前缀
  • 同上，保留前缀后的第一位的字符一定要大于等于原串对应位置的字符

综上所述，我们可以得到一种优雅并且正确的写法：

  • 如果原串已经是一个 K - 美丽的字符串了，就直接输出
  • 倒序遍历可能维护的前缀长度，并维护前缀不同字符的出现次数
  • 尝试将前缀后的第一个字符修改为任何大于原串的字符
  • 判断除去该字符的后缀能否和前面的已确定字符组成 K - 美丽字符串

然后就可以写出这个题的代码：

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
struct fast_read
{
    template<class name>
    fast_read operator, (name &x)
    {scanner(x); return fast_read{};}
} fastRead;
#define $$ fastRead,

const int N = 1e5 + 5;
int cnt[30];
char s[N], app[N];

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int T = scanner.nextInt(), n, k, need;
    const auto stillNeed =
    [&](int x) {return (k - x % k) % k;};
    const auto alter =
    [&](char ch, int delta)
    {
        need -= stillNeed(cnt[ch - 'a']);
        cnt[ch - 'a'] += delta;
        need += stillNeed(cnt[ch - 'a']);
    };
    while (T --)
    {
        $$ n, k;
        if (n % k) {println(-1); continue;}
        memset(cnt, 0, sizeof cnt);
        $$ s;
        for (int i = 0; i < n; ++ i)
            ++ cnt[s[i] - 'a'];
        for (int i = need = 0; i < 26; ++ i)
            need += stillNeed(cnt[i]);
        if (!need) {println(s); continue;}
        for (int i = n - 1; i >= 0; -- i)
        {
            alter(s[i], -1);
            for (auto alt = s[i] + 1; alt <= 'z'; ++ alt)
            {
                alter(alt, +1);
                if (i + need < n)
                {
                    for (int j = 0; j < i; ++ j)
                        print(s[j]);
                    print((char)alt);
                    int cur = 0, res = n - i - 1;
                    for (char ch = 'a'; ch <= 'z'; ++ ch)
                    {
                        int m = stillNeed(cnt[ch - 'a']);
                        res -= m;
                        while (m --) app[cur ++] = ch;
                    }
                    while (res --) app[cur ++] = 'a';
                    app[cur] = 0;
                    sort(app, app + cur);
                    println(app);
                    goto complete;
                }
                alter(alt, -1);
            }
        }
        complete: continue;
    }
    return 0;
}

实际上也没有那么多需要注意的地方，关键就在于最开始写代码的思路是否正确）如果抓着修改字符来看的话，代码会难想而且难写许多，浪费比赛时间。

D - GCD of an Array

给一个长度为 \(n \leq 2 \cdot 10^5\) 的数组 \(a\)，满足 \(a_i \leq 2 \cdot 10^5\)；

然后对这个数组进行 \(q \leq 2 \cdot 10^5\) 次操作：单点修改为原来的 \(x\) 倍，且 \(x \leq 2 \cdot 10^5\)；

在每次操作后，要求输出现在数组的 gcd 对于 1e9 + 7 的模数。

STL 嗯做题：首先要意识到将所有的 \(a_i\) 分解成 \(\prod p_j^{k_i}\) 的形式，那么 GCD 可以表示为 \(\prod p_j^{\textrm{min}k_i}\)；又因为修改只有单点倍增，GCD 只会有增无减；所以可以考虑用 STL 维护每个数组成员的分解结果，以及整个数组每个质因子的分解结果集合，需要支持查询最小值；

这样，每当进行单点修改时，我们就可以通过更新分解结果，然后更新数组质因子的维护结果，并借此更新答案

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
75
76
77
78
79
80
81
82
83
#define $$ fastRead,

template <int n> auto &EulerSieve()
{
    static vector<int> prime;
    static array<int, n + 1> vis;
    for (int i = 2; i <= n; ++ i)
    {
        if (!vis[i])
            prime.push_back(i), vis[i] = i;
        for (auto & pp : prime)
        {
            if ((longs)i * pp > n) break;
            vis[i * pp] = pp;
            if (i % pp == 0) break;
        }
    }
    return vis;
}

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

longs fastPow(longs a, ulongs b)
{
    longs ans = 1;
    while(b)
    {
        if (b & 1u) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1u;
    }
    return ans % mod;
}

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int n, q, a;
    longs ans = 1;
    auto pp = EulerSieve<N>();
    vector<unordered_map<int, int>> part;
    unordered_map<int, multiset<int>> maintain;
    const auto update =
    [&](int div, int last)
    {
        if (maintain[div].size() != n) return;
        int now = *maintain[div].begin();
        ans = ans * fastPow(div, now - last) % mod;
    };
    const auto alter =
    [&](int i, int x)
    {
        while (1 != x)
        {
            auto div = pp[x], cnt = 0;
            while (div == pp[x])
                ++ cnt, x /= div;
            auto old = part[i][div];
            part[i][div] += cnt;
            int last = 0;
            if (maintain[div].size() == n)
                last = *maintain[div].begin();
            if (old)
            {
                auto it = maintain[div].find(old);
                maintain[div].erase(it);
            }
            maintain[div].insert(old + cnt);
            update(div, last);
        }
    };
    $$ n, q, part.resize(n + 1);
    for (int i = 1; i <= n; ++ i) $$ a, alter(i, a);
    int i, x;
    while (q --) $$ i, x, alter(i, x), println(ans);
    return 0;
}

E - Enormous XOR

对于两个大整数 \(l\) 和 \(r\)（\(l \leq r\)），定义函数： \(G_{l, r} = \bigoplus_{i=l}^ri\)，\(F _ {l, r} = \mathrm{max} _ {l \leq x \leq y \leq r} G _ {x, y}\)；

现在给定 \(l\) 和 \(r\) 的二进制表示形式（\(l \leq r < 2^{10^6}\)）；要求求出 \(F_{l, r}\) 的值。

抖机灵题：令 \(l\) 和 \(r\) 的最高位分别为 \(H_l\)，\(H_r\)；

如果 \(H_l \ne H_r\)，那么显然有 \(F_{l, r} = 2^{H_r + 1} - 1\)：因为 \(2^{H_r},\ 2^{H_r} - 1 \in [l, r]\) 显然成立，而 \(2^{H_r} \oplus (2^{H_r} - 1) = 2^{H_r + 1} - 1\)；否则，答案至少有最大值 \(r\)；考虑选出答案的区间：为了保持可能存在的最高位存在，得到答案的区间 \([x, y]\) 的大小必定是奇数；且不难想到其中 \(y = r\)；

我们考虑 \(r\) 的奇偶性：

  • 如果 \(r\) 为奇数，因此除了最大的一个数字之后，最大的数字是 \(r - 1\)——除了奇数位之外和 \(r\) 完全一致；不难发现区间中的数字是成对出现的，因此 \(r\) 能确定保留的位只有奇数位，不如 \(r\) 优；
  • 如果 \(r\) 为偶数，同理，显然最低位（奇偶位）必然为 1，所以异或值为 \(r + 1\)，更优；

但是以上操作都要建立在区间 \([l, r]\) 允许的情况下；如果允许区间小于 3，则无法进行上述操作，答案为 \(r\)；

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
#define $$ fastRead,

const int N = 1e6 + 5;
char l[N], r[N], ans[N], tmp[N];

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int n = scanner.nextInt();
    $$ l, r;
    int hl = 0, hr = 0;
    while (l[hl] != '1') ++ hl;
    while (r[hr] != '1') ++ hr;
    if (hl != hr)
    {
        for (int i = min(hl, hr); i < n; ++ i)
            ans[i] = '1';
        for (int i = 0; i < min(hl, hr); ++ i)
            ans[i] = '0';
        ans[n] = '\0';
    }
    else if (r[n - 1] == '1')
        memcpy(ans, r, sizeof ans);
    else
    {
        memcpy(tmp, r, sizeof tmp);
        for (int i = n - 2; i >= 0; -- i)
            if (tmp[i] == '1')
            {tmp[i] = '0'; break;}
            else tmp[i] = '1';
        memcpy(ans, r, sizeof ans);
        if (strcmp(tmp, l) >= 0) ans[n - 1] = '1';
    }
    println(ans);
    return 0;
}

F - Enchanted Matrix

这是一个交互题；有一个 \(n \times m\) 的矩阵，求合法的 \((x, y)\) 的数对个数：

合法的 \((x, y)\) 数对的定义：可以将原矩阵完整的划分为一些 \(x \times y\) 的子矩阵，这些子矩阵相等。

最多可以询问 \(3 \cdot \lfloor \textrm{log}_2(n + m) \rfloor\) 次两个不相交的子矩阵是否相等。

分析

首先可以意识到这个问题中行列是互相独立的问题：显然有 [x, y] === [x, m] && [n, y]

然后再一个显然的就是要求出这个数对，必须要先求出行列方向上的最短循环节，再由循环节凑出其他的答案——这是一个很常见的套路：串的分多段全等的问题可以转化为找它的最短循环节。

如何在单维（也就是一个串）中寻找最短的循环节呢？我们首先利用筛预处理出范围内整数的质因数分解，然后以每一个质因数作为本次分段数，在上一次分割后的循环节上进行尝试；最后剩下的没有被除去的质因数的乘积就是最短循环节的长度。

那么如何判断分出的段在当前串中是否是循环节呢？

首先，如果不考虑重叠的限制条件，对于任何串的候选循环节；我们先令该串包含了 \(L\) 个候选循环节，候选循环节的长度为 \(x\)：这样，我们只需要比较原串长度为 \((L - 1)x\) 的前缀和长度为 \((L - 1)x\) 的后缀是否相等即可；也就是前 \(L - 1\) 节和后 \(L - 1\) 节是否相等；这也是很容易证明的；

但是题目限制了不允许询问重叠的区间，所以上述做法在这并不可行；但是我们还是可以基于这种思路，采用迂回的办法来完成询问；因为我们每次都是对于一个串（原串或者已经被分割后的），使用它长度的质因数来作为划分段数；令划分的段数为 \(L\)，这里的段显然和上面说的候选循环节由相同的意义。

因为 \(L\) 是质因数，所以只有可能是两种情况：

  • \(L = 2\)，此时直接询问两段是否相等即可；
  • \(L > 2\)，此时 \(L\) 必定是奇数；令 \(l = \lfloor \frac{L}2 \rfloor\)；
    • 我们选取前 \(l\) 段作为中转，那么还剩下连续的 \(l + 1\) 段
    • 剩下的 \(l + 1\) 段也是奇数，可以使用最初说的方法进行判断
    • 但是我们不直接比较重叠的两段，而是让它们分别于前面选出的中转段进行比较
  • 这样就可以在 2 次询问之内判断一个候选循环节是否是串的循环节

综上所述，我们就可以在题目规定的询问次数之内完成最小循环节的求解了；

还需要特别注意的是，答案并不是最小循环节划分的段数的乘积；而是划分段数的因数个数的乘积。

代码

下面代码的欧拉筛以经过修改：可以使用代码中的办法从小到大地获取一个整数的质因数。

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
const int N = 1005;

int ask(int h, int w, int x1, int y1, int x2, int y2)
{
    cout << "? " << h << ' ' << w << ' ' << x1 << ' '
         << y1 << ' ' << x2 << ' ' << y2 << endl;
    int tmp; cin >> tmp; return tmp;
}

template <int n> auto &sieve()
{
    static vector<int> prime;
    static array<int, n + 1> vis;
    for (int i = 2; i <= n; ++ i)
    {
        if (!vis[i])
            prime.push_back(i), vis[i] = i;
        for (auto & pp : prime)
        {
            if ((longs)i * pp > n) break;
            vis[i * pp] = pp;
            if (i % pp == 0) break;
        }
    }
    return vis;
}

signed main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
#if 0
    freopen("in.txt", "r", stdin);
#endif
    int n, m;
    auto p = sieve<N>();
    const auto askM =
    [&](int len, int time) -> bool
    {
        const auto h = n, w = time / 2 * len;
        if (time == 2)
            return ask(h, w, 1, 1, 1, w + 1);
        else return
            ask(h, w, 1, 1, 1, w + 1) &&
            ask(h, w, 1, 1, 1, w + len + 1);
    };
    const auto askN =
    [&](int len, int time) -> bool
    {
        const auto h = time / 2 * len, w = m;
        if (time == 2)
            return ask(h, w, h + 1, 1, 1, 1);
        else return
            ask(h, w, h + 1, 1, 1, 1) &&
            ask(h, w, h + len + 1, 1, 1, 1);
    };
    cin >> n >> m;
    auto [nn, mm] = make_pair(n, m);
    for (int i = nn; i > 1; i /= p[i])
        if (askN(nn / p[i], p[i])) nn /= p[i];
    for (int i = mm; i > 1; i /= p[i])
        if (askM(mm / p[i], p[i])) mm /= p[i];
    const auto nt = n / nn, mt = m / mm; 
    longs np = 0, mp = 0;
    for (int i = 1; i <= nt; ++ i) np += !(nt % i);
    for (int i = 1; i <= mt; ++ i) mp += !(mt % i);
    cout << "! " << np * mp << endl;
    return 0;
}

最后不能直接输出 nt * mt！

后记

参考资料

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://shiraha.cn/2021/codeforces-round-705-div2/

更新于：2021年3月11日

算法

ACM

Codeforces

评论