2 条题解
-
0
暴力过不了是因为大量重复计算,连足够多边之后两个大区间相同的条件并不能给区间中间的元素带来新的限制,连接两个边缘即可
#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
- 上传者