【CF1425B】 Blue and Red of Our Faculty! 题解

原题链接

简要翻译:
有一个连通图,A和B同时从点1出发,沿不同的路径前进。原本,图上的每一条边都是灰色的。A将经过的边涂成红色,B将经过的边涂成蓝色的。每个回合每个人只能走灰色的边。当某个回合中不存在两条不同的灰色路径同时移动A和B时,游戏结束。试求结束时,图上边的涂色情况有多少种?只要有一条边颜色不同,就视为两种情况。特别的,对图中除点1外的点,每一个点都有且只有两条边与之相连
数据范围:
\(2\leq N\leq3e5\),\(2\leq M\leq 2\times N\)
题解:
(说是题解,其实更像是思考过程。想直接看正解的可以下拉到我推导n个环的地方)

显然,我们可以发现,图中所有的环都只有点1一个公共点,或者说,这个图是由以且只以点1为公共点的环构成的

边军训边想想了一整天,我决定打开cf看下标签
Divide and Conquer 分治算法
好吧没看懂

首先,我们先求出环的数量与每个环中点的数量,复杂度为 \(O(N)\) ,简单的遍历即可。
当然,你也可以一边读入一边利用并查集确定除1外每个点的归属,然后直接统计,这样就省去了建图遍历的过程。

染色部分只含有1个环时:

  • 答案加 \(2\) 。(红蓝互换)

染色部分只含有2个环时:

  • 若两个环大小不同,则终点会在较大环里,且由于大小不同,终点不会将环平分,所以终点在环上会有一个对称的位置。再加上红蓝互换,答案加 \(4\)
  • 当然,记得加上含有一个环的情况。
  • 此时,总答案为8。这便是样例的情况。
  • 若两个环大小相同,则终点为1。若图上没有别的环了,则答案加 \(2\) ,否则答案加 \(0\) 。(因为终点为点1,但与点1相连的环还有其他的,可以继续移动)

当含有3个环时,记这三个环的点数分别为 \(a\leq b\leq c\) :

  • 若 \(a+b=c\) ,与上面2个环的情况类似, 当终点在1时,如果只有3个环,答案加 \(2\) ,否则答案加 \(0\) 。当终点在c上时,若 \(a=b\) ,答案加 \(2\) ,否则加 \(4\) 。
  • 否则若 \(a+b<c\) ,显然终点只能出现在第三个环里。当两个小环颜色相同,与两个环的第一种情况同理,答案加 \(4\) ;当两个小环颜色不同,若这两个环大小相同,则终点平分第三个环,答案加 \(2\) ,否则,答案加 \(4\) 。
  • 若 \(a+b>c\) :
    • 若 \(a=b\) ,答案加 \(2(终点在c)+4(终点在b)+4(终点在a)\)
    • 若 \(a<b\) ,答案加 \(4+4+4\)
  • 不难发现:当终点所在环两侧环的点数相同时,答案加 \(2\) ,否则答案加 \(4\)

对于含有n个环的情况下,记这n个环点数分别为 \(a_1\leq a_2\leq ...\leq a_n\)

  • 我们将这些环分为3个部分,\(S_1,S_2,a_k\) ,注意 \(S_1,S_2\) 可以为0,我们记终点在 \(a_k\) 中,且 \(S_1\leq S_2\) ,则 \(a_k\) 可以作为终点环,当且仅当 \(S_1+a_k>S_2\) 。
  • 若 \(S_1=S_2\) ,答案加 \(2\) 。否则,答案加 \(4\) 。
  • 但是,这样的组合会有很多种,枚举显然不能解决问题。
  • 若 \(S_1+a_k=S_2\) ,且没有更多的环时,答案加 \(2\) ,否则答案加 \(0\) 。

假定我们已经求出n-1个环下的答案,现在让我们尝试推导出n个环的答案
思路1:

  • 对于原有的每个对答案有贡献的情形:
  • 注意,此处我们将 \(S_1+a_k=S_2\) 的情形也加入讨论
  • 假若我们是按大小顺序加入环,对于每个 \(S_1+a_k>S_2\) 的情形,如果我们把 \(a_k\) 并入 \(S_1\) ,新环设为终点环,情况仍然是合法的,即满足 \(S_2+a_n>(S_1+a_k)\)
  • 对于 \(a_n<S_2-S_1+a_k\) 的情形,我们将新环并入 \(S_1\) 后,有 \(S_2+a_k>(S_1+a_n)\) ,情况仍然合法
  • ...
  • 下面不再列举出各种情况。但是,我们不难发现,如果我们维护的是各个 \(d=S_2-S_1+a_k\) 的数量,在某些情形下,合并后,我们就无法利用 \(d\) 计算出 \(d'\) ,进而无法更新。如果维护 \(d=S_1-S_2+a_k\) ,也有类似的问题。
  • 比方说,我们维护的是 \(d=S_2-S_1+a_k\) ,对于每个 \(S_1+a_k>S_2\) 的情形,我们将新环设为终点环,把 \(a_k\) 并入 \(S_1\) 之后, \(d'=(S_1+a_k)-S_2+a_n\) ,由于符号的改变,我们无法在只知道 \(d\) 的情况下推出 \(d'\)
  • 而两个同时维护,复杂度又不允许。
  • 也就是说,我们需要更巧妙的维护方式。

在我们上面的分析中,我们都是整个环整个环的操作,并且根据大小关系的合法与否来实现统计和更新,拥有繁琐的判断过程和无法维护的弊端,那么,是否有更为通用的方法呢?

思路2(正解):

  • 我们发现,无论我们维护的 \(d\) 是怎样的形式,\(S_1\) 与 \(S_2\) 总是相抵的。现在,我们将红色边的数量记为正,蓝边数量记为负,则最终我们希望二者相抵为0。

  • 边的变化有两种方式,一是加入整个环,二是将环确认为终点环并加入环中的部分边。

  • 我们让 \(f[i][j][0]\) 表示考虑到第i个环,边数相抵后的值为j,0表示答案是由完整的环加减也就是还未确定终点环下得到的,1表示答案是已经确定了终点环后得到的。

  • 显然,有: \(f[i][j][0]=f[i-1][j-a_i][0]+f[i-1][j+a_i][0]+f[i-1][j][0]\)

  • 接下来我们讨论把当前环i作为终点环的情况

  • 我们将环平分为两个非空的部分,不难发现,以这个环为终点环后其对j值的影响如下:\(1-(a_i-1),2-(a_i-2),...,(a_i-1)-1\) 不难发现,影响是从 \(2-a_i\) 到 \(a_i-2\) 的间隔为2的数,我们记这个影响的集合为 \(D_1\)

  • 应有: \(f[i][j][1]+=\sum f[i-1][p][0]\) , \(p\in D_1\)

  • 另外,别忘了统计终点环不是i但已经确定终点环的情况: \(f[i][j][1]+=f[i-1][j-a_i][1]+f[i-1][j+a_i][1]+f[i-1][j][1]\)

  • 什么?你以为这样就完了?太天真了。

  • 题目可没有保证蓝色和红色最终能到达同一个点。也就是说,可能存在这样的情况:蓝色和红色的终点在同一个环上某条边的两端

  • 注意此时跟上面的情况有点区别,上面我们要求将环平分为非空的两部分,是因为在用上了整个环的情形下,如果红边或蓝边的边数为0,则终点会在1点,而由于1点的特殊性(如果你真的看了我前面的推导思路),我们无法在此处判断把共同终点设在1点是否合法,所以,我们要求两部分非空。

  • 但在现在,我们在环中空出了一条边,不论两部分是否为空,我们都能确定终点(边)在这个环中,所以可以为空

  • 此时,这个终点环对j的影响如下: \(0-(a_i-1),1-(a_i-2),...,(a_i-1)-0\),我们记这个影响的集合为 \(D_2\)

  • 我们发现 \(D_1\cup D_2=[1-a_i,a_i-1]\)

  • 那么我们自然而然地想到,维护f[i-1][j][0]的前缀和,然后 \(f[i][j][1]+=sum[j+a_i-1]-sum[j-a_i]\)

  • 那么恭喜你,这里还有一个坑。

  • 假如我们在环中空出的这条边的一端为1点,也就是上面我们分析到的其中一部分为空的情况,需要满足一个前提条件:用上所有的环。或着这么表述:整个图中空下来保持褐色的,只有这条边,因为如果还有别的环,这个环必然与1相连,那么这两种颜色就可以从1点沿着环继续延伸,这种情况是不合法的。

  • 因此,我们在计算空出了边且边与1相连的情况时,有如下调整:

  • 统计终点环不是i但已经确定终点环的情况时,不能加上 \(f[i-1][j][1]\) ,也就是不能不用这个环。

  • 但这就与我们上面的公式相矛盾。

  • 因此,我们需要将这种情况同以1为终点的情况一起拿出来单独计算。

  • 顺带一提,我们上面算的 \(f[i][j][1]\) 的终点环处经过红蓝互换后可以形成新的答案,所以最终答案要乘以2。

最后是代码:

#include <cstdio>
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
#define Rep(i,a,b) for(REG int i=a;i>=b;i--)
inline char getc(){
    static char buf[1<<14],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline int scan(){
    REG int x=0; REG char ch=0;
    while(ch<48) ch=getc();
    while(ch>=48) x=x*10+ch-48,ch=getc();
    return x;
}
inline void swap(int &A,int &B){
    REG int x=A; A=B; B=x;
}
inline int max(const int&A,const int&B){
    return A>B?A:B;
}
inline int min(const int&A,const int&B){
    return A<B?A:B;
}
const int MOD=1e9+7;
inline int add(int A,int B){
    //if(B<0) B+=MOD
    return B>MOD-A?A-MOD+B:A+B;
}
const int N=2e3+5,M=4e3+5;
int n,m,fa[N],c[N],a[N],cn,f[2][M<<1][2];
inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    n=scan(); m=scan();
    rep(i,1,n) fa[i]=i,c[i]=1;
    rep(i,1,m){
        REG int u=find(scan()),v=find(scan());
        if(u==1||v==1||u==v) continue;
        fa[v]=u; c[u]+=c[v];
    }
    rep(i,2,n) if(fa[i]==i) a[++cn]=c[i]+1;
    REG int zero=m+1,t=1,ans;
    f[0][zero][0]=1; 
    for(REG int i=1;i<=cn;i++,t^=1){
        //直接继承i-1的答案,是这个环不走的情况
        rep(j,1,(m<<1)+1){
            f[t][j][0]=f[t^1][j][0]; 
            f[t][j][1]=f[t^1][j][1];
        }
        rep(j,1,(m<<1)+1){
            if(j-a[i]>0){
                f[t][j][0]=add(f[t][j][0],f[t^1][j-a[i]][0]);
                f[t][j][1]=add(f[t][j][1],f[t^1][j-a[i]][1]);
            }
            if(j+a[i]<(m+1)<<1){
                f[t][j][0]=add(f[t][j][0],f[t^1][j+a[i]][0]);
                f[t][j][1]=add(f[t][j][1],f[t^1][j+a[i]][1]);
            }
        }
        rep(j,1,(m<<1)+1) f[t^1][j][0]=add(f[t^1][j][0],f[t^1][j-1][0]);
        rep(j,1,(m<<1)+1){
            REG int l=max(1,j-a[i]+2),r=min(j+a[i]-2,(m<<1)+1);
            f[t][j][1]=add(f[t][j][1],add(f[t^1][r][0],MOD-f[t^1][l-1][0]));
        }
    }
    //终点环内红蓝互换(或者说把环镜像翻转),答案翻倍
    ans=add(f[t^1][zero][1],f[t^1][zero][1]);
    //printf("t1:%d\n",ans);
    rep(j,1,(m<<1)+1) f[t][j][0]=f[t^1][j][0]=f[t][j][1]=f[t^1][j][1]=0;
    f[t^1][zero][0]=1;
    for(REG int i=1;i<=cn;i++,t^=1){
        //想要以1为唯一终点或终点之一,就不能空出任何环
        rep(j,1,(m<<1)+1) f[t][j][0]=f[t][j][1]=0;
        rep(j,1,(m<<1)+1){
            if(j-a[i]>0){
                f[t][j][0]=add(f[t][j][0],f[t^1][j-a[i]][0]);
                f[t][j][1]=add(f[t][j][1],f[t^1][j-a[i]][1]);
            }
            if(j+a[i]<(m+1)<<1){
                f[t][j][0]=add(f[t][j][0],f[t^1][j+a[i]][0]);
                f[t][j][1]=add(f[t][j][1],f[t^1][j+a[i]][1]);
            }
            //统计空出一条边且该边与1相连的情况
            if(j-a[i]+1>0) f[t][j][1]=add(f[t][j][1],f[t^1][j-a[i]+1][0]);
            if(j+a[i]-1<(m+1)<<1) f[t][j][1]=add(f[t][j][1],f[t^1][j+a[i]-1][0]);
        }
    }
    //对于f[i][0][0]也就是以1为唯一终点的情况 红蓝的各种组合在红正蓝负相抵中已经体现了,不需要互换了。
    ans=add(ans,f[t^1][zero][0]);
    //printf("t2:%d\n",ans);
    //对于f[i][0][1]我们镜像翻转 答案翻倍
    ans=add(ans,add(f[t^1][zero][1],f[t^1][zero][1]));
    printf("%d\n",ans);
    return 0;
}
上一篇:小探究:CSSの渐变


下一篇:java 5.7上机练习