家里网太差，没能上分，可惜，今天补题，发现我可以写四题，嗯就是到D1那题
感觉和半年前打cf有很大进步吧，以前只可打2题（上次打就是半年前）
摸鱼一天，勉强补完D2
最后一题数论，好了，数论fw的我放弃了补
摸鱼了一天。。。本来说看看逆向的结果就这样摸鱼摸了一天，明天一定hhh

[A.Mocha and Mat](http://codeforces.com/contest/1559/problem/A) 
题意：
给一个正整数序列a，长为n，每次可以选择一个区间[l,r]，然后让a[l+i]=a[l+i]&a[r-i]
可以无数次操作求最后得到的序列a里最大值最小是多少
思路：
每次&操作，只会使得a[i]减小或者不变，不可能变大(&操作性质决定)
基于这样子的想法，我让每个数&上其他所有数即可，这样子，就使得所有数一样，且是最小
emm，每个数&上其他所有数的操作一定是可以做到的，怎么做到，枚举就行
代码如下:
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        int ans;
        scanf("%d",&n);
        scanf("%d",&ans);
        for(int i=1;i<n;i++)
        {
            int a;
            scanf("%d",&a);
            ans&=a;
        }
        printf("%d\n",ans);
    }

    return 0;
}

[B. Mocha and Red and Blue](http://codeforces.com/contest/1559/problem/B) 
题意：
一行有n个点，给每个点上色，只要红和蓝两种颜色，求使得任意相邻两点颜色相同最少
?代表自由上色，R代表只能红色，B代表只能蓝色
思路：
明显得到dp嘛，dp[i][j]表示从头到i点以j颜色结尾的两点颜色相同的对数
dp[i][j]=min(dp[i-1][(j+1)%2],dp[i-1][j]+1])//由于j和j颜色相同，所以对数+1
再开一个数组记录当前状态是由那个状态转移来的，方便确定答案
代码如下
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        int dp[105][2],find[105][2];
        char str[105],ans[105];
        memset(dp,0x3f,sizeof(dp));//最大化

        scanf("%d",&n);
        scanf("%s",str);

        if(str[0]=='R')
        dp[0][0]=1;
        else if(str[0]=='B')
        dp[0][1]=1;
        else
        {
            dp[0][1]=1;
            dp[0][0]=1; 
        }
        for(int i=1;i<n;i++)
        {
            //cout<<i<<endl;
            if(str[i]=='R')
            {//如果只能填这个颜色，那就只更新这个点的这个颜色的j
                if(dp[i-1][0]+1<dp[i-1][1])
                {
                    dp[i][0]=dp[i-1][0]+1;
                    find[i][0]=0; 
                }
                else 
                {
                    dp[i][0]=dp[i-1][1];
                    find[i][0]=1; 
                }
                continue;
            }
            else if(str[i]=='B')
            {
                if(dp[i-1][1]+1<dp[i-1][0])
                {
                    dp[i][1]=dp[i-1][1]+1;
                    find[i][1]=1; 
                }
                else 
                {
                    dp[i][1]=dp[i-1][0];
                    find[i][1]=0; 
                }
                continue;
            }
            for(int j=0;j<2;j++)
            {
                if(dp[i-1][j]+1<dp[i-1][(j+1)%2])
                {
                    dp[i][j]=dp[i-1][j]+1;
                    find[i][j]=j;
                }
                else
                {
                    dp[i][j]=dp[i-1][(j+1)%2];
                    find[i][j]=(j+1)%2;
                }
            }
        }

        int j;
        if(dp[n-1][0]>dp[n-1][1])
        ans[n-1]='B',j=1;
        else
        ans[n-1]='R',j=0;
        //cout<<ans[n-1]<<endl;
        j=find[n-1][j];

        for(int i=n-2;i>=0;i--)
        {
            //cout<<j<<endl;
            if(j==1)
            ans[i]='B';
            else
            ans[i]='R';

            j=find[i][j];
        }
        ans[n]='\0';

        printf("%s\n",ans);
    }

    return 0;
}

[C. Mocha and Hiking](http://codeforces.com/contest/1559/problem/C) 
题意
给一个n+1个点，2n-1条边的有向图，前n-1条边连接点i到i+1(1<=i<=n-1)
剩下一个长为n的序列a,a[i]==1代表这条边是点n+1指向点i，a[i]==0代表点i指向n+1
任一点出发，任意点结束求重复走完全部点的路径，不存在这样子的路径输出-1
思路
不难发现，一定存在解，首先我们可以从1走到n只剩下n+1这个点没走
那么如果a[1]=1,那我们可以先从n+1走到1，然后1到2、2到3······n-1到n
如果a[1]!=1但是a[n]==0,那我们从1出发走到n再从n走到n+1
当a[1]==0&&a[n]==1时，我们发现，整个a序列，一定存在两个点使得a[i]!=a[i-1]
这样子的第一个i，一定是a[i-1]==0,a[i+1]=1，毕竟a[1]=0,第一个不同不就是a[i]==1吗
这样子的话，说明我们可以从1走到i-1，i-1到n+1,n+1到i，i到n+1
代码如下
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        int a[10005],lo=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(i>1&&a[i]!=a[i-1]&&!lo)
            lo=i;
        }

        if(a[1]==1)
        {
            printf("%d",n+1);
            for(int i=1;i<=n;i++)
            {
                printf(" %d",i);
            }
            printf("\n");
        }
        else if(a[n]==0)
        {
            for(int i=1;i<=n;i++)
            printf("%d ",i);
            printf("%d\n",n+1);
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(i!=1)
                printf(" ");
                if(i==lo)
                {
                    printf("%d %d",n+1,i);
                    continue;
                }
                printf("%d",i);
            }
            printf("\n");
        }

    }

    return 0;
}

[D1. Mocha and Diana (Easy Version)](http://codeforces.com/contest/1559/problem/D1) 
题意
给我们两个点数相同的森林，每次选择两个点连边，要求这两个点在两个森林里都是属于不同的树
求最多可以连多少边
思路
首先数据n<=1000，暴力不慌，我们利用并查集，将同一个树的点连接
双重for循环，判断i和j在俩个森林里是不是两个树，如果说是，就连接
只要由一个森林变为一棵树的时候就不能合并了
代码如下
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

int f[1005],d[1005];
int find(int x,int fa[])
{
    if(fa[x]!=x)
    fa[x]=find(fa[x],fa);
    return fa[x];
}

int main()
{
    int n,m1,m2;
    scanf("%d %d %d",&n,&m1,&m2);
    for(int i=1;i<=n;i++)
    f[i]=i,d[i]=i;

    while(m1--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        a=find(a,f);b=find(b,f);
        if(f[a]!=b)
        f[a]=b;
    }

    while(m2--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        a=find(a,d);b=find(b,d);
        if(d[a]!=b)
        d[a]=b;
    }

    vector<pair<int,int> > ans;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
    if(find(i,f)!=find(j,f)&&find(i,d)!=find(j,d))
    {
        ans.push_back({i,j});
        f[find(i,f)]=find(j,f);
        d[find(i,d)]=find(j,d);
    }

    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    cout<<ans[i].first<<" "<<ans[i].second<<endl;
    return 0;
}

[D2.Mocha and Diana (Hard Version)](http://codeforces.com/contest/1559/problem/D2) 
题意
和上题一样，但是n数据范围变为n<=100000，意味着不能够暴力
思路
上一题，我们耗时主要是在查找两个森林里都不同树的两个点，那么我们记录下来不就好了吗
利用二维，行x代表一个森林里的树x，列y代表另一个一个森林里的树y。mp[x][y]这两个树通过这个点相连
行x数组记录与他相连的列，列y数组记录与他相连的行
确保行数更少，这样子我们把行合并，一直到行只有一行代表着有一个森林只有一棵树
每次合并行，我们找到两行里面不同的列，然后通过mp找那两个点，这样子就找到了两个点在两个森林里都是属于两棵树
需要开set存与行相连的列和与列相连的行(set去重)
需要开一个set存所有的行并且按行所连的列数从大到小排序
特别注意是从大到小排序，只有这样才能保证取出的头两行他们的列数不完全一致
如果说是从小到达排序参考数据(如果你从小到达排序，但是你是从set的尾部开始合并当我没说)
6 3 3
1 2
3 4
5 6
1 2
2 3
3 4
为什么从大到小就能保证两行所连的列不完全一致呢
参考上面的数据，当我们发现，由两个行所含的点都在同一个列时
为了保证列数>=行数，那么剩下的点只能属于更多的树，这样子剩下的行就会分配到更多的列
照这个思路想就知道为什么了
代码如下
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int fa1[N],fa2[N];
set<pair<int,int> > rows;
set<int> row[N],col[N];
set<int>::iterator it;
map<int,int> mp[N];
pair<int,int> ans[N];

int find(int fa[],int x)
{
    if(fa[x]!=x)
    fa[x]=find(fa,fa[x]);
    return fa[x];
}

void merge_row(int x,int y)
{//合并行操作 
    for(it=row[y].begin();it!=row[y].end();it++)
    {//将与y连通块相连的列移到x中 
        mp[x][*it]=mp[y][*it];//map记录的是x行y列通过节点mp[x][y]相连，
        //不用担心原本x和这个列相连的问题，毕竟只是记录两个相连的纽带而已 
        row[x].insert(*it);//x继承了与y相连的列，由于是set，不需要担心重复 
        col[*it].erase(y);//y行消失，所以与y行相交的列里需要消除y 
        col[*it].insert(x);//x行继承y行相交的列，所以x插入他的列中
        //以上操作均在set中进行，自动去重 
    }
}

void merge_col(int x,int y)
{//合并列操作 
    for (it=col[y].begin();it!=col[y].end();it++)
    {
        mp[*it][x]=mp[*it][y];
        col[x].insert(*it);
        row[*it].erase(y);
        row[*it].insert(x);
    }
}

int main()
{
    int n,m1,m2,h=0,i;
    scanf("%d %d %d",&n,&m1,&m2);

    for(int i=1;i<=n;i++)
    {
        fa1[i]=i;fa2[i]=i;
    }

    for(int i=1;i<=m1;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        x=find(fa1,x);y=find(fa1,y);
        fa1[x]=y;
    }
    for(int i=1;i<=m2;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        x=find(fa2,x);y=find(fa2,y);
        fa2[x]=y;
    }

    if(m1<m2)//确保行比列少，这样子能够减少合并操作
    swap(fa1,fa2);

    for(int i=1;i<=n;i++)
    {
        int a=find(fa1,i),b=find(fa2,i);
        //节点i在一个森林里所属的树是a，另一个是b 
        mp[a][b]=i;//两个森林里的a,b两棵树通过i相连
        //行代表一个森林，列代表另一个森林 
        row[a].insert(b);
        col[b].insert(a);
    }

    for(int i=1;i<=n;i++)
    if(find(fa1,i)==i)//rows使得行按拥有的节点数排序 
    rows.insert({-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());//一次取出两行合并

        it=row[x].begin();
        int a=*it,b=*row[y].begin();

        if(a==b)//如果子树x和y第一个相连的列相同，就换一个列 
        a=*++it;//找到两个子树里不同的列
        //不同列代表在另一个森林两个点不在同一个树里 
        ans[++h]={mp[x][a],mp[y][b]};//通过这两个点相连
        if(col[a].size()<col[b].size())
        swap(a,b);//将节点少的并入到节点多的后面，减少合并操作
        //每次相连都是把两个森林里的两棵树合并 
        merge_row(x,y);
        merge_col(a,b);
        rows.insert({-row[x].size(),x});//合并好的行插入回去 
    }

    printf("%d\n",h);
    for(int i=1;i<=h;i++)
    printf("%d %d\n",ans[i].first,ans[i].second);

    return 0;
}
不得不说，这个题很有意思