[Acwing] 健康的荷斯坦奶牛 -二进制枚举

前言

传送门 : https://www.acwing.com/problem/content/description/1364/ 传送门2: https://www.acwing.com/problem/content/description/1364/ 如果用二进制枚举Ac了,他不会提高你的二进制枚举能力,只提高了你debug能力 (代码大概写了5分钟,debug半小时)

前置技能

什么是 二进制枚举

我们高中都学过 二进制系数性质

C ( N , 0 ) + C ( N , 1 ) + C ( N , 2 ) + … + C ( N , N ) = 2 n C(N, 0)+C(N, 1)+C(N, 2)+\ldots+C(N, N)=2^{n} C(N,0)+C(N,1)+C(N,2)+…+C(N,N)=2n

当然没学过也不要紧,你只要知道这是N个数中,选0-N个数的所有选法

又因为每个二进制数唯一,因此我们可以用二进制数表示选的方案

例如 : 5 = 101 表示拿了1号位和0号位

因此我们就有一个枚举模板出来了:

for(int j = 0; j