关于flag布尔数组标记 和 set 标记 的一些想法-ProLightsfxjh

关于flag布尔数组标记 和 set 标记 的一些想法

1、当只做整体标记时，即测试本组数据时不用重置。

1) 如果 需要标记的东西不是很大，且能够用flag数组的下标来存储状态信息，则用flag数组 无论是空间复杂度还是时间复杂度都会更优越些，毕竟set查询是O(logn)的而flag数组是O(1) 的，并且由于封装出set所以带的功能比较多，需要的内存要多一些也属正常。

比如 http://codeforces.com/problemset/problem/699/D 这题。

全用flag布尔数组，

源码 http://codeforces.com/contest/699/submission/20972041

时间  561 ms

内存 7420KB

而如果纯用set做标记，

源码 http://codeforces.com/contest/699/submission/20973614

时间 873 ms

内存 19604KB

2) 如果 需要标记的东西很大，不能够用flag数组的下标来存储状态信息，则只能用 set 或 map 了。

2、当只作局部标记，即测试本组数据时有很多次重置。

flag数组不断地用memset重置要浪费大量的时间去重置没有使用过的地方，

故，如果不能在 回溯等过程中直接对使用过的地方逐一重置，则用 set 或map 更好，否则可以用 flag布尔数组。

3、此外 1)当要标记的东西不能够用flag数组的下标来存储状态信息 比如很多long long int的整型数，或者直接对string 或其它类类型进行标记，一般就用 set 或者 map 标记了

2)当要标记的东西很离散时，建议用set 或者 map，这样不用浪费太多内存 。

参考资料 《C++ Primer 5th》、Codeforces 等

2016-09-29 00:52:20

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx