ACGO 排位赛#4题解Q1-Q4
题解地址：排位赛#4题解Q5、Q6
赛事地址：排位赛#4
直播预告：1月20日（周六）下午4点-6点 B站ACGO官方账号 排位赛#4复盘（欢迎观看大型翻车现场）
直播主讲：アイドル老师 ：小码王C++ 信奥算法讲师，3年C++算法竞赛教学经验，第47届国际大学生程序设计竞赛亚洲区域赛铜奖。
Q1 夺宝升级
题目解析
nnn 个谜题，每个谜题 iii 挑战成功需要当前等级至少为 ai(1≤i≤n)a_i (1 \le i \le n)ai (1≤i≤n) ，挑战成功即可将当前等级提升 bi(1≤i≤n)b_i (1 \le i \le n)bi (1≤i≤n)，谜题挑战的顺序不做限制。
那么显然我们可以按照谜题挑战需要的等级，从小到大挑战谜题。
AC代码
复杂度分析
将谜题按照 aia_iai 从小到大排序时间复杂度为 O(nlogn)O(n\log{n})O(nlogn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Q2 公约数序列
提示1
如果一个数组的最大公约数大于 111，那么说明数组中的每个元素都有一个共同的质因数。
提示2
若 aaa 为奇数，bbb 为偶数，那么 gcd(a,b)\gcd(a, b)gcd(a,b) 的值为多少？
题目解析
要使整个数组的最大公约数大于 111，每个元素都必须有一个共同的质因数，因此我们需要找到数组中出现次数最多的质因数，然后将有这个质因数的数字与没有这个质因数的元素合并，答案就是 数组的大小 - 出现次数最多质因数的出现次数。
因为数字是连续的，所以出现次数最多的质因数一定是 222。因此，我们需要做的最少操作次数就是给定范围 [l,r][l, r][l,r] 内奇数的数量。
令 odd(x)odd(x)odd(x) 表示小于等于 xxx 的奇数的数量，那么答案就是 odd(r)−odd(l−1)odd(r) - odd(l-1)odd(r)−odd(l−1)。
当需要做的最少操作次数小于等于 kkk 时答案为 YES 否则为 NO。
需要注意一个特殊情况是当 l=rl=rl=r 时， 如果 l=r=1l = r = 1l=r=1 那么显然答案为 NO，否则若 l=r>1l = r > 1l=r>1 答案显然为 YES。
AC代码
复杂度分析
对于每个查询我们可以直接计算出 odd(l - 1) 和 odd(r)，所以对于每个用例时间复杂度为 O(1)O(1)O(1)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Q3 树枝
提示
三角形的性质：任意两边之和大于第三边 或 较短两条边之和大于最长边。
题目解析
求给定大小为 nnn 的数组中选择三个元素能够构成一个三角形的方案数。
那么我们需要考虑三角形的性质：任意两边之和大于第三边 或 较短两条边之和大于最长边。
那么一个比较明显的思路是直接三重循环枚举三条边，然后检查即可。
但是这种方法的时间复杂度为 O(n3)O(n^3)O(n3)。本题 n(1≤n≤5000)n(1 \le n \le 5000)n(1≤n≤5000) 显然此种做法无法在时限内通过本题。
那么接下来我们考虑如何优化枚举。
首先考虑真的需要枚举三条边吗？如果我们已经确定了两条较小的边 i,ji, ji,j，就可以确定最长的边的大小最大为 ai+aj−1a_i + a_j - 1ai +aj −1。
为了方便我们可以将数组从小到大排序，然后可以使用二分来确定合法最长边在数组中的范围。此做法时间复杂度为 O(n2logn)O(n^2\log{n})O(n2logn)。
由于本题为单测试点多测试用例，10×5000×5000×log25000≈3×10910 \times 5000 \times 5000 \times \log_{2}{5000} \approx 3 \times 10^910×5000×5000×log2 5000≈3×109，所以此做法仍然无法通过本题。
本题的数据范围要求时间复杂度在 O(n2)O(n^2)O(n2) 及以内的做法，可以考虑把二分优化掉。
在上述枚举两条较短边，再使用二分确定第三条边的做法中，从小到大枚举前两条边，那么他们的长度之和显然是逐渐增大的，确定的两条较小边 i,j(1≤i<j+1<n)i, j(1 \le i < j + 1 < n)i,j(1≤i<j+1<n) ，令数组中 第一个大于等于 ai+aja_i + a_jai +aj 的元素下标为 kjk_jkj ，那么对于边 i,j+1i, j + 1i,j+1 令数组中 第一个大于等于 ai+aj+1a_i + a_{j+1}ai +aj+1 的元素下标为 kj+1k_{j+1}kj+1 ，那么显然 kj≤kj+1k_j \le k_{j+1}kj ≤kj+1
，也就是说第三条边的最大长度是不断变大的。
那么我们便可以不用每次都重复地使用二分来判断最长第三边的位置。而是直接使用一个变量 kkk 来表示 第一个大于等于 ai+aja_i + a_jai +aj 的元素在数组中的位置。随着第二条边的长度 aja_jaj 的增大，那么 kkk 也是不断增大的。这样我们枚举出两条较小边 i,ji, ji,j 后，向后移动 kkk 直到 ai+aj≥aka_i + a_j \ge a_kai +aj ≥ak ，可选的第三条边的数量就是 k−j−1k - j - 1k−j−1 。
AC代码
复杂度分析
两重循环枚举较小的两条边时间复杂度为 O(n2)O(n^2)O(n2) ，第三条边的范围随着第二条边从小到大枚举，也是不断增大的，内层的 while 循环在整个枚举第二条边的过程中最多执行 nnn 次，所以总的时间复杂度为 O(n2)O(n^2)O(n2)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Q4 画板
提示1
至少需要几条直线可以构成一个封闭图形？
提示2
如果存在一组平行线和另一组斜率不同的平行线会是什么情况？
题目解析
提示1：最少 333 条斜率不同且没有相交于同一点的直线可以构成一个封闭图形。
提示2：如果存在一组平行线和另一组斜率不同的平行线，那么必然可以构成一个封闭图形。
根据 提示2 我们将题目分成两种情况。
A. 存在一组平行线和另一组斜率不同的平行线。
B. 不存在一组平行线和另一组斜率不同的平行线。
对于 情况A，我们可以将所有斜率相同的直线的截距 bbb 放到一个集合中，令斜率为 kik_iki 但截距不同的直线数量为 cntkicnt_{k_i}cntki 。
若存在 cntki>1,cntkj>1(ki≠kj)cnt_{k_i} > 1, cnt_{k_j} > 1(k_i \neq k_j)cntki >1,cntkj >1(ki =kj ) 则必然存在封闭区域。
对于 情况B，此时所有的直线中至多有一个斜率 kik_iki 中截距不同的直线数量 cntki>1cnt_{k_i} > 1cntki >1， 对于其他斜率 cntkj=1,(kj≠ki)cnt_{k_j} = 1, (k_j \neq k_i)cntkj =1,(kj =ki )。
那么对于 情况B 我们只需要考虑 提示1 的情况：333 条斜率不同且没有相交于同一点的直线可以构成一个封闭图形即可。
对此我们可以枚举直线 iii，然后枚举直线 j,(ki≠kj)j, (k_i \neq k_j)j,(ki =kj )，若存在两条直线 ja,jb(kja≠kjb)j_a, j_b (k_{j_a} \neq k_{j_b})ja ,jb (kja =kjb ) 和直线 iii 相交与不同的两点，则说明可以构成封闭图形。
在实现上，情况B 留给我们的特殊性质，使得我们可以通过枚举斜率 kik_iki 的方式得到更低的复杂度（思考下为什么）。
AC代码
复杂度分析
对斜率相同的直线集合去重时间复杂度为 O(∣k∣log∣b∣)O(\left|k\right|\log{\left|b\right|})O(∣k∣log∣b∣)。
若为 情况A，此时便可直接得到答案。
若为 情况B，枚举直线时间复杂度为 O(n2)O(n^2)O(n2)，枚举斜率的时间复杂度为 O(n⋅∣k∣)O(n \cdot \left|k\right|)O(n⋅∣k∣)（思考下为什么）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
