U626763 小D的奶牛

暑假，小D去了一个神奇的岛屿度假，在这个岛上有一群有神奇的奶牛。

岛屿上的奶牛一共有$N$只，每一天，有一部分奶牛去工作，另一部分奶牛去玩乐。哪些奶牛去工作由奶牛首领决定。 奶牛们都是暴躁老哥，一旦工作安排使他们不满就会发生暴动；具体来说如果某天去工作的奶牛中存在两只奶牛不是朋友关系，它们就会烦躁；或者某天的工作安排和之前某天相同，他们会厌倦，这两种情况下就会暴动。 显然，暴动是一定会发生的。奶牛首领想要暴动尽量晚发生，向小D询问暴动最晚的发生时间；但小D还要忙着颓废，于是把这个问题交给了你。

第一行一个整数$N$，描述奶牛的数量。 接下来$N$行，每行$N$个0/1字符描述关系矩阵$A$。 若$A_{i,j}=1$表示$i$和$j$是朋友关系。 保证$A_{i,j}=A_{j,i}$，$A_{i,i}=0$

输出到文件`cows.out`中。 一行一个整数$Ans$，奶牛最晚发生暴动的时间。

对于$10\%$的数据，$N\leq 9$ 对于$30\%$的数据，$N\leq 20$ 另有$20\%$的数据， 每个奶牛的朋友数量不超过$ 20$ 对于$100\%$的数据，$N\leq 50$ ## 10%： 暴力； ## $n\le20$：状压dp； ## 另外20%数据： 团的大小$\leq 21$: 枚举团上编号最小的点，然后同上一部分； ## 正解 考虑Meet in the middle： 先考虑前$N / 2$个点，求出每种取点方式是否能形成一个团； 再考虑后$N / 2$个点，求出每种取点方式有多少个子集是一个团； 枚举每个前部分的点的选取方式，然后求出后半部分有哪些点和它们都有边； 然后后半部分能取的集合的数量就是，后半部分那些点的子集中形成的团的数量； $O(N * 2 ^ (N / 2))$ std ```cpp #include #include using namespace std; const int MAX = 50; const int MANY = 1 > n; int n1 = n/2; int n2 = (n+1)/2; assert(1 c; M[i][j] = c -'0'; if (i > j) assert(M[i][j] == M[j][i]); if (M[i][j]==0) continue; if (i < n1 && j < n1) Adj1[i] |= 1 = n1) Adj12[i] |= 1 = n1 && j >= n1) Adj2[i] |= 1