cf 1559(div2)

比赛链接：https://codeforces.com/contest/1559

因为一些不良代码习惯，前期做得慢了；掉分T_T

题意：

给两个森林，要求加相同的边，求在两边都不生成环的情况下最多能加多少条边，并输出能加的边。

分析：

可以用set，较暴力地做。

首先，左边森林和右边森林都各自有一些连通块。当我们想要在两点之间连边，需要保证它们在左右两边都不在同一个连通块里。

最终状态一定是某一边的森林变成了一棵树（原因下面细讲）——由于加边是同时的，所以变成树的森林是一开始连通块就比较少的那个森林。下面我们把它作为左边森林。

如果我们在连接左边的两个连通块时，能知道这两个连通块里包含的右边连通块的情况，并且选出两个在右边不是同一个连通块的两个点，连边，就好了。

为了方便想，把左边的连通块成为“行”，右边的连通块成为“列”，行列相交的格子里存放的是同时在两个连通块里的点。

我们用一个map来存格子的“代表点”：mp[a][b]=p表示用p这个点来代表同时在左边a连通块、右边b连通块的那些点。

然后，我们给每一行开一个set，里面存放它的点涉及到的列；给每一列开一个set，里面存放它的点涉及到的行。

这样，当我们想要合并两行时，可以从它们的set中取出两个不同的列，通过map找到对应的两个代表点，然后把它们连边。

问题是，这两行的set中一定有两个不同的元素吗？万一所有的元素都是相同的怎么办？

这需要我们再安排一个合并的顺序——将行按set的大小排序，每次取最大的两个合并。如果最大的那个行的set也只有一个元素，那么所有行的set都只有一个元素；但是前面我们选择让连通块较少的森林作为左边森林，也就是行数(<)列数；所以这种情况一定是行数(=)列数，那么每一行的set里存的元素就是彼此不同的。如果最大的那个行有两个及以上元素，那必然可以找到一个和次大的行中第一个元素不同的元素。

所以我们每次一定能在两行的set中找到符合条件的两个元素，对应了左边森林的两个连通块和右边森林的两个连通块。通过map可以找到同时在左右对应连通块中的代表点，把两个代表点连边即可。

这个过程也告诉我们，最终状态一定是左边森林只剩下了一个连通块，也就是变成了一棵树。

接着，连边了以后我们需要合并两行和两列——这里当然是把小的往大的合并。需要改变的信息是set和map：把被合并者set中的每个元素都放进合并者的set里，并且在那个元素的set里把被合并者删除，加入合并者；对应被合并者的map也要改成对应合并者。时间复杂度(O(nlog^2(n)))。

当然，我们区分各行和各列是用并查集的。

代码如下：

#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#define mkp make_pair
using namespace std;
int const N=1e5+5;
int n,m1,m2,fa[3][N],ans,pl[N],pr[N],t1,t2;
set<int>row[N],col[N];
set<pair<int,int> >rows;
map<int,int>mp[N];
int rd()
{
    int ret=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
    return ret*f;
}
int find(int t,int x)
{
    if(fa[t][x]!=x)fa[t][x]=find(t,fa[t][x]);
    return fa[t][x];
}
void merge1(int x,int y)
{
    for(int it:row[y])
    {
        row[x].insert(it);
        col[it].erase(y); col[it].insert(x);
        mp[x][it]=mp[y][it];
    }
}
void merge2(int x,int y)
{
    for(int it:col[y])
    {
        col[x].insert(it);
        row[it].erase(y); row[it].insert(x);
        mp[it][x]=mp[it][y];
    }
}
int main()
{
    n=rd(); m1=rd(); m2=rd(); t1=1; t2=2;
    for(int t=1;t<=2;t++)
        for(int i=1;i<=n;i++)fa[t][i]=i;
    for(int i=1,x,y;i<=m1;i++)
    {
        x=rd(); y=rd();
        x=find(1,x); y=find(1,y); fa[1][x]=y;
    }
    for(int i=1,x,y;i<=m2;i++)
    {
        x=rd(); y=rd();
        x=find(2,x); y=find(2,y); fa[2][x]=y;
    }
    if(m1<m2)swap(t1,t2);
    for(int i=1,p1,p2;i<=n;i++)
    {
        p1=find(t1,i); p2=find(t2,i);
        row[p1].insert(p2); col[p2].insert(p1);
        mp[p1][p2]=i;
    }
    for(int i=1;i<=n;i++)
        if(find(t1,i)==i)rows.insert(mkp(-row[i].size(),i));
    while(rows.size()>1)
    {
        int x=(*rows.begin()).second;
        rows.erase(rows.begin());
        int y=(*rows.begin()).second;
        rows.erase(rows.begin());
        int a=*row[x].begin();
        int b=*row[y].begin();
        if(a==b)
        {
            set<int>::iterator it=row[x].begin();
            it++; a=*it;
        }
        ans++; pl[ans]=mp[x][a]; pr[ans]=mp[y][b];
        if(col[a].size()<col[b].size())swap(a,b);
        merge1(x,y); merge2(a,b);
        rows.insert(mkp(-row[x].size(),x));
    }
    printf("%d
",ans);
    for(int i=1;i<=ans;i++)printf("%d %d
",pl[i],pr[i]);
    return 0;
}

View Code

分析：

(gcd=1)不好处理，但(gcd)等于某个具体的数（的倍数）的方案数好求。所以我们考虑容斥做。

对于(1)到(m)中的每个数(x)，都求一下(gcd=x)的方案数——这个可以用背包做，只要枚举(x)的倍数即可。但是比赛时卡在时间复杂度的计算上了，以为是(O(nm^2))，还是太不熟悉……这个时间复杂度其实是(O(nmlnm))的，所以可做。

求出这个以后从大到小容斥，把原来的“(gcd)是(x)的倍数的方案数”容斥成“(gcd)恰好是(x)的方案数”，就得到我们要的(gcd=1)的方案数了。

背包DP在转移的时候要用一下差分，否则会TLE……也不能开滚动数组，否则会TLE……看来是每次异或(1)让时间太长了……

代码如下：

#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
int const md=998244353,N=55,M=1e5+5;
int n,m,l[N],r[N],f[N][M],ans[M];
int add(int x,int y){ll ret=x+y; return (ret>=md)?ret-md:ret;}
/*
int cal(int d)
{
    memset(f,0,sizeof f); 
    int t=0,M=m/d; f[1][0]=1;
    for(int i=1;i<=n;i++)
    {
        int L=(l[i]+(d-1))/d,R=r[i]/d;
        for(int j=0;j<=M;j++)f[t][j]=0;
        for(int j=0;j+L<=M;j++)
        {
            f[t][j+L]=add(f[t][j+L],f[t^1][j]);
            f[t][min(M+1,j+R+1)]=add(f[t][min(M+1,j+R+1)],md-f[t^1][j]);
        }
            // for(int k=L;k<=R;k++)
            //     if(j-k>=0)f[t][j]=((ll)f[t][j]+f[t^1][j-k])%md;
        for(int j=1;j<=M;j++)
            f[t][j]=add(f[t][j],f[t][j-1]);
        t^=1;
    }
    int ret=0;
    for(int i=1;i<=M;i++)
        ret=add(ret,f[t^1][i]);
    return ret;
}
*/
int cal(int d)
{
    int M=m/d;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=M;j++)f[i][j]=0;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int L=(l[i]+(d-1))/d,R=r[i]/d;
        for(int j=0;j+L<=M;j++)
        {
            f[i][j+L]=add(f[i][j+L],f[i-1][j]);
            f[i][min(M+1,j+R+1)]=add(f[i][min(M+1,j+R+1)],md-f[i-1][j]);
        }
        for(int j=1;j<=M;j++)
            f[i][j]=add(f[i][j],f[i][j-1]);
    }
    int ret=0;
    for(int i=1;i<=M;i++)
        ret=add(ret,f[n][i]);
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
    for(int i=1;i<=m;i++)ans[i]=cal(i);
    for(int i=m;i>=1;i--)
        for(int j=2*i;j<=m;j+=i)
            ans[i]=add(ans[i],md-ans[j]);
    printf("%d
",ans[1]);
    return 0;
}

View Code