Codeforces Round#697 (Div. 3)

自南京区域赛结束之后就一直在准备期末考试，直到最近结束考试之后开始了复建的生活，这场 Div3 除了 D 题因为爆了 int 然后卡了，G题真的没在比赛期间想出来，其他题目都是非常顺利的解决掉了，且只用了一个小时

A. Odd Divisor

题目大意

给你一个整数，请问它是否存在一个不为 1 的奇因子

题解

因为除 1 以外的所有奇因子都可以分解出至少一个奇质因子，那么只需要找到那些不包含奇质因子的数进行排查就行。而不包含奇质因子的数字很明显就是所有的 2 的幂次，所以打表就可以了。注意别忘记范围超过了 int

AC code

B. New Year’s Number

题目大意

给你一个数，请问它是不是 n 个 2020 和 m 个 2021 相加得到的

题解

把 2021 看成 2020 + 1，那么就变成了 (n + m) 个 2020 和 m 个 1 相加得到，由于 n 肯定是自然数，则只要满足这个数除以 2020 的商(也就是 n + m 部分)大于等于余数(也就是 m)即可

AC code

C. Ball in Berland

题目大意

有两组人，分别为 a 和 b ，有 k 对组合，每对组合都是从 a 中选出一个，从 b 中选出一个。你现在需要选出两对组合，使得这两对组合不会发生冲突，即不会出现 a 中的人同时参与了这两个组合或者 b 中的人同时参与了这两个组合或者两者都同时参与

题解

可以用类似容斥的办法解决。因为保证了每一对组合都不同，所以当我选出一对的时候，那么还有 k - cnt[a] - cnt[b] + 1 对我可以选，其中的 cnt 为这个人参与的组合数量。只需要遍历所有的组合，然后对于每对组合进行求解即可

AC code

D. Cleaning the Phone

大致题意

有一组物品，他们有各自的代价和价值，其中代价只有 1 或者 2 两种，请问如何选择物品，使得代价尽可能小的情况下满足所需要的价值

题解

直接考虑枚举，比如枚举选择了 x 件代价为 1 的物品，求出这时候至少需要多少件代价为 2 的物品，然后枚举所有情况，输出最小的情况即可。

AC code

E. Advertising Agency

大致题意

给你一组数据，要求你从中取出 k 个数据，使得这 k 个数据的之和最大，问有几种取法

题解

首先取最大必然只能从大到小取，直到取满 k 个。但是在取最后几个相同的值的时候，由于有多个选择，则可以产生多个方案。而这个方案数量很明显即为组合数。

AC code

F. Unusual Matrix

大致题意

给你两个 01 矩阵，问能否通过下面两个方式将第一个矩阵转为和第二个矩阵一样

• 将一行的值翻转
• 将一列的值翻转

题解

由于是翻转相同，那么首先直接对这两个矩阵做异或，可以得到一个矩阵，接下来只需要把这个矩阵给转为只有 0 或者只有 1 的矩阵即可

这时候其实可以模拟，假定这行第一个值为 1 则翻转，否者不翻转，然后最后判定是否为纯 0 矩阵

但是这样太麻烦了，其实可以直接判断相邻两行之间是否相同或者相异，即任意两行或者两列的异或结果全为 0 或者 全为 1 则可以，否则不可以

AC code

G. Strange Beauty

大致题意

给你一组数列，请问至少需要删除几个数字，使得整个数列的任意两个值满足大数取模小数为 0

题解

利用素数筛的方式来 dp 求算最多能有多少个值能满足此条件，相减就能得到答案

AC code

Generated by RSStT. The copyright belongs to the original author.

Source