抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

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

博客

随笔

朋友

归档

关于

Codeforces Round#708 div.2 回顾

题解

发布于：2021年3月18日

补题链接：Dashboard - Codeforces Round #708 (Div. 2) - Codeforces

记录

推特做题术

7_QMZFWQ_2JMS4Z46F_T9.png

虽然还是勉强保住了 ABC 选手的尊严，但是这场题目是真的偏简单…… ABC 连两千名都进不了（）明明参加人数就只有两万人不到，可以说是很捞了== 赛后一看 E1 比 D 简单，C2 比 C1 简单，也真神秘（

题解

A - Meximization

看样例猜解法：

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 = scanner.nextInt();
        map<int, int> cnt;
        for (int i = 1; i <= n; ++ i)
            ++ cnt[scanner.nextInt()];
        for (auto [i, ii] : cnt)
            print(i, ' ');
        for (auto [i, ii] : cnt)
            while (-- ii) print(i, ' ');
        println();
    }
    return 0;
}

B - M-arrays

按照mod m\mathrm{mod} \ m 进行分组统计答案就行：

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
const int N = 1e5 + 5;
int a[N], cnt[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();
    while (T --)
    {
        int n = scanner.nextInt(),
            m = scanner.nextInt();
        for (int i = 1; i <= n; ++ i)
            a[i] = scanner.nextInt();
        memset(cnt, 0, sizeof(int) * m);
        for (int i = 1; i <= n; ++ i)
            ++ cnt[a[i] % m];
        int ans = bool(cnt[0]), lim = m / 2;
        for (int i = 1; i <= lim; ++ i)
        {
            auto aa = cnt[i], bb = cnt[m - i];
            if (!aa && !bb) continue;
            ans += max(abs(bb - aa), 1);
        }
        println(ans);
    }
    return 0;
}

C1 - k-LCM (easy version)

实际上没我代码写的那么复杂；如果是奇数的话就输出 1 k/2 k/2 就行，偶数但是不是 4 的倍数的话就是 2 k/2-1 k/2-1；再不然就是 n/2 n/4 n/4；不用看了，肯定是对的 ==

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
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 = scanner.nextInt(),
            k = scanner.nextInt();
        if (__builtin_popcount(n) == 1)
        {
            print(n / 2, ' ', n / 4, ' ', n / 4, '\n');
            continue;
        }
        longs mod2 = 1;
        while (!(n % 2)) n /= 2, mod2 *= 2;
        int tmp = n / 2;
        print(mod2, ' ', mod2 * tmp, ' ', mod2 * tmp, '\n');
    }
    return 0;
}

C2 - k-LCM (hard version)

这个题目就更搞了…… 因为服务器中途宕机的原因，我交的很慢，甚至还因为原想法过于花哨边界条件太多而 wa 了一发（）但是实际上这个题比 C1 还要简单：

对于 n 和 k，只需要先输出 k - 3 个 1，然后再用 C1 的办法处理就行了（（（

显然，C1 的办法保证得到的三个数的 LCM 满足 lcm <= (k - 3) / 2，而我们其他的数都是 1，对 lcm 没有任何贡献，所以最后的结果显然也是满足题意的（

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
void C1(int n)
{
    if (n % 2) print("1 ", n / 2, ' ', n / 2);
    else if (n % 4) print("2 ", n / 2 - 1, ' ', n / 2 - 1);
    else print(n / 2, ' ', n / 4, ' ', n / 4);
}

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 = scanner.nextInt(),
            k = scanner.nextInt();
        int m = k - 3; C1(n - m);
        while (m --) print(" 1");
        println();
    }
    return 0;
}

就不贴我赛场上写的丑陋的甚至还 WA 了一发代码了…… 我真傻，真的（

XJQ1VOCX5_3_D_4ML2KN.png

还是不够机智==

D - Genius

有1…n1 \dots n 共n≤5000n \leq 5000 个位置：ii-th 位置有tagitag_i、ci=2ic_i = 2^i 和sis_i 分数；初始有IQ=0\mathrm{IQ} = 0 和S=0S = 0；

如果你当前在ii 点，那么仅当IQ<∣ci−cj∣\mathrm{IQ} < |c_i - c_j| 和tagi≠tagjtag_i \ne tag_j 同时满足时才能到达jj 点；
到达jj 点之后，你的IQ\mathrm{IQ} 变为∣ci−cj∣|c_i - c_j|，并且获得∣si−sj∣|s_i - s_j| 分数；

你可以任意选择起点，问你可以获得的最大分数；

特别说明：内存限制 32MB

首先，定义边权wi,j=∣ci−cj∣w_{i, j} = |c_i - c_j|；显然所有的边的“边权”都是不同的；然后考虑动态规划：定义FiF_i 表示最后停留在点ii 最大能获得的分数；显然最初情况下全部为 0；然后转换题目限制条件，进行转移：

  • tagi≠tagjtag_i \ne tag_j：这个简单，如果不满足直接阻止对应的转移就行了。
  • IQ<∣ci−cj∣\mathrm{IQ} < |c_i - c_j|：意思就是说走的边越来越长；因此我们总是先转移短边再转移长边就行。

综上所述，我们就可以在一维 DP 内完成答案的求解；

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
const int N = 5050;
int s[N], tag[N];
longs dp[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();
    while (T --)
    {
        int n = scanner.nextInt();
        for (int i = 1; i <= n; ++ i)
            tag[i] = scanner.nextInt();
        for (int i = 1; i <= n; ++ i)
            s[i] = scanner.nextInt();
        memset(dp, 0, sizeof(longs) * (n + 1));
        for (int i = 1; i <= n; ++ i)
            for (int j = i - 1; j; -- j)
                if (tag[i] != tag[j])
                {
                    auto ii = dp[i], jj = dp[j];
                    auto add = abs(s[i] - s[j]);
                    maximize(dp[i], jj + add);
                    maximize(dp[j], ii + add);
                }
        println(*max_element(dp + 1, dp + 1 + n));
    }
    return 0;
}

有的时候想问题还是要跳出局部纵观全体；像这个题就是做的时候视野集中在走的策略上，并且还被预处理 tag 连通块的想法所牵制，最后离正解渐行渐远（

E1 - Square-free division (easy version)

给定长度为n≤2⋅105n \leq 2 \cdot 10^5 的数组；现在你需要将数组划分成一些连续的段，使得每个段中不包含两个数，它们的乘积为完全平方数；求满足此要求可以划分的最少的段数。

首先肯定要对数组里每个数字进行分解质因数；因为相乘就是分解质因数得到的多项式的指数相加，而完全平方数分解得到的多项式的指数均为 2；那么我们可以得到结论：如果 x 和 y 的乘积是完全平方数，那么 x 和 y 分解质因数得到的多项式中关于每一个质数的指数都是mod 2\mathrm{mod} \ 2 相等的。

因此，我们只需要记录每个元素质因数分解之后指数mod 2\mathrm{mod} \ 2 的情况，然后划分不包含相同 pattern 的元素即可：这样，这个问题就退化为划分不包含相等数字的段；众所周知，这个问题可以贪心的解决。

那么应该如何维持这个 pattern 呢？使用一个很大的 bitset 嘛？完全没有必要：因为ai≤107a_i \leq 10^7，那么质因子指数不会超过 1 的 pattern 的乘积自然也不会超过这个限制；所以只需要将它们乘起来就可以了，即快又优雅（

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
const int N = 2e5 + 5, A = 1e7 + 7;
int a[N], pattern[N];

// PrimeFactorizationSieve()
namespace PFS {...}

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();
    using PFS::prime, PFS::fact;
    PFS::start();
    while (T --)
    {
        int n = scanner.nextInt(),
            k = scanner.nextInt();
        for (int i = 1; i <= n; ++ i)
            a[i] = scanner.nextInt();
        fill(pattern, pattern + n + 1, 1);
        for (int i = 1; i <= n; ++ i)
        {
            int exp = 0, base = 0, tmp = a[i];
            while (tmp > 1)
            {
                int p = fact[tmp];
                if (base == p) ++ exp;
                else
                {
                    if (exp % 2) pattern[i] *= base;
                    base = p, exp = 1;
                } tmp /= p;
            }
            if (exp % 2) pattern[i] *= base;
        }
        int ans = 1;
        set<int> unique;
        for (int i = 1; i <= n; unique.insert(pattern[i ++]))
            if (unique.count(pattern[i])) ++ ans, unique.clear();
        println(ans);
    }
    return 0;
}

真就比 D 简单呗？以后打 CF 也不能盯着一个题死看了，得适当设定递归深度（（

话说我的欧拉筛写成函数竟然会过不了编译（提示编译得到的文件过大），只好拆成命名空间的形式才能过，倒是挺神秘的有点==

E2 - Square-free division (hard version)

在 E1 的基础上，你获得了k≤20k \leq 20 次的单点修改的机会：你可以将任意位置修改为任意数字不超过kk 次；

看到 k 非常的小，所以可以考虑 DP；令 DP 数组Fi,jF_{i, j} 的含义是在长度为 i 的前缀中，允许不超过 j 次的修改，可以得到的最少的分段数；那么，我们至少可以考虑到两种显然的转移：

  • 若j>0j > 0，那么显然可以从Fi,k(k<j)F_{i,k} (k < j) 转移到Fi,jF_{i, j}；
  • 若区间(i,k](i, k] 消耗了xx 次修改而得以连续，那么Fk,j+x=Fi,j+1F_{k, j + x} = F_{i, j} + 1

因此，如果我们可以维护一段区间维持连续而消耗的次数，就可以利用第二种转移求出最后的答案；

当然，我们不可能去维护所有的区间；将第二种转移反过来，我们只需要维护对于每一个满足x≤jx \leq j 的修改次数，以一个确定的右端点ii，可以到达的最远的左端点ll 即可。这样的转移一定是更优的。而预处理求出这个距离也并不难；我们依然可以像 E1 那样通过一次遍历就完成维护（因为 pattern 的大小是有限的，我们可以使用桶来去重而不是 set，这样时间复杂度就是线性的）；维护kk 中不同的修改情况的复杂度是O(nk)O(nk) 的；

这样，我们就可以利用上面说到的两种转移方法进行转移了；时间复杂度是O(nk2)O(nk^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
const int N = 2e5 + 5, A = 1e7 + 7;
int a[N], pattern[N], cnt[A];
int ll[N][25], f[N][25];

// PrimeFactorizationSieve()
namespace PFS { ... }

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();
    using PFS::prime, PFS::fact;
    PFS::start();
    while (T --)
    {
        int n = scanner.nextInt(),
            k = scanner.nextInt();
        for (int i = 1; i <= n; ++ i)
            a[i] = scanner.nextInt();
        fill(pattern, pattern + n + 1, 1);
        for (int i = 1; i <= n; ++ i)
        {
            int exp = 0, base = 0, tmp = a[i];
            while (tmp > 1)
            {
                int p = fact[tmp];
                if (base == p) ++ exp;
                else
                {
                    if (exp % 2) pattern[i] *= base;
                    base = p, exp = 1;
                } tmp /= p;
            }
            if (exp % 2) pattern[i] *= base;
        }
        for (int j = 0; j <= k; ++ j)
        {
            int cur = n + 1, use = 0;
            for (int i = n; i > 0; -- i)
            {
                while (cur - 1 >= 1 &&
                       use + !!cnt[pattern[cur - 1]] <= j)
                    use += !!(cnt[pattern[-- cur]] ++);
                ll[i][j] = cur;
                if (cnt[pattern[i]] --> 1) -- use;
            }
        }
        for (int i = 1; i <= n; ++ i)
            memset(f[i], 0x3f, sizeof(f[i]));
        memset(f[0], 0, sizeof(f[0]));
        for (int i = 1; i <= n; ++ i)
            for (int j = 0; j <= k; ++ j)
            {
                if (j) minimize(f[i][j], f[i][j - 1]);
                for (int l = 0; l <= j; ++ l)
                    minimize(f[i][j], f[ll[i][l] - 1][j - l] + 1);
            }
        int ans = 0x3f3f3f3f;
        for (int i = 0; i <= k; ++ i)
            minimize(ans, f[n][i]);
        println(ans);
    }
    return 0;
}

后记

《就这》：比赛中：Codeforces 服务器就这？比赛后：你这通过情况就这？

服务器恢复：拿好你的 15 分钟，我们没有找到任何 unrated 的原因！半小时后：我们 unrated 了！

Codeforces Round#708 div.2 回顾
https://shiraha.cn/2021/codeforces-round-708-div2/
本文作者
七海
发布于
2021年3月18日
许可协议
CC BY-NC-SA 4.0

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

您可以参见本网站的声明和许可来了解详情

更新于：2021年3月23日

算法

ACM

Codeforces

评论