uva11205 The broken pedometer 子集生成
2024-09-06 09:06:28
PS:此题我在网上找了很久的题解,发现前面好多题解的都是没有指导意义的。后来终于找到了一篇好的题解。
好的题解的链接:http://blog.csdn.net/u013382399/article/details/23516051
我在他的解题的基础上,有了自己的理解。
题意:
有n(100以内)个位数为p(15以内)的二进制数,最少需要几个二进制位就可以把他们区分开。
题目分析:
数据较小,用的是暴力的方法,就是枚举每一个二进制位取或不取。就是相当于是枚举矩阵的列。
刘汝佳的小白书120页提到的子集生成就是这样的枚举。这道题我用了位向量法。
对于此题,某一列(一个二进制位或者说是某一盏灯)取或不取可以这样理解。不取就认为所有的n个数中这一位数是相同的,可以是全部赋值为1也可以是0。
然后就是判断这n个数中有没有重复的数。转化为字符串好比较,当然也可以是转化为进制数比较(原来的数认为是二进制数)。
我根据这个意思,自己写了一份代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std; int n,p,cur;
int ans;
int a[][];
char s[][];
bool vis[];
map<string,int > st;
int DFS(int x)
{
if(x==p)
{
int t=;
for(int i=;i<n;i++)
for(int j=;j<p;j++)
if(vis[j]){t++;s[i][j]=a[i][j]+;}
else s[i][j]=;
for(int i=;i<n;i++) s[i][p]=;
st.clear();
for(int i=;i<n;i++)
{
//puts(s[i]);
if(!st[s[i]]) st[s[i]]=;
else return ;
}
t/=n;
ans=min(t,ans);
return ;
}
vis[x]=;
DFS(x+);
vis[x]=;
DFS(x+);
return ;
}
int main()
{
//freopen("test.txt","r",stdin);
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&p,&n);
for(int i=;i<n;i++)
for(int j=;j<p;j++)
scanf("%d",&a[i][j]);
ans=p;
memset(vis,,sizeof(vis));
DFS();
printf("%d\n",ans);
}
return ;
}
下面是一份看上去更简洁更暴力的代码,是我从网上找的,因为很久之前找的,所以都不知道出处了。
它的思想是这样的:因为是p位二进制,所以范围在0 ~ 2p 。并且p是不大于15的。所以可以直接枚举。对于i属于[0,2p ],如果n个数中每个数 & i的结果没有重复,就代表i是一个可能的解,只要把i这个数二进制位为1的个数求出来,就是一个可能的答案。最后取最小值。这个的原理,我不知道,但是可以编程来验证。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std; int a[];
int p,n;
set<int > s;
int main()
{
//freopen("test.txt","r",stdin);
int ca,i,j,k,ans,t,flag,r;
scanf("%d",&ca);
while(ca--)
{
memset(a,,sizeof(a));
scanf("%d%d",&p,&n);
for(i=;i<n;i++)
for(j=;j<p;j++)
{
scanf("%d",&t);
a[i]=a[i]*+t;
}
ans=;
for(i=;i<(<<p);i++)
{
flag=;
s.clear();
for(j=;j<n;j++)
{
t=i&a[j];
if(s.find(t)!=s.end()) {flag=;break;}
s.insert(t);
}
if(!flag)
{
r=;
for(k=;k<p;k++)
if(i&(<<k)) r++;
if(r<ans) ans=r;
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- mysql数据类型
- angular源码阅读,依赖注入的原理:injector,provider,module之间的关系。
- imadjust从用法到原理—Matlab灰度变换函数之一
- Memento(备忘录)-对象行为型模式
- tomcat 假死现象(转)
- Firemonkey ListView 获取项目右方「>」(Accessory) 事件
- Java并发之CountDownLatch 多功能同步工具类
- 升级WebService图形服务,将K10.2和K10.3写到一个类库,所有服务放在一个类库
- LSTM/RNN的应用Case
- 浅析WCF与WebService、WPF与Silverlight 区别
- String.Split()功能
- numpy数组取每一列的数据
- 用VS制作的windows服务安装包 安装完后如何让服务自动启动
- git 处理
- struts2注释返回json数据
- vue实现添加与删除图书
- Java Web 项目简单配置 Spring MVC进行访问
- HttpClient与HttpUrlConnection下载速度比较
- 自然语言交流系统 phxnet团队 创新实训 项目博客 (七)
- 【monkey】mokey常用事件<;二>;