T4 - AZUSA的计划 题目链接跳转：点击跳转 这道题的难度也不是很高，稍微思考一下即可。 任何事件时间 ttt 对 (a+b)(a + b)(a+b) 取模后，事件可以映射到一个固定的周期内。这样，问题就转化为一个固定长度的区间检查问题。 因此，在读入数字后，将所有的数字对 (a+b)(a + b)(a+b) 取模并排序，如果数字分布（序列的最大值和最小值的差值天数）在 aaa 范围内即可满足将所有的日程安排在休息日当中。但需要注意的是，两个日期的差值天数不能单纯地使用数字相减的方法求得。以正常 777 天为一周作为范例，周一和周日的日期差值为 111 天，而不是 7−1=67 - 1 = 67−1=6 天。这也是本题最难的部分。 如果做过 区间 DP 的用户应该能非常快速地想到如果数据是一个 “环状” 的情况下该如何解决问题（参考题目：石子合并（标准版））。我们可以使用 “剖环成链” 的方法，将环中的元素复制一遍并将每个数字增加 (a+b)(a + b)(a+b)，拼接在原数组的末尾，这样一个长度为 nnn 的环就被扩展为一个长度为 2n2n2n 的线性数组。 最后只需要遍历这个数组内所有长度为 nnn 的区间 [i,n+i−1][i, n + i - 1][i,n+i−1]，判断是否有任意一个区间的最大值和最小值的差在 aaa 以内即可判断是否可以讲所有的日程安排都分不在休息日中。 本题的时间复杂度为 O(Nlog⁡2N)O(N \log_2 N)O(Nlog2 N)。 本题的 C++ 代码如下： 本题的 Python 代码如下：

首先我们需要对d∗id*_id∗i 进行预处理，求得他在一个星期当中的实际变化数值，通过取d∗id_*id∗ i mod A+BA+BA+B即可得出。 随后可以对其进行升序排列，去除重复项后得到序列E=E∗1,E∗2,...,EkE = {E*_1, E_*2,..., E_k}E=E∗1 ,E∗ 2,...,Ek 。 如果答案为Yes，那么序列EEE一定满足： 存在一个i(1≤i≤k)i(1 \leq i \leq k)i(1≤i≤k)，使得(E∗i+1−E∗i)(E*_{i+1} - E_*i)(E∗i+1 −E∗ i) mod (A+B)>B(A + B) > B(A+B)>B ， 边界值E∗k+1=E∗1E*_{k + 1} = E_*1E∗k+1 =E∗ 1。 我们可以尝试着枚举iii的取值，若满足即可输出Yes，否则输出No。 时间复杂度为:O(nlogn)O(nlogn)O(nlogn)