題解

這個題好妙啊
首先我們發現，如果我們可以暴力，就是把相同的元素拿并查集合起來，最后統計集合個數\(cnt\)
答案是\(9\*10^{cnt - 1}\)
然而我們做不到= =
我們可以用倍增的思想，類似st表，一次合并兩個長度為\(2^l\)的區間
然后再從區間長度最長往下下放，從長到短遍歷，就下放一層，之后會繼續遍歷到這層然后下放
最后統計集合個數，復雜度是\(O(n \log n)\)的

代碼

#include <bits/stdc++.h> //#define ivorysi #define MAXN 100005 typedef long long int64; typedef unsigned int u32; using namespace std; const int MOD = 1000000007; int fa[MAXN * 25]; int st[MAXN][20],cnt = 0; int log_2[MAXN],n,m; int lc[MAXN * 25],rc[MAXN * 25]; int getfa(int x) {return x == fa[x] ? x : fa[x] = getfa(fa[x]);} void merge(int x,int y) {if(getfa(x) == getfa(y)) return;fa[getfa(x)] = getfa(y); } void Init() {scanf("%d%d",&n,&m);for(int i = 2 ; i <= n ; ++i) log_2[i] = log_2[i / 2] + 1;for(int j = log_2[n] ; j >= 0 ; --j) {for(int i = 1 ; i + (1 << j) - 1 <= n ; ++i) {st[i][j] = ++cnt;fa[cnt] = cnt;}}for(int j = 1 ; j <= log_2[n] ; ++j) {for(int i = 1 ; i + (1 << j) - 1 <= n ; ++i) {lc[st[i][j]] = st[i][j - 1];rc[st[i][j]] = st[i + (1 << j - 1)][j - 1];}} } void Solve() {int s1,e1,s2,e2;while(m--) {scanf("%d%d%d%d",&s1,&e1,&s2,&e2);int l = log_2[e1 - s1 + 1];merge(st[s1][l],st[s2][l]);merge(st[e1 - (1 << l) + 1][l],st[e2 - (1 << l) + 1][l]);}for(int j = 1; j <= cnt; ++j) {if(!lc[j] || !rc[j]) continue;int t;if((t = getfa(j)) != j) {merge(lc[j],lc[t]);merge(rc[j],rc[t]);}}int sum = 0;for(int i = 1 ; i <= n ; ++i) {if(getfa(st[i][0]) == st[i][0]) ++sum;}int64 ans = 9;for(int i = 1 ; i < sum ; ++i) ans = ans * 10 % MOD;printf("%lld\n",ans); } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve(); }

轉載于:https://www.cnblogs.com/ivorysi/p/9155831.html

總結

以上是生活随笔為你收集整理的【LOJ】#2014. 「SCOI2016」萌萌哒的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。