P9779Solution

题意简述

$n$ 个选项的多选题，答案是某个非空选项集合。每次操作勾选或取消一个选项，勾中答案即通过。求最坏情况下通过所需的最少操作次数。

解题思路

非空选项集合共 $2^n-1$ 种，都可能是答案。每次操作改变一个选项，相当于在 $n$ 维超立方体上从一个集合走到相邻集合。

从空集出发按格雷码顺序遍历，每次操作恰好走到一个新集合，依次试遍所有非空集合。最坏情况下答案是最后一个被试到的，要 $2^n-1$ 次操作；这同时是下界——可能要试完全部 $2^n-1$ 个集合才碰上答案。

故答案为 $2^n-1$。

时间复杂度为 $O(1)$。

参考代码

161 Bcpp

#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;
}