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

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

博客

随笔

朋友

归档

关于

Codeforces Round#712 div.2 回顾

题解

发布于：2021年4月11日

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

记录

只能说进入四月一来一直颓的可以，，不仅没怎么训练没怎么准备考研，倒是莫名其妙地出去混了一天又一天，真的是愧对父母，，虽然出了各种各样的事情，但是再怎么说成年人还是应该对自己的行为负责…… 不废话了（

题目的话，A 白给一发，不过当时带人来 401 玩了，我还没有牛逼到一心二用还能好好写代码（）然后干脆直接 Div1 起步，从 C 开始做；然后做出了 C 和 D（当然，也花了相当的时间）之后就没怎么管了，，再之后（指一个星期之后的今天）补完了所有的题目。

但是听说这场 ABC 蓝名选手是要掉分的，做出了 ABCD 四个题的喜悦瞬间荡然无存，，

题解

A - Déjà Vu

反正就是破坏回文串：最简单的方法就是在前面加或者在后面加；都不行就输出 NO 就完事了（

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
const auto null = nullptr;
const int N = 3e5 + 5;

char a[N], b[N], c[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int T = $.nextInt();
    while (T --) {
        input, a;
        auto n = strlen(a);
        strcpy(b, a);
        b[n] = 'a', b[n + 1] = '\0';
        strcpy(c, b);
        reverse(c, c + 1 + n);
        if (strcmp(b, c) != 0) {
            $.put("YES").put(b);
            continue;
        }
        strcpy(b + 1, a);
        b[0] = 'a', b[n + 1] = '\0';
        strcpy(c, b);
        reverse(c, c + 1 + n);
        if (strcmp(b, c) != 0) {
            $.put("YES").put(b);
            continue;
        } else $.put("NO");
    }

    return 0;
}

顺便，这是我第一次使用全新的傻逼快读板子 cquery，IO 交互和以往的代码可能有较大的差距（

B - Flip the Bits

和前缀和很想，可以很容易的想到如果要反转，反转的端点一定要出现在可以翻转的位置上；

本来想着先遍历维护端点，在遍历求区间，在验证区间是否合法的；但是实际上只需要双指针（甚至单个指针）就完事了；代码量远没有我想象的那么大……

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 auto null = nullptr;
const int N = 3e5 + 5;

char a[N], b[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int T = $.nextInt();
    while (T --) {
        int n = $.nextInt();
        $(a + 1, b + 1);
        int cnt0 = 0, cnt1 = 0, ok = 1;
        for (int i = 1; i <= n; ++ i) {
            if (a[i] != b[i]) {
                if (cnt1 != cnt0) { ok = 0; break; }
                int j = i;
                while (a[j] != b[j]) {
                    ++ (a[j] == '1' ? cnt1 : cnt0);
                    ++ j;
                }
                if (cnt1 != cnt0) { ok = 0; break; }
                else i = j;
            }
            ++ (a[i] == '1' ? cnt1 : cnt0);
        }
        $.put(ok ? "YES" : "NO");
    }

    return 0;
}

只能说写代码还是写少了，，惭愧惭愧（

C - Balance the Bits

给一个 01 字符串：现在你要构造两个等长的括号序列，要求字符串为 0 的位置两个序列的括号不同，为 1 的位置相同；输出一种构造或者声明这是不可能的。

显然，0 和 1 的位置必须都是偶数个，并且两端的数字都为 1；否则显然不行。

现在分开考虑 0 和 1；0 本身构成的序列一定是一个合理的序列，但是要求翻转之后也要成立；为了避免麻烦的括号嵌套，只能构造为 ()()()... 的序列了；这样翻转之后的 )()()(... 也可以和两端为 1 的位置匹配。

同样还是为了解决麻烦的括号嵌套问题：因为 0 位置翻转之后可能会造成不必要的闭括号，所以考虑尽量提高嵌套层数；构造为 ...((()))... 的形式可以达到这个目标；至此，我们得到了一种构造方法；

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
const int N = 2e5 + 5;
char s[N], ans[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();
        scanner(s);
        int cnt0 = 0;
        for (int i = 0; i < n; ++ i)
            if (s[i] == '0') ++ cnt0;
        if (cnt0 % 2 || s[0] == '0' || 
            s[n - 1] == '0') println("NO");
        else 
        {
            println("YES");
            int cnt1 = n - cnt0, half = cnt1 / 2;
            int flag0 = 0, flag1 = 0;
            for (int i = 0; i < n; ++ i)
                if (s[i] == '1') 
                    ans[i] = flag1 ++ < half ? '(' : ')';
                else ans[i] = flag0 ? '(' : ')', flag0 = 1 - flag0;
            ans[n] = '\0', println(ans);
            for (int i = 0; i < n; ++ i)
                if (s[i] == '0') ans[i] = ans[i] == '(' ? ')' : '(';
            println(ans);
        }
    }
    return 0;
}

我也不知道怎么证明，，题解也什么都没有说清楚……只能说想到了就是想到了（

D - 3-Coloring

有n×nn \times n 的棋盘和三种颜料；提供一个长度为n2n^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
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, b, x, y, a;
    cin >> n;
    const int t = n * n;
    int T = t;
    queue<pair<int, int>> pos1, pos2;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            ((i + j) % 2 ? pos2 : pos1).emplace(i, j);
    while (T --)
    {
        cin >> a;
        switch (a)
        {
            case 1:
                if (!pos2.empty()) 
                    x = pos2.front().first, 
                    y = pos2.front().second, 
                    b = 2, pos2.pop();
                else
                    x = pos1.front().first, 
                    y = pos1.front().second, 
                    b = 3, pos1.pop();
                break;
            case 2:
                if (!pos1.empty())
                    x = pos1.front().first, 
                    y = pos1.front().second, 
                    b = 1, pos1.pop();
                else
                    x = pos2.front().first, 
                    y = pos2.front().second, 
                    b = 3, pos2.pop();
                break;
            case 3:
                if (!pos1.empty())
                    x = pos1.front().first, 
                    y = pos1.front().second, 
                    b = 1, pos1.pop();
                else
                    x = pos2.front().first, 
                    y = pos2.front().second, 
                    b = 2, pos2.pop();
                break;
            default: break;
        }
        cout << b << ' ' << x << ' ' << y << endl;
    }
    return 0;
}

愿天堂没有失明🙏

E - Travelling Salesman Problem

有nn 个城市，每个城市有一个美丽值aia_i 和起步价cic_i，初始在11 号城市；现在我们要到达所有的nn 个城市一次后返回11 号城市；路途i→ji \to j 的花费是max⁡(ci,aj−ai)\max(c_i, a_j - a_i)，求出达成目标的最少花费。

从哪个城市出发无所谓的，因为路程是一个环；考虑这个起步价是一条路途出边决定的，而我们确定要从每个城市出去一次，所以这笔钱省不了；问题就在如何最小化额外花费；考虑路途i→ji \to j 的额外花费，我们不难得到：

max⁡(ci,aj−ai)=ci+max⁡(0,aj−ai−ci)\max(c_i, a_j - a_i) = c_i + \max(0, a_j - a_i - c_i)

显然，我们可以把美丽值看作是海拔：这样下坡就是免费的，上坡的话根据起点有所减费。我们的旅途反正是一个环，此时就转变为从最高点俯冲而下，然后再借助某些位置作为减费跳板回到山顶；这样的话会重复访问节点？拜托，俯冲的时候跳过这些节点不就完了，反正又不要钱（

此时，我们已经可以将这个问题转化为一个最短路问题，建模求解；建图方式如下：

  • 下坡：相邻的位置之间连边，显然免费
  • 上坡：在坡上二分查找，找到最高的可以被减至 0 费的位置
    • 对于这个位置，显然连免费边：定义里都已经这么说了
    • 对于这个位置的更高位置，连边，并用公式计算费用

其实原问题就可以朴素建图解决，但是边数是O(n2)O(n^2) 的只能作罢；但是为什么可以这么建图呢？现在对于这个建图方法的合理性进行简单的说明：

下坡的话已经没有什么好说的了，我直接连免费边和从一堆免费边过去有什么区别呢？上坡的话可这么理解：首先上坡肯定是尽量的最大化的利用减费的——但是并不是没有代价：如果你要采用某个点的减费政策，就要放弃看来自更低的位置的减费；而前者未必比后者优。因此这个抉择就可以转化为：对于每个节点的减费政策，我是直接采用还是放弃前面的减费政策。

在前面的减费非常诱人的情况下，可能包含了多个可以免费的上坡位置——但是我们只需要建最高的位置即可：因为其他的位置可以用下坡边回流；但是一定会有一个位置，它可以减费但是无法减至免费：这个位置是关键位置，不可以被其他的边表示，因此也要连边。

综上所述，上述建图就可以完成对原问题的描述；在建图上跑最短路就可以得到答案。

当然，题解还提供了一种更简单的做法，但是相应地也更加的抽象难懂：

就像上面说的那样，下坡已经无所畏惧了，问题就是怎么巧妙利用减费来上坡；因此我们可以对所有节点根据“海拔”排序之后，从底部出发，递推地维护上坡到每个位置之后的最小花费。转化的答案可以描述为下面：

∑i=2nmax⁡(0,ai−max⁡j<i(aj+cj))\sum_{i = 2}^n \max(0, a_i - \max_{j<i}(a_j + c_j))

即维护在更低位置中的最大折扣，到达每个位置的费用都等于到达最大折扣的位置的最少费用加上利用这个折扣跳转到当前位置的费用之和。但是我们毕竟只关注到达顶点的费用，如对于每一个位置都严格的维护这个又显的太过于复杂；所以只需要维护到达每个位置使用可用的最大减费之后的费用和即可。

那么为什么这样是正确的呢？显然，在没有这个减费的情况下，上坡的费用完全就是势能的转化：那个高中物理名词叫啥我忘记了；减费政策就相当于在坡上放倒三角；我们维护的总是当前势能加上减费后能量最高的位置——也就是加上减费后最高的位置。我们爬斜坡需要能量，但是倒三角覆盖的部分不需要能量；因此，我们只需要尽量用倒三角覆盖斜坡，就可以统计得到最小的费用。

补题代码

贪心也得取之有道啊，瞎**贪心是做不出题目的啊（

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], c[N], id[N];

bool compare(int l, int r)
{return a[l] < a[r];}

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();
    longs ans = 0;
    for (int i = 1; i <= n; ++ i)
        a[i] = scanner.nextInt(),
        c[i] = scanner.nextInt(),
        ans += c[i];
    iota(id, id + 1 + n, 0);
    sort(id + 1, id + 1 + n, compare);
    longs discount = a[id[1]] + c[id[1]];
    for (int i = 2, p = id[i]; 
        i <= n; p = id[++ i])
    {
        ans += max(0ll, a[p] - discount);
        maximize(discount, (longs)a[p] + c[p]);
    }
    println(ans);
    return 0;
}

只能说做题的时候还是瞎想多了，，

F - Flip the Cards

有nn 张牌，牌的两面写了互不相同的[1,2n][1, 2n] 的数字；现在你需要对牌进行排序，并翻转部分牌，得到一个新的牌的序列：满足正面的数字递增且反面的数字递减。求出最少的翻转次数或者证明这不可能。

我距离做出这个题的距离还是挺遥远的…… 甚至当晚看题解都没有看懂……菜爆了（

首先需要意识到有解的套牌必须满足一张牌的两面必须一个属于[1,n][1, n] 另一个属于[n+1,2n][n+1, 2n]，否则无解；这也很好理解，毕竟我问我的学弟队友，他也是一眼意识到这个只有我这个老东西后知后觉了呜呜

满足了上述限制的套牌，我们先进行翻转，保证正面比反面的数字小，那么就可以桶排序；按照正面数字排序之后的套牌，第ii 张的正面数字是ii，反面的数字记为f[i]f[i]；

首先给出一种确定可以构造出满足题意的排序的构造方法：如果上述的f[i]f[i] 构成的序列，可以拆分成两个递减的子序列，那么可以将拆解得到的两个部分中的一部分翻转后倒序，拼装到另一个部分的后面组成一个满足题意的序列；如果考虑到最少翻转次数，只需要翻转其中翻转成本较低的一组即可。

翻转成本的计算也非常简单：分成的序列中可能包含了一些在桶排序的时候翻转的卡牌，翻转一个序列的成本就是另一个序列中的这些卡牌的数量加上待翻转序列中除此之外的卡牌的数量。

但是问题就是f[i]f[i] 可能有多种分割的方法；而上述翻转的成本中的冗余都是因为有些卡牌可以放到另一个序列中避免翻转或者翻转回来导致的。因此我们有必要进行唯一的最优分解，才能求出这个答案；最优的分解很显然就是每当出现逆序对的时候，考虑翻转的成本，并选择更优的一侧翻转；之后将这些逆序对合并成序列即可。

但是并不是所有的划分都是可以复原的，所以划分时需要加入条件；这里采用的是f[i]f[i] 的前缀最小值大于后缀最大值的时候可以划分；这至少是一个充分的条件，保证翻转之后的序列的两个部分可以嵌套着还原为原序列。

虽然有很多部分还是没有太清楚的明白，但是还是知道了一些事情：我只需要考虑可以构造出最小花费的序列的方法即可，至于有没有别的方法，Who care？当然，必要性还是需要证明的……这我就实在不太懂了（

补题代码

经典对着标程猜测题解，，逊（

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
const int N = 2e5 + 5;
pair<int, int> a[N];
bitset<N> rev;
int f[N], suf[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n = $.nextInt();
    $.nextArray(a + 1, a + 1 + n);
    bool legal = true;
    for (int i = 1; i <= n; ++i) {
        if (a[i].first > a[i].second) {
            swap(a[i].first, a[i].second);
            rev.set(a[i].first);
        }
        if (a[i].first > n || a[i].second <= n) {
            legal = false;
            break;
        } else f[a[i].first] = a[i].second;
    }
    if (!legal) {
        output, -1, endl;
        return 0;
    } else {
        suf[n + 1] = -1;
        for (int i = n; i >= 1; -- i)
            suf[i] = max(f[i], suf[i + 1]);
        int pref = 0x3f3f3f3f;
        int cosA = 0, cosB = 0, ans = 0;
        vector<int> seqA, seqB;
        for (int i = 1; i <= n; ++ i) {
            minimize(pref, f[i]);
            if (seqA.empty() || seqA.back() > f[i])
                seqA.push_back(f[i]), cosA += rev[i];
            else if (seqB.empty() || seqB.back() > f[i])
                seqB.push_back(f[i]), cosB += rev[i];
            else {
                output, -1, endl;
                return 0;
            }
            if (pref > suf[i + 1]) {
                int sizA = (int)seqA.size(),
                    sizB = (int)seqB.size();
                ans += min(cosA + sizB - cosB, cosB + sizA - cosA);
                cosA = cosB = 0;
                seqA.clear(), seqB.clear();
            }
        }
        output, ans, endl;
    }
    return 0;
}

这甚至还是个 2-SAT 问题，，可以见得乱搞的方法有很多，只是我都不会罢了（

后记

想到了昨天 zcysky 说过的：Div2 本身已经足够白给了；突然就再次的感觉到——不管是为了什么的努力，重要的是看到成效，而不仅仅是自虐地自我满足。说教别人警惕这种繁荣的幻想的同时，我自己不也是这样吗？

对于我这种起步晚，学习慢的残疾 ICPCer 而言，更应该是脚踏实地地讲究训练方法效率，做有用的事情才行啊（

YJ_JI1_O_AZV2_HWPA_YQ.jpg

唉，还是且行且珍惜——

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

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

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

更新于：2021年4月11日

算法

ACM

Codeforces

评论