大一寒假训练四（二进制枚举）【更新完成】

本次训练共7题，本文附AC代码和题目链接。

本次训练中稍有难度的题：nefu 1285 趣味解题 和 nefu 1641 权利指数

nefu 643 teacher Li
思路就是把所有字符串的每个字符依次异或，字符对应得ascii码也是一个数字，所以字符也可以去异或。
而且在二进制中，0与任何数异或都等于那个数本身。

#include <bits/stdc++.h>
using namespace std;
int n,i,j,cas;
string x,ans;
int main()
{
    ios::sync_with_stdio(false);
    cas=0;
    while(cin>>n>>ans)
    {
        for(i=1;i<=2*n-2;i++)
        {
            cin>>x;
            for(j=0;j<max(x.length(),ans.length());j++)//这里必须取字符串较长的那个
                ans[j]=ans[j]^x[j];
        }
        printf("Scenario #%d\n",++cas);
        printf("%s\n\n",ans.c_str());
    }
    return 0;
}

nefu 1172 Find different

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,x,ans=0;
    ios::sync_with_stdio(false);
    while(cin>>n)
    {
        while(n--)
        {
            cin>>x;
            ans=ans^x;
        }
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1205 和为K
这题要多组输入，单组输入会Wrong answer

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

nefu 1285 趣味解题
刚开始做可能觉得有点难，其实只要把概率的计算写清楚就不难了

#include <bits/stdc++.h>
using namespace std;
int t,n,x,i,j,cnt;
double a[15],b[15],c[15],ac[15],wa[15],ans,p;
//ac[i]表示团队做对第i题的概率，wa[i]表示团队做错第i题的概率
int main()
{
    cin>>t;
    while(t--)
    {
        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;
        ans=0;
        for(i=0;i<(1<<n);i++)
        {
            p=1;cnt=0;
            for(j=0;j<n;j++)
            {
                wa[j]=(1-a[j])*(1-b[j])*(1-c[j]);//3个人都不会做这题，即团队做不出这题的概率
                ac[j]=1-wa[j];
                if(i&(1<<j))
                {p=p*ac[j];cnt++;}//cnt记录团队ac数量
                else
                    p=p*wa[j];
            }
            if(cnt==x)
                ans=ans+p;
        }
        printf("%.4lf\n",ans);
    }
    return 0;
}

nefu 1505 陈老师加油

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t,tmp,ans,k1,k2,i,j;
    cin>>t;
    ans=0;
    for(i=0;i<(1<<15);i++)
    {
        tmp=t;
        k1=k2=0;
        for(j=0;j<15;j++)
        {
            if(i&(1<<j))
            {tmp=tmp*2;k1++;}
            else
            {
                tmp--;k2++;
                if(tmp==0)break;
            }
        }
        if(k1==5&&k2==10&&tmp==0)ans++;
    }
    printf("%d\n",ans);
    return 0;
}

nefu 1518 纸牌游戏

#include <bits/stdc++.h>
using namespace std;
int i,j,n,k,s,ans,a[21];
int main()
{
    while(cin>>n>>k)
    {
        for(i=0;i<n;i++)
        cin>>a[i];
        ans=0;
        for(i=0;i<(1<<n);i++)
        {
            s=0;
            for(j=0;j<n;j++)
            {
                if(i&(1<<j))
                s=s+a[j];
            }
            if(s==k)
            ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

nefu 1641 权利指数
先选出任意个小团体，选出来后做好标记(flag=1)，并保证他们的票数之和小于等于总票数的一半，之后在没被选出来的小团体(flag=0)中再选出任意一个小团体，设他的票数为a[j]，若加上a[j]后票数之和大于总票数的一半，那么这个a[j]就是“关键加入者”，则他的权利指数+1。

#include <bits/stdc++.h>
using namespace std;
int n,t,i,j,s,tmp,a[21],ans[21],flag[21];
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        s=0;
        for(i=0;i<n;i++)
        {cin>>a[i];s=s+a[i];}
        memset(ans,0,sizeof(ans));
        for(i=0;i<(1<<n);i++)
        {
            tmp=0;
            memset(flag,0,sizeof(flag));
            for(j=0;j<n;j++)
            {
                if(i&(1<<j))
                {tmp=tmp+a[j];flag[j]=1;}
            }
            if(tmp<=s/2)
            {
                for(j=0;j<n;j++)
                {
                    if(tmp+a[j]>s/2&&flag[j]==0)
                    ans[j]++;
                }
            }
        }
        for(i=0;i<=n-2;i++)
        printf("%d ",ans[i]);
        printf("%d\n",ans[n-1]);
    }
    return 0;
}