首先做法很简单：令缓存大小为n，然后直接把操作模拟一遍，后期如果我们限制了缓存大小为x，那就等价于取我们在模拟时长度为x的前缀。
然后我们显然可以把前缀哈希算一算，插到std::unordered_map里，然后成功TLE。
然后我们考虑另一个做法：把询问插到字典树里，仍然对操作进行模拟，每模拟一次后，在字典树上把序列走一遍，并标记对应的询问为Yes。
但是有几个地方要注意
- 一个点可能对应多个询问，所以用一个vector来挂询问吧。
- 一组询问在去除后缀0之后可能长度为0，此时询问是被挂在根上的，务必进行处理，否则WA！
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <assert.h> #include <algorithm> #include <cstring> #include <iostream> #include <unordered_map> #include <vector> using int_t = int; using std::cin; using std::cout; using std::endl; using map_t = std::unordered_map<int_t, struct Node*>; const int_t LARGE = 5e3 + 20; char inputbuf[(int64_t)1e8]; char* head = inputbuf; void initinput() { fread(inputbuf, 1, sizeof(inputbuf), stdin); } char nextchar() { assert(head <= inputbuf + sizeof(inputbuf)); return *(head++); } template <class T> void read(T& x) { x = 0; char chr = nextchar(); while (chr < '0' || chr > '9') chr = nextchar(); while (chr >= '0' && chr <= '9') { x = x * 10 + chr - '0'; chr = nextchar(); } } struct Node { std::vector<bool*> result; map_t chd; ~Node() { for (const auto& kvp : chd) delete kvp.second; } }; int_t arr[LARGE + 1]; int_t arr1[LARGE + 10], queue[LARGE + 1]; bool result[LARGE + 1]; int main() { initinput(); int_t T; read(T); while (T--) { queue[0] = 0; int_t n, q; read(n), read(q); Node* root = new Node; for (int_t i = 1; i <= n; i++) { read(arr[i]); } for (int_t i = 1; i <= q; i++) { result[i] = false; Node* curr = root; int_t len; read(len); #ifdef DEBUG cout << "insert len " << len << endl; #endif for (int_t j = 1; j <= len; j++) { int_t x; read(x); if (x == 0) continue; #ifdef DEBUG cout << "insert " << x << endl; #endif auto& ref = curr->chd[x]; if (ref == nullptr) ref = new Node; curr = ref; } curr->result.push_back(&result[i]); #ifdef DEBUG cout << "insert ok, result to " << i << endl; #endif } for (int_t i = 1; i <= n; i++) { int_t x = arr[i]; arr1[0] = 0; arr1[++arr1[0]] = x; for (int_t j = 1; j <= queue[0]; j++) { if (queue[j] != x) arr1[++arr1[0]] = queue[j]; } // arr1[0] = std::min(arr1[0], n); assert(arr1[0] <= n); memcpy(queue, arr1, sizeof(arr1[0]) * (n + 1)); Node* curr = root; #ifdef DEBUG cout << "mapping seq "; for (int_t i = 1; i <= queue[0]; i++) cout << queue[i] << " "; cout << endl; #endif for (int_t i = 1; i <= queue[0]; i++) { if (!curr->chd.count(queue[i])) break; else curr = curr->chd[queue[i]]; #ifdef DEBUG cout << "walk with " << queue[i] << endl; #endif for (auto ptr : curr->result) { *ptr = true; #ifdef DEBUG cout << "mark result " << (ptr - result) << " to true" << endl; #endif } } } for (auto x : root->result) *x = true; for (int_t i = 1; i <= q; i++) { if (result[i]) { puts("Yes"); } else { puts("No"); } } delete root; } return 0; } |