大一寒假训练四（二进制枚举）【更新完成】
本次训练共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;
}
#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;
}
#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;
}
#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;
}
投递百度等公司10个岗位 >