《课程安排》是今年百度之星初赛Day 2的第二题，题目难度明显高于初赛第一天，不少同学在这个位置花了超过预期的时间，所以我在这里将解题的思路整理了一下，希望能够对刷题的小伙伴有所帮助。
题目
【百度之星2022题解】课程安排 题目 （题目版权为“百度之星”所有，原题请参考官网）
思路
- 首先思考一个问题：暴力解法可行吗？n的范围是105，看起来很正常，但是注意s[i]，f[i]，和t[i]的范围都达到了1018，这就明显暗示了，直接暴力会有问题；
- 既然暴力解法不可行，那么题目在什么地方给了我们暗示呢？注意备注的最后一句，特意规定了要么t[i]=t[j]，要么t[i]和t[j]互质，也就是说，避免了t[i]和t[j]为倍数的可能；
- 这个提示为什么这么重要？可以说没有这个提示题目的复杂度将是一个不可控的情况；
- 根据这个提示，可以得到推论如果不同课程的间隔时间（循环节t）不一样，那么一定会相交。看起来因为互质可以找到t[i]和t[j]的最小公倍数，在最小公倍数范围内不相交就不会相交。但实际上，如果两个数互质，那么小循环的节的任意一位数字，会在最小公倍数的重复次数中，出现在大循环节的每一位。原因很简单，如果出现在了之前重复的位置，那么这个位置就已经是一个公倍数了，和最小公倍数的假设相反。（参考扩展欧几里得算法）；
- 那么只有在循环节（t）一样的时候才需要处理；
- 把所有的课程时间全部取模，使其处在[0, t)之间；
- 但是这里要注意，有可能课程结束时间f会因为取模小于开始时间f；
- 这种情况有很多处理方式，比较简单的一种就是在处理时间的时候，把范围扩大到[0, 2t)，也就是如果f<s，那么给f加上一个循环节的时间。但此时循环节依旧是t，只是相当于把因为循环折叠到左边的区间扩展到右边，并没有改变每个课程的实际时间；
- 这时候就可以通过总时间除以循环节大小，计算有多少个循环节，通过一个循环节内的上课时间乘上循环节个数，就能计算循环的课程时间；
- 最麻烦的位置是处理剩余的时间（rem），因为rem和课程时间相交的位置有可能有有多种情况，很容易出错。这时候有几个需要注意的点：
- 有边界要处理，因为之前循环的时候区间是左闭右开；
- 也可以扩展成两个循环体来处理rem；
- 这时候时间的样子是 * * _ _ _ * * _ _ ，* 代表rem时间，_代表实际上没有的时间，用来占位；
- 画图分析各种交叉情况，由于进行了扩展，所以所有的课程都有开始时间<结束时间。那么需要注意的是，课程的开始时间可以分为s≤rem和rem≤s<循环节；
- 然后处理结束时间就可以，对于第一种情况，结束时间可以是min(f, comm)+(f-comm)[当这个数大于0的时候]。对于第二种情况，实际用时就是min(f, rem+comm)-comm+1。
代码
#include<bits/stdc++.h>
#define ll long long
#define AL 1000000000000000000
using namespace std;
struct node
{
ll s, f, t;
};
int n;
ll comm = 0;
bool flag = true;
ll amu = 0;
ll ans = 0;
vector<node> a;
int main( ){
a.clear();
cin >> n;
for(int i = 0; i < n; i++){
node tmp;
cin >> tmp.s >> tmp.f >> tmp.t;
tmp.s = tmp.s % tmp.t;
tmp.f = tmp.f % tmp.t;
if(tmp.s > tmp.f){
tmp.f = tmp.f + tmp.t;
}
a.push_back(tmp);
if(i==0){
comm = tmp.t;
}
else{
if(tmp.t != comm){
flag = false;
break;
}
}
}
// cout<<"flag: "<<flag<<endl;
// cout<<"comm: "<<comm<<endl;
if(flag){
sort(a.begin(), a.end(), [](node a, node b){
return a.f < b.f;
});
amu = a[0].f - a[0].s+1;
for(int i=1; i<n; i++){
if(a[i].s <= a[i-1].f){
cout << "N" << endl;
return 0;
}
amu += a[i].f - a[i].s + 1;
// cout << "amu: " << amu << endl;
}
// cout << amu << endl;
ll shang = AL / comm;
ll rem = AL - shang * comm;
ans = shang*amu;
// cout << shang << " " << rem << endl;
// cout << ans << endl;
for(int i=0; i<n; i++) {
if (a[i].s <= rem) {
ans += min(a[i].f, rem) - a[i].s + 1;
if (a[i].f >= comm) {
ans += min(a[i].f, rem + comm) - comm + 1;
}
} else {
if (a[i].f >= comm) {
ans += min(a[i].f, rem + comm) - comm + 1;
}
}
}
cout << "Y" << endl;
cout << ans << endl;
} else {
cout<<"N"<<endl;
}
return 0;
}
