先向各位大佬介绍一个水题
任何一个正整数都可以用2的幂次方表示。例如
137=2^7+2^3+2^0 同时约定方次用括号来表示，即a^b 可表示为a(b)。
由此可知，137可表示为：
2(7)+2(3)+2(0)进一步：7= 2^2+2+2^0 (2^1用2表示)
3=2+2^0 所以最后137可表示为：
2(2(2)+2+2(0))+2(2+2(0))+2(0)又如：
1315=2^10 +2^8 +2^5 +2+1所以1315最后可表示为：
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)输入输出格式
输入格式：
一个正整数n(n≤20000)。
输出格式：
符合约定的n的0，2表示(在表示中不能有空格)
输入输出样例
1315
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
作为蒟蒻的我，对这道题表示被括号吓到了，但。。。
大致思路是这样的
1315 1: 1024+256+32+2+1 //需要位运算的支持（请忽略） stack 0 1 5 8 10 2: 10=2+8 stack 0 1 5 8 1 3 stack 0 1 5 8 1 0 1 if(stack[i]<=1) s.pop(); return i; else printf("2(%d)",find(x));
思路大概是对的，但对于我来说，程序实践又成为了一个问题。
不打代码都不知道自己原来这么水。orz
于是我去翻了翻题解
#include <cstdio> #include <iostream> #include <algorithm> #include <bitset> using namespace std; int n; void solve(int x) { if(x==1||x==2||x==0)return ;//1,2,0不作分解 bitset<32> b=x;//STL大法好啊 int sum=b.count(),s=0;//记录何时到最后一位，以便输出"+" for(int i=b.size()-1;~i;--i)//从高阶位遍历 if(b[i])//如果是1，则处理 { s++;//记录已经走过的位数 printf("2"); if(i!=1)printf("(");//只有次幂不为一时输出括号 solve(i);//递归 //递归输出： if(i==0||i==2)printf("%d",i);//只输出2,0 if(i!=1)printf(")"); if(s<sum)printf("+"); } } int main() { cin>>n; if(n==1)return printf("2(0)"),0;//特殊点判断 if(n==2)return printf("2"),0; solve(n);//进入递归 return 0; } //作者: 蠢萌_小三爷 (luogu ID) orz
我觉得bitset这个东西简直太神奇了。
所以我就去查了查：
C++语言的一个类库，用来方便地管理一系列的bit位而不用程序员自己来写代码。
bitset除了可以访问指定下标的bit位以外，还可以把它们作为一个整数来进行某些统计。
（人话：定义一串二进制数）
具体操作：
定义：
#include<bitset> using namespace std; bitset<32> u(s); //32位的u,是s的一个副本 bitset<32> u(s,pos,n) //32位的u,是从n开始的s的一个副本 bitset<32> u; //32位的u,每一位都为0
bitset<32> u(0x7ffff)
和vector的元素一样，bitset中的位是没有命名的，程序员只能按位置来访问它们。位集合的位置编号从0开始，因此，bitvec的位序是从0到31。以0位开始的位串是低阶位（low-order bit），以31位结束的位串是高阶位(high-order bit)。
当用unsigned long值作为bitset对象的初始值时，该值将转化为二进制的位模式。
在32位unsigned long的机器上，十六进制值0xffff表示为二进制位就是十六个1和十六个0（每个0xf可表示为1111）。可以用0xffff初始化bitset对象
当用string对象初始化bitset对象时，string对象直接表示为位模式。
具体函数操作
to_ulong操作返回一个unsigned long值，该值与bitset对象的位模式存储值相同。仅当bitset类型的长度小于或等于unsigned long的长度时，才可以使用to_ulong操作。
果然还是好神奇！！！
ps：本文的部分资料来自
Liam Q的专栏，各位可以去膜拜原大佬
连接在此：http://blog.csdn.net/qll125596718/article/details/6901935