Codeforces Good Bye 2019 回顾

七海

题解

发布于：2020年6月15日

次浏览

这场比赛的编号是 1270，可以去洛谷上搜索 CF1270X 或者去官网补题。

题目质量还是不错的，明明长着一副 div2 的样子却把我搞得要死== 我属实不太行（

其实这应该算不上是什么题解，充其量就算是做题记录吧（

A - Card Game

签到题

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, k1, k2, t, a;
    cin >> t;
    while (t --)
    {
        cin >> n >> k1 >> k2;
        bool firstWin = false;
        while (k1 --)
        {
            cin >> a;
            if (a == n) firstWin = true;
        }
        while (k2 --) cin >> a;
        cout << (firstWin ? "YES" : "NO") << endl;
    }

    return 0;
}

B - Interesting Subarray

简单的在草稿纸上推一下，就会知道这不会存在越位的问题：对于数列 [A, B, C] ：如果 A-B 不行，那么 A-C 也必然不行；从另一个角度来看，也就是说，所有的可行的 (l, r) 最后一定可以转化为 (x, x+1)；所以我们可以扫一遍数组，如果元组 (i, i+1) 可以满足要求，就记录答案，最后输出即可；

现在有一种一般性的思维来考虑：设 max(a) = i，min(a) = j，那么 max(a) - min(a) ≥ k 就可以转化为 |a[i] - a[j]| ≥ |i-j|；假设一下顺序，就可以移项转化成 a[i] + i < a[j] + j 或者 a[i] - i > a[j] - j；这样的话就可以遍历数组求 f(x) = a[x] + x 以及 g[x] = a[x] - x；统计它们的最值，如果符合要求就输出即可；

#include <iostream>

using namespace std;

const int N = 2e5 + 5;
int a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t, n; cin >> t;
    while (t --)
    {
        cin >> n >> a[0];
        int ll = -1, rr = -1;
        for (int i = 1; i < n; ++ i)
        {
            cin >> a[i];
            if (abs(a[i] - a[i - 1]) > 1)
                ll = i, rr = i + 1;
            else continue;
        }
        if (ll == -1 && rr == -1) cout << "NO" << endl;
        else cout << "YES\n" << ll << ' ' << rr << endl;
    }

    return 0;
}

C - Make Good

给你一个数列，它的和是 a，环和是 b；现在你要给这个序列再加上不超过 3 个数，使得新的 a' = 2b'；

数列不重要，遍历数列知道了 a 和 b 就可以了；题目允许我们加三个数字，那么这个题目有一种很巧妙的构造方法；加法的性质我们都很熟悉，在说这个之前先简单回顾一下环加（异或）的性质：a ⊕ a = 0，a ⊕ 0 = a；也就是说我们可以通过把环和置零，将环和置为任何一个数字；所以这个题目可以这么做：

先加上 b：此时，a' = a + b，b' = b ⊕ b = 0；
再加上 a + b：此时，a' = 2(a + b)，b' = 0 ⊕ (a + b) = a + b；

这样就在三个数字之内实现了题目的要求：

#include <iostream>

using namespace std;
typedef unsigned long long ulongs;

const int N = 1e5 + 5;
ulongs a[N], sum, x_sum;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t, n; cin >> t;
    while (t --)
    {
        cin >> n;
        sum = x_sum = 0;
        for (int i = 1; i <= n; ++ i)
        {
            cin >> a[i];
            sum += a[i];
            x_sum ^= a[i];
        }
        if ((x_sum << 1u) == sum)
            cout << 0 << endl << endl;
        else cout << 2 << endl << x_sum
            << ' ' << (x_sum + sum) << endl;
    }

    return 0;
}

但是，如果我们只允许在序列末尾增加一个数字呢？可以实现题目的要求吗？

虽然不知道应该怎么数学证明，但是这是可以的。

D - Strange Device

交互机器有一个长度为 n 数列，每个元素互不相同；对于这个数列，你可以进行询问：
? x1 x2 …… xk ：询问包含 k 个数字的单调递增数列，xi 是原数列的下标；
交互机器返回 pos val ：pos 是询问序列中第 m 大的元素的下标，val 是它的值；
现要求你在不超过 n 次询问中求出 m 的值，满足 m ≤ k < n；

虽然说交互机器持有了一个不为我们所知的 n 元数组，但是注意到我们求的东西和数组的值或者某个下标的值实际上没有任何关系，所以可能是闪光弹== 每次询问可以获得长度为 k 的元素互不相同的数组中的第 m 大的元素，为了确定这个 m 的值，一种很容易想到的策略如下：

取 k + 1 数字（互不相同），对于从中取出 k 个数字的每种组合进行询问
因为互不相同，所以元素之间的关系非常单纯：只有大于和小于的区别
这样应该只会得到两种应答：一种是因为被丢弃的数字比第 m 个小，一种是因为大
可以根据这两种应答数字的相对大小来确定它们的来源，从而确定 m

这样的做法要求询问 k + 1 次，数组中至少要包括 k + 1 个元素；但是题目已经贴心的安排了 k < n，所以这种方法必然可以采用；事实上题目的样例输入输出就是采用的这种方法进行判定，只是 k + 1 = n 混淆视听罢了。

#include <iostream>
#include <unordered_map>

using namespace std;

#define ask cout << "? "
#define chk cout << "! "

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, k, pos, val;
    cin >> n >> k;
    unordered_map<int, int> x;
    const int lim = k + 1;
    int m_pos = -1, m_val = -1;
    for (int i = 1; i <= lim; ++ i)
    {
        ask;
        for (int j = 1; j <= lim; ++ j)
            if (j == i) continue;
            else cout << j << ' ';
        cout << endl;
        cin >> pos >> val;
        if (val > m_val) m_pos = pos, m_val = val;
        ++ x[pos];
    }
    chk << x[m_pos] << endl;

    return 0;
}

E - Divide Points

给你 n ≥ 2 个整数坐标，要求你将它分成两组，并且满足下面的需求：
所有的点对之间连边；将两个点在同一组的边称为 A 类边，否则称为 B 类边；
不存在长度相等的 A 类边和 B 类边；即长度相等的边必须同类；
确保对于所有的输入数据，存在这样的分组方法；保证输入的每个点独一无二；

看到分组，还是和图论相关的分成两组，难以不想到二分图，并查集乌拉乌拉…… 然而遗憾的是这个题和它们没有半点关系；1e6 的数据范围和 1s 的时限让它最多只能接受 O(n√n) 的算法，所以它是个思维题（

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
typedef unsigned int uint;

const int N = 1050;
pair<uint, uint> p[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    vector<uint> ans;
    uint cnt[2][2], &p00 = cnt[0][0], &p11 = cnt[1][1],
            &p01 = cnt[0][1], &p10 = cnt[1][0];
    uint n, x, y, msk = 1;
    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> x >> y;
        p[i] = make_pair(x, y);
    }
    while (true)
    {
        memset(cnt, 0, sizeof cnt);
        for (int i = 1; i <= n; ++ i)
            ++ cnt[bool(p[i].first & msk)][bool(p[i].second & msk)];
        if (p01 + p10 && p00 + p11)
        {
            for (int i = 1; i <= n; ++ i)
                if ((p[i].first & msk) ^ (p[i].second & msk))
                    ans.push_back(i);
            break;
        }
        else if (p00 + p01 && p10 + p11)
        {
            for (int i = 1; i <= n; ++ i)
                if (p[i].first & msk) ans.push_back(i);
            break;
        }
        else msk <<= 1u;
    }
    cout << ans.size() << endl;
    for (auto &ii : ans) cout << ii << ' ';
    cout << endl;

    return 0;
}

刚刚发现坐标原来可以是负数，我还拿了个 uint 来存…… 虽然说负数坐标映射不改变其奇偶性，导致上述代码仍然可以 AC，但是无论怎么说这还是太不小心了，好歹读进来整体平移啊（

F - Awesome Substrings

给一个长度为 n 的 01 字符串；现在需要求出满足条件的区间 [l, r] 的数目：区间 [l, r] 满足 r - l + 1 是区间内值为 1 的位数的倍数；
数据范围：n ≤ 2e5；

G - Subset with Zero Sum

给你一个长度为 n 的整数数组 a，下标为 1 ~ n；对于 a 中的元素有 i - n ≤ a[i] ≤ i - 1；现在要求你找出这个数组中元素集合的子集 S，集合内的元素的和为 0；可以证明对于满足这个条件的数组 a，这样的子集必然存在。
数据规模：n 不超过 1e6；

这个题目看起来比较的奇怪：说是数组，要找的自己和却是一个和数组下标顺序没有任何关系的东西；看起来求和为 0 的子集无从保证，但是随便写几组数据发现确实存在；就……感觉这题目做不得了（

从看起来最奇怪的约束不等式入手：两个边界都有 +i 存在，可以考虑移项，得到：1 ≤ i - a[i] ≤ n；似乎和下标的范围完全一致，所以就可以建图了~~别问我我也不知道题解怎么想的~~：建立一个 n 个点的有向图，连边 i → i - a[i]，就得到了一个基环内向森林——每一个节点的出度为 1 的图；

这样的图有一个特性，即一定存在环；先说结论，对于这个图中的任何一个环，环上的所有节点构成的集合一定满足题目要求：即集合内点的和为 0；证明如下：

由我们的建图方式可以知道，对于该图的任何一条边；起点为 i，终点为 i - a[i]；
如果形成了一个环，那么这个环上所有边的起点集和终点集完全一致，等于处于这个环上的点集；
那么，对于起点集求和一定和终点集求和相等；因为这两个集合相等；令环上点集为 S；
上述关系写成式子就是 \(\sum_{i \in S} i = \sum_{i \in S} (i - a_i)\)，移项整理可得 \(\sum_{i \in S} a_i = 0\)；

综上所述，对于按照 i → i - a[i] 建立的图，图上任意一个环上的所有点构成的集合就满足题目要求；且这样构成的图中一定存在环。

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>

using namespace std;

inline int nextInt()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - 48; ch = getchar();}
    return x * f;
}

const int N = 1e6 + 5;
int to[N], vis[N];

int main()
{
    int t = nextInt(), n;
    while (t --)
    {
        n = nextInt();
        for (int i = 1; i <= n; ++ i)
            to[i] = i - nextInt(), vis[i] = 0;
        int now = 1, st;
        while (!vis[now]) vis[now] = 1, now = to[now]; 
        vector<int> ans;
        st = now, now = to[now];
        while (now != st) ans.push_back(now), now = to[now];
        ans.push_back(st);
        printf("%d\n", (int)ans.size());
        for (auto &ii : ans) printf("%d ", ii);
        puts("");
    }

    return 0;
}

这个题目似乎卡了IO，同样逻辑的代码如果使用 C++ IO 的话会在第八个点几乎一定会 TLE；这种题目姑且还算是个组合题，值和下标在同一个范围内，和经典问题“没有指针的链表”的思想很像== 害也就那么回事吧（

H - Number of Components

一个长度为 n 的元素互不相同的数组 a，映射为一张包含 n 个节点的无向图 G；映射关系为：当 i < j 和 a[i] < a[j] 同时成立时，认为节点 i 和 j 之间存在连边；现在将会修改数组 a 某位置的值，要求动态地维护图 G 中连通块的数目；修改次数为 q，保证修改后数组元素依然互不相同；
数据范围：n, q ≤ 5e5；1 ≤ a[i] ≤ 1e6；i ≠ j ⇔ a[i] ≠ a[j]；

I - Xor on Figures

有一个 \(2^k × 2^k\) 的矩阵 A，行列从 0 开始标号；给定长度为 t 的数列 x，y；现在你可以进行操作，操作的定义如下：
操作接受三个参数：p，q，w；记 \(X = (x_i+p)\ mod\ 2^k\)，\(Y = (y_i+q)\ mod\ 2^k\)；
对于 \(\forall a \in X, \ b \in Y\)，将使得矩阵的 \(A_{a,b} = A_{a,b} \oplus w\)；
现要求仅使用上述操作将矩阵 A 变为零矩阵，求最小的操作次数；
数据范围：k ≤ 9，t ≤ 99 且为奇数；