小胖的奇偶（Viojs1112）题解

原题：

题目描述

　　 huyichen和xuzhenyi在玩一个游戏：他写一个由0和1组成的序列。 huyichen选其中的一段（比如第3位到第5位），问他这段里面有奇数个1 还是偶数个1。xuzhenyi回答你的问题，然后huyichen继续问。 xuzhenyi有可能在撒谎。huyichen要检查xuzhenyi的答案，指出在xuzhenyi的第几个回答一定有问题。有问题的意思就是存在一个01序列满足这个回答前的所有回答，而且不存在序列满足这个回答前的所有回答及这个回答。

输入格式

第1行一个整数，是这个01序列的长度（≤1000000000)（≤1000000000) 第2行一个整数，是问题和答案的个数(≤5000)(≤5000)。第3行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是xuzhenyi的回答。odd表示有奇数个1，even表示有偶数个

输出格式

输出一行，一个数X,表示存在一个01序列满足第1到第X个回答，但是不存在序列满足第1到第X+1个回答。如果所有回答都没问题，你就输出所有回答的个数。

很明显，这道题是并查集（不要问我怎么看出来的）。

由于数据太大，需要离散化。

所谓离散化，就是把较大的一组数进行排序，然后对他们根据大小重新赋值，当数的大小不对数据本身有影响，只有大小对其有影响时，可以使用离散化。

离散化的标准姿势见点这里

然而蒟蒻并不会标准姿势，说说自己的方法：

以本题为例，把所有的数据都存在nd结构体中

void init()

{

    for(int i = ;i<=m;i++)

    {

        int x,y;

        scanf("%d%d%s",&x,&y,c);

        nd[i].p = x;//数组开三倍，p表示临时变量。一倍存左端点。

        nd[i+m].p = y;//二倍存右端点。

        nd[i].num = i;//每一倍都要给他们打上编号，一会排序时后会乱。

        nd[i+m].num = i;if(c[]=='e')

        {

            nd[i+m+m].odd = ;//三倍存奇偶

        }else

        {

            nd[i+m+m].odd = ;

        }

    }

}

读进来之后进行离散化。

void discretization()

{

    for(int i = ;i<=*m;i++)

    {

        if(nd[nd[i].num].l==-)

        {

            nd[nd[i].num].l = cnt-;

        }else

        {

            nd[nd[i].num].r = cnt;

        }

        if(nd[i+].p!=nd[i].p)

        {

            cnt++; //去重，不一样的时候再+1

        }

    }

    for(int i = ;i<=m;i++)

    {

        nd[i].odd = nd[i+m+m].odd;从三倍搬回原数组

    }

}

这样就离散完了。

接下来就是带权并查集的操作。

在合并和路径压缩的时候处理。

思路就是将一个区间右面的点认左面的点为父亲，两端区间合并的时候，根据奇偶性判断，0表示偶数，1表示奇数（有点懒，具体0或1见代码）。

int find(int x)

{

    if(f[x]==x)

    {

        return f[x];

    }

    int fx = find(f[x]);

    g[x] = (g[f[x]]+g[x])%;

    return f[x] = fx;

}

最后上总代码：

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

#define N 105550

using namespace std;

char c[];

ll n;

int m;

int cnt = ;

struct node

{

    int l;

    int r;

    int num;

    int odd;

    int p;

}nd[N+N+N];

int f[N];

int g[N];

int cmp(node a,node b)

{

    return a.p < b.p;

}

void init()

{

    for(int i = ;i<=m;i++)

    {

        int x,y;

        scanf("%d%d%s",&x,&y,c);

        nd[i].p = x;

        nd[i+m].p = y;

        nd[i].num = i;

        nd[i+m].num = i;

        nd[i].l = -;

        nd[i+m].l = -;

        if(c[]=='e')

        {

            nd[i+m+m].odd = ;

        }else

        {

            nd[i+m+m].odd = ;

        }

    }

}

void discretization()

{

    for(int i = ;i<=*m;i++)

    {

        if(nd[nd[i].num].l==-)

        {

            nd[nd[i].num].l = cnt-;

        }else

        {

            nd[nd[i].num].r = cnt;

        }

        if(nd[i+].p!=nd[i].p)

        {

            cnt++;

        }

    }

    for(int i = ;i<=m;i++)

    {

        nd[i].odd = nd[i+m+m].odd;

    }

}

int find(int x)

{

    if(f[x]==x)

    {

        return f[x];

    }

    int fx = find(f[x]);

    g[x] = (g[f[x]]+g[x])%;

    return f[x] = fx;

}

int ans;

bool flag;

void uion(int x,int y,int i)

{

    int fx = find(x);

    int fy = find(y);

    if(fx==fy)

    {

        if((nd[i].odd==&&g[x]==g[y])||(nd[i].odd==&&g[x]!=g[y]))

        {

            ans = i-;

            flag = ;

            return ;

        }

        find(y);

        find(x);

    }else

    {

        f[fy] = fx;

        g[fy] = (g[x]+g[y]+nd[i].odd)%;

        find(x);

        find(y);

    }

}

void solve()

{

    for(int i = ;i<=cnt;i++)

    {

        f[i] = i;

    }

    for(int i = ;i<=m;i++)

    {

        int l = nd[i].l;

        int r = nd[i].r;

        uion(l,r,i);

        if(flag==)

        {

            printf("%d\n",ans);

            return ;

        }

    }

    printf("%d\n",m);

}

int main()

{

    scanf("%lld",&n);

    scanf("%d",&m);

    init();

    sort(nd+,nd++m+m,cmp);

    discretization();

    solve();

    return ;

}

巴特西

小胖的奇偶（Viojs1112）题解

题目描述

输入格式

输出格式

最新文章

热门文章