2017 Multi-University Training Contest 2 总结

第二场,各种巧合最后 6 题,是挺好的成绩了,不过毕竟是开黑来的成绩,不能代表什么。这场首先在签到题上卡了很久,这个是非常严重的失误,在后面的找规律也没有找出来,表现挺差的。在写代码的时候也是有很多地方没有考虑到,这些地方都应该在以后注意。最后放上 官方题解 上次忘记关 pingback 了,导致一些丢人的操作😟😟😟😟😟😟。
 

1001 Is Derek lying?

这题在于两个人的分数差是如何产生的,注重那么有多少题答案相同,有多少题答案不同。相同的题有两种可能:他们都对了,他们都错了。不同的题有三种可能:其中一个人对了一个人错了,两个人都错了。从这里入手得到关系。
比赛时 WA 了 3 发,很难受。。。

 

1003 Maximum Sequence

这题利用贪心的思想,我们发现,尽量将较小的 b_i 用在位置靠前的 a_i 上收益最大,所以将 \{b_n\} 从小到大排序,接着就是模拟,因为每次要取一个区间的最大值,所以用线段树即可。

 

1004 Puzzle

很巧的是同学的 Java 课程设计正好写到了这个,判定的规则是将所有拼图编号放在一排,记其逆序对数为 f(s), 若当前状态 st 满足 f(s) \equiv f(t)\ (Mod 2) 即为有解。所以只需统计按题目的要求放入的逆序数的奇偶性即可。
我们只考虑每个数放入后会对以后的影响。首先可以知道的一点是,如果现在还剩下的数,重新按顺序编号后,逆序数不影响,因为大小关系不变。所以我们每次取完 np+1 个后可以看成一个新的序列再去。那么现在考虑放入后对以后能够构成多少对逆序数。例如现在取到了 xp + 1, 在以后能够对他造成逆序的数只有 1 ~ xp, 而这些数中又有被取走的,剩下的个数为 x(p-1) 个,即是当前取到的数对答案的贡献。我们只需模拟取数过程记录逆序数即可。

 

1006 Funny Function

这道题可以找规律,也可强推。
放一个推导链接,RedPolya博客

 

1009 TrickGCD

首先题目的条件可以看成生成出的序列的所有数的最大公因数不为 1,即所有数都有一个共同的不为 1 的因数。所以我们可以从因数去考虑来计数。但是在这个过程中发现有些数被重复算了,比如穷举 4 的时候,它的贡献已经包含在 2 的贡献里了。所以有些因子的贡献得加上,有的得减去,有的得不计入。而这个系数是多少?因为所有数都是在它的质数因子被计入,而类似于 6 的这种由质数相乘而得的数被算了多次。由容斥原理得,我们知道每个质数的贡献的系数为 (-1)^{k+1}, n = p_1 p_2 p_3 ... p_n, 这恰恰就是莫比乌斯反演的系数,可以由线性筛求得。
所以我们先穷举每个数 k, 依次加上贡献,答案即为 \sum_{k = 2}^{100000} (-\mu(k) \prod_{i = 1}^{n} \frac{a_i}{k}).
然而,在计算 \prod_{i = 1}^{n} \frac{a_i}{k} 时我们依旧很头疼,因为复杂度依旧很高。
所以,我们采用前缀和加上快速幂这种优化。数组 s[x] 表示小于 xa_i 有多少个。那我们可以得知,除以 k 等于 ja_is[k*(j+1)-1] - s[k*j-1] 个(前缀和思想)。那这么多数对答案的贡献为 j ^ {s[k*(j+1)-1] - s[k*j-1]}, 可以用快速幂算出。所以,我们只需要穷举除 k 的结果 j 即可。
所以最后的答案为 \sum_{k = 2}^{100000} (-\mu(k) \prod_{j = 1}^{\lfloor n/k \rfloor} j ^ {s[k*(j+1)-1] - s[k*j-1]}).
时间复杂度为 O(n * (1/2 + 1/3 .... + 1/n) * log(n)) 约为 O(nlog^2(n)).

 

1011 Regular polygon

因为是正多边形,每个点都得在整点上,所以只有正方形满足条件。所以穷举两个点作为对角线,算出对答案的贡献,最后除去重复的部分。

 

完结

2 thoughts on “2017 Multi-University Training Contest 2 总结

  1. Pingback: 2017 Multi-University Training Contest – Team 1

发表评论

电子邮件地址不会被公开。 必填项已用*标注