2020.1.3大一寒假训练四（二进制枚举）

103熊出没事件QAQ！！陈老师表示心里苦呀！！

一大波兴安熊正在接近！

 

如果感觉位运算&&二进制枚举不太懂，可以访问本博主的文章位运算&&二进制枚举

Problem:A    teacher Li（NEFU　643）

解题思路：字符串的异或运算，字符有自己的ascii码，也可以用于异或。

#include<bits/stdc++.h>
using namespace std;
int n, tot=0;
string start, follow;
int main()
{
	while(cin>>n)
	{
		cin>>start;
		for(int i=1; i<n*2-1; i++)
		{
			cin>>follow;
			for(int j=0; j<max(start.size(), follow.size()); j++)
				start[j] ^= follow[j];
		}
		cout<<"Scenario #"<<++tot<<endl<<start<<endl<<endl;
	}
	return 0;
}

Problem:B    Find different(NEFU 1172)

解题思路：数字的异或运算。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    int n;
    while(cin >> n)
    {
        long long ans=0;
        int x;
        for(int i=1;i<=n;i++)
        {
            cin >> x;
            ans=ans^x;
        }
        cout << ans << endl;
    }
    return 0;
}
 

Problem:C    和为K--二进制枚举(NEFU 1205)

解题思路：模板二进制枚举。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    long long k;                    //WA是因为忘开long long ,虽然我也不知道为啥
    while(cin >> n)
    {
        cin >> k;
        int a[25];
        for(int i=0; i<n; i++)
            cin >> a[i];
        int flag=0;
        for(int i=0; i<(1<<n); i++)
        {
            long long tmp=0;
            for(int j=0; j<n; j++)
            {
                if(i&(1<<j))
                    tmp+=a[j];
            }
            if(tmp==k)
            {
                flag=1;
                break;
            }
        }
        if(flag)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}
 

Problem:D    陈老师加油-二进制枚举（NEFU 1505）

解题思路：模板二进制枚举。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    while(cin >> t)
    {
        long long ans=0;
        for(int i=0;i<(1<<15);i++)
        {
            int flag1=0,flag2=0,tmp=t;
            for(int j=0;j<15;j++)
            {
                if(i&(1<<j))
                {
                    flag1++;
                    tmp=tmp*2;
                }
                else
                {
                    flag2++;
                    tmp--;
                }
                if(tmp<=0)        //直接跳出，没油就走不动了
                    break;
            }
            if(flag1==5&&flag2==10&&tmp==0)
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}
 

Problem:E    纸牌游戏-二进制-搜索（NEFU 1518）

解题思路：模板二进制枚举，题意中11代表J，12代表Q，13代表K，他不输入JQK，而是输入数字。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,p;
    while(cin >> n >> p)
    {
        int i,j;
        long long ans=0;
        int a[50];
        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==p)
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}
 

Problem:F    权利指数(NEFU 1641)

解题思路：模板二进制枚举，明白题意就行，可以设一个计数器，循环遍历一遍，得出答案。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    int t,n;
    while(cin >> t)
    {
        while(t--)
        {
            cin >> n;
            double sum=0;
            int data[25],num[25]={0},flag[25]={0};
            for(int i=0;i<n;i++)
            {
                cin >> data[i];
                sum+=data[i];
            }
            for(int i=0;i<(1<<n);i++)
            {
                memset(flag,0,sizeof(flag));
                double tmp=0;
                for(int j=0;j<n;j++)
                {
                    if(i&(1<<j))
                    {
                        tmp+=data[j];
                        flag[j]=1;      //记录符合的单位，为后面进行判断
                    }
                }
                if(tmp>sum/2)
                {
                    for(int j=0;j<n;j++)
                    {
                        if(flag[j]==1&&(tmp-data[j]<=sum/2))
                            num[j]++;
                    }
                }
            }
            for(int i=0;i<n;i++)
            {
                cout << num[i];
                if(i!=n-1)
                    cout << " ";
                else
                    cout << endl;
            }
        }
    }
    return 0;
}

Problem:G    趣味解题(NEFU 1285)

解题思路：模板二进制枚举，加上数学概率问题。

#include <bits/stdc++.h>

using namespace std;

struct problem{
    double a,b,c;
    double WA=0;
}data[15];
int main()
{
    ios::sync_with_stdio(0);
    int t,n,f;
    while(cin >> t)
    {
        while(t--)
        {
            memset(data,0,sizeof(data));
            cin >> n;               //n道题
            for(int i=0;i<n;i++)
                cin >> data[i].a;
            for(int i=0;i<n;i++)
                cin >> data[i].b;
            for(int i=0;i<n;i++)
                cin >> data[i].c;
            cin >> f;           //解出的题
            for(int i=0;i<n;i++)
                data[i].WA=(1-data[i].a)*(1-data[i].b)*(1-data[i].c);//WA的概率
            double ans=0,tmp=1;
            for(int i=0;i<(1<<n);i++)
            {
                int sum=0;//记录解出题的个数
                tmp=1;    //计算每一种情况的概率
                for(int j=0;j<n;j++)
                {
                    if(i&(1<<j))
                    {
                        sum++;
                        tmp=tmp*(1-data[j].WA);
                    }
                    else
                        tmp=tmp*data[j].WA;
                }
                if(sum==f)
                {
                    ans+=tmp;
                }
            }
            cout << fixed << setprecision(4) << ans << endl;
        }
    }
    return 0;
}