2020.1.3 大一寒假训练四(二进制枚举)
今日之榜,乃史上最强之阵!!!
请见文末彩蛋~
异或 | 二进制枚举 |
---|---|
A B | C D E F G |
Problem A:NEFU643 teacher Li
思路就是把所有字符串的每个字符依次异或,字符对应得ascii码也是一个数字,所以字符也可以去异或。
而且在二进制中,0与任何数异或都等于那个数本身。
题目翻译
Description
这一次,李老师突然想找出谁咕了有趣的动规课来取乐。被揪出来的学生将受到严厉的惩罚,因为,李老师希望所有的学生都掌握DP算法。
然额,李老师不想浪费上课时间去点名,所以他让学生们把自己的名字写在一张纸上,令他满意的是,这次只有一个学生没有来。
他能知道没来上课的学生的名字,但是这很麻烦,而且,老师总是有很多事情要考虑,所以,李老师想让在ACM队伍的你来找出这个憨憨孩子的名字。
Input
有多个测试用例,每个样例的第一行有一个正整数N,N是学生人数,N<=500000。
然后紧接着N行,每行包含一个应到学生的名字,N行之后读入N-1行,这N-1行表示实到学生的名字,每行包含一个名字。
学生姓名的长度不大于30。
处理到文件尾。
Output
对于每个测试用例,首先打印一行“Scenario#k”,其中k是测试用例的编号。
然后输出未到学生的姓名。每行一个。
在每个测试用例(即便是最后一个测试用例)之后,打印一个空行。
#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:NEFU1172 Find different
题目翻译
Description
给出一个奇数n(1<=n<=10000001)。
给你一个含有n个数的数组:a[1],a[2],a[3] … a[n],他们都是正整数。
有n/2个数字出现两次,只有1个数字出现一次。
现在你需要指出只出现一次的那个数字。
Input
有多个测试用例,以EOF结束。
第一行是一个整数n。
第二行有n个整数a[1],a[2]…a[n]。
Output
对于每个样例,输出那个孤独的数字。
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
while(cin>>n)
{
int x1, xn;
cin>>x1;
for(int i=1; i<n; i++)
{
cin>>xn;
x1 ^= xn;
}
cout<<x1<<endl;
}
return 0;
}
Problem C:NEFU1205 和为K–二进制枚举
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k, a[25];
while(cin>>n>>k)
{
for(int i=0; i<n; i++)
cin>>a[i];
bool flag = 0;
for(int i=0; i<(1<<n); i++)
{
int sum=0, tmp=k;
for(int j=0; j<n; j++)
{
if(i&(1<<j))
tmp -= a[j];
}
if(!tmp)
{
flag=1;
break;
}
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
Problem D:NEFU1505 陈老师加油-二进制枚举
陈老师要玩得开心呐
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
while(cin>>T)
{
int cnt=0, flag=T;
for(int i=0; i<(1<<15); i++)
{
flag = T;
int cnt1=0, cnt2=0;
for(int j=0; j<15; j++)
{
if(i&(1<<j))
{
flag *= 2;
cnt1++;
}
else
{
flag -= 1;
cnt2++;
if(flag<=0) break;
}
}
if(cnt1==5 && cnt2==10 && flag==0) cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
Problem E:NEFU1518 纸牌游戏-二进制-搜索
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k, a[25];
while(cin>>n>>k)
{
int cnt=0;
for(int i=0; i<n; i++)
cin>>a[i];
bool flag = 0;
for(int i=0; i<(1<<n); i++)
{
int sum=0, tmp=k;
for(int j=0; j<n; j++)
{
if(i&(1<<j))
tmp -= a[j];
}
if(!tmp)
{
flag=1;
cnt++;
//eak;
}
}
cout<<cnt<<endl;
}
return 0;
}
Problem F:NEFU1641 权利指数
#include<bits/stdc++.h>
using namespace std;
int t, n, vote[25], cnt[25];
bool flag[25];
int main()
{
while(cin>>t)
{
while(t)
{
memset(cnt, 0, sizeof(cnt));
cin>>n;
double sum=0;
for(int i=0; i<n; i++)
{
cin>>vote[i];
sum += vote[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 += vote[j];
flag[j] = 1;
}
}
if(tmp>sum/2)
for(int j=0; j<n; j++)
if(flag[j] && (tmp-vote[j])<=sum/2)
cnt[j]++;
}
for(int i=0; i<n-1; i++)
cout<<cnt[i]<<" ";
cout<<cnt[n-1]<<endl;
t--;
}
}
}
Problem G:NEFU1285 趣味解题
感谢高中,感谢人教版数学
概率题实在是妙啊
#include<bits/stdc++.h>
using namespace std;
struct acm{
double ai, bi, ci, tot;
}ti[15];
int T, n, x;
int main()
{
while(cin>>T)
{
while(T--)
{
double lv=1, ans=0;
cin>>n;
for(int i=0; i<n; i++)
cin>>ti[i].ai;
for(int i=0; i<n; i++)
cin>>ti[i].bi;
for(int i=0; i<n; i++)
{
cin>>ti[i].ci;
ti[i].tot = 1-(1-ti[i].ai)*(1-ti[i].bi)*(1-ti[i].ci);
}
cin>>x;
for(int i=1; i<(1<<n); i++)
{
int cnt = 0;
lv = 1;
for(int j=0; j<n; j++)
{
if(i&(1<<j))
{
cnt++;
lv *= ti[j].tot;
}
else lv *= (1-ti[j].tot);
}
if(cnt == x) ans += lv;
}
printf("%.4lf\n", ans);
}
}
return 0;
}
彩蛋:榜单
感谢大佬指导,让本弱无伤AK
赠送福利:NEFU1665 四糸乃买花
#include<bits/stdc++.h>
using namespace std;
int n, w, cnt, ans, a[30];
int main()
{
cin>>n;
for(int i=0; i<n; i++)
cin>>a[i];
cin>>w;
for(int i=1;i<(1<<n)-1;i++)// i=0:None i=2^n-1:All
{
int tmp = w;
cnt = 0;
for(int j=0; j<n; j++)
{
if(i&(1<<j))
{
tmp -= a[j];
cnt++;
}
}
if(tmp>=0 && cnt%4==0 && tmp%4==0) ans++;
}
printf("%d\n", ans);
return 0;
}
上一篇: 使用gulp-file-include对前端公共部分进行封装
下一篇: MySql学习之主从复制