3 solutions
-
1
难得能比较简短地写出来一个T3，发现已有题解用链表做的，我是用堆做的，于是简单分享一下。
大体思路还是模拟，关于如何定位是否存在某个编号的内存块，我选择用一个
set，将关键字设置为块编号，用内置lower_bound来实现。还有一点是需要找最近最久未使用，即时间戳最小的一个块，这里还是用一个set，但是这两个set关键字不同，于是乎我开了两个set来解决这个问题（）每次修改同时维护即可。（鄙人陋习，写cp代码不空格）
#include<bits/stdc++.h> using namespace std; const int maxn=(1<<16)+10; struct Node1{ int id,ti; bool ch; bool operator < (const Node1 &rhs) const { return id==rhs.id?ti<rhs.ti:id<rhs.id; } }; struct Node2{ int id,ti; bool ch; bool operator < (const Node2 &rhs) const { return ti==rhs.ti?id<rhs.id:ti<rhs.ti; } }; int n,N,m,cnt; set<Node1> s1[maxn]; set<Node2> s2[maxn]; int main() { scanf("%d%d%d",&n,&N,&m); while(m--) { int opt,x;scanf("%d%d",&opt,&x); int id=x%(n*N)/n;x++; auto it1=s1[id].lower_bound({x,0,0}); if(it1!=s1[id].end()&&(it1->id)==x) { Node1 u=*it1; s1[id].erase(it1); s1[id].insert({x,++cnt,u.ch||opt}); auto it2=s2[id].lower_bound({0,u.ti,0}); s2[id].erase(it2); s2[id].insert({x,cnt,u.ch||opt}); continue; } if((int)s2[id].size()<n) { // printf("==="); printf("0 %d\n",x-1); s1[id].insert({x,++cnt,(bool)opt}); s2[id].insert({x,cnt,(bool)opt}); } else { auto it2=s2[id].begin(); Node2 u=*s2[id].begin(); if(u.ch) { // printf("==="); printf("1 %d\n",u.id-1); } // printf("==="); printf("0 %d\n",x-1); it1=s1[id].lower_bound({u.id,0,0}); s1[id].erase(it1); s1[id].insert({x,++cnt,(bool)opt}); s2[id].erase(it2); s2[id].insert({x,cnt,(bool)opt}); } } return 0; } -
0
链表+hash
链表：便于pop_back()删去末尾缓存行 l.back()取末尾缓存行内存编号，push_front()将新取的缓存行放入首行
hash映射：unordered_map<int,Block> hamp,Block.it迭代器，Block.f表示是否被写； 便于hmap.count()查找内存是否存在该缓存(O(1))，hamp[a]便于直接找到缓存的位置（iterator迭代器，是否被写）
注：替换不是放到缓存行最后，而是放到行首 缓存替换+lru比较复杂，建议先在网上学下，自己动手模拟下
#include <iostream> #include <vector> #include <list> #include <algorithm> #include <unordered_map> using namespace std; struct Block{ list<int>::iterator it; bool f = false; }; int main(){ int n,N,t; cin>>n>>N>>t; int op,a; vector<list<int>> lru(N); vector<unordered_map<int,Block>> hmap(N); while(t--){ cin>>op>>a; int grp = (a/n)%N; auto& L = lru[grp]; auto& T = hmap[grp]; if(T.count(a)){//命中 auto& itr = T[a].it; L.erase(itr); L.push_front(a); T[a].it = L.begin(); if(op == 1) T[a].f = true; } else{//未命中 if(L.size()==n){//full if(T[L.back()].f == true){ cout<<1<<' '<<L.back()<<endl; } T.erase(L.back()); L.pop_back(); L.push_front(a); T[a].it = L.begin(); if(op == 1) T[a].f = true; cout<<0<<' '<<a<<endl; } else{//未命中，没满 L.push_front(a); cout<<0<<' '<<a<<endl; T[a].it = L.begin(); if(op == 1) T[a].f = true; } } } } -
0
本题作为 T3 其实相对简单，除了读题稍微有点难度之外，实现起来比较简单。
我们可以对每一个缓存行组封装成一个结构体，然后对每一个对象单独操作。
而内部的操作内容本质上是 LRU 算法，这个在 leetcode 都能搜到，利用一个链表记录已有缓存，并且利用一个哈希表记录关键字以及其在链表当中的位置。然后按照 LRU 策略模拟即可。
需要注意的是，我们在数据中卡掉了暴力 LRU 策略的做法，在复刻数据中只能拿到 80 分。有关 LRU 的内容，建议前往 这里 学习。
#include <stdio.h> #include <assert.h> #include <vector> #include <unordered_map> struct fastIO { static const int BUFF_SZ = 1 << 18; char inbuf[BUFF_SZ], outbuf[BUFF_SZ]; fastIO() { setvbuf(stdin, inbuf, _IOFBF, BUFF_SZ); setvbuf(stdout, outbuf, _IOFBF, BUFF_SZ); } } IO; inline int rd() { int k = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') f = (c == '-') ? 0 : f, c = getchar(); while (c >= '0' && c <= '9') k = (k << 1) + (k << 3) + (c ^ 48), c = getchar(); return f ? k : -k; } inline void wr(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) wr(x / 10); putchar((x % 10) ^ '0'); } const int LIM = (1 << 16) | 10; inline void read_mem(int x) { putchar('0'), putchar(' '), wr(x), putchar('\n'); } inline void write_mem(int x) { putchar('1'), putchar(' '), wr(x), putchar('\n'); } // value : 0 read / 1 write struct LRUCache { int sz, lim; // current sz std::unordered_map<int, int> cache; // <key, list-ptr> // de-list struct delist_node { int k, v; // <key, value> int pre, nxt; }; std::vector<delist_node> no; std::vector<int> rec; int top, cnt; int newnode() { return top ? rec[top--] : ++cnt; } // notice : clear value flag when recycled void recycle(int u) { no[u].k = no[u].v = no[u].pre = no[u].nxt = 0, rec[++top] = u; } inline int add_front(int key) { int u = newnode(); no[no[0].nxt].pre = u, no[u].nxt = no[0].nxt; no[0].nxt = u, no[u].pre = 0; no[u].k = key, cache[key] = u; return u; } inline void adjust_to_front(int u) { no[no[u].pre].nxt = no[u].nxt, no[no[u].nxt].pre = no[u].pre; no[no[0].nxt].pre = u, no[u].nxt = no[0].nxt; no[0].nxt = u, no[u].pre = 0; } inline void pop_back() { int u = no[lim + 1].pre; no[lim + 1].pre = no[u].pre, no[no[u].pre].nxt = lim + 1; if (no[u].v) write_mem(no[u].k); // value = 1 : write to memory cache.erase(no[u].k), recycle(u); } // LRUCache(int capacity) inline void init(int capacity) { sz = top = cnt = 0, lim = capacity; rec.resize(lim + 2); no.resize(lim + 2); no[0].nxt = lim + 1, no[lim + 1].pre = 0; } inline int get(int key) { return cache.count(key) ? (adjust_to_front(cache[key]), no[cache[key]].v) : -1; } inline void put(int key, int value) { if (cache.count(key)) adjust_to_front(cache[key]), no[cache[key]].v |= value; else { // cache miss : read from memory (1.in : write first, and then read) if (sz >= lim) pop_back(); else ++sz; read_mem(key); int u = add_front(key); no[u].v |= value; } } } cache[LIM]; int n, N, q, mask; int bn, bN; int o, a; int main() { n = rd(), N = rd(), q = rd(); bn = __builtin_ctz(n), bN = __builtin_ctz(N), mask = (1 << (bn + bN)) - 1; for (int i = 0; i < N; ++i) cache[i].init(n); while (q--) { o = rd(), a = rd(); int id = (a & mask) >> bn; cache[id].put(a, o); } }
- 1