4 条题解

  • 1
    @ 2026-7-12 16:31:11

    一开始看这里的题解，感觉太复杂，看了一眼锣鼓，讲一种简单一点的解法

    暴力思路

    首先先想一想暴力，每一次限制我们都用一个并查集记录下来每一个点和哪一些点值要一样，最后直接枚举有多少个不同的集，排除掉首位不为零即可

    80分代码

    #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,P=1e9+7;
int fa[N],n,m;
int find(int x){return fa[x]==x?x:(fa[x]=find(fa[x]));}
int qpow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;
	return res;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)fa[i]=i;
	int cnt=n;
	while(m--)
	{
		int a,b,x,y;scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		for(int i=x,j=a;i<=y;i++,j++)
		{
			int tx=find(i),ty=find(j);
			if(tx!=ty)
			{
				fa[tx]=ty;
				cnt--;
			}
		}
	}
	printf("%lld\n",9*qpow(10,cnt-1)%P);
	return 0;
}

    数据好水~~~

    正解思路

    仔细观察发现，这里面每一次我们都要让区间内所有的数都进行同一种操作，我们可不可以同意操作？

    答案是可以的，只需要开一个ST表即可。定义fai,jfa_{i,j}表示ii号点到i+2j−1−1i+2^{j-1}-1号点的区间的公共父亲。每一次限制只需要把ST表更新一下即可。

    限制完了之后我们需要把所有的点统一转移一下，通过把区间对半分之后分开更新，具体如下：

    merge(i,pos,k−1);merge(i,pos,k-1); merge(i+(1<<k−1),pos+(1<<k−1),k−1);merge(i+(1<<k-1),pos+(1<<k-1),k-1);

    最后只需要统计每一个fai,0==ifa_{i,0}==i的个数，在计算即可。

    AC代码

    #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,P=1e9+7;
int n,m,fa[N][18],ans;
int find(int x,int k){return fa[x][k]=(fa[x][k]==x?x:find(fa[x][k],k));}
//二维并查集 
void merge(int x,int y,int k)//合并 
{
	x=find(x,k),y=find(y,k);
	if(x!=y)fa[x][k]=y;
}
int main()
{
	scanf("%d%d",&n,&m);
	int K=int(log2(n));
	for(int i=1;i<=n;i++)for(int k=0;k<=K;k++)fa[i][k]=i;//初始化 
	for(int i=1,l1,l2,r1,r2;i<=m;i++)
	{
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		for(int k=K;~k;k--)if(l1+(1<<k)-1<=r1)//找最大的区间（省事） 
			merge(l1,l2,k),l1+=1<<k,l2+=1<<k;//区间合并 
	}
	for(int k=K;k;k--)for(int i=1;i+(1<<k)-1<=n;i++)
	{
		int pos=find(i,k);
		merge(i,pos,k-1);merge(i+(1<<k-1),pos+(1<<k-1),k-1);//转移 
	}
	int ans=0;
	for(int i=1;i<=n;i++)if(fa[i][0]==i)
	{
		if(!ans)ans=9;//首位不为零 
		else ans=1ll*ans*10%P;//其余情况 
		//因为是int类型可能会炸，用1ll转long long 
	}
	printf("%d\n",ans);//输出 
	return 0;
}
    • 0
      @ 2026-7-12 16:31:45

      思路

      把需要值相同的位，加入同个集合 设 SS 为集合数量，则 ans=9×10S−1ans=9\times10^ {S-1} ，这是由于每个集合可以填 00 至 99 共有 1010 种选择，含首位的集合不能选 00 ，因此只有9种选择。复杂度为 O(n2logn)O(n^2 logn) 。 将询问区间拆分成 若干个小区间（不多于 lognlogn 个），将 区间与区间 合并，最后计算答案时 将区间的信息下放到点上。 fa[i][k]fa[i][k] 表示左端点为 位置 ii，长度为 2k2^ k 的区间所在集合的根的左端点。

      最终计算答案时，将所有层的对应端点合并即可，将每层和他的上层合并。

      代码

      #include <bits/stdc++.h>
using namespace std;
const int maxn = 100005, mod = 1e9+7;
int n, m, fa[maxn][18], ans;

// 第k层倍增并查集（以i为起点，长度2^k的区间）
int find(int x, int k) {
	return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k);
}
void merge(int x, int y, int k) {
	x = find(x,k), y = find(y,k);
	if(x != y) fa[x][k] = y;
}

int main() {
	scanf("%d%d", &n, &m);
	int maxk = log2(n);
	
	// 初始化每层并查集
	for(int i=1; i<=n; ++i)
		for(int k=0; k<=maxk; ++k)
			fa[i][k] = i;
	
	for(int i=1,l1,r1,l2,r2; i<=m; ++i) {
		scanf("%d%d%d%d", &l1,&r1,&l2,&r2);
		
		// 对 [l1,r1] 和 [l2,r2] 做二进制拆分
		// 从大到小拆成若干个 2^k 长度的块
		for(int k = maxk; ~k; --k) {
			// 如果当前 2^k 长度还能放进剩余区间，就取这一块
			if(l1 + (1<<k) - 1 <= r1) {
				
				// 直接合并两个等长 2^k 大块
				// 把一整段相等关系，用 O(logn) 次合并搞定
				merge(l1, l2, k);
				
				// 指针跳过这 2^k 长度，处理剩下的区间
				l1 += 1<<k;
				l2 += 1<<k;
			}
		}
	}
	
	// 从大层往小层拆：大区间相等 → 左右两个子区间也必须相等
	for(int k = maxk; k >= 1; --k) {
		for(int i=1; i + (1<<k) - 1 <= n; ++i) {
			// 找到 i 所在的 2^k 等价块的起点 pos
			int pos = find(i, k);
			
			
			// 把 2^k 区间的等价关系，拆成两个 2^(k-1) 子区间
			// 前半段合并
			merge(i, pos, k-1);
			// 后半段合并
			merge(i + (1<<k-1), pos + (1<<k-1), k-1);
			
		}
	}
	
	// 统计最底层单点连通块
	for(int i=1; i<=n; ++i)
		if(fa[i][0] == i)
			ans = !ans ? 9 : 1LL * ans * 10 % mod;
	
	printf("%d\n", ans);
	return 0;
}
      • 0
        @ 2026-7-12 16:09:23

        两种写法。

        首先对于题干，到最后显然会把整个数化为若干组，每一组内部的书必须相同。根据乘法原理，假设化成了 nn 组，则答案为 9×10n−19\times 10^{n-1}。

        既然相等具有传递性，所以采用并查集维护，最后统计有多少个数对应的根为它自己就可以得出有多少个组。

        线段树+哈希+二分

        我们注意到，在暴力写法中，会超时的原因是我们合并了已经属于同一个集合的两个数，所以排除掉这些情况就可以。

        但显然，一个个扫去判断是不可行的。所以考虑使用哈希来快速进行区间比较。也就是对 fafa 数组进行哈希。考虑到需要修改所有的不同区间，所以在每个位置找到之后的第一个不同的数字。使用二分进行优化。

        考虑合并，对于被合并的那个树，修改里面的所有 fafa。

        总结起来是一个单点修改，区间查询的问题。所以使用线段树维护。

        代码：

        #include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int mx=1e5+5;
const ull base=998245353,mod=1e9+7;
ull p[mx],tree[mx<<2];
int fa[mx];
int n,m;
vector<int> vec[mx];
void up(int root,int l,int r){
	int mid=(l+r)>>1;
	tree[root]=tree[root<<1]*p[(r-mid)]+tree[root<<1|1];
}
void build(int root,int l,int r){
	if(l==r){
		tree[root]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	up(root,l,r);
}
void change(int root,int l,int r,int x,int y){
	if(l==r){
		tree[root]=y;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid){
		change(root<<1,l,mid,x,y);
	}
	else{
		change(root<<1|1,mid+1,r,x,y);
	}
	up(root,l,r);
}
int query(int root,int l,int r,int ql,int qr){
	if(ql<=l && r<=qr){
		return tree[root];
	}
	int mid=(l+r)>>1;
	if(qr<=mid){
		return query(root<<1,l,mid,ql,qr);
	}
	else if(ql>mid){
		return query(root<<1|1,mid+1,r,ql,qr);
	}
	else{
		return query(root<<1,l,mid,ql,qr)*p[(min(r,qr)-mid)]+query(root<<1|1,mid+1,r,ql,qr);
	}
}
int find(int d){
	return fa[d]==d?d:fa[d]=find(fa[d]);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y){
		return;
	}
	if(vec[x].size()<vec[y].size()){
		swap(x,y);
	}
	for(auto v:vec[y]){
		change(1,1,n,v,x);
		vec[x].push_back(v);
	}
	fa[y]=x;
	vec[y].clear();
}
int diff(int l1,int r1,int l2,int r2){
	int l=1,r=r1-l1+1,mid,ans=-1;
	while(l<=r){
		mid=(l+r)>>1;
		if(query(1,1,n,l1,l1+mid-1)!=query(1,1,n,l2,l2+mid-1)){
			ans=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		vec[i].push_back(i);

	}
	p[0]=1;
	for(int i=1;i<=n;i++){
		p[i]=p[i-1]*base;
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		while(true){
			int val=diff(a,b,c,d);
			if(val==-1){
				break;
			}
			merge(a+val-1,c+val-1);
			a+=val,c+=val;
		}
	}
	int ji=0;
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			ji++;
		}
	}
	long long ans=9;
	for(int i=1;i<ji;i++){
		ans=ans*10%mod;
	}
	cout<<ans;
	return 0;
}

        倍增

        考虑到两个区间相等可以拆分成两个区间的子区间相等，可以使用倍增将两个区间拆分成它们的子区间，然后连接起来。

        做到这里，就可以采用常见的倍增进行处理，在最后将相等关系下放到子区间上。

        代码：

        #include<bits/stdc++.h>
using namespace std;
int fa[100005][21];
int lg[100005];
const long long mod=1e9+7;
int find(int x,int y){
	return fa[x][y]==x?x:fa[x][y]=find(fa[x][y],y);
}
void merge(int x,int y,int le){
	x=find(x,le),y=find(y,le);
	fa[x][le]=y;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=2;i<=n;i++){
		lg[i]=lg[i/2]+1;
	}
	for(int i=0;i<=20;i++){
		for(int j=1;j<=n;j++){
			fa[j][i]=j;
		} 
	}
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		int le=lg[b-a+1];
		merge(a,c,le);
		a=b-(1<<le)+1,c=d-(1<<le)+1;
		merge(a,c,le);
	}
	for(int i=20;i>=1;i--){
		for(int j=1;j+(1<<i)-1<=n;j++){
			merge(j,fa[j][i],i-1);
			merge(j+(1<<(i-1)),fa[j][i]+(1<<(i-1)),i-1);
		}
	}
	long long ans=1;
	for(int i=1;i<=n;i++){
		if(fa[i][0]==i){
			if(ans==1){
				ans=9;
			}
			else{
				ans=ans*10%mod;
			}
		}
	}
	cout<<ans;
	return 0;
}
        • 0
          @ 2026-5-10 4:07:37

          Solution

          lxl 上课讲的做法，题解区里竟然没有/jy

          我们考虑开一个并查集，将所有的 k∈[0,r1−l1]k\in [0,r1-l1] 将 l1+kl1+k 和 l2+kl2+k merge 在一起。

          这样子直接做最差是 Θ(nq)\Theta(nq) 的，显然过不去。

          考虑优化。我们发现，复杂度浪费在了，有一些点本来已经是相同的了，但是我们又把他 merge 了一遍，所以浪费了大量时间。我们考虑对序列进行哈希，每次二分找到最近的不相同的节点，然后把他们 merge 起来，再把所有和他们位置相同的节点的哈希值改掉。

          我们考虑使用线段树动态维护哈希值，并查集启发式合并，由于每个节点都只会被合并 log⁡\log 次，然后每次需要花费 log⁡\log 的代价更改哈希值，所以复杂度是 Θ(qlog⁡2n)\Theta(q\log^2{n})。

          这个做法比题解区里大部分做法要强的一点是可以支持在线时时询问和修改，但是常数太大，我的实现在吸氧情况下最慢点跑了 900ms。

          Code

          #include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e5+5,MOD=1e9+7;
const ull base=1145141;
ull p[N];
int fa[N],n,m;
vector<int> vec[N];
struct node {
    int l,r; ull val;
}; node tree[N<<2];
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
void push_up(int k) {
    tree[k].val=tree[ls(k)].val*p[tree[rs(k)].r-tree[rs(k)].l+1]+tree[rs(k)].val;
}
void build(int k,int l,int r) {
    tree[k].l=l; tree[k].r=r;
    if(l==r) {
        tree[k].val=l;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    push_up(k);
}
void update(int k,int qx,int val) {
    if(tree[k].l==tree[k].r) {
        tree[k].val=val;
        return;
    }
    if(qx<=tree[ls(k)].r)
        update(ls(k),qx,val);
    else
        update(rs(k),qx,val);
    push_up(k);
}
int query(int k,int ql,int qr) {
    if(ql<=tree[k].l&&tree[k].r<=qr)
        return tree[k].val;
    if(qr<tree[rs(k)].l)
        return query(ls(k),ql,qr);
    else if(ql>tree[ls(k)].r)
        return query(rs(k),ql,qr);
    else
        return query(ls(k),ql,qr)*p[min(tree[k].r,qr)-tree[rs(k)].l+1]+query(rs(k),ql,qr);
}
void init() {
    p[0]=1;
    rep(i,1,n)
        p[i]=p[i-1]*base;
    rep(i,1,n)
        fa[i]=i,vec[i].push_back(i);
    build(1,1,n);
}
int find(int x) {
    if(fa[x]!=x)
        fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int u,int v) {
    u=find(u); v=find(v);
    if(u==v)
        return;
    if(vec[u].size()<vec[v].size())
        swap(u,v);
    for(auto x:vec[v]) {
        update(1,x,u);
        vec[u].push_back(x);
    }
    fa[v]=u;
    vec[v].clear();
}
int get_diff(int l1,int r1,int l2,int r2) {
    int l=1,r=r1-l1+1,ans=-1;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(query(1,l1,l1+mid-1)!=query(1,l2,l2+mid-1))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    return ans;
}
signed main() {
    scanf("%d%d",&n,&m);
    init();
    while(m--) {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        while(true) {
            int val=get_diff(l1,r1,l2,r2);
            if(val==-1)
                break;
            merge(l1+val-1,l2+val-1);
            l1+=val; l2+=val;
        }
    }
    int ans=9;
	bool flag=false;
    rep(i,1,n) {
        if(find(i)==i) {
			if(flag)
				ans=ans*10ll%MOD;
			flag=true;
		}
    }
    printf("%d\n",ans);
    return 0;
}
          • 1

          [SCOI2016] 萌萌哒

          信息

          ID
          6234
          时间
          1000ms
          内存
          256MiB
          难度
          9
          标签
          递交数
          129
          已通过
          14
          上传者
          1. Language
          2. 兼容模式
          3. 主题
          3. Worker 0, 10ms
          4. Powered by Hydro v5.0.1 Community