题目描述 输入 输出 样例输入 样例输出 数据范围限制 提示 想都不想多的，我们直接开始暴力枚举，先想log2（109）<30，暴力枚举完全部也只用230,更别说只找到一个正解就可以，其实真实时间复杂度为O（log（n））左右。 我用的是倒推法，剪枝条件就用以上铺垫的奇偶性分析，当参数为偶是退出，直到找到正解为止。
西西需要把输入的电压1伏通过一系列电压放大器放大成原来的N倍，然后输出。
西西现在手上有两种放大器：
第一种能够把X伏的电压放大成2X-1伏
第二种能够把X伏的电压放大成2X+1伏
放大器是串联（即按顺序放在一条线路上）的。
现在西西手上有用不完的放大器，他希望能组出一个电路，使用数量最少的放大器，使得电压被放大了刚好N倍。
一行一个正整数N(1<=N<=2*10^9)
如果无法组成电路则输出一行No solution
否则输出两行，第一行一个整数表示最少的放大器个数K，第二行K个用空格隔开的1或2，表示放大器序列。1表示第一种，2表示第二种，其中左边为输入端。如果有多解输出任意一组。
5
2
2 1
20%的数据中 N<=1000
50%的数据中，N<=1000000
100%的数据如题。
先经过放大器2，1 * 2+1=3，然后经过1，3 * 2-1=5。满足要求思路：
铺垫：
我们可以从奇偶性分析：
1.奇数×2+1=奇数
2.偶数×2+1=奇数
3.奇数×2-1=奇数
4.偶数×2-1=奇数正解：
优先枚举第二种情况才可以保证使用最少的放大器（重点）
实现void dfs(int o){ if(o%2==0) return ;//剪枝条件 if(bj==1) return ;//找到一个后就不找了 if(o==1){//找到正解 bj=1; printf("%dn",a[0]); for(int i=a[0];i>=1;i--){ printf("%d ",a[i]); } return ; } a[0]++; a[a[0]]=2; dfs((o-1)/2);//优先枚举第二种情况才可以保证使用最少的放大器（重点） a[a[0]]=1; dfs((o+1)/2);//枚举第一种放大器 a[a[0]]=0; a[0]--; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
