2019牛客暑期多校训练营（第三场） - J - LRU management - 模拟
2024-09-05 20:36:44
https://ac.nowcoder.com/acm/contest/883/J
根据这个数据结构的特点，也就是计算机组成原理里面学过的cache的LRU管理算法，每次访问都会在cache中查询一页，查询成功则调用该页的值并将该页移动到删除队列的尾部。否则直接加载该页在删除队列的尾部，当队列满时弹出队首。另一种操作是查询到某页后调用其、或其前一页、或其后一页，失败均返回Invalid。
那么一个可以删除中间元素的队列，明显用链表实现，而且要其前一页、后一页，那就双向链表。因为链表的瓶颈在于查询，而这道题的特点可以使用其他数据结构加速查询的过程。这里都是短的字符串，可以用unordermap或者trie来维护“字符串对应的链表节点”。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500010;
const int maxm = 5000010;
const int FAIL = -100;
struct ListNode;
struct TrieNode {
TrieNode *ch[10];
ListNode *lid;
};
struct Trie {
TrieNode tn[maxm], *root;
int top;
inline void Init() {
top = 0;
root = NewNode();
}
inline TrieNode *NewNode() {
for(int i=0;i<10;++i)
tn[top].ch[i]=nullptr;
tn[top].lid = nullptr;
return &tn[top++];
}
inline TrieNode *Insert(char *s, ListNode *lid) {
TrieNode *cur = root;
int len=strlen(s);
for(int i = 0; i < len; ++i) {
int c = s[i] - '0';
if(!cur->ch[c])
cur->ch[c] = NewNode();
cur = cur->ch[c];
}
cur->lid = lid;
return cur;
}
inline TrieNode *Query(char *s) {
TrieNode *cur = root;
int len=strlen(s);
for(int i = 0; i < len; ++i) {
int c = s[i] - '0';
if(!cur->ch[c])
return nullptr;
cur = cur->ch[c];
}
return cur;
}
} T;
struct ListNode {
ListNode *prev, *next;
int val;
TrieNode *tid;
};
struct List {
ListNode ln[maxm];
ListNode *head, *tail;
int top, size;
void Init() {
//head,tail都是虚拟节点
top = 0, size = 0;
head = NewNode(-1, nullptr, nullptr, &ln[1]);
tail = NewNode(-1, nullptr, &ln[0], nullptr);
}
ListNode *NewNode(int val, TrieNode *tid, ListNode *prev, ListNode *next) {
ln[top].val = val;
ln[top].tid = tid;
ln[top].prev = prev;
ln[top].next = next;
return &ln[top++];
}
void Append(int val, TrieNode * tid) {
Insert(val, tid, tail->prev);
}
void Insert(int val, TrieNode *tid, ListNode *pn) {
//在pn后面插入
ListNode *newNode = NewNode(val, tid, pn, pn->next);
pn->next->prev = newNode;
pn->next = newNode;
++size;
}
void Delete(ListNode *pn) {
//删除pn
pn->prev->next = pn->next;
pn->next->prev = pn->prev;
--size;
}
} L;
int M;
char s[105];
inline int OP0(int _val) {
TrieNode *x = T.Query(s);
int val;
if(!x||!x->lid) {
val = _val;
if(L.size == M) {
L.head->next->tid->lid = nullptr;
L.Delete(L.head->next);
}
L.Append(val, nullptr);
L.tail->prev->tid = T.Insert(s, L.tail->prev);
} else {
ListNode *y = x->lid;
val = y->val;
L.Delete(y);
L.Append(val, x);
x->lid = L.tail->prev;
}
return val;
}
inline int OP1(int _val) {
TrieNode *x = T.Query(s);
if(!x)
return FAIL;
ListNode *y = x->lid;
if(!y)
return FAIL;
if(_val > 0) {
y = y->next;
if(y == L.tail)
return FAIL;
return y->val;
}
if(_val < 0) {
y = y->prev;
if(y == L.head)
return FAIL;
return y->val;
}
return y->val;
}
int main() {
#ifdef local
freopen("a.txt", "r", stdin);
#endif // Yinku
int t, q, op, v;
scanf("%d", &t);
while(t--) {
T.Init();
L.Init();
scanf("%d%d", &q, &M);
for(int i = 0; i < q; ++i) {
scanf("%d%s%d", &op, s, &v);
if(!op)
printf("%d\n", OP0(v));
else {
int ans = OP1(v);
if(ans == FAIL)
puts("Invalid");
else
printf("%d\n", ans);
}
}
}
return 0;
}
最新文章
- mysql 修改root密码
- Android框架之AndroidAnnotations实战
- JavaScript基础介绍
- 什么是好的API设计？（转）
- oracle10g配置小记
- Python全栈开发day3
- jmeter 监听的介绍
- 类成员函数作为pthread_create函数参数
- Self-Paced Training (3) - Docker Operations
- 安装tomcat出现failed to install tomcat8 service错误及解决方法
- poj2186Popular Cows（强连通分量）
- 轻松学习Ionic （二） 为Android项目集成Crosswalk（更新官方命令行工具）
- Linux系统ifconfig命令找不到，centos ifconfig Command not found
- 【转】android 电容屏（二）：驱动调试之基本概念篇
- Failed to load c++ bson extension, using pure JS version
- Targeted Learning R Packages for Causal Inference and Machine Learning（转）
- Redis之基本使用
- 原生js标识当前导航位置（给当前导航一个className=active）
- Xaml引用图片路径的方式
- java基础面试题-2