2018.7 月赛题解

oxx1108 edited 2 年,9 月前

除了防 AK 题数三角形,其余每题代码不超过 20 行。
前三题 by oxx,后两题 by zerol

数三角形

防ak题,显然计算出三元组后减去三点共线的。

三点共线中先去掉平行坐标轴的,剩下的要么左下右上或者右下左上,然后遍历左下和右上构成的矩形,便可以列出含 gcd 的平方的式子。

接下去就是化简,讲括号里的式子展开,每个都是积性函数,分别做莫比乌斯反演后可变为线性的 (类似于 51nod 上的求 gcd 的和,其中有一个比较难推)。

当然用杜教筛可以做 $10^{10}$ 的数据范围,当然我不会。

其实公式打个表 OEIS 上就能找到,或者直接搜题目有类似的原题。

锐角三角形

签到题(貌似还是太难了),一和二不行,其余分奇偶,偶数 $(0,0),(2,0),(1,s/2)$,奇数 $(1,0),(0,1),((s+1)/2,(s+1)/2)$。

大鱼吃小鱼

贪心,按以下规则排序。

  1. 正的优先
  2. 正的中 $w$ 小的优先
  3. 负的中 $w+a$ 大的优先

证明自己思考。

最小值二分答案或者直接遍历都可以。注意一点就是当 $w+a$ 小于等于 $0$ 时将 $w$ 改为 $1-a$,为了满足任何时刻鱼都要大于零。

数蝌蚪

令 $b_i=a_i-ki$ (0-indexed),然后就转化为把所有数变为相同的非负整数至少要操作多少步。直接取中位数即可(注意要特判小于 0 的情况),当然也可以排个序前缀和维护一下。

注意数据范围会爆 int

对称与科学美

对每一个 $i$ 维护一个二进制数 $b_i$ 表示 $a_1,a_2,\ldots,a_i$ 出现过的数的奇偶性的向量。例如对于数列 $1,2,3,5,2$ 就记忆为 $10101$。每次转移(添加一个新的数)时,只要异或一个 $0\cdots 010\cdots 0$ 就好了。

由于数据规模问题,这个二进制数会非常的长。我们不妨考虑把要异或的那个数对一个质数取模,即异或 $2^{a_i} \bmod p$。这样效果是不变的。想法类似于(就是)哈希(注:不一定要对 2 取幂,可以对其他数取幂,你只需要让每个数对应一个足够随机的数,然后判异或就好了)。

求到了前缀和之后,只要看每个数之前出现了几次就好了。由于异或性质,这段区间就是异或和为 0,也就是每个数都出现了偶数次的。

由于数据问题需要双哈希更稳妥(对两个质数取模)。

Comments

palayutm

nice problem

JacobLiu

锐角三角形
偶数的第三个坐标写反了

ultmaster

已修正。感谢。

你当前正在回复 博客/题目
存在问题!