nice problem
2018.7 月赛题解
oxx1108 edited 6 年，4 月前
除了防 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)$。
大鱼吃小鱼
贪心，按以下规则排序。
- 正的优先
- 正的中 $w$ 小的优先
- 负的中 $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，也就是每个数都出现了偶数次的。
由于数据问题需要双哈希更稳妥（对两个质数取模）。
已修正。感谢。