我想知道在noip中如何用二进制来表示集合我在一篇文章中看到这样一段话：不过值得注意的是集合的表示方法：将一个集合与一个二进制数对应,再将二进制数与十进制数对应.为了方便

Question

我想知道在noip中 如何用二进制来表示集合
我在一篇文章中看到这样一段话：
不过值得注意的是集合的表示方法：将一个集合与一个二进制数对应,再将二进制数与十进制数对应.为了方便操作,单词的编号也可以从1…N,改成0…N-1.比如：集合[1,4,5]->集合[0,3,4]->11001(2)->2^0+2^3+2^4=25.这样操作不但节省了空间,而且在进行集合操作时可以用位操作,又节省了时间.
请问这段话中的集合具体是怎么表示?
感激不尽!

Answer 1

简单说就是把集合用一个数表示：
[1,4,5]就表示为25,25就是集合[1,4,5].
为什么呢?
25表示成二进制是11001,第1,4,5位是1,就说明集合中含有1,4,5这三个数,其余位是0,则表示集合中不含其它数.
这样表示对吗?
答案是肯定的.因为,对于一个集合,任意一个数只有两个状态,属于or不属于,0表示不属于,1表示属于,完全可以.
再就几个例子：
集合[2,4],可表示为1010,转化为十进制就是10,然后10就可表示集合[2,4];
集合[1,2,5,7],可表示为1010011,转化为十进制是83,83就表示集合[1,2,5,7];
数23,变为二进制是10111,对应的集合就是[1,2,3,5];
这样一个数就可以表示一个集合了,简洁明了,还可以进行位运算.但有限制,集合里的数不能太大,若是有个100000,你就需要2^（100000-1）这么大的数存了.那就得不偿失了.
建议：学习一下 位运算,很好很强大的一个工具.
还有不明白的尽管问,