题目传送门

本题是基本的写法就是并查集的基本的应用

c++代码

#include<algorithm>
#include<cstring>

using namespace std;

const int N =100000;

int n,m;

int p[N];

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


int main()
{
    scanf("%d%d",&n,&m);
    //首先先对每一个数列集合进行初始化
    for(int i=0;i<n;i++) p[i]=i;
    while (m -- ){
        char op;
        int a,b;
        scanf("%s%d%d",&op,&a,&b);
        if(op=='M')
          p[find(a)]=find(b);//将两个集合合并
        else{
            if(find(a)==find(b)) printf("Yes\n");
            else printf("No\n");
        }

    }
    return 0;
}

算法基础课复盘

并查集的具有如下的两个作用:

1.将两个集合合并
2.询问两个元素是否在一个集合中

使用并查集的原因

假设用一个元素来存储某个元素属于哪一个集合：

belong[x]=a

判断两边元素是否在同一个集合中:
通常写作

if(belong[x]==belong[y])

通常其时间复杂度为o(1)

但上述的问题是如果数据很大，则暴力的情况会出现耗时

运用并查集可以完美的解决问题，使得在近乎o(1)来完成操作

实现的基本思想

利用树的形式来维护所有的集合
那么每个集合的编号即为根节点的编号
在每个点上存储的是该点的父节点。
当想求某一个点属于哪一个集合的时候，从底部往上遍历，直到找到树根为止(当前元素的树根编号也就是集合的编号)

几个问题:

1.如何判断是不是树根

if(p[x]=x)//也就是说，当前节点的编号x与树中存储的编号p[x]是相同的，此时就到达了树根

2.如何求x的集合编号(判断两个元素是否在同一个集合中)

while(p[x]!=x)x=p[x];/一路往上走，如果当前的编号x与集合编号p[x]不相同，那么就进行更新编号（也就是处于的新的节点）直到`p[x]=x`

3.如何合并两个集合

加边:把右集合当作左集合的儿子或者把左集合当做右集合的儿子(插在另一个集合的某一个位置)。
假设p[x]是集合x的编号，p[y]是集合y的编号
合并:p[x]=y;直接更新集合x的编号，也就是把x插到y集合里。

如此以上的时间复杂度为o(n)

并查集优化:

并查集具有特殊的能力进行优化
一般情况是从树底一路走上去，而并查集在第一个找到树根之后，剩下的全部的则可以直接的指向树根，如下图所示:

这样使得时间复杂度变成了o(1)

另一个优化是按秩合并，但是由于效果并不明显，因此并不使用

#include<algorithm>
#include<cstring>

using namespace std;

const int N =100000;

int n,m;

int p[N];

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


int main()
{
    scanf("%d%d",&n,&m);
    //首先先对每一个数列集合进行初始化
    for(int i=0;i<n;i++) p[i]=i;
    while (m -- ){
        char op;
        int a,b;
        scanf("%s%d%d",&op,&a,&b);
        if(op=='M')
          p[find(a)]=find(b);//将两个集合合并
        else{
            if(find(a)==find(b)) printf("Yes\n");
            else printf("No\n");
        }

    }
    return 0;
}

题目传送门

考察点：并查集

分析

根据题目描述，如果两个人是亲戚，则两个人亲戚的亲戚也互为亲戚
因此需要涉及到两个集合合并

那么也就转化成了:两个人是否是亲戚也就是询问两个人是否在同一个集合里面

关于并查集的算法与模板可以查看下面链接:
Acwing836合并集合

c++d代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N =200010;

int n,m;
int p[N];//定义父节点

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


int main()
{
    scanf("%d%d",&n,&m);
    //预处理并查集中每个点的父节点
    for(int i=1;i<=n;i++)p[i]=i;

    //依次读入亲戚关系
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);

        //合并两个点
        p[find(a)]=find(b); 
     } 
     int q;
     scanf("%d",&q);
     while(q--)
     {
        int c,d;
        scanf("%d%d",&c,&d);
        if(find(c)==find(d))printf("Yes\n");
        else printf("No\n");
     }
     return 0;
}

如果用cin和cout会超时

#include<iostream>
#include<algorithm>
#include<cstring>


using namespace std;

const int N =1000010;

int n,m,q,c,d;

//定义并查集数组
int  p[N];

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


int main()
{
    scanf("%d%d",&n,&m);
    while (n -- )p[n]=n;//对数组进行初始化
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        //构建并查集
        p[find(a)]=find(b);//如果a有祖先，那么将a的祖先赋予b，a的祖先同时也成为b的祖先
    }
    scanf("%d",&q);
    while(q--)
    {

        scanf("%d%d",&c,&d);
        if(find(c)==find(d))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

题目传送门

本质方法:递推

从思路上看，本题思路容易想出，但是如果写出来，则比较费解

原型题: Acwing1208.翻硬币

具体思路

翻硬币的题目是从左往右枚举，固定最左边的变化后不动。而此题的数据变成了二维，引申下来则可以固定每一行。
对于第一行来说，自己枚举操作一遍开和闭。
然后第一行的结果，导致第二行的操作是开还是闭(因为第二行会直接影响第三行)
同理第三行、第四行、第五行以此类推，都会受到其上一行的影响。然而最后一行在为了上一行操作之后，后面就不会再有行来操作影响它。
因此最后一行的最终形态是整个结果的决定性因素，如果最后一行都是1，那么说明变化成功，可以判断操作次数并且输出答案。否则该方案则直接为错误，跳出进行下一组方案循环。

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 6;

const int INF=100000;

char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,0,-1};

//变化函数
void step(int x,int y)
{
    //枚举上下左右四个方向，并且从0变到1
    for(int i=0;i<5;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=5||b<0||b>=5)continue;
        g[a][b]^=1;
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
      int res=INF;//因为超过6就结束，则总计数可以先定义一个最大值
      for(int i=0;i<5;i++)cin>>g[i];
    //首先先按第一行
        //对于一排灯来说，一共32种情况的亮和灭
        for(int op=0;op<1<<5;op++)
        {
            //因为需要枚举其他情况，因此需要将串备份
            memcpy(backup,g,sizeof g);
            int ans=0;//记录当前的次数
            //每行一共有5盏灯
            for(int j=0;j<5;j++)
            {

                //对于每盏灯的每个选项，如果当前情况不是1，则改变灯
                if(op>>j&1)
                {
                    ans++;

                    step(0,j);
                }
            }  
            //接下来操作下面4行(第五行不会被动影响)
            for(int i=0;i<4;i++)
            {
                for(int k=0;k<5;k++)
                {
                    if(g[i][k]=='0')
                      {
                          ans++;
                          step(i+1,k);
                      }
                }
            }

            //最后判断最后一行是否为黑色
            bool is_successful=true;
            for(int i=0;i<5;i++)
            {
                if(g[4][i]=='0')
                {
                  is_successful=false;
                   break;
                }

            }
            if(is_successful)res=min(ans,res);//每次来更新新的答案
            memcpy(g,backup,sizeof backup);//重新恢复g数组

        }
        //if)(res>6)cout<<-1<<endl;//这样的话，大于6没有覆盖
         if(res>6)res=-1;
         cout<<res<<endl;
    }
    return 0;

}

//递推版本
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int INF=100000000;

char g[10][10];
int dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1};


//按灯的辅助函数
void turn(int x,int y)
{
    //枚举以xy为中心的5个数
    for(int i=0;i<5;i++){
        int a=x+dx[i],b=y+dy[i];
        //如果当前在范围内，则可以枚举
        if(a>=0&&a<=5&&b>=0&&b<=5)
        {
            //将数进行改变，从0变到1，从1变到0
            g[a][b]='0'+('1'-g[a][b]);

        }

    }
}

int work()
{
    int ans=INF;
    //首先先枚举下第一行的状态
    for(int k=0;k<1<<5;k++)
    {
        int res=0;
        //因为要枚举多次，每次要保证状态不变，因此需要开一个备用数组，来存储下状态
         char backup[10][10];
         memcpy(backup,g,sizeof g);

        //第一行一共有32种状态
        for(int j=0;j<5;j++)
          if(k>>j&1)
          {
              //每按下一次，当前方案数+1
              res++;

              turn(0,j);
             //对于每次枚举，需要记录下当前方案的最小值
          }

        //从前往后去递推前n-1行
        for(int i=0;i<4;i++)\
          for(int j=0;j<5;j++)
            if(g[i][j]=='0')
            {
                //如果当前位置上0，则在下一行对应的位置按一下
                res++;
                turn(i+1,j);
            }

    //前面4行都已经调整好了，接下来是需要去判断一下最后一行是否都为1
    bool is_successful=true;
    //只要有一位不为0，则为false
    for(int j=0;j< 5;j++)
    {
        if(g[4][j]=='0')
        {
            is_successful=false;
            break;
        }
    }
    //如果当前方案合法，更新答案
     if(is_successful) ans=min(ans,res);

     //恢复g数组，以方便美军下一个状态
     memcpy(g,backup,sizeof g);


    }
    if(ans>6) ans=-1;//如果6步不能变亮，则输出-1
    return ans;
}


int main()

{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=0;i<5;i++)cin>>g[i];//输入所有灯的初始状态

        cout<<work()<<endl;

    }
    return 0;
}

题目传送门

相似题目: Acwing 3777.砖块

个人思路

首先是根据题意，需要翻转相邻的两个硬币。根据相似题目的思路的延伸想到

Acwing 3777砖块的题解

对于需要翻转的字符串，从左到右进行枚举与翻转。如果当前枚举到的要翻转的串的形状与对应的参考串的位置不相符，则就翻转相邻两个，否则则不翻转。

对于整个串里面的每一个形状，对于第一个来说只会影响一次，后续的字符串翻转则不影响其形状。而对于后面的形状，同一个位置要么不变化(其左边翻转了 ，其右边也翻转了)，要么就变化一次。

因此不会说出现如果从左到右翻转，左边那个需要翻转，而此不需要翻转，但是相邻翻转使其变化回不去的情况，当前位于相对的左边的时候，就可以翻转回去

对于最后一个元素，由于前面的已经排好，则其是否有解是整个串是否能够有解的决定性因素，根据题目已知:

保证一定有解

则就不需要再去考虑这种情况，一定是保证匹配的。

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N =110;

char a[N],b[N];//定义char来存储

//定义函数进行翻转
void turn(int i)
{
    if(a[i]=='*')a[i]='o';
    else a[i]='*';
}


int main()
{
    cin>>a>>b;
    //定义结果
    int res=0;
    int n =strlen(b);//取出长度
    //最后一个元素，由于保证一定有解，因此不用枚举
    for(int i=0;i<n-1;i++)
    {
        //如果当前位置上对不起来，则从左到右进行翻转
        if(a[i]!=b[i])
        {
             turn(i),turn(i+1);
             res++;
        }

    }
    cout<<res<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N =110;

char a[N],b[N];//定义char来存储

//定义函数进行翻转
void turn(int i)
{
    if(a[i]=='*')a[i]='o';
    else a[i]='*';
}


int main()
{
    cin>>a>>b;
    //定义结果
    int res=0;
    int n =strlen(b);//取出长度
    //最后一个元素，由于保证一定有解，因此不用枚举
    for(int i=0;i<n-1;i++)
    {
        //如果当前位置上对不起来，则从左到右进行翻转
        if(a[i]!=b[i])
        {
             turn(i),turn(i+1);
             res++;
        }

    }
    cout<<res<<endl;
    return 0;
}

题目传送门

暴力！暴力！ 还是tm的暴力！

当时比赛时的思路

u1s1，现在回过头来看，我都看不懂我是怎么想到这么不合逻辑的思路,以及奇怪的公式，为了不给字节造成混乱，就不再深究，只将代码放在这作为警示！

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;

using namespace std;
const int N =1000010;
int a,b,n;
int main()
{
    LL day=1;
    int sum=0;
    scanf("%d%d%d", &a, &b,&n);
    while(sum<=n)
    {
        sum+=a;
        day++;
        if(day%7==0)
        {
            sum+=2*b-a;
        }

    }
    printf("%d",day);
    return 0;

}

题目分析

首先给定的数据范围为10的18次方，如果最坏情况下假设最低每天1道题，枚举也需要10的18次方，会导致TLE
根据题目，首先可以列出一周的做题数量为5a+2b
而已经知道了要做够的总的题目数量：n
故将n与一周题目数量进行相除，得到能够被除尽的做够一周的天数，剩下的n%s(如果有，就是不足7天的，可以进行枚举)

通过这样的方法，将时间复杂度降到7次以内

c++代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;



int main()
{
    LL a,b,n;
    cin>>a>>b>>n;

    LL s=5*a+2*b;//一周做的题目的数量

    //整除能够除开的天数
    LL res=n/s*7;

    //剩余的不能够整除的题目数量，一定不足7，因此可以枚举 
    //剩余的题目数量为
    n%=s;

    //剩下的题目由于可以直接枚举，因此为了方便，可以开一个数组，用来存储每一天的做题目数量
    LL d[]={a,a,a,a,a,b,b};

    for(int i=0;n>0;i++)
    {
        n-=d[i];//减去当天的做题数量
        res++;


    }
    cout<<res<<endl;
    return 0;

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long LL;



int main()
{
    LL a,b,n;
    cin>>a>>b>>n;

    LL s=5*a+2*b;//一周做的题目的数量

    //整除能够除开的天数
    LL res=n/s*7;

    //剩余的不能够整除的题目数量，一定不足7，因此可以枚举 
    //剩余的题目数量为
    n%=s;

    //剩下的题目由于可以直接枚举，因此为了方便，可以开一个数组，用来存储每一天的做题目数量
    LL d[]={a,a,a,a,a,b,b};

    for(int i=0;n>0;i++)
    {
        n-=d[i];//减去当天的做题数量
        res++;


    }
    cout<<res<<endl;
    return 0;

}