2 条题解

  • 0
    @ 2026-11-9 20:48:17

    暴力过不了是因为大量重复计算,连足够多边之后两个大区间相同的条件并不能给区间中间的元素带来新的限制,连接两个边缘即可

    #include<bits/stdc++.h>
    #define mod 1000000007
    using namespace std;
    int n,m,k,jc,l1,r1,l2,r2;
    long long ans=1;
    vector<int> to[100007];
    bitset<100032> vis;
    void dfs(int i){
        vis[i]=true;
        for(int j : to[i]){
            if(!vis[j]){
                dfs(j);
            }
        }
    }
    signed main(){
    	ios::sync_with_stdio(0);
        cin.tie(0);
        cin>>n>>k;
        for(int i=1;i<=k;++i){
            cin>>l1>>r1>>l2>>r2;
            if(l1==l2){
                continue;
            }
            if(l1==1||l2==1){
                jc=1;
            }
            if(m>7251031){
                for(int j=l1;j<=min(r1,l1+15);++j){
                    to[j].emplace_back(j+l2-l1);
                    to[j+l2-l1].emplace_back(j);
                    ++m;
                }
                for(int j=max(l1+16,r1-15);j<=r1;++j){
                    to[j].emplace_back(j+l2-l1);
                    to[j+l2-l1].emplace_back(j);
                    ++m;
                }
                continue;
            }
            for(int j=l1;j<=r1;++j){
                to[j].emplace_back(j+l2-l1);
                to[j+l2-l1].emplace_back(j);
                ++m;
            }
        }
        for(int i=1;i<=n;++i){
            if(!vis[i]){
                dfs(i);
                ans*=(i==1 ? 9 : 10);
                ans%=mod;
            }
        }
        cout<<ans;
        return 0;
    }
    

    信息

    ID
    897
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    24
    已通过
    6
    上传者