CFGYM102394L CCPC2019哈尔滨 L题 LRU Algorithm

首先做法很简单：令缓存大小为n，然后直接把操作模拟一遍，后期如果我们限制了缓存大小为x，那就等价于取我们在模拟时长度为x的前缀。

然后我们显然可以把前缀哈希算一算，插到`std::unordered_map`里，然后成功TLE。

然后我们考虑另一个做法：把询问插到字典树里，仍然对操作进行模拟，每模拟一次后，在字典树上把序列走一遍，并标记对应的询问为Yes。

但是有几个地方要注意

• 一个点可能对应多个询问，所以用一个vector来挂询问吧。
• 一组询问在去除后缀0之后可能长度为0，此时询问是被挂在根上的，务必进行处理，否则WA！

#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;
}