Codeforces Round 697(Div 3)题解(1475A~G)
(zhanglichen 2021.2.11)
(A.Odd Divisor)
题意：
检验(n)是否有大于1的奇数除数。
题解：
除了2的整数次幂，都是合法答案。
所以不断把(n)除2，看看是否能遇到奇数即可。
时间复杂度(O(logn))。
(B.New Year's Number)
题意：
询问(n)是否可以化成若干个2020和若干个2021的和。
题解：
贪心的做法是先把(n)分成尽可能多的2020，分不了的数给已经被分配的2020，让它们中的一部分变成2021。
所以可以设(x=n/2020)，(y=n\%2020)。
当(y<=x)的时候，就一定有解。
时间复杂度(O(1))。
(C.Ball in Berland)
题意：
给出来参加舞会的男生和女生的人数，然后给出(k)对必须在一起跳舞的夫妇。
现在请你必须选出2对来跳舞，但是不能有一个男生都在2对中，或者一个女生都在2对中。
询问有多少种选择方法。
题解：
给出的男生和女生人数其实是没啥用的。
考虑枚举单独选择每一对的情况，假设我们当前枚举的是第(i)对，那么与第(i)对能凑成组合的只可能是不包含这一对的男生和女生的对。
这样我们就可以先预处理出每个男生参加了多少对，每个女生参加了多少对。
然后枚举每一对。
假设我们当前枚举的这一对，男生叫(x)，女生叫(y)，那么可以与这一对一起选的对数就是(k-cnt(x)-cnt(y)+1)
为什么最后要加一，因为之前的减法把这一对本身也算进去了。
时间复杂度(O(n))。
(D.Cleaning the Phone)
题意：
给出(n)个手机应用，它们每个占用一定的内存(a_i)，删除它们自身需要花费费用(b_i)。
(b_i)只可能是1或2。
现在想删除至少(m)个内存的应用，询问怎么删使得总费用最少。
题解：
注意到(b_i)只可能是(1)或(2)这个条件。
首先考虑本题的弱化版本：
每个手机应用占用的费用都一样，怎么删使得总费用最少。
那肯定是删除最少的应用费用最少。所以就把所有应用从大到小排个序，然后从前往后枚举，一旦总内存大于(m)了就停止，这样费用一定是最少的。
再回到这个问题。
当删除花费1的应用数量固定时，删除花费2的应用的数量也固定。
考虑这个思路：
对花费1和花费2的应用分两个数组存，分别从大到小排序。然后枚举删除花费1的应用的数量的方案，取最优解。
那么怎么对每个方案取删除花费2的应用的方案数呢？
考虑先预处理花费2的数组的前缀和，转化为对花费2的数组的前缀和数组取1个最小的下标使得总内存大于等于(m)。
前缀和数组具有单调性，这一步可以二分。
所以枚举+二分顺利通过此题。
时间复杂度(O(nlogn))。
(E.Advertising Agency)
题意：
给出一个数组，可以选择其中的(k)个数字。
询问选择数字和的方案数最大有多少种。
题解：
首先我们将数组排序，取前(k)个最大的，作为一种方案。
其他方案的种数只和数组里有多少个和第(k)个数一样的数有关。
假设前(k)个里有(x)个和第(k)个数一样，整个数组里有(y)个和第(k)个数一样。
问题就转化为在(y)个一样的数里选(x)个有多少种选法。
那就是简单的排列组合问题了。求组合数可以暴力也可以卢卡斯。
(F.Unusual Matrix)
题意：
给出2个01矩阵(A)和(B)。
支持2种操作：
垂直异或：取(A)里的一列元素异或1。
水平异或：取(A)里的一行元素异或1。
询问是否可以异或使得(A)变成(B)。
题解：
对于一个元素来说，想让他发生变化，所在的行和列必须有一个被操作奇数次。
对于一行来说：
如果它被操作奇数次，那么这一行上面不同的元素所在的列必定被操作偶数次。
如果它被操作偶数次，那么这一行上面不同的元素所在的行必定被操作奇数次。
可以把每一行每一列操作奇数次、偶数次单独作为点建图，然后并查集，看是不是有一个连通块包含2n个点。
可以证明同一行不会合并。
时间复杂度(O(nlogn))。
(G.Strange Beauty)
题意：
一个漂亮数组被定义为：数组里的元素两两之间可以被整除。
询问数组(a)删除的最少元素，使得剩下的元素组成的数组是漂亮数组。
题解：
先将数组(a)从小到大排序。
然后从前往后枚举，定义状态(f(x))为以元素(x)结尾的漂亮序列的最大长度。
对于(a)里的每个元素(y)，只需要枚举(y)的所有因子的状态，取最大的+1，就是以(y)结尾的最优解。
最后(min_{i=1}^n(n-f(a_i)))就是答案。
时间复杂度(O(nsqrt n))