Educational Codeforces Round 120
https://codeforces.com/contest/1622
E. Math Test
n个学生,
m个题目
你知道每个学生 哪些题目对了哪些题目错了, 正确得分错误不得分
r[i] = 第i个学生的真实得分 = 正确题目得分之和
x[i] = 第i个学生的标准得分, 给定
问如何给题目 的分设置为 1~m 的排列
能让 sum |xi-ri| 最大, 求最大值
范围
n 10
m 1e4
2s
256mb
我的思路
这n很小, 就很想bitmask
但是 bitmask怎么用
想的是 分别计算 f(bitmask) = bitmask中的学生真实得分 >= 标准得分, 其它的学生 真实 < 标准
这样去掉了绝对值
然后如何算呢
这样得到 10个 不等式 和一个要求的最大值
正确错误的1/0串[i] * 题目分数设置 = r[i] >= x[i]
…
正确错误的1/0串[j] * 题目分数设置 = r[j] < x[j]
…
要求 max( 正确错误1/0加权和 * 题目分数设置)
有点像线性规划?
但一个是排列, 一个是又有大于等于, 又有小于等于, 并不知道怎么搞
题解
注意到 |xi-ri| 只有两种可能, xi-ri 或者 ri-xi
可以尝试 2^n 个, 但是不需要不等式
对于每个学生, 选定它们给答案贡献什么
那么一个题目 的 分数贡献为 权重和 * 题目分数
那么权重和越大的题目 期望的分数越大, 贪心就完了…..
F. Quadratic Set
如果 序列a 中的数 的阶乘 乘积为平方数, 那么这个序列是 quadratic, ($\prod\limits_{i=1}^{k} a_i! = m^2$)
在 [1,2,3,…,n] 中找最大(元素个数最多)的子集, 使得子集为 quadratic
范围
n 1e6
4s
256mb
我的思路
1e6 是不是都可以打表了
假设选出来的是 a0,a1,a2…
因为是[1,..n] 的子集, 所以两两不同
考虑对它们排序
如果有偶数个, 那么可以看成 两个两个一组, 构成的中间值的乘积为平方数, 因为 a0! a1! = (a0!)^2 (a0+1…a1)
如果有奇数个, 注意到1一定在, 所以去掉1的部分 一定也可以 变成区间
所以问题变成
在 [1…1e6] 之间, 最多找多少个不相邻区间, 让所有区间中的数字乘积为平方数
例如样例2
1,3,4 => 3,4 => (3,4] = [4]
例如样例3
1,4,5,6 => (1,4], (5,6] => [2,3,4] [6]
一个方法时 把n/2 以上的偶数选了, 这样对应小的部分是连续的, 和它又成对
[k...w] <= [2k,2(k+1),2(k+2) .... 2w]
这样保证2的个数, 大概是 n/4 左右的方案数, 但注意到 [1..k-1] 还没有选, 所以 递归下去, 1/4+1/4(1/4+1/4(…))大概有 ~n/3 左右的方案数
但这里要最大, 要么能证明 这就是上限, 要么这个观察就毫无用处
比如 7:
7/2=3.5
[2,3] [4],[6] => [2...4],[6] 是一个最优解
9:
9/2=4.5
[3,4] [6],[8] => 也是最优解
题解
一个好的开始是打表看一下小数据, 小数据里不会小于n-3
如果n是偶数, 按照奇偶拆开, 令$n=2k$
$\prod\limits_{i=1}^{2k} i! = \prod\limits_{i=1}^{k} (2i-1)! (2i)! = \prod\limits_{i=1}^{k} (2i-1)!^2 2i = (\prod\limits_{i=1}^{k} (2i-1)!)^2 \prod\limits_{i=1}^{k} 2i = (\prod\limits_{i=1}^{k} (2i-1)!)^2 2^k k!$
说明 最多去掉2(看k奇偶),n/2 就是一个解答
而如果n是奇数, 最多需要去掉n,2(看k奇偶),(n-1)/2 就是一个解答
所以下界很明显
所以要做的就是, 检查有没有办法不去除,去除1个,去除2个的方案
使用 xor hash!
给每个质数一个64bit 随机映射
乘法就是对应的做xor hash
总结
E
这评分只有2200
哎, 我好蠢啊, 这又是属于使用|a-b| = max(a-b,b-a) 的性质, 这个就是可以真的去掉, 而可以省去 不等式的限制, 这样增加了不少 “不可能存在的值”,但是又不会影响最大值的正确性
F
没有去打表看一下小数据…. 很不应该, 这个推还是很自然的
xor hash 印象中 应该遇到过,但应该也只遇到过一次
好奇这个能不能再多点数学, 连最后的xor hash都省略掉