暑假期间的最后一篇NOIP题解，有点开心啊。
T1 同余方程
exgcd的模板题，$ax\equiv 1\pmod b\Rightarrow ax+by=1$，用exgcd解出x，(x+b)%b就是x的最小正整数解。
代码在此。
T2 借教室
这题第一眼看上去是用线段树进行区间加并维护区间最小值，但是线段树的常数太大，想尽办法优化也只有95分可以拿，最后一个点会TLE。
正解应该是二分答案，判定时搞一个初值为0的数组a，对于1~mid的每个订单i，$a_{s_i}$递增$d_i$，$a_{t_i}$递减$d_i$，然后对a数组求前缀和，若某一个前缀和小于零，就说明前mid个订单至少有一个无法满足。
不过知道正解的时候代码已经打好了，就不想打正解了……
代码在此。
T3 疫情控制
这题是我这几天做过的最神的一道题了，思路还是二分答案，然后贪心验证。
首先要倍增预处理，二分的判定方法如下：
对于每支部队，让它尽可能向根节点走，如果走不到根节点，就让它停在他能到达的最靠近根节点的地方，能到达的则记录它的编号和到达后剩余的时间，稍后有用。
然后DFS求出那些二层节点能被控制（控制指一个节点上有驻军或其所有子节点都被控制）。
对于每支能走到根节点的军队，如果它的剩余时间不够回到它来的那个二层节点，就让它驻扎在该二层节点。
对剩下的可以到根的军队，按剩余时间从小到大排序。
枚举每一支军队，如果它来的那个二层节点没有被控制就让它控制该二层节点，否则就让他控制还没有被控制且里根节点最近的二层节点。
如果最后还有二层节点没有被控制就说明该时间限制不可行。
这个思路应该是对的，但是我的代码写得比较萎，所以只能过官方数据，在vijos上要WA一个点，TLE一个点。
代码在此。
评论 (0)
