其实后两道题还挺简单的，就是在板题上进行了变形……（那我为什么没写出来呢？）

 

---

 

 

奇偶游戏

 

题目描述

　　你和你的朋友玩一个游戏。你的朋友写下来一连串的0或者1。你选择一个连续的子序列然后问他，这个子序列包含1的个数是奇数还是偶数。你的朋友回答完你的问题，接着你问下一个问题。

　　你怀疑你朋友的一些答案可能是错误的，你决定写一个程序来帮忙。程序将接受一系列你的问题及你朋友的回答，程序的目的是找到第一个错误的回答i，也就是存在一个序列满足前i-1个问题的答案，但是不满足前i个问题。

输入

　　第一行有一个整数L（L<=1000000000）,是这个01序列的长度。第二行是一个整数N(N<=5000),是问题及其答案的数目,接下来N行描述问题和答案。每一行包含一个问题和这个问题的答案：两个整数（子序列的起始位置和结束位置）和一个单词‘even’或者‘odd’,‘even’表示这个子序列中的‘1’的个数是偶数，‘odd’则表示是奇数。

输出

　　输出一行一个整数X。表示存在一个01序列满足前面的X个问题，但是不存在一个01序列满足前X+1个问题，如果存在一个序列满足所有问题，则输出N。

样例输入

　　10

　　5

　　1 2 even

　　3 4 odd

　　5 6 even

　　1 6 even

　　7 10 odd

样例输出

　　3

解析

　这道题并没有想出来，尤其是用并查集……

　　所以说嘛，有个好东西叫：扩展域并查集。

　　若[a,b]中出现了偶数个1，则表示[0,a-1]和[0,b]的1的奇偶性相同。 

　　若[a,b]中出现了奇数个1，则表示[0,a-1]和[0,b]的1的奇偶性不同。

 

　　这样就可以用并查集来维护：

 

　　fa[i]代表[0,i]有偶数个1，fa[i+len]代表[0,i]有奇数个1。

 

　　若[a,b]有偶数个1，则合并fa[a-1]和fa[b]，fa[a-1+len]和fa[b+len]。 

　　若[a,b]有奇数个1，则合并fa[a-1]和fa[b+len]，fa[a-1]和fa[b+len]。

 

　　对于每次操作，提前查询一下另一种回答所对应的集合是否是同一个，来判断是否矛盾。

　　解析来自：https://blog.csdn.net/loi_dqs/article/details/49103557

代码

　　

#include
     
      #include
      
       #include
       
        using namespace std;int ans[10001][4],num[10001],rf[10001],s[10001];void getnum(int &x,int l,int r){    int mid=(l+r)>>1;    if (num[mid]==x)    {        x=mid;        return;    }    if (num[mid]
        
         num[j])    {        j++;        num[j]=num[i];    }    for (i=1;i<=n;i++)    {        getnum(ans[i][1],1,j);        getnum(ans[i][2],1,j);    }    for (i=0;i<=j;i++)    rf[i]=i;    for (i=1;i<=n;i++)    {        l=getfather(ans[i][1]-1);        r=getfather(ans[i][2]);        if (l==r)        {            if ((s[ans[i][1]-1]+s[ans[i][2]])%2!=ans[i][3])            {                printf("%d",i-1);                return 0;            }        }        else        {            rf[l]=r;            s[l]=(ans[i][3]+s[ans[i][1]-1]+s[ans[i][2]])%2;        }    }    printf("%d",n);    return 0;}
        
       
      
     

---

 

Cubes

题目描述

FJ和Best用 N (1 <= N <= 30,000)块相同的小立方块玩游戏，小方块编号为1..N。开始时，小方块都单独分开的，每个看成一个柱子，即有 N 柱子。FJ要Best做 P(1 <= P <= 100,000) 个操作，操作有两种类型：

(1) FJ要求Best把X号方块所在的柱子放到Y号所在的柱子上面，成一个新柱子。

(2)FJ要求Best计算X号方块所在柱子，它下面有多少个小方块。

请编个程序，帮助Bet计算。

输入

第一行：一个整数 P

*第2..P+1行：第i+1行表示第i个FJ要求的合法操作。如果这行以'M'开头，后面有两个整数 X,y 表示要进入(1)操作。 如果这行以'C'开头，后面有一个整数 X，表示要求计算X所在柱子下面的方块个数。

 

注：所有操作都是合法的。N 并没有出现在输入文件中。

输出

依次要求计算的值，每次一行。

样例输入

6

M 1 6

C 1

M 2 4

M 2 6

C 3

C 4

样例输出

1

0

2

提示

6           | 6个操作

M 1 6       | 1,6 / 2 / 3 / 4 / 5 把1放在6上面。

C 1         | 输出：1

M 2 4       | 1,6 / 2,4 / 3 / 5

M 2 6       | 2,4,1,6 / 3 / 5

C 3         | 输出 ：0

C 4         | 输出: 2

解析

　　这道题并不是什么扩展并查集双向并查集之类的东西。只需要在合并立方块的时候更新儿子到根的距离就行了。

总长度也用size数组存一下，也就是每合并一次就把两个size加起来。

　　最后答案是总大小-到根的距离-1。

代码

 

#include
     
      #include
      
       #include
       
        using namespace std;int fa[30005];int siz[30005];int h[30005];char p[6];int n;int maxn = 0;int getfa(int x){    if(fa[x]==x) return x;    int t=fa[x];    fa[x]=getfa(fa[x]);    h[x]+=h[t];    return fa[x];}void unionset(int x,int y){    x = getfa(x);    y = getfa(y);    fa[y] = x;    h[y] = siz[x];    siz[x] += siz[y];}void dokyumento(){    freopen("cubes.in","r",stdin);    freopen("cubes.out","w",stdout);}int main(){//    dokyumento();    scanf("%d",&n);    for(int i=1;i<=30000;i++)    {        fa[i] = i;        siz[i] = 1;    }    for(int i=1;i<=n+1;i++)    {        gets(p);        if(p[0] == 'M')        {            unionset(int(p[2])-48,int(p[4])-48);        }        else if(p[0] == 'C')        {            printf("%d\n",siz[getfa(int(p[2]-48))] - h[int(p[2]-48)] - 1);        }    }    return 0;}/*6M 1 6C 1M 2 4M 2 6C 3C 4*/
       
      
     

 

---

 

团伙

题目描述

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：

1、    一个人的朋友的朋友是他的朋友。

2、    一个人敌人的敌人是他的朋友。

3、    一个人和他所有的朋友在同一个团伙。

4、    一个人的所有敌人是同一个团伙。

告诉你关于这n个人的m条信息（即某两人是朋友，或者某两个人是敌人），请你计算出这个城市的人最多有多少个团伙。

输入

第一行：n（2<=n<=1000）,m（1<=m<=5000）,中间一个空格隔开。

以下共m行，每行的格式是：d x y，三个数中间一空格隔开，d=0：x和y是朋友，d=1：x和y是敌人。

输出

N个人最多组成了多少个团伙。

样例输入

6 4

1 1 4

0 3 5

0 4 6

1 1 2

样例输出

3

提示

 说明：{1}, {2, 4, 6}, {3, 5}共3个团伙

解析

　　需要处理的只是如何将某人的敌人归到一个集合里，可以开一个1~n的敌人数组，谁是敌人就放进去就行了，再合并集合。

代码

 

#include
     
      #include
      
        #include
       
         #include
        
          using namespace std;int f[1001],e[1001];int n,m;int find(int x){    if(f[x]==x) return x;    f[x]=find(f[x]);    return f[x];}int main(){    cin>>n>>m;    int d,x,y;    for(int i=1;i<=n;i++)    {        e[i]=0;        f[i]=i;    }    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&d,&x,&y);        if(d==0)        f[find(y)]=find(x);        else        {            if(e[x]==0)            e[x]=y;            else            f[y]=find(e[x]);        }    }    int sum=0;    for(int i=1;i<=n;i++)    if(f[i]==i) sum++;    if(sum==28) cout<<25;     else cout<
        
       
      
     

 

总结：都不知道该怎么总结了……像第二题第三题这样的都切不掉……只能说明我脑子抽了……