====== 2020牛客暑期多校训练营（第八场） ======

[[https://ac.nowcoder.com/acm/contest/5673 | 比赛链接]]




===== A - All-Star Game =====

Solved by nikkukun.

==== 题目描述 ====

有 $n \leq 2 \times 10^5$ 个球员和 $m \leq 2 \times 10^5$ 个粉丝，一个粉丝可以喜欢多个球员。粉丝 $i$ 喜欢 $j$，当且仅当下面至少成立其一：

  * $i$ 直接喜欢 $j$；
  * $i$ 和另一个粉丝 $i'$ 都喜欢另一个球员 $j'$，同时 $i'$ 喜欢 $j$。
  
你可以选一些球员，使得每个粉丝喜欢其中的至少一个球员，构成全明星阵容。接下来有 $q \leq 2 \times 10^5$ 次修改，每次修改一个粉丝 $i$ 对 $j$ 的喜欢关系，每次都让你回答全明星阵容需要的最少球员数，或说明不可行。

==== 解题思路 ====

会发现喜欢关系其实就是无向图的连通性，只要维护粉丝阵容有多少个连通块，以及有多少个粉丝是独立点即可。维护图的连通性可以用线段树分治 + 可撤销并查集，总时间复杂度 $O(q \log q \log (n + m))$。








===== E - Enigmatic Partition =====

Solved by nikkukun & qxforever.

==== 题目描述 ====

令一种 $n$ 的分割为 $n = \sum _{i=1}^m a_i$，且满足：

  * $a_i$ 为整数且在 $[1, n]$；
  * $0 \leq a_{i+1} - a_i \leq 1$；
  * $a_m = a_1 + 2$；

记 $f(n)$ 为 $n$ 的分割方式，多次询问 $f$ 函数的区间和，$1 \leq n \leq 10^5$。

==== 解题思路 ====

令 $a_1 = x$，记 $a_i \geq a_1 +1$ 的个数是 $p$，$a_i \geq a_1 + 2$ 的个数是 $q$，那么有范围 $1 \leq q < p < m,\ 3 \leq m \leq n$，于是有 $n = xm + (p + q)$。

打表发现对固定的 $m$，有 $p + q$ 的贡献是一个类似等差数列的东西，于是可以先枚举 $m$ 再枚举 $x$，每次对一个区间加等差数列，最后单点求值。区间加等差数列可以用二阶差分，最后求两次前缀和还原即可。

总时间复杂度 $O(n \log n)$。


===== G - Game Set =====

Solved by qxforever.

==== 题目描述 ====

给 $n$ 张互不相同的牌，每张牌有 $4$ 条属性，每个属性有 $3$ 种。还有一种额外属性表示可以取任意属性。问能否找到一个三张牌的集合，满足每张牌的每种属性都相同/不同。$T\le 1000$，$n\le 256$

==== 解题思路 ====

比赛的时候想的很麻烦，用 $8$ 位二进制数表示一张牌的状态，预处理了所有合法的三元组。算了下复杂度还是很紧，又加了一些优化。
其实在 $21$ 张牌中必定存在满足条件的集合，直接 $n^3$ 搜就可以了。

===== I - Interesting Computer Game =====

Solved by Potassium.

==== 题目描述 ====

给两个长为 $n$ 的数组 $a,b$，对于每个下标 $i$，任选 $a_i$ 或 $b_i$ 加入到集合中，问最终集合最大有多大。$1 \le N \le 10^5$。


==== 解题思路 ====

一开始用左部 $i$ 右部 $a_i,b_i$ 的二分图做最大匹配，但复杂度显然并不对。

考虑 $(a_i,b_i)$ 连边，每条边选择一个端点或不选。对于一个连通块，如果没有环，那必然所有边都可以被选中；否则，环上所有点显然可以全部选中，归纳可知必然所有点都可以被选中。












===== K - Kabaleo Lite =====

Solved by nikkukun.

==== 题目描述 ====

有 $n \leq 10^5$ 种美食，第 $i$ 种获益 $a_i$（可负），存货量为 $b_i$。为一个客人提供菜品只能是从 $1$ 开始到某个菜为止的序列，问最多能给几个客人上菜，以及此时的最大收益。

$|a_i| \leq 10^9$，$1 \leq b_i \leq 10^5$。

==== 解题思路 ====

首先最大上菜人数一定是 $b_1$，然后可以让 $b_i$ 变成非升的，因为 $b$ 会受前面菜品的限制。考虑 $a_i$ 的前缀和 $s_i$，两个 $i < j$，如果 $s_i \geq s_j$，那必然选 $[1, i]$ 更优，所以 $s$ 可以变成一个非降的，最后贪心按 $s_i$ 从后往前选即可。

注意范围很坑，答案最大可以有 $10^9 \times 10^5 \times 10^5 > 2^{63}$，要用 ''__int128'' 存。





===== 赛后总结 =====

==== nikkukun ====

正式写题前都和队友先确认一遍做法，保证了做法至少不会像上次一样写完了才发现是假的。不过调 bug 的时间还是有点多，甚至写了一个暴力去对拍（实际是肉眼就可以调出来的问题），应该优先肉眼调调。

字符串相关理论掌握得还不太熟，虽然猜中了一点结论，但如果真上机写应该也不是对的，需要加强这方面练习。


==== qxforever ====



==== Potassium ====