Deltix Round, Summer 2021[CF1556]
链接
题解
rating：${\color{Yellow} 2162->2147}$。
A
题意
两个初始为 $0$ 的数 $a,b$，可执行以下三种操作：
- 选择一个正整数 $k$，$a+=k,b+=k$；
- 选择一个正整数 $k$，$a-=k,b+=k$；
- 选择一个正整数 $k$，$a+=k,b-=k$；
问 $(a,b)$ 变成 $(c,d)$ 的最小操作次数。
$c,d\geq 0$。
题解
显然若 $c+d\equiv 1\pmod 2$，那么无论如何也无法变成。
否则，由于 $c,d\geq 0$，若 $c=d$，则只需一次操作，否则需要两次。
注意 $(0,0)$ 的特判。
时间复杂度 $O(1)$。
B
题意
给定一个序列，每次可以交换相邻的两个数，问最少的操作次数使得两两相邻数奇偶性不同。
$n\le 10^5$
题解
设 $cnt=\sum_{i=1}^n[a_i\equiv 1\pmod 2]$，若 $cnt> \lceil \frac{n}{2} \rceil$ 或 $cnt < \lfloor \frac{n}{2} \rfloor$，则一定不行。
否则，枚举第一个数的奇偶性，之后依次交替，记录当前向右的第一个奇数与偶数，然后计算。
初始化最值一定要设大一点！！！
C
题意
给定一个长度为 $n$ 的序列，若 $i$ 为奇数，则表示跟着有 $a_i$ 个左括号；若 $i$ 为偶数，则表示跟着有 $a_i$ 个右括号。
形成一个长度为 $\sum a_i$ 的括号字符串，问有多少 $[l,r]$ 满足 $S[l,r]$ 为合法的括号序列。
$n\le 10^3,a_i\le 10^9$。
题解
枚举 $l$ 所在的位置 $i$，然后从小到大枚举 $r$ 所在的位置 $j$，$O(1)$ 判断是否合法并计算即可。
时间复杂度 $O(n^2)$，应该可以优化到一个log或者线性。
D
题意
交互题。
给定 $n,k$，有一个长度为 $n$ 的非负整数数组 $a_1,a_2\cdots a_n$，最多询问一共 $2n$ 次两个不同下标的数的与/或，使得能求出数组 $a$ 的第 $k$ 小。
$n\geq 3$。
题解
显然，因为 $a+b=a & b+a | b$，我们花 $2n-2$ 次，求出 $a_1+a_i(i\geq 2)$。
之后再花 $2$ 次，求出 $a_2+a_3$。然后就可以解得 $a_1$，剩下的 $a_i$ 也全部求出来了。
找第 $k$ 小用 nth_element。
时间复杂度 $O(n)$。
E
题意
对于两个数组 $a,b$，每次操作可以选择偶数个不同的下标，从小到大排好序后，排名为奇数的下标的 $a$ 加一，偶数的下标的 $b$ 减一。
给定两个数组，多次询问某个区间 $[l,r]$，问只在该区间进行上述操作，最少的操作次数使得区间内 $a_i=b_i$。
$n,q$ 在 $10^5$ 级别。
题解
设 $c_i=a_i-b_i$，如果 $\sum_{i=l}^rc_i\neq 0$ 则无解。
如果出现某个 $j$，使得 $\sum_{i=l}^jc_i > 0$ 也无解。
否则，最少的操作次数就是 $\sum_{i=l}^j c_i$ 的最小值取个相反数。
于是，记录 $c$ 前缀和 $s$，每次相当于询问 $s$ 的某个值，$s$ 的区间最大值，$s$ 的区间最小值。
时间复杂度 $O(n\log n)$。
F
题解
对于一个图，如何判断有哪些人赢呢？
强连通分量缩点，又因为是竞赛图，因此只有一个入度为 $0$ 的连通分量，且里面的人会赢。
设 $f_S$ 表示只有集合 $S$ 中的人赢的概率，那么答案就是 $\sum |S|f_S$。
设 $g_S$ 表示 $S$ 中的人两两可达的概率，$h_{S,T}$ 表示集合 $S$ 中的人都赢了 $T$ 中的所有人的概率。
那么 $f_S=g_S\times h_{S,\complement_{U}^{S}}$。
$g_S$ 的计算考虑补集转换，则有 $g_S=1-\sum_{T\subset S,|T|\neq 0}g_T\times h_{T,S-T}$。
枚举子集，暴力 $O(n^2)$ 计算 $h$，时间复杂度 $O({3^n}n^2)$，无法通过。
考虑预处理，优化计算 $h$ 的方法，很容易做到 $O({3^n}n)$。
于是就做完了。
程序
1 |
|