前言：
牛客2021多校Alice and Bob ，在这题中5000 * 5000 * 5000的复杂度，用bitset 140ms，bool 493ms。bitset快到起飞。
AcWing348–最优比率生成树，这题用bitset会TLE，用bool反而AC。
讨论：
如果一直连续访问数组中的元素，bool明显快于bitset。
bool : 26ms
bitset : 108ms
#includeusing namespace std;#define int long longconst int N = 1e6 + 5, mod = 1e9 + 7;bitset f;signed main(){ srand((unsigned)time(0)); freopen("data.in","r",stdin);freopen("data.out","w",stdout);clock_t start, stop; start=clock(); int T = 50; while(T--){ for (int i = 1; i <= N - 5; i++) { f[i] = 1; } for (int i = 1; i <= N - 5; i++){ f[i] = 0; } } stop = clock(); cout << endl << "time: " << stop - start; return 0;}
但是访问较为随机的时候，bitset又比bool更快：
bool : 283ms
bitset : 224ms
#includeusing namespace std;#define int long longconst int N = 1e6 + 5, mod = 1e9 + 7;bitset f;signed main(){ srand((unsigned)time(0)); freopen("data.in","r",stdin);freopen("data.out","w",stdout);clock_t start, stop; start=clock(); int T = 10; while(T--){ for (int i = 1; i <= N - 5; i++) { int x = rand() * rand() % (N - 5); f[x] = 1; } } stop = clock(); cout << endl << "time: " << stop - start; return 0;}
总结：
随机访问时，bitset更快；连续访问时，bool更快。所以多测如果要清空时，建议选bool数组，选bitset此时可能会TLE。牛客多校那题开头sg函数打表是比较随机的，且多测不用清空，所以bitset会非常快。