Codeforces Round#710 div.3 回顾 比赛链接：https://codeforces.ml/contest/1506
记录 比赛的时候可以说还是有点捞的，，竟然没有时间写完最后一题，属是不是很行（
但是精彩还是在比完之后：
_XMUTFT_4YHFRV__35DML_Y.png 直呼就这？
题解 毕竟是 Div3，所以就只贴被 Hack 的题和没写出来的题好了：
原来是 unordered_map 被卡了，，也不能这么说，也许遍历 unordered_map 就是意外的要慢（
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 const int N = 2e5 + 5 ;map <int , int > cnt;signed main () ios::sync_with_stdio(false ); std ::cin .tie(nullptr ); std ::cout .tie(nullptr ); #if 0 freopen("in.txt" , "r" , stdin ); #endif int T = scanner.nextInt(); while (T --) { int n = scanner.nextInt(); cnt.clear(); for (int i = 1 ; i <= n; ++ i) ++ cnt[scanner.nextInt()]; int major = 0 ; for (auto [k, v] : cnt) maximize(major, v); println(max(n % 2 , major - (n - major))); } return 0 ; }
哦，，破案了，，实际上是不断扩容消耗了大量的时间，，在使用之前预留空间就没有任何问题（
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 const int N = 2e5 + 5 ;unordered_map <int , int > cnt;signed main () ios::sync_with_stdio(false ); std ::cin .tie(nullptr ); std ::cout .tie(nullptr ); #if 0 freopen("in.txt" , "r" , stdin ); #endif int T = scanner.nextInt(); while (T --) { int n = scanner.nextInt(); cnt.clear(), cnt.reserve(n * 2 ); for (int i = 1 ; i <= n; ++ i) ++ cnt[scanner.nextInt()]; int major = 0 ; for (auto [k, v] : cnt) maximize(major, v); println(max(n % 2 , major - (n - major))); } return 0 ; }
就结果而言实际上跑的比 map 还要快：
M_H5_L__9533_L__SQT__EV.png 上面是 unordered_map + reserve 两倍空间，下面是 map；
没什么好说的，典型的复杂度估计错误，，这种数据范围 1e5 的，还要求在指定范围内寻找最大最小值的，拿个对数数据结构维护一下是再适合不过了；而且实际上也不难写，，只能说有些意识还是不够（
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 const int N = 2e5 + 5 ;int pmx[N], pmn[N], q[N];set <int > umx, umn;signed main () ios::sync_with_stdio(false ); std ::cin .tie(nullptr ); std ::cout .tie(nullptr ); #if 0 freopen("in.txt" , "r" , stdin ); #endif int T = scanner.nextInt(); int mx = 0 , mn = 0 ; const auto update = [&](int pos) { while (++ mx < pos) umx.insert(mx); while (++ mn < pos) umn.insert(mn); }; while (T --) { int n = scanner.nextInt(); for (int i = 1 ; i <= n; ++ i) q[i] = scanner.nextInt(); memset (pmx, 0 , sizeof (int ) * (n + 1 )); memset (pmn, 0 , sizeof (int ) * (n + 1 )); umx.clear(), umn.clear(); pmx[1 ] = pmn[1 ] = q[1 ], mx = mn = 0 ; update(q[1 ]); for (int i = 2 ; i <= n; ++ i) if (q[i] > q[i - 1 ]) pmx[i] = pmn[i] = q[i]; for (int i = 2 ; i <= n; ++ i) { if (!pmx[i]) { pmx[i] = *umx.rbegin(); umx.erase(*umx.rbegin()); } else update(pmx[i]); if (!pmn[i]) { pmn[i] = *umn.begin(); umn.erase(umn.begin()); } } for (int i = 1 ; i <= n; ++ i) print(pmn[i], " \n" [i == n]); for (int i = 1 ; i <= n; ++ i) print(pmx[i], " \n" [i == n]); } return 0 ; }
看来对 bitset 的无脑崇拜也得差不多得了（
十分经典的问题，讲清楚了其实就没什么好说的；只能说思考题目的时候应该更加地理性，而不是总是对玄学抱有不切实际的幻想；比如这个题，如果看到就去考虑什么玄学构造方法，瞎几把贪，还欺骗自己的做法是正确的且很有道理，那就会贻笑大方，一辈子也做不出了（
首先，很显然待构造的 \(t\) 是 \(s\) 的子序列：这说明我们可能可以按照顺序遍历每个字符，来确定是否要把它加入到 \(t\) 的末尾（当然 \(t\) 最开始是一个空串）；对于一个构造到一半的 \(t\) ，在某个位置 \(i\) 的字符 \(s[i]\) 可以加入 \(t\) 的末尾的必要条件是，\(s\) 从 \(i\) 开始的后缀（后面记作 \(s_i\) ）包含了所有 \(t\) 不包含的字符。
显然，\(t\) 的总长度也是确定的（并且极其有限），所以我们可以遍历字符串 \(t\) 需要，但是目前的构造阶段还不包含的可能的字符，找到可以插入且尽可能大的字符插入即可。每次插入的字符都确保它的后缀中有足够的其他字符使得构造不会失败，因此我们总是可以找到合理的字符并插入其中。
当然，这里实际上也有一个小小的贪心：字符串前面的字符大的字符串字典序更大（可以说是显然了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 const int N = 2e5 + 5 ;char s[N], t[N];vector <int > pos[30 ];signed main () ios::sync_with_stdio(false ); std ::cin .tie(nullptr ); std ::cout .tie(nullptr ); #if 0 freopen("in.txt" , "r" , stdin ); #endif int T = scanner.nextInt(); const auto suffix = [&](char ch, int st) { auto &p = pos[ch - 'a' ]; auto it = lower_bound(p.begin(), p.end(), st); if (it == p.end()) return -1 ; else return *it; }; const auto count = [&](int st) { if (st == -1 ) return 0 ; int ret = 0 ; for (const auto &ii : pos) { auto it = lower_bound(ii.begin(), ii.end(), st); if (it != ii.end()) ++ ret; } return ret; }; while (T --) { scanner(s); int n = strlen (s), len = 0 ; set <char > ss (s, s + n) const int siz = ss.size(); for (int i = 0 ; i < n; ++ i) pos[s[i] - 'a' ].push_back(i); int st = 0 ; while (len < siz) { char add = 0 ; for (auto ch : ss) if (count(suffix(ch, st)) + len == siz) maximize(add, ch); t[len ++] = add; st = suffix(add, st) + 1 ; pos[add - 'a' ].clear(); ss.erase(add); } t[len] = '\0' ; println(t); } return 0 ; }
每次检查一个字符是否合法的复杂度是 \(O(26\text{log}n)\) 的，因为只有小写拉丁字母，所以检查次数是 \(O(26\cdot26)\) 的；上面的代码去重用了 set（其实完全没必要），复杂度是 \(O(n\text{log}n)\) 的；综上所述，总时间复杂度是 \(O((26^3 + n)\cdot\text{log}n)\) 的；如果不用 set 去重，时间复杂度可以做到 \(O(\text{log}n)\) 的。
后记 不要盲目崇拜 bitset 和 unordered_map；至少要明白使用它们意味着什么：
unordered_map 本质是哈希表，它的访问是将键值经过哈希计算映射到本地的连续空间，从而可以快速的“随机访问”的；如果这段连续空间不足以存储数据，就必须要开辟更大的空间，并且 rehash，从而将键值映射到更大的连续空间中；这个过程很显然是极其耗时的，但是在做题的时候我们大概知道元素的数量，所以可以使用它提供的 reserve 方法，预留足够的空间，就可以减少这个过程的发生，从而达到提速的目的。
当然，pb_ds 里的哈希表又是另一回事，得找个时间去了解才行。
至于这个 G，确实是和我还颇有渊源，，，这个就不提了（）但是确实在做题的时候应当舍弃不切实际的无聊幻想，用做题的思维去考虑才行==
