翻转硬币（思维题，巧用bitset）

0翻转硬币 - 蓝桥云课

 

#include <bits/stdc++.h> using namespace std; bitset<200000001> t; int main() { int n;cin>>n; int ans=1; t[1]=1; int tot=n-1; for(int i=2;i<=n;i++){ if(t[i]) continue; int j=i; ans++; while(j<=n){ t[j]=!t[j]; if(t[j]) tot--; else tot++; j+=i; } if(!tot) break; } cout<<ans; return 0; }

这段代码中，bitset<200000001> t; 是一个非常关键的声明，它定义了一个名为 t 的 bitset 对象，大小为 200,000,001 位（即 200,000,001 个布尔值）。bitset 是 C++ 标准库中的一个模板类，用于高效地存储和操作位（bit）序列。

在 C++ 中，bitset 的大小是固定的，必须在编译时确定。因此，bitset<200000001> 中的 200000001 是必须明确指定的，它表示 bitset 的大小为 200,000,001 位。如果不写这个大小，编译器会报错，因为 bitset 的大小是必须的。

1. bitset 的作用

bitset 是一种特殊的容器，它将每一位存储为一个布尔值（0 或 1）。它非常适合用于处理大规模的布尔状态数组，因为它的存储效率非常高，每一位只占用一个比特（bit）的空间，而不是一个字节（byte）。

在这个代码中，t 用于记录每个数字的状态。具体来说：

如果 t[i] 为 1，表示数字 i 被标记为“已处理”或“已翻转”。

如果 t[i] 为 0，表示数字 i 未被处理。

2. 为什么选择 bitset

内存效率：bitset 的内存占用非常小，因为它直接操作位，而不是使用更大的数据类型（如 bool 或 int）。对于大规模数据（如 200,000,001 个数字），使用 bitset 可以显著减少内存占用。

操作效率：bitset 提供了高效的位操作方法，例如翻转、设置、清除等操作，这些操作的时间复杂度为 O(1)。