标签：le 题解 CF times leq 数组 序列 考虑 合集

CF 比赛题解合集

\(\downarrow 2023.09.04\)

CF1952, CF1954

1952

A. Ntarsis' Set

有一个集合，初始状态里面有数字 \(1\)、\(2\)、\(3\)、\(4\)、\(5\)、......、\(10^{1000}\)。

现在给你一个长度为 \(n\) 数组 \(a (1\leq a_i \leq 10^9 )\)，要进行 \(k\) 次操作，每次操作将当前集合中第 \(a_1\) 小、第 \(a_2\) 小、......、第 \(a_n\) 小的数同时移除。

请问 \(k\) 次操作之后，最小的数是多少。

顺难则逆。

考虑如果已知删除后在集合中的位置，可以很简单的找到删除前的位置。

所以已知初始的位置，也可以很简单的找到删除后的位置，\(O(n + k)\) 即可。

void work() {
    int n, k; cin >> n >> k;

    for (int i = 1; i <= n; ++i) cin >> a[i];

    lint i = 1, cur = 1, pre = 0;
    while (k--) {
        cur += pre;
        while (i <= n && a[i] <= cur)
            ++cur, ++i, ++pre;
    }

    cout << cur << '\n';
}

B. Imbalanced Arrays

对于一个给定的长度为 \(n\) 的数组 \(A\)，定义一个长度为 \(n\) 的数组 \(B\) 是不平衡的当且仅当以下全部条件满足：

• \(-n \leq B_{i} \leq n\) 且 \(B_{i} \ne 0\)。即每个数在 \([-n,n]\) 内且不为 \(0\)。

• \(\forall i,j \in [1,n], B_{i} + B_{j} \neq 0\)。即数组内不存在一对相反数。

• \(\forall i \in [1,n], \sum_{j = 1}^{n} [ \left (B_{i} + B_{j} \right) > 0] = A_{i}\)。即对于任意的 \(i\)，数组中与 \(B_{i}\) 和大于 \(0\) 的数的个数恰好为 \(A_{i}\)。注意：这里需要计算本身。也即 \(i\) 与 \(j\) 可以相等。

请构造长度为 \(n\) 的不平衡序列。

两种方法，其一可以参见 hfjh。

考虑递归的构造序列，如果当前存在 \(A_i = 0\) 或者 \(A_i = n\)，那么其对应所填的数必定为 \(-n\) 或者 \(n\)。

由于相反数不可能同时出现，所以两个不能同时存在，否则无解。

递归的构造即可。

代码链接：https://codeforces.com/contest/1852/problem/B

C. Ina of the Mountain

• 给定一个长度为 \(n\) 的序列 \(a\) 和正整数 \(k\)。

• 每次可以选择一个区间 \([l,r]\)，\(\forall i \in [l,r],a_{i} = a_{i} -1\)。

• 如果 \(a_{i} = 0\)，则将 \(a_{i}\) 变为 \(k\)。

求让序列全部为 \(k\) 的最小操作次数。

多组测试数据，\(1 \leq n \leq 2 \times 10^{5}\)。

先不考虑 \(\bmod k\) 的情况，则构造差分序列 \(d\)，答案即为：

\[\sum_{i} [d_i \gt 0]d_i \]

那么考虑每次 \(0 \to k\) 的变换，相当于在原序列上加了 \(k\)，然后求上式。

考虑变成差分序列上加减。也就是有地方 \(+k\)，有地方 \(-k\)，使得上式最小。

所以考虑正负平衡一下即可。

代码链接：https://codeforces.com/contest/1852/submission/221761642

能考场切自是极好。

D.Miriany and Matchstick

你有一个 \(2\times n\) 的矩阵，第一行给定（字符串 \(s\)），你需要在第二行的位置填上 \(A\) 或 \(B\)。

你需要构造矩阵的第二行，使得该矩阵相邻的格子不同的个数恰好为 \(k\)。

考虑很 naive 的 DP \(f_{i, 0/1, k}\) 表示填完前 \(i\) 个数，恰好为 \(k\) 是否可行。

打表可以发现，\(k\) 可行的集合至多为两个区间。

证明：每一次转移可以是 \(+1\) 或者 \(+2\)，同时又是前面的两个区间并过来的，所以空缺只会是 \(0/1\) 个。

所以可以压成 \(f_{i, 0/1}\) 即可 /kel

\[f_{i, 0} = (f_{i - 1, 0} \cup (f_{i - 1, 1} + 1)) + (s_i \ne s_{i - 1}) \\ f_{i, 1} = ((f_{i - 1, 0} + 1) \cup f_{i - 1, 1}) + (s_i \ne s_{i - 1}) \]

所以可以用 bitset 对吧。

最后贪心的构造即可。

E. Rivalries

Ntarsis 有一个长为 \(n\) 的数组 \(a\)。

定义一个子数组 \(a_l \cdots a_r\) 的权重为：

• 在整个数组 \(a\) 中，只出现在该子数组 \(a_l \cdots a_r\)中的最大元素 \(x\)。
• 若不存在这样的 \(x\)，权重为 \(0\)。

称数组 \(b\) 与 \(a\) 数组匹配，当且仅当满足：

• \(2\) 者长度相等。
• 数组 \(a\) 中的每个子数组的权重都与数组 \(b\) 对应的子数组的权重相等。
• \(b\) 中的数都为正数。

最大化 \(b\) 的权值和。

\(1 \le n,t \le 10^5\)

考虑几个 hints

• 对于每一个值，只有最左边和最右边的两个之外的区间可以做出贡献。

• 将最左和最右记成二元组，如果存在 \(a_i \gt a_j\) 并且 \(i\) 完全被 \(j\) 覆盖，那么 \(j\) 将无法做出任何贡献。

• 为了不改变权重，我们只可能增加上面所说的 \(j\) 区间。

• 并且至多会有一个区间会加上某一个数。

1954

A. Dual

有 \(t\)（\(1\le t\le 500\)）组数据，对于每组数据给出一个长度为 \(n\)（\(1\le n\le 20\)）的序列 \(a\)（\(-20\le a_i\le 20\)）。

可以进行 \(k\)（\(0\le k\le 31\)）次操作，每次操作任选一组 \(i,j\)（\(1\le i,j\le n\)），把 \(a_i\leftarrow a_i+a_j\)，最后使得整个序列单调不减。

对于每组数据，第一行输出 \(k\)，之后 \(k\) 行输出执行操作的 \(i,j\)。

超级分讨。

考虑到全部变成正的，或者全部变成负的，然后前缀/后缀和即可，这需要 \(19\) 次。

首先找到绝对值最大的那个数。

如果异号的个数 \(\le 12\)，那么直接加上即可。

反之，则同好的个数 \(\le 7\)，那么找到最大的正数，做 \(5\) 次自加操作，然后加上去即可。

代码链接：Submission #221821611 - Codeforces

B. Earn or Unlock

有一长度为 \(n\) 的一副牌，每张牌上都有一个数字，设第 \(i\) 张牌上的数字为 \(a_i\)。初始时，你手里只有第一张牌。对于每一张牌，你有两种选择：

• 如果剩余的牌数量 \(< a_i\)，则将牌摸完，否则继续往下摸 \(a_i\) 张牌。摸牌完成后，这张牌会被丢弃。

• 获得 \(a_i\) 的分数，并丢弃这张牌。

求你能获得的最大分数。

对于所有数据，保证 \(1 \le n \le 10 ^ 5\)，\(0 \le a_i \le n\)。

考虑如果可以摸完 \(k\) 张牌，由于摸一张牌的代价为 \(1\)，所以得分为：

\[- k + 1 + \sum_{i = 1}^k a_i \]

所以判断哪些地方可以摸到即可。

考虑一个 naive 的 \(O(n^2)\) DP。

有：

\[f_i |= f_{i - a_i} \text{~ then ~} f_i = 0 \]

于是可以考虑用 bitset 优化。

所以总的复杂度为 \(O(\frac {n^2} w)\)。

代码：https://codeforces.com/contest/1854/submission/221792387

C. Expected Destruction

给定大小为 \(n\) 的正整数集合 \(S\)，\(S\) 中的每个数在 \(1\sim m\) 之间。

每一秒进行如下操作：

1. 从 \(S\) 中等概率随机选择一个数 \(x\)。
2. 将 \(x\) 从 \(S\) 中删去。
3. 若 \(x + 1\leq m\) 且 \(x + 1\notin S\)，则将 \(x + 1\) 加入 \(S\)。

求 \(S\) 变成空集的期望时间，对 \(10 ^ 9 + 7\) 取模。

\(1\leq n\leq m \leq 500\)，\(1\leq S_1 < S_2 < \cdots < S_n \leq m\)。

\(\downarrow 2023.09.06\)

1830

B. The BOSS Can Count Pairs

多组数据。

每组数据给你一个 \(n\) 和两个序列 \(a,b\)。

求有多少个数对 \((i,j)\) 满足 \(1 \le i < j \le n\) 且 \(a_i \times a_j = b_i + b_j\)

对于每一个 \(i\) 看作用 \(a_i \times x - b_i = y\) 这条线来切所有的点。

注意到当 \(a_i\) 很大的时候的简单的，我们只需要用一个桶记录一下 \((x, y)\) 的个数即可，然后可以 \(O(\frac n {a_i})\) 求出。

此时设一个阈值 \(B\)，当 \(a_i \gt B\) 的时候认为是很大的，所以上面的复杂度可以看作 \(O(\frac n B)\)。

问题在于当 \(a_i\) 很小的时候，注意到其实可以 \(O(B)\) 预处理出 \(\forall k \in [1, B]\) \(k \times a_i - b_i\) 的值。

这样就可以 \(O(1)\) 查询了。

两者稍微平衡一下，令 \(B = \sqrt {2n}\) 于是可以 \(O(n \sqrt {n})\) 解决本题。

代码链接： https://codeforces.com/contest/1830/submission/222008847

C. Hyperregular Bracket Strings

给定一个数 \(n\) 和 \(k\) 个区间 \(\left[l_i,r_i\right]\in [1,n]\)。

我们定义，对于一个长度为 \(n\) 的，仅由 ( 和 ) 组成的合法括号序列，如果它的每一个区间 \(\left[l_i,r_i\right]\) 内的子串都是合法括号序列，那么这个括号序列是好的。

求好的括号序列的数量，答案对 \(998244353\) 取模。

相交和包含的情况很 naive，重点在于如何处理。

类比 \(2023.09.05\) izumi，采用一个随机化异或的做法。

每一个区间附上一个神秘的权值，差分前缀一次。

如果异或权值相同，意味着需要形成一个合法括号，这预处理卡特兰数即可。

rapper 的讲解见：hfjh

代码链接：https://codeforces.com/contest/1830/submission/222007540

D. Mex Tree

给定一棵 \(n\) 个结点的树，点有点权，点权为 0 或 1。你需要给一种指定点权的方案，使得每一条路径的点权 \(\operatorname{mex}\) 之和最大。

\(n\le 2\times 10^5\)，多组数据。

如果考虑跨越多种数的正贡献，发现很难。于是考虑块内的负贡献。

正难则反！！！！！！！！！！！！！！！！！！！！！！！哦

对于每一个连通块，考虑树形背包。

\[\begin{aligned} f_{x, i, 0} &\leftarrow \min(f_{x, i, 0} + f_{j, k, 1}, f_{x, i - k, 0} + f_{j, k, 0} + (i - k) \times k) \\ f_{x, i, 1} &\leftarrow \min(f_{x, i, 1} + f_{j, k, 0}, f_{x, i - k, 1} + f_{j, k, 1} + 2 \times (i - k) \times k ) \end{aligned} \]

关键结论是连通块的大小一定不会很大，否则减少的贡献太多了。

有证明在 \(n \le 2e5\) 小不会超过 \(258\)。

代码：https://codeforces.com/contest/1830/submission/222027041

E.Bully Sort

对于一个非升序的排列 \(\{p_i\}\)，定义一次操作为按顺序执行以下步骤：

1. 令 \(p_i\) 为排列中最大的满足 \(p_i\neq i\) 的数。

2. 令 \(p_j\) 为排列中最小的满足 \(i<j\) 的数。

3. 交换 \(p_i\) 和 \(p_j\)

可以证明在排列非升序的前提下总能找到满足条件的 \(i\) 和 \(j\)。

定义一个排列的权值为将其升序排序所需的操作次数，可以证明总能在有限次操作内将其升序排序，注意如果排列本身就是升序的那么其权值为零。

现在给定一个排列和若干次修改操作，求出每次修改后排列的权值，每个修改操作为交换排列中指定的两个数。

注意修改是永久的。

发现排序方式和冒泡排序很像，于是考虑与逆序对之间的关系。

发现每次交换 \((i, j)\) 使得逆序对的个数减少 \(2(j - i) - 1\)。

发现 \(2(j - i)\) 这个东西很好，考虑交换会影响什么改变 \(2(j - i)\)。

发现 \(\sum_{i = 1}^n |p_i - i|\) 符合要求。

发现两者最后都为 \(0\)。

发现操作次数等于 \(\sum_{i = 1}^n |p_i - i|\) 与逆序对个数之差。

于是动态维护逆序对即可。

发现分块很优秀，\(O(n \sqrt{n \log n})\)，虽然是正常的 \(O(n \log^2 n)\) 的树套树的四倍时间……

代码：https://codeforces.com/contest/1830/submission/222012835

1835

B. Lottery

给定一个长度为 \(n\) 的序列 \(v\)，其值域为 \([0,m]\)。

现在你需要选择一个 \(x \in [0,m]\)，使其权值最大。定义一个数 \(x\) 的权值为：

\[\sum_{c=0}^{m}[\sum_{i=1}^{n}[\vert v_i - c \vert \leq \vert x - c \vert] < k] \]

请你找到权值最大的数 \(x\)，若有多个，输出最小的那个。

考虑 \(k = 1\) 的特殊情况，发现两个人内部的所有点都造成了 \(\frac 12\) 的贡献。所以告诉我们不需要枚举太多的点，在一些点的周围枚举一下即可。

这可以很合理的外推到所有的 \(k\) 的情况。

C.Twin Clusters

给定 \(2^{k+1}\) 个 \([0,4^k)\) 内的整数，请求出任意两个不交非空区间使得其异或和相等，若无解则输出 -1。

抽屉原理抽象题。-1 是不可能的，这一定有解。

于是考虑生日悖论，随机化一些区间即可（逃。

考虑正解，将 \(4^k\) 分成前 \(k\) 位和后 \(k\) 位。

前缀异或和有 \(2^{k + 1} + 1\) 个，而前 \(k\) 位最多有 \(2^k\) 种取值。所以至少会有 \(2^k + 1\) 对前 \(k\) 位相等的前缀。

考虑把这些对找出来，其后 \(k\) 位却也只有 \(2^k\) 种取值，所以至少有两对的后 \(k\) 位的异或值相等。所以就完了。

代码：https://codeforces.com/contest/1835/submission/222050899

D. Doctor's Brown Hypothesis

给定一张 \(n\) 个点 \(m\) 条边的简单有向图和常数 \(k\)，请求出有多少组 \((x,y)\) 满足 \(1\le x\le y\le n\) 且存在一条 \(x\) 到 \(y\) 和一条 \(y\) 到 \(x\) 的长为 \(k\) 的路径，\(k\ge n^3\)。

发现 \(n^3\)，所以发现可以随便走环凑最小公约数。

于是先缩点，在连通块内考虑。

找出生成树，考虑一个非树边，有结论，\(d | \mathrm{abs}(dep_y - dep_x - 1)\)。

所以可以找出 \(d\)，而合法当 \(k \equiv 0 \pmod d\) 或者 \(d \equiv 0 \pmod 2 \text{ and } k \equiv \frac d2 \pmod d\)。

用桶记录一下即可。

代码：Submission #222076413 - Codeforces

标签：le,题解,CF,times,leq,数组,序列,考虑,合集
From： https://www.cnblogs.com/jeefy/p/17692039.html