牛客多校第三场J LRU management（双向链表）题解

素颜马尾好姑娘i 2021-11-05 02:10 254阅读 0赞

# 题意： #

给一个长度为\\(m\\)的队列，现给定以下操作：  
\\(opt=0\\)，插入一个串，如果不在队里直接插入栈尾，如果超出\\(m\\)删队首；在队里就拿出来重新放到队尾，返回\\(v\\)值。  
\\(opt=1\\)，问某串的前/中/后的串的\\(v\\)值是什么，不存在输出\\(Invalid\\)。

# 思路： #

把串\\(Hash\\)，然后用双向链表维护这个队列。标程建议用\\(Trie\\)去\\(Hash\\)，不过也可以用\\(unordered\\\_map\\)卡过去。

# 代码： #

/***** 双向链表板子 *****/ struct Node{ //双向链表 int v; //val或者其他属性 int pre; //前面 int nex; //后面 }p[maxn]; //p[i]表示值为i的节点 int head, tail, sz; void ins(int ID){ //插在末尾 int u = p[tail].pre; p[tail].pre = ID; p[u].nex = ID; p[ID].pre = u; p[ID].nex = tail; sz++; } void del(int ID){ //删除 int u = p[ID].pre; int v = p[ID].nex; p[u].nex = v; p[v].pre = u; sz--; } void init(){ head = 0; //头 tail = 1; //尾(空) sz = 0; //链表中的节点数 p[head].nex = tail; p[tail].pre = head; }

#include<map> #include<set> #include<cmath> #include<cstdio> #include<stack> #include<ctime> #include<vector> #include<queue> #include<cstring> #include<string> #include<sstream> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 500000 + 5; const int INF = 0x3f3f3f3f; const ull seed = 131; const ll MOD = 1e9 + 7; using namespace std; struct Node{ //双向链表 int v; //val或者其他属性 int pre; //前面 int nex; //后面 }p[maxn]; //p[i]表示值为i的节点 unordered_map<ull, int> id; unordered_set<int> in; int head, tail, sz, tot; void ins(int ID){ //插在末尾 int u = p[tail].pre; p[tail].pre = ID; p[u].nex = ID; p[ID].pre = u; p[ID].nex = tail; in.insert(ID); sz++; } void del(int ID){ //删除 int u = p[ID].pre; int v = p[ID].nex; p[u].nex = v; p[v].pre = u; in.erase(ID); sz--; } void init(){ tot = 2; head = 0; //头 tail = 1; //尾(空) sz = 0; p[head].nex = tail; p[tail].pre = head; } char s[maxn]; int main(){ int T; scanf("%d", &T); while(T--){ int Q, m; scanf("%d%d", &Q, &m); id.clear(); in.clear(); init(); while(Q--){ int op, v; char s[20]; scanf("%d%s%d", &op, s, &v); int len = strlen(s); ull Ha = 0; for(int i = 0; i < len; i++) Ha = Ha * seed + s[i]; if(id.find(Ha) == id.end()) id[Ha] = tot++; int ID = id[Ha]; if(op == 0){ if(in.find(ID) == in.end()){ ins(ID); p[ID].v = v; if(sz > m) del(p[head].nex); } else{ del(ID); ins(ID); } printf("%d\n", p[ID].v); } else{ if(in.find(ID) == in.end()) printf("Invalid\n"); else{ if(v == 1){ if(p[ID].nex == tail) printf("Invalid\n"); else printf("%d\n", p[p[ID].nex].v); } else if(v == -1){ if(p[ID].pre == head) printf("Invalid\n"); else printf("%d\n", p[p[ID].pre].v); } else printf("%d\n", p[ID].v); } } } } return 0; }

转载于:https://www.cnblogs.com/KirinSB/p/11301693.html