CF1702 C, D, E, F 题解

C. Train and Queries

题意：

题目链接（CF，洛谷）
给你一个长度为 $n (1\le n \le 2 \cdot 10 ^ 5)$ 的数组 $u$。代表所有的火车站。火车只能从左边的站台开到右边的站台。也就是从 $u_1$ 开始，再到 $u_2, \ u_3$，最后到 $u_n$。

现在给你 $k (1\le k \le 2 \cdot 10 ^ 5)$ 个询问，每个包含两个整数 $a_i$ 和 $b_i$，问你是否可以从 $a_i$ 这个站台开始，坐火车到 $b_i$。

比如：$u$ 数组为 $[3,7,1,5,1,4]$，有以下三个询问：

• $a_1 = 3, b_1 = 5$。
  从 $3$ 号站台坐车到 $5$ 号站台是可能的，有以下路径：$[3,7,1,5]$。
• $a_2 = 1, b_2 = 7$
  没有路径可以从 $1$ 号站坐车做到 $7$ 号站台。
• $a_3 = 3, b_3 = 10$
  没有路径可以从 $3$ 号站台坐车到 $10$ 号站台（$10$ 号根本不存在）。

思路：

我们只需要知道某个站台第一次出现的位置和最后一次出现的位置就行了。假设站台 $i$ 第一次出现的位置为 $f_i$，最后一次出现的位置为 $l_i$。并且这时有询问 $a, b$。

那么只要 $f_a < l_b$ 就一定可以从站台 $a$ 坐车到站台 $b$ 了。因为我们知道第一个 $a$ 号站台在最后一个 $b$ 号站台的左边，而火车只能从左向右开，所以可以到达 $b$。

因为要形成一个站台编号到位置的映射，并且站台的编号比较大（$1e9$），站台编号的数量相对较少（$2e5$）。用平常的数组肯定不行，因为需要的空间过大 （$1e9$）。所以有两种办法，离散化（用排序离散化）和使用 map。

这里我开了两个 map，其中一个是站台编号到第一次出现位置的映射，还有一个，和前面讲的一样，是编号到最后一次出现位置的映射。

然后我们就可以得到如下代码：

代码：

因为使用的是 cin 和 cout，所以可能会因为输入速度比较慢造成 TLE，所以可以取消一下同步。

// author: ttzytt (ttzytt.com)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        int a[n + 1];
        map<int, int> v2pos_frt, v2pos_bk;
        //编号->第一次出现， 编号->第二次出现
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            
            if (!v2pos_frt[a[i]]) 
                v2pos_frt[a[i]] = i;
            // 只有第一次才会赋值

            v2pos_bk[a[i]] = i;
        }
        while (k--) {
            int l, r;
            cin >> l >> r;
            int lp = v2pos_frt[l];
            int rp = v2pos_bk[r];
            if (lp <= rp && lp != 0 && rp != 0) {
                // 如果根本没有这个站台，那 lp 或 rp 就会为 0
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
}

D. Not a Cheap String

题意：

设 $s$ 为一个由小写拉丁字母组成的字符串。它的价格被定义为，字符串中每个字母在字母表中的位置的和。

比如，字符串 $\texttt{abca}$ 的价格是 $1 + 2 + 3 + 1 = 7$。

现在给你一个字符串 $w (|w| \le 2\cdot 10^5)$，和一个整数 $p$，请你从字符串中尽量少的移除字母，使得 $w$ 的价格小于或等于 $p (1 \le p \le 5\ 200\ 000)$。注意移除的字母数量可以是 $0$ 个，也可以是字符串中全部的字母。

思路：

这道题的难度其实跟上一个差不多。因为题目让你删除尽量少的字母，所以我们直接挑对价格贡献大的字母删，直到整个字符串的价格小于等于 $p$。

具体的实现上，我们还是可以用 map 建立一个字符到出现次数的映射（或者说桶）。

然后我们倒着遍历这个 map，这样先遍历到的字符就对价格有更大的贡献。然后在遍历时如果发现当前的价格大于 $p$，就删除这个字符。并且如果我们删除了这个字符，那也相应的给字符的出现次数 $-1$。

最后输出时，我们遍历原来的字符串，如果发现对应的字符在桶里有出现，就输出，然后把出现次数 $-1$，否则就不输出了。

代码：

// author: ttzytt (ttzytt.com)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        string str;
        int p;
        cin >> str >> p;
        map<char, int> bkt; // 桶
        ll price = 0;
        for (char ch : str) {
            bkt[ch]++;
            price += (ch - 'a' + 1);
            //计算初始价格
        }
        map<char, int>::reverse_iterator it = bkt.rbegin();
        //倒着遍历 map，所以需要用反向迭代器
        while (price > p) {
            // 如果价格没有小于等于 p，就一直删
            (*it).second--; 
            // 减少桶代表的出现次数
            price -= ((*it).first - 'a' + 1);
            // 维护价格
            if ((*it).second <= 0) {
                // 如果说这个字母已经被删光了
                if (it != bkt.rend()) it++;
                // 并且这不是字符串中最小的字符
                // 我们就开始删比当前字符小的字符
            }
        }
        string ans;
        for (char ch : str) {
            if (bkt[ch] > 0) {
                //如果发现这个字符还没被删除
                ans.push_back(ch);
                bkt[ch]--;
            }
        }
        cout << ans << endl;
    }
}

E. Split Into Two Sets

题意

给你 $n$ （$n$ 为偶数，$2 \le 2 \cdot 10^5$）个，数对。数对中的每个数字都是从 $1$ 到 $n$ 的。

现在问你是否能将这些数对分到两个集合中。使得每个集合中没有任何一个重复的数字。

比如有下面这四个数对：$\{1, 4\}, \{1, 3\}, \{3, 2\}, \{4, 2\}$。

那么可以这样分配这些数对：

• 第一个集合包含数对 $\{1, 4\}$ 和 $\{3, 2\}$。第二个包含 $\{1, 3\}$ 和 $\{4, 2\}$。

思路

看起来是个贪心，能放一个集合的就放，不能就放另一个，另一个还不行就输出 $\texttt{NO}$ ，但毕竟是个 E 题，所以没那么简单。（别学我直接交了个贪心上去，还半天都想不明白为什么错）。

要证明这个贪心是错的，只需要举一个反例，顺便吐槽一下，这个题的样例还是挺坑的，你用贪心完全能过。

比如给你下面这样一个数据：

6
1 2    
5 4
2 3 
4 3  
5 6
6 1

如果我们用贪心做，设第一个集合为 $A$，第二个为 $B$，就可以把前两个，也就是 $\{1, 2\}$ 和 $\{5, 4\}$ 放到 $A$ 中。到第三个，就会发现 $\{2, 3\}$ 中的 $2$ 和 $\{1, 2\}$ 的 $2$ 重复了，于是放到 $B$ 中。

而对于第四个数对 $\{4, 3\}$ ，可以发现不管放到哪里都有重复的。

然而，这个数据是可以合法的分到两个集合的：

$$A: \{1, 2\} \ \{4, 3\} \ \{5, 6\}\\ B: \{2, 3\} \ \{5, 4\} \ \{6, 1\}$$

我们可以把数对拆称每个数字来看。

从 $1$ 开始，所有数对中，包含 $1$ 的有两个：$\{1, 2\}$ 和 $\{6, 1\}$。那么我们知道，因为两个数对都有 $1$，所以肯定不能放到一个集合里。

按照相同的方式来看 $2$。包含 $2$ 的数对有两个：$\{2, 3\}$ 和 $\{1, 2\}$。所以这两个也一定在不同的集合中。

按照这样的方法从 $1$ 到 $n$ 的列出包含这些数字的集合，可以得到：

$$1 \to \{1, 2\} \ \{6, 1\}\\ 2 \to \{2, 3\} \ \{1, 2\}\\ 3 \to \{2, 3\} \ \{4, 3\}\\ 4 \to \{4, 3\} \ \{5, 4\}\\ 5 \to \{5, 4\} \ \{5, 6\}\\ 6 \to \{5, 6\} \ \{6, 1\}$$

然后我们检查这些条件，发现似乎没有矛盾的，并且你可以根据这些条件得到我之前给出的分配方法。

这样一看，告诉你两个东西在不同的集合中，并且让你判断这些规则是否能满足，那不就是一种带逻辑关系的并查集吗？

如果你不熟悉，可以去看看这些题目：

• 洛谷P1892 [BOI2003]团伙
• P2024 [NOI2001] 食物链

的确，这个题是可以用带逻辑关系的并查集来做的，tourist 就是这么做的。

不过，我们还可以从图论的角度来思考。

如果我们给一个数对中的两个数字连上一条边，就可以得到下面这样的图：

1 <--> 2 <--> 3
|             |
6 <--> 5 <--> 4

可以发现，因为和之前一样的原因，对于一个数字，比如 $2$。我们不可能把包含 $2$ 的两个数对，也就是 $\{2, 3\}$ 和 $\{1, 2\}$，放到一个集合里。

也就是说可以从边的角度思考，$2$ 这个节点连了两个边，而我们不能同时选 $2$ 的两条边放到一个集合里。

那么唯一能满足这个要求的办法就是交替的把边分配到集合中。

比如：

1 <--> 2 <==> 3    or     1 <==> 2 <--> 3 
||            |   <--->   |             ||
6 <==> 5 <--> 4           6 <--> 5 <==> 4

其中 <--> 这样的边和 <==> 这样的边代表边上的两个节点会被放到不同的集合中。

接下来我们可以分类讨论一下，不同的图是否能满足要求。

首先，如果一个节点连了三个及以上的边，那么一定是不能满足交替放入不同集合中的。

比如：

   A 
  /|\
 / | \
B  C  D

因为如果要把 $B, C, D$ 放入两个集合中，$AB, AC$， $AC, AD$，或是 $AB, AD$ 就一定会被放入一个集合中，然后就不能满足交替出现的要求了，因为 $A$ 不可避免的出现了两次。

其次，如果图中只有一个链，那么交替的放入不同集合中是一定能满足的。

最后，如果图是一个环，并且有偶数的边（就像上面那样），那是一定可以满足交替出现的要求的。而奇数就不行了。

判断环奇偶的办法其实比较直观，我们给每个边设置一个颜色的属性，共有两种颜色，然后用 dfs 去遍历一遍这个环。

遍历时尝试给边交错的染上颜色，如果我们不能成功的交错染色，那一定是奇环，反之亦然。（如果能交错的染色，那么两种颜色的数量一定是相等的，因此一定是偶环）。

还有一点在具体实现时需要注意，我们建出来的图不一定是联通的，所以需要尝试对每一个节点 dfs，同时，之间按照输入建图可能有重边，而我们需要避免。

代码

整体来说，代码还是比较简洁的。

// author: ttzytt (ttzytt.com)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct E {
    int to, color;
};

const int MAXN = 2e5 + 10;

vector<E> e[MAXN];
set<int> have_e[MAXN];

bool iseven_cycle(int cur, int fa, bool cur_color) {
    if (e[cur].size() < 2) return true;
    // 小优化，size 小于 2 说明是一个链的终点。
    // 那么一个链是一定可以交错的染色的，这时候直接返回 true
    for (E &nex : e[cur]) {
        if (nex.to == fa) continue;
        if (nex.color == -1) // -1 是初始值，所以直接给它染和当前边不同的颜色
            nex.color = !cur_color;
        else if (nex.color == cur_color)// 如果发现下一个边和当前边同色，那肯定是不能成功染色的
            return false;
        else if (nex.color == !cur_color)// 有颜色了，但是是我们想染的。
            return true;
        if (!iseven_cycle(nex.to, cur, !cur_color)) return false;
    }
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for_each(e + 1, e + 1 + n, [](vector<E> &a) { a.clear(); });
        for_each(have_e + 1, have_e + 1 + n, [](set<int> &a) { a.clear(); });
        // 每次清空一下数据。

        bool isable = true;
        map<int, int> bkt; // 记录每个节点的度，如果大于 2 那一定不行（原因如上文）
        for (int i = 1; i <= n; i++) {
            int x, y;
            cin >> x >> y;
            bkt[x]++, bkt[y]++;
        
            if (bkt[x] > 2 || bkt[y] > 2 || x == y) isable = false; // 发现度大于 2
        
            if (!have_e[x].count(y)) { //用于避免重边
                e[x].push_back({y, -1});
                have_e[x].insert(y);
            }
            if (!have_e[y].count(x)) {
                e[y].push_back({x, -1});
                have_e[y].insert(x);
            }
        }
        for (int i = 1; i <= n && isable; i++) {
            if (e[i][0].color == -1) 
                isable = iseven_cycle(i, 0, 1); 
                // 建出来的图不一定联通，所以尝试对每个节点 dfs   
        }
        if (isable)
            cout << "yes\n";
        else
            cout << "no\n";
    }
}

F. Equate Multisets

前言：本题解的解法参考了这个视频。

题意

多重集是一种特殊的集合，其元素可以重复，并且，和集合一样，元素的顺序不重要。如果两个多重集中，每个元素的出现次数都一样，那么这两个多重集就是相等的。

如，$\{2, 2, 4\}$ 和 $\{2, 4, 2\}$ 是相同的。而 $\{1, 2, 2\}$ 和 $\{1, 1, 2\}$ 不是相同的。

现在给你两个多重集 $a$ 和 $b$，每个包含 $n (1 \le 2\cdot 10^5)$ 个整数。

在一次操作中，$b$ 中的一个元素可以被翻倍或是减半（向下取整）。或者说，对于一个 $b$ 中的元素 $x$，你可以做下面两种操作。

• 替换 $x$ 为 $2x$
• 替换 $x$ 为 $\lfloor \frac{x}{2} \rfloor$

注意你不能对多重集 $a$ 做任何操作。

请问你是否能使多重集 $b$ 在经过任意数量的操作后和 $a$ 相等（也可以是 $0$ 个操作）。

一些性质

这个 $\times 2$ 和 $\lfloor \div 2 \rfloor$ 可以联系到位运算的左移和右移。如 $5$ 的二进制形式为 $(101)_2$，$5\times 2$ 的二进制形式就为 $(1010)_2$。可以看到相比 $5$，$10$ 的二进制形式在最后加了一个 $0$。而 $10 \div 2$ 就是 $5$，二进制形式下的 $5$ 在最后一位比 $10$ 少了一个 $0$。

所以左移和乘二的运算是等价的，右移和向下取整的除二是等价的。

那么我们就可以发现一个性质，也就是集合（实为多重集，这里为了方便称为集合） $a$ 和 $b$ 中元素的后缀 $0$ 是不重要的。

这里我来解释一下什么是后缀 $0$，以及“不重要”。

现在有一个数，比如 $40$，其二进制形式为 $(101000)_2$。可以看到二进制下的 $40$ 在尾部有 $3$ 个 $0$。那么这三个 $0$ 就是 $40$ 的后缀 $0$。

而不重要的意思是：

如果我们设 $\alpha \in a, \beta \in b$。再设 $\alpha^\prime$ 和 $\beta^\prime$ 分别为 $\alpha$ 和 $\beta$ 去掉后缀 $0$ 的后的数字。那么如果我们能通过提供的两个操作，把 $\beta$ 转换成 $\alpha$ 就一定能把 $\beta^\prime$ 转换为 $\alpha^\prime$。

这是因为可以通过左移和右移操作，在 $\beta^\prime$ 的尾部增加和删去任意数量的 $0$。

这样就可以让 $\beta^\prime$ 变成 $\beta$。而对于 $\beta$， 我们已经知道了可以将其转换成 $\alpha$ 。现在我们再在当前数字上减去一些 $0$，就可以变成 $\alpha^\prime$。

所以为了计算的方便，可以直接在输入的时候去掉元素的后缀 $0$。

接下来，还有一个性质：

当且仅当 $\alpha^\prime$ 在二进制形式下是 $\beta^\prime$ 的前缀，我们可以将 $\beta^\prime$ 转换为 $\alpha^\prime$。

这里先解释一下，什么是二进制形式下的前缀。有两个数字，$9$ 和 $75$。其二进制形式分别是 $(1001)_2$ 和 $(1001011)$。

那么从字符串的角度来看，$\texttt{1001}$ 就是 $\texttt{1001011}$ 的前缀。而能将 $\beta^\prime$ 转换为 $\alpha^\prime$ 是因为右移操作，我们可以把 $\beta^\prime$ 的尾部去掉使其变成自己的任意二进制下的前缀。

并且，显而易见的，如果 $\alpha^\prime > \beta^\prime$， $\alpha^\prime$ 一定不是 $\beta^\prime$ 二进制形式下的前缀。那就自然不能将 $\beta^\prime$ 转换为 $\alpha^\prime$。

具体实现

有了这些性质，我们就可以搞出一些奇怪的方法了。

首先我们把集合 $a$ 的元素存到一个数组里，把集合 $b$ 的元素存到一个优先队列里。在存之前，需要先去掉后缀 $0$。

vector<int> a(n);
priority_queue<int> b;
for (int i = 0; i < n; i++) { 
    cin >> a[i];
    while ((a[i] & 1) == 0) { // 如果最后一位是 0，那就一直右移来消除后缀 0
        a[i] >>= 1;
    }
}
for (int i = 0; i < n; i++) {
    int temp;
    cin >> temp;
    while ((temp & 1) == 0) {
        temp >>= 1;
    }
    b.push(temp);
}

然后再对 $a$ 升序排序，之后就可以搞出一些骚操作了：

sort(a.begin(), a.end());
while (b.size()) {
    int lb = b.top();
    b.pop();
    int la = a.back();
    if (la > lb) {
        goto FAIL;
    } else if (la < lb) {
        lb /= 2;
        b.push(lb);
    } else {  // la == lb
        a.pop_back();
    }
}

可以看到，在这个 while 中，我们每次取出的 $la$ 和 $lb$ 都分别是 $a$ 和 $b$ 中最大的元素。

那么有三种情况。

1. $la > lb$：这种情况下，可以直接输出 NO 了，因为 $la$ 绝对不是 $lb$ 二进制形式下的前缀（见前文）。而 $lb$ 已经是整个集合 $b$ 中最大的元素了，也就是说如果不能让 $lb$ 转换成 $la$，集合 $b$ 中的其他元素就更不可能转换成 $la$ 了。
2. $la = lb$：因为两个元素相等了，所以可以从集合中去掉（集合为空时，我们就可以输出 YES）。所以有 a.pop_back(); 这句话。
3. $la < lb$：这时我们不知道 $la$ 是否是 $lb$ 的前缀，但是有这个可能性。那我们就直接让 $lb$ 右移一位，变成自己的最长前缀，然后之后再看 $\lfloor \frac{lb}{2} \rfloor$ 是否能跟其他 $a$ 中的元素一样。

对于第三种情况，如果说直接把 $lb$ 右移了然后放入优先队列中，那是否会造成： $lb$ 本来是可以跟 $a$ 中别的元素匹配，但现在不行了的情况呢？

答案是不会的，因为 $a$ 中最大的元素已经小于 $lb$ 了，那其他元素一定也小于它，所以不会有别的元素等于 $lb$ 了。

完整代码

#include <bits/stdc++.h>
using namespace std;
// author: tzyt
// ref: https://www.youtube.com/watch?v=HIiX3r5n27M
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        priority_queue<int> b;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            while ((a[i] & 1) == 0) { // 如果最后一位是 0，那就一直右移来消除后缀 0
                a[i] >>= 1;
            }
        }
        for (int i = 0; i < n; i++) {
            int temp;
            cin >> temp;
            while ((temp & 1) == 0) {
                temp >>= 1;
            }
            b.push(temp);
        }
        sort(a.begin(), a.end());
        while (b.size()) {
            int lb = b.top();
            b.pop();
            int la = a.back();
            if (la > lb) {
                goto FAIL;
            } else if (la < lb) {
                lb /= 2;
                b.push(lb);
            } else {  // la == lb
                a.pop_back();
            }
        }
    SUCC:
        cout << "YES\n";
        continue;
    FAIL:
        cout << "NO\n";
    }
}

最后那个 G2，现在还没完全搞懂，我太菜了。。

最后，希望这篇题解对你有帮助，如果有问题可以通过评论区或者私信联系我。