ACM.二进制枚举

Dear 丶 2023-06-28 11:15 47阅读 0赞

一.二进制运算  
算数位运算：  
1、与（&）:  
对于指定的两个数A=60(0011 1100)  
B=13(0000 1101)  
执行一下操作 A&B=12(0000 1100)  
就是对二进制每一位进行了一次与操作，同为1，结果为1，否则为0  
2、或（|）:  
对于指定的两个数A=60(0011 1100)  
B=13(0000 1101)  
执行一下操作 A|B=61(0011 1101)  
就是对二进制每一位进行了一次或操作，同为0，结果为0，否则为1  
3、非 按位取反（~）:  
对于指定的一个数A=60(0011 1100)  
执行以下操作 ~A=195(1100 0011)  
就是对二进制每一位进行了一次取反操作，若二进制数位0，则变成1，否则变成0.  
4、异或运算（^）  
即为每一位上不进位的加法，0^0=0, 1 ^ 0=1,1 ^ 1=0，  
对于异或一个非常重要的性质，对于一个值异或同一个值两次，则结果还是原值。  
二进制位运算：  
1、左移<<  
例如：A=5（0101）  
如果向左移动一位即A<<1结果为1010，十进制的10。二进制中的左移就是乘二操作,在c/c++中左移运算速度比乘二速度要快。  
2、右移>>  
例如：A=5（0101）  
如果向右移动一位即A>>1结果为0010，十进制的2。二进制中的右移就是除二操作（舍去小数）。

对于二进制的每一位来说，1代表取这个元素，0代表不取（也可反着来），所以我们要枚举所有的可能性，即为枚举元素个数n，长度为n的二进制数字从00000……到111111……，所有的可能性，本质上也是一种暴力枚举。

题目  
异或运算的应用  
一.NEFU-1172  
Find different  
Problem:B  
Time Limit:20000ms  
Memory Limit:5000K  
Description  
Give an odd number n, (1<=n<=10000001)  
Given you an array which have n numbers : a\[1\], a\[2\] a\[3\] … a\[n\].They are positive num.  
There are n/2 numbers which appear twice and only one number appears once.  
Now you should tell me the number which appears only once.  
Input  
There are several test cases end with EOF.  
The first line there is a integer n.  
Then the 2nd line there are n integer a\[1\],a\[2\]…a\[n\].  
Output  
For each case, output the number which appears only once.  
Sample Input  
7  
3 2 7 2 1 7 3  
1  
7  
11  
1 1 2 2 3 3 4 4 5 5 9  
Sample Output  
1  
7  
9

#include <bits/stdc++.h>
    using namespace std;
    int sum,i;
    int main()
    {
        
        int n;
        while(cin>>n)
        {
        
            int sum=0;
            int x;
            cin>>sum;     //先读入第一个数
            for(i=1;i<n;i++)
            {
        
                cin>>x;
                sum=sum^x;    //再读入接下来的数字，相同的数字异或运算后可以消除，最后只剩下出现过奇数次的那个数字留下。
            }
            cout<<sum<<endl;
        }
        return 0;
    }

二.NEFU-643  
teacher Li  
Problem:A  
Time Limit:1000ms  
Memory Limit:65536K  
Description  
This time,suddenly,teacher Li wants to find out who have missed interesting DP lesson to have fun.The students who are found out will get strictly punishment.Because,teacher Li wants all the students master the DP algorithm.  
However,Li doesn’t want to waste the class time to call over the names of students.So he let the students to write down their names in one paper.To his satisfaction,this time, only one student has not come.  
He can get the name who has not come to class,but,it is troublesome,and,teacher always have many things to think about,so,teacher Li wants you, who is in the ACM team, to pick out the name.  
Input  
There are several test cases.The first line of each case have one positive integer N.N is the number of the students,and N will not greater than 500,000.  
Then,following N lines,each line contains one name of students who have attended class.The N-1 lines are presented after N lines.These N-1 lines indicates the names of students who have come to class this time,one name in one line.  
The length of student’s name is not greater than 30.  
Process to the end of file.  
Output  
For each test case, first print a line saying “Scenario \#k”, where k is the number of the test case.Then output the name of the student who have not come to class.One case per line.Print a blank line after each test case, even after the last one.  
Sample Input  
3  
A  
B  
C  
B  
C  
Sample Output  
Scenario \#1  
A

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int n,i,j;
        int t=0;
        while(cin>>n)
        {
        
            char c1[40],c2[40];
            scanf("%s",c1);
            for(i=0;i<n*2-2;i++)  //算上第一个输入的一共输入2n-1次
            {
        
                scanf("%s",c2);
                int l1=strlen(c1),l2=strlen(c2);
                for(j=0;j<max(l1,l2);j++)     //一定要以较长的为结束标志
                {
        
                    c1[j]=c1[j]^c2[j];         //字符每一位依次进行异或运算，根据ascii码值，也可达到相同的异或后消除的效果。
                }
            }
            printf("Scenario #%d\n",++t);
            cout<<c1<<endl<<endl;
        }
        return 0;
    }

二进制枚举：  
一.NEFU——1205  
和为K–二进制枚举  
Problem:C  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
给出长度为n的数组,求能否从中选出若干个,使他们的和为K.如果可以,输出:Yes,否则输出No  
Input  
第一行：输入N,K,为数组的长度和需要判断的和(2<=N<=20,1<=K<=10^9)  
第二行：N个值，表示数组中元素的值(1<=a\[i\]<=10^6)  
Output  
输出Yes或No  
Sample Input  
5 13  
2 4 6 8 10  
Sample Output  
No  
基础没话说

#include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int n,i,j,k;
        while(cin>>n>>k)
        {
        
            int a[n+1];
            int flag=0;
            for(i=0;i<n;i++)
            {
        
                cin>>a[i];
            }
            for(i=0;i<(1<<n);i++)
            {
        
                int sum=0;
                for(j=0;j<n;j++)
                {
        
                    if(i&(1<<j))
                    {
        
                        sum+=a[j];
                    }
    
                }
                if(sum==k) {
        flag=1;
                cout<<"Yes"<<endl;
                break;
            }
        }
        if(flag==0) {
        cout<<"No"<<endl;}
        }
        return 0;
    }

二.NEFU——1285  
趣味解题  
Problem:G  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
ACM程序设计大赛是大学级别最高的脑力竞赛，素来被冠以"程序设计的奥林匹克"的尊称。大赛至今已有近40年的历史，是世界范围内历史最悠久、规模最大的程序设计竞赛。比赛形式是：从各大洲区域预赛出线的参赛队伍，于指定的时间、地点参加世界级的决赛，由1个教练、3个成员组成的小组应用一台计算机解决7到13个生活中的实际问题。  
现在假设你正在参加ACM程序设计大赛，这场比赛有 n 个题目，对于第 i 个题目你有 a\_i 的概率AC掉它，如果你不会呢，那么这时候队友的作用就体现出来啦，队友甲有 b\_i 的概率AC掉它， 队友乙有 c\_i 的概率AC掉它，那么现在教练想知道你们队伍做出 x 个题目的概率。  
Input  
输入一个正整数T(T<=100)，表示有T组数据，对于每组数据首先输入一个 n (7<=n<=13)，表示有 n 个题目，接下来输入三行，  
第一行输入 n 个数a\_i,第二行输入 n 个数b\_i,第三行输入 n 个数c\_i, 其中 a\_i, b\_i, c\_i 的意义如题，最后输入一个 x 表示教练想要知道你们队伍做出的题目数(x>=0)。  
Output  
输出一行表示结果，保留4位小数  
Sample Input  
2  
7  
0.1 0.2 0.3 0.4 0.5 0.6 0.7  
0.2 0.3 0.4 0.5 0.6 0.7 0.8  
0.3 0.4 0.5 0.6 0.7 0.8 0.9  
1  
7  
0.1 0.2 0.3 0.4 0.5 0.6 0.7  
0.2 0.3 0.4 0.5 0.6 0.7 0.8  
0.3 0.4 0.5 0.6 0.7 0.8 0.9  
5  
Sample Output  
0.0000  
0.2811

主要是注意概率的算法，高中数学知识了。

#include <bits/stdc++.h>
    using namespace std;
    int T,i,j,n,x,y,sum;
    double a[20],b[20],c[20],ac[20],gg[20],ssum,gl;
    int main()
    {
        
        cin>>T;
        for(y=0;y<T;y++)
            {
        
               cin>>n;
               for(i=0;i<n;i++)
               {
        
                   cin>>a[i];
               }
               for(i=0;i<n;i++)
               {
        
                   cin>>b[i];
               }
               for(i=0;i<n;i++)
               {
        
                   cin>>c[i];
               }
               cin>>x;
               ssum=0;
               for(i=0;i<(1<<n);i++)
               {
        
                   sum=0;
                   gl=1;
                   for(j=0;j<n;j++)
                   {
        
                       gg[j]=(1-a[j])*(1-b[j])*(1-c[j]);     //做不出来的概率
                       ac[j]=1-gg[j];
                       if(i&(1<<j)) {
        
                       gl*=ac[j];
                       sum++;
                       }
                       else
                       {
        
                           gl*=gg[j];
                       }
                   }
                   if(sum==x){
        ssum+=gl;}
               }
               printf("%.4lf\n",ssum);
            }
        return 0;
    }

三.NEFU-1505  
陈老师加油-二进制枚举  
Problem:D  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
陈老师经常开车在哈尔滨的大街上行走，假设刚开始油箱里有T升汽油，每看见加油站陈老师就要把汽油的总量翻倍（就是乘2）；每看见十字路口气油就要减少1升；最后的时候陈老师的车开到一个十字路口，然后车就没油了------就熄火了，陈老师好痛苦啊~~~！  
然后他就开始回忆，一路上一共遇到5个加油站，10个十字路口，问造成这种惨烈的境遇有多少种可能？  
Input  
输入一个T ，（1<=T<=100）;  
Output  
输出可能的方案数。  
Sample Input  
1  
Sample Output  
10

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
        int T,i,j;
        while(cin>>T)
        {
        
            int sum=0;
            for(i=0;i<(1<<15);i++)
            {
        
                int k1=0,k2=0,tmp=T;
                for(j=0;j<15;j++)
                {
        
                    if(i&(1<<j))
                    {
        
                      tmp*=2;
                      k1++;
                    }
                    else
                    {
        
                        tmp--;
                        k2++;
                        if(tmp<=0)
                            break;
                    }
                }
            if(k1==5&&k2==10&&tmp==0) sum++;
            }
                cout<<sum<<endl;
        }
    return 0;
    }

四.NEFU-1641  
权利指数  
Problem:F  
Time Limit:1000ms  
Memory Limit:65535K  
Description  
在选举问题中，总共有n个小团体，每个小团体拥有一定数量的选票数。如果其中m个小团体的票数和超过总票数的一半，则此组合为“获胜联盟”。n个团体可形成若干个获胜联盟。一个小团体要成为一个“关键加入者”的条件是：在其所在的获胜联盟中，如果缺少了这个小团体的加入，则此联盟不能成为获胜联盟。一个小团体的权利指数是指：一个小团体在所有获胜联盟中成为“关键加入者”的次数。请你计算每个小团体的权利指数。  
Input  
输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为一个正整数n（0<n<=20）。第二行有n个正整数，分别表示1到n号小团体的票数。  
Output  
对每组测试数据，在同一个行按顺序输出1到n号小团体的权利指数。  
Sample Input  
2  
1  
10  
7  
5 7 4 8 6 7 5  
Sample Output  
1  
16 22 16 24 20 22 16  
关键在于理解权力指数的计算方法

#include <bits/stdc++.h>
    using namespace std;
    int T,i,j,n,sum[21],flag[21],s,a[21],tm,q,i1;
    int main()
    {
        
        while(cin>>T)
        {
        
            for(i1=0;i1<T;i1++)
            {
        
                memset(sum,0,sizeof(sum));
                cin>>n;
                s=0;
                for(i=0;i<n;i++)
                {
        
                    cin>>a[i];
                    s+=a[i];
                    flag[i]=1;
                }
                for(i=0;i<(1<<n);i++)
                {
        
                    memset(flag,0,sizeof(flag));
                    int tm=0;
                    for(j=0;j<n;j++)
                    {
        
                        if(i&(1<<j))
                        {
        
                         tm+=a[j];
                         flag[j]++;
                        }
                    }
                    if(tm<=(s/2))
                    {
        
                      for(q=0;q<n;q++)
                      {
        
                          if(tm+a[q]>(s/2)&&flag[q]==0)
                          {
        
                              sum[q]++;
                          }
                      }
                    }
                }
                for(int g=0;g<n;g++)
                {
        
                    if(g==n-1){
        cout<<sum[g]<<endl;}
                    else {
        cout<<sum[g]<<" ";}
                }
            }
        }
        return 0;
    }