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;elsecout << "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 << " ";elsecout << 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);}elsetmp=tmp*data[j].WA;}if(sum==f){ans+=tmp;}}cout << fixed << setprecision(4) << ans << endl;}}return 0;
}