HDU 5214 Movie (賽碼

五一有幸跟着老師去了一次杭電，求虐之行，坐等清華北大等巨巨AK全場，總結經驗，激勵前進！

【題目連結】​​click here~~​​

【題目大意】在多個不确定區間裡面，問能否選出三個互不相交的區間

【解題思路】 

ps:當時是hjs敲題，敲完之後三個人都檢查了一遍，發現沒有問題,但是交上去卻CE了，後面于是各種調，各種錯誤，最後發現把取模去掉，直接判斷一下是否存在一個區間位于已經出來的區間中間且不交叉即可，悲劇。。。

【官方解題報告】首先我們考慮如何選擇最左邊的一個區間，假設最左邊的區間标号是i, 那選擇的另外兩個區間的左端點必定要大于Ri，若存在i之外的j, 滿足Rj<Ri, 那麼另外兩個區間的選擇餘地必定不會減少，是以，為了使另外兩個區間有盡可能多的選擇，我們選擇一個右端點最小的區間作為最左邊的區間是最好的，同理，我們選擇一個左端點最大的區間為最右邊的區間，也将提供最多的選擇，确定了這兩個區間之後，隻需判斷是否存在一個區間位于它們中間且不交叉即可

本題的取模值十分特殊，用unsigned int的自然溢出可以達到同樣的效果，時間複雜度O(N)

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
const int inf=0x3f3f3f3f;
struct node
{
    unsigned int pre,last;
} Map[N];
int main()
{
    int T,n;
    unsigned int L1,R1,a,b,c,d,maxx,minn;
    bool flag;
    scanf("%d",&T);
    while(T--)
    {
        flag=false;
        cin>>n>>L1>>R1>>a>>b>>c>>d;
        maxx=0;
        minn=inf;
        Map[0].pre=L1;
        Map[0].last=R1;
        for(int i=1; i<n; i++)
        {
            Map[i].pre=Map[i-1].pre*a+b;
            Map[i].last=Map[i-1].last*c+d;
        }
        for(int i=0; i<n; i++)
        {
            if(Map[i].pre>Map[i].last) swap(Map[i].pre,Map[i].last);//全部處理之後再交換！
            if(Map[i].pre>maxx) maxx=Map[i].pre;//左端點最大的區間作為最右邊的區間
            if(Map[i].last<minn) minn=Map[i].last;//右端點最小的區間作為最左邊的區間
        }
        for(int i=0; i<n; i++)
        {
            if(Map[i].last<maxx&&Map[i].pre>minn)
            {
                puts("YES");
                flag=true;
                break;
            }
        }
        if(!flag) puts("NO");
    }
    return 0;
}