题解：P9779 [HUSTFC 2023] 不定项选择题
lailai0916
·
·
题解
题意简述
## 解题思路
非空选项集合共 $2^n-1$ 种，都可能是答案。每次操作改变一个选项，相当于在 $n$ 维超立方体上从一个集合走到相邻集合。
从空集出发按格雷码顺序遍历，每次操作恰好走到一个新集合，依次试遍所有非空集合。最坏情况下答案是最后一个被试到的，要 $2^n-1$ 次操作；这同时是下界——可能要试完全部 $2^n-1$ 个集合才碰上答案。
故答案为 $2^n-1$。
时间复杂度为 $O(1)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
cout<<(1<<n)-1<<'\n';
return 0;
}
```