[题解]小X的液体混合

2022-12-09 21:12:53

版权说明：来自石门ss学校 Guohao OJ ,禁止转载

题目描述

虽然小X不喜欢化学原理，但他特别喜欢把一大堆液体倒在一起。

现在小X有n种液体，其中m对会发生反应。现在他想把这n种液体按某种顺序倒入一个容器内，让他获得最刺激的体验，也就是使危险系数尽量大。

我们可以这样计算危险系数，一开始容器内没有任何液体，危险系数为1。每次液体倒入容器时，若容器内已有一种或多种液体会与这种液体发生反应，则危险系数会乘2，否则危险系数不变。

最大危险系数小X不会算，希望你帮帮他。

输入输出格式

输入格式：

第一行包含两个整数n，m。

接下来m行，每行包含两个整数a，b，表示液体a和液体b会发生反应。

输出格式：

一行，包含一个整数，表示最大危险系数。

输入输出样例

输入样例：

输出样例：

说明

数据规模：

对于30%的数据，n≤10；

对于100%的数据，1≤n≤1000，a≠b，同种反应不会出现多次。

题目分析：

通过题目可以发现，不用管放置的顺序，我们就可以轻而易举得想到并查集，将液体合并为后，一个集的危险指数就为 2 的（集合内个数-1），最后将所有集合值加起来就是答案。

代码

 #include<iostream>

 #include<fstream>

 using namespace std;

 typedef string str;

 const int Max_N=1e3+;

 int n,m;

 int Fa[Max_N],tot[Max_N];

 string mul(string s1,string s2)

 {

 //    一连串的高精度乘法，个人码风问题不建议借鉴

 //     最好自己手写一个

     #define len1 (s1.size())

     #define len2 (s2.size())

     int maxx=max(len1,len2);

     register int i,j,k,l;

     int Ans[maxx<<|];

     for(i=;i<=(maxx<<);i++)Ans[i]=;

     for(i=;i<len1;i++)s1[i]-='';

     for(i=;i<len2;i++)s2[i]-='';

     for(i=len1-,k=;i>=;i--,k++){

         for(j=len2-,l=(maxx<<)-k;j>=;j--,l--)

             Ans[l]+=(int)s1[i]*s2[j];

     }

     for(i=(maxx<<);i>=;i--)

         if(Ans[i]>){

             int xy=Ans[i]/;

             Ans[i-]+=xy;

             Ans[i]%=;

         }

     int top=;

     while(Ans[top]==&&top^(maxx<<))top++;

     string res;

     for(i=top;i<=maxx<<;i++)res+=Ans[i]+'';

     return res;

 }

 int Find(int p)

 {

 //    查询祖先

     if(Fa[p]==p)

         return p;

     return Fa[p]=Find(Fa[p]);

 }

 void megre(int u,int v)

 {

     Fa[Find(u)]=Fa[Find(v)];

     return ;

 }

 str Pow(str b,int p)

 {

 //    字符串版快速幂:-D

     if(!p)

         return "";

     str res="";

     while(p){

         if(p&)

             res=mul(res,b);

         b=mul(b,b);

         p>>=;

     }

     return res;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     int u,v;

     register int i,j;

     for(i=;i<=n;i++)

         Fa[i]=i;

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

         scanf("%d%d",&u,&v);

         megre(u,v);//²¢²é¼¯ºÏ²¢²Ù×÷

     }

     for(i=;i<=n;i++)

         tot[Find(i)]++;//统计集合内个数

     str res="";

     for(i=;i<=n;i++)

         if(tot[i]>)

             res=mul(res,Pow("",tot[i]-));

 //    答案为集合内的 pow(2,(集合内个数-1)) 的和

     cout<<res;

     return ;

 }

代码

写在最后的话：

题解仅供思路，要想成为 dalao ，请学会并尽量会做到教他人甚至自己写题解。

博主（目前）是一名初二蒟蒻，如有问题还请大家指出，一起交流学习！

Happy every day!　　　　　　　　——2019.4.11

码农公寓