题意：
已知每个数都能用x=1 + 2 + 4 + ... + 2k - 1 + r （k ≥ 0, 0 < r ≤ 2k）来表示，
给出一串数字问这串数字能有几个x表示。输出可能的长度。
思路：
https://www.cnblogs.com/TnT2333333/p/6828340.html?utm_source=itdadao&utm_medium=referral
这个题昨天没有做出来，今天看的大佬的博客理解的
大体思路是这个样子的
分别对2的倍数，与2倍数间隔间的数计数，结果个数最多为1的个数，
对每个个数，我们判断其是否可行。
我们贪心当前2的倍数之后一个的2的倍数，
使剩下来的2的倍数的数量和非2倍数数量和尽可能少，因为剩下的个数为最小的划分的数的个数。
代码：
#include <iostream> #include <cstring> #include <vector> #include <cstdio> using namespace std; typedef long long ll; const int M = 1e5 + 10; ll a[M]; vector<int>equ , betw , ans;//equ[i]表示a[i]中有几个2^i,betw[i]表示a[i]中有几个大于等于2^(i-1)小于2^(i)的数。ans用来存结果。 bool Is(int len) { vector<int>e , b; e = equ , b = betw; if(e[0] < len) return false;//如果1的数量比长度少显然不可能组成。 b[1] += e[0] - len;//把多余的a[i]用到b[i+1]中。 for(int i = 1 ; i < 41 ; i++) { if(b[i] > len) return false;//显然b[i]如果比长度还多那么也是不存在的。 if(e[i] > len) b[i + 1] += (e[i] - len);//把多余的a[i]用到b[i+1]中。 else if(e[i] < len) { b[i] -= (len - e[i]); b[i] = max(0 , b[i]); len = e[i];//由于b[i]放上去后这串数就不能再放a了所以要更新一下len } b[i + 1] += b[i];//把多余的b加上，后面可以用。 } return true; } int main() { int n; scanf("%d" , &n); ans.clear() , equ.clear() , betw.clear(); for(int i = 1 ; i <= n ; i++) { scanf("%lld" , &a[i]); } int po = 0; for(int i = 0 ; i < 42 ; i++) { equ.push_back(0); betw.push_back(0); } for(int i = 1 ; i <= n ; i++) { while(a[i] > ((ll)1 << po)) { po++; } if(a[i] == ((ll)1 << po)) { equ[po]++; } else { betw[po]++; } } for(int i = 1 ; i <= n ; i++) { if(Is(i)) { ans.push_back(i); } } if(ans.size()) { for(int i = 0 ; i < ans.size() ; i++) { printf("%d " , ans[i]); } } else { printf("-1"); } printf("\n"); return 0; }
