CF949E Binary Cards 题解
2024-10-07 01:46:21
首先发现：一个数最多会出现1次；
然后深入推出：一个数不会既用它又用它的相反数；
这样就可以依次考虑每一位了:
如果所有的数都不含有这一位,那么就直接把所有的数除以2
如果含有，那么就减去这一位的数，再除以2；
2
当含有的时候搜索就可以了；
注意需通过去重来优化dfs，否则会TLE掉；
#include <bits/stdc++.h>
#define N 100010
using namespace std;
int a[N],b[21][N],ans[N],st[N],top=0;
int anss=INT_MAX;
void dfs(int dep,int n){
if(n<=1&&!b[dep][1]){
if(top<anss){
anss=top;
for(int i=1;i<=top;i++){
ans[i]=st[i];
}
}
return;
}
if(dep>20||top>=anss){
return;
}
bool flag=1;
for(int i=1;i<=n;i++){
if(b[dep][i]&1){
flag=0;
break;
}
}
if(flag){
for(register int i=1;i<=n;i++){
b[dep+1][i]=b[dep][i]/2;
}
n=unique(b[dep+1]+1,b[dep+1]+n+1)-b[dep+1]-1;
dfs(dep+1,n);
return;
}
else{
for(register int i=1;i<=n;i++){
if(b[dep][i]&1){
b[dep+1][i]=(b[dep][i]-1)/2;
}
else{
b[dep+1][i]=b[dep][i]/2;
}
}
st[++top]=1*(1<<dep);
register int tmp=unique(b[dep+1]+1,b[dep+1]+n+1)-b[dep+1]-1;
dfs(dep+1,tmp);
top--;
for(register int i=1;i<=n;i++){
if(b[dep][i]&1){
b[dep+1][i]=(b[dep][i]+1)/2;
}
else{
b[dep+1][i]=b[dep][i]/2;
}
}
st[++top]=-1*(1<<dep);
tmp=unique(b[dep+1]+1,b[dep+1]+n+1)-b[dep+1]-1;
dfs(dep+1,tmp);
top--;
}
}
int main()
{
register int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;i++){
b[0][i]=a[i];
}
dfs(0,n);
printf("%d\n",anss);
for(int i=1;i<=anss;i++){
printf("%d ",ans[i]);
}
}
最新文章
- shell 条件判断语句整理
- 使用 AForge.NET 做视频采集
- USACO Section 3.3: Riding the Fences
- 记录一次MySQL复制问题的处理
- zDialog无法获取未定义或 null 引用的属性“_dialogArray”
- Android（java）学习笔记173：BroadcastReceiver之 静态注册 和 动态注册
- kvm 存储
- Ubuntu 麒麟版下安装：Apache+php5+mysql+phpmyadmin.
- 免费的编程中文书籍索引 from github
- SQL之left join、right join、inner join
- 【转】缓存淘汰算法系列之2——LFU类
- JDK自带VM分析工具jps，jstat，jmap，jconsole
- android动画介绍之 自己定义Animation动画实现qq抖一抖效果
- 【20190304】JavaScript-知识点总结：Set，异或
- c#获取url请求的返回值
- C#编程（七十五）----------C#使用指针
- 如何自动播放光盘、解决win7电脑不能播放光盘
- UDP方式实现广域网的P2P通信
- Spring-framework应用程序启动loadtime源码分析笔记（二）——@Transactional
- 【tensorflow】1.安装Tensorflow开发环境，安装Python 的IDE--PyCharm