APIO2019

深藏阁楼爱情的钟 2021-11-22 07:00 243阅读 0赞

device：

用最小公倍数的知识或是画网格模拟转移，神仙们也可以找规律。然后就变成区间覆盖了。

忘记特殊情况了，大众分→Ag

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef long long i64;
    const int N=2e6+6;
    const i64 INF=1e18+7;
    
    struct sgm{
        i64 x,y;
        bool operator<(const sgm a)const{
            return x<a.x||x==a.x&&y<a.y;
        }
    }t[N];
    int cnt;
    
    i64 gcd(i64 n,i64 m){
        while(n%m){
            swap(n,m);
            m%=n;
        }
        return m;
    }
    
    int main()
    {
        int n,i;
        i64 a,b,x,y;
        scanf("%d%lld%lld",&n,&a,&b);
        i64 l;
        if(a/gcd(a,b+1)>=(double)INF/b)
            l=INF;
        else
            l=a/gcd(a,b+1)*b;
        for(i=1;i<=n;i++){
            scanf("%lld%lld",&x,&y);
            if(y-x+1>=l){　　//我怎么就这么睿智（
                printf("%lld",l);
                return 0;
            }
            else{
                x%=l,
                y%=l;
                if(x<=y){
                    ++cnt,
                    t[cnt].x=x,
                    t[cnt].y=y;
                }
                else{
                    ++cnt,
                    t[cnt].x=0,
                    t[cnt].y=y;
                    ++cnt,
                    t[cnt].x=x,
                    t[cnt].y=l-1;
                }
            }
        }
        sort(t+1,t+cnt+1);
        x=t[1].x,
        y=t[1].y;
        i64 s=0;
        for(i=2;i<=cnt;i++)
            if(t[i].x>y){
                s+=y-x+1;
                x=t[i].x,
                y=t[i].y;
            }
            else
                y=max(y,t[i].y);
        s+=y-x+1;
        printf("%lld",s);
        return 0;
    }

bridges：

分块

lamps：

不会做咕咕咕

转载于:https://www.cnblogs.com/wanghaoyu/p/APIO2019.html