缓存模拟

GitHub跳转原题关系图 Canvas 关系图返回列表

用哈希表定位缓存块，用每组的双向链表维护 LRU 顺序，并按替换先写回再读入的顺序输出内存操作。

OJ: shumeng

题目 ID: CSP202412C

难度:普及+/提高-

标签:模拟LRU哈希表双向链表

日期: 2026-07-31 16:21

形式化题目

缓存共 $N$ 组，每组 $n$ 个缓存行；内存块 $a$ 所属组为 $(a / n) \bmod N$ 。依次执行 $q$ 条指令（0 读、1 写）：

命中：直接在缓存中访问，写指令把该缓存行标记为脏；
未命中：从内存读入该块；若组已满，按 LRU 规则淘汰最久未使用的缓存行，脏行需先写回内存。

输出所有实际发生的内存操作：读入块输出 0 块号，写回脏块输出 1 块号，按发生顺序输出。

思路

核心是同时维护三件事：块到缓存行的定位、每组的 LRU 顺序、每个缓存行的脏位。

朴素做法：每组用 vector 扫描

先看直接模拟：每组用一个 vector 保存缓存行，命中时线性查找，未命中且满时淘汰尾部，命中或新插入都移到头部。

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，用 vector 顺序扫描每组中的缓存行来模拟 LRU。
#include <bits/stdc++.h>
using namespace std;

struct Entry {
    int block;  // 缓存行保存的内存块编号
    bool dirty; // 是否被写改过
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, group_count, q;
    cin >> n >> group_count >> q;
    vector<vector<Entry> > cache(group_count); // 每组一个 vector，表头是最新使用的

    for (int operation = 1; operation <= q; operation++) {
        int type, block;
        cin >> type >> block;
        int group = (block / n) % group_count;

        // 线性查找当前组是否已缓存该块
        int hit = -1;
        for (int i = 0; i < (int)cache[group].size(); i++) {
            if (cache[group][i].block == block) {
                hit = i;
                break;
            }
        }

        if (hit != -1) {
            // 命中：按操作更新脏位，并移到表头
            Entry entry = cache[group][hit];
            if (type == 1) entry.dirty = true;
            cache[group].erase(cache[group].begin() + hit);
            cache[group].insert(cache[group].begin(), entry);
            continue;
        }

        // 未命中且已满：先写回最久未使用的脏块，再淘汰
        if ((int)cache[group].size() == n) {
            Entry victim = cache[group].back();
            if (victim.dirty) cout << "1 " << victim.block << '\n';
            cache[group].pop_back();
        }
        cout << "0 " << block << '\n';
        Entry entry;
        entry.block = block;
        entry.dirty = (type == 1);
        cache[group].insert(cache[group].begin(), entry);
    }

    return 0;
}

做法能正确确认操作顺序，但每次访问可能扫描整组并移动元素，只适合小数据。

主解：哈希定位 + 双向链表

把两个动作分开：

用哈希表 location 记录“内存块 → 缓存槽位”，期望 $O(1)$ 判断命中并定位；
每组维护一条双向链表，表头是最近使用、表尾是最久未使用的缓存行。命中时把节点移到表头；未命中且已满时淘汰表尾。

缓存总容量 $n \times N \le 65536$ ，可预先为每组分配 $n$ 个连续槽位：空槽直接使用，满组替换时复用 LRU 尾节点。

输出顺序

未命中时顺序很重要：若尾节点是脏的，先输出 1 old_block 写回，再输出 0 block 读入。写指令命中或读入后只把缓存行标记为脏，不会立刻再产生一次内存写。

样例推演

下表记录样例中组 $0$ 的 LRU 状态（星号表示脏行）：

指令	访问	结果	实际内存操作	处理后 LRU（表头在左）
1	读 0	未命中	`0 0`	`0`
2	读 1	未命中	`0 1`	`1, 0`
3	写 2	未命中	`0 2`	`2*, 1, 0`
4	读 1	命中	无	`1, 2*, 0`
5	写 0	命中	无	`0, 1, 2`
6	读 32	未命中	`0 32`	`32, 0, 1, 2`
7	写 33	未命中	`1 2`，`0 33`	`33, 32, 0, 1`
8	读 34	未命中	`0 34`	`34, 33, 32, 0`

注意第 7 条：组满后淘汰的尾节点是块 2，它曾被写入过，所以先写回 1 2 再读入 0 33。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

struct CacheLine {
    int block;
    int previous;
    int next;
    bool dirty;
};

struct CacheSet {
    int head;
    int tail;
    int used;
};

vector<CacheLine> lines;
vector<CacheSet> cache_sets;

void remove_from_lru(int group, int index) {
    int previous = lines[index].previous;
    int next = lines[index].next;

    if (previous == -1) cache_sets[group].head = next;
    else lines[previous].next = next;
    if (next == -1) cache_sets[group].tail = previous;
    else lines[next].previous = previous;

    lines[index].previous = -1;
    lines[index].next = -1;
}

void insert_to_front(int group, int index) {
    int old_head = cache_sets[group].head;
    lines[index].previous = -1;
    lines[index].next = old_head;
    if (old_head == -1) cache_sets[group].tail = index;
    else lines[old_head].previous = index;
    cache_sets[group].head = index;
}

void touch(int group, int index) {
    if (cache_sets[group].head == index) return;
    remove_from_lru(group, index);
    insert_to_front(group, index);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, group_count, q;
    cin >> n >> group_count >> q;

    lines.resize(n * group_count);
    cache_sets.resize(group_count);
    for (int group = 0; group < group_count; group++) {
        cache_sets[group].head = -1;
        cache_sets[group].tail = -1;
        cache_sets[group].used = 0;
    }
    unordered_map<int, int> location;
    location.reserve(q * 2 + 1);

    for (int operation = 1; operation <= q; operation++) {
        int type, block;
        cin >> type >> block;
        int group = (block / n) % group_count;

        unordered_map<int, int>::iterator found = location.find(block);
        if (found != location.end()) {
            int index = found->second;
            if (type == 1) lines[index].dirty = true;
            touch(group, index);
            continue;
        }

        // 未命中时先处理被替换缓存行的写回，再从内存读入新块。
        int index;
        if (cache_sets[group].used < n) {
            index = group * n + cache_sets[group].used;
            cache_sets[group].used++;
        } else {
            index = cache_sets[group].tail;
            if (lines[index].dirty) cout << "1 " << lines[index].block << '\n';
            location.erase(lines[index].block);
            remove_from_lru(group, index);
        }

        cout << "0 " << block << '\n';
        lines[index].block = block;
        lines[index].dirty = (type == 1);
        location[block] = index;
        insert_to_front(group, index);
    }

    return 0;
}

复杂度

设缓存总容量 $C = nN$ 、指令数 $q$ 。

时间：哈希表操作期望 $O(1)$ ，每条指令只做常数次链表操作，总期望 $O(q)$ 。
空间：缓存行与哈希表 $O(C + q)$ 。

总结

缓存模拟的关键不是只判断命中，而是同时维护组映射、LRU 顺序和脏位。哈希表负责快速定位，双向链表负责 $O(1)$ 调整顺序；发生替换时严格按照“脏块写回、目标块读入”的顺序输出。

图示解析

这张流程图概括一条读写指令的处理路径：

text

1
2
3
4
5
6
7访问内存块 a
|- 哈希表命中
|  `- 按操作更新脏位并移动到 LRU 表头
`- 未命中
   |- 组未满：使用空槽位
   `- 组已满：检查 LRU 尾节点并写回脏块
      `- 输出读取 a，插入表头，写操作标记为脏

命中和未命中都必须更新 LRU 顺序。只有替换脏块才产生实际内存写，未命中的读入操作始终先产生实际内存读。

题目来自第 36 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛半导体制造厂近期正在研发一种新型的处理器产品。该处理器的缓存，计划采用组相连的方式。为了选定合适的组相连参数，我们需要对缓存的工作过程进行模拟，进而推算其性能。

处理器的缓存，存储着内存中的部分数据。当处理器的运行需要访问内存中的数据时，如果所需数据已经存储在缓存中，则可以用更为快捷的缓存访问代替内存访问，来提高处理器性能。

处理器的缓存包含若干缓存行，每个缓存行存储特定大小的数据。为了便于叙述，我们认为处理器对内存的访问，也是以缓存行为单位进行的。以缓存行的大小为单位，将全部内存空间划分为若干块（编号从 $0$ 开始），这样每个内存块的数据便可以恰好存储在一个缓存行中。

$n$ -路组相联是这样的一种缓存结构：每 $n$ 个缓存行划分为一组。假设共有 $N$ 个这样的组（编号从 $0$ 到 $N - 1$ ），那么编号为 $k$ 的内存块仅可以被存储在编号为 $(k \div n) \% N$ 的组这 $n$ 个缓存行的任意一个中。其中， $\div$ 表示忽略余数的整除运算， $\%$ 表示整除取余数运算。一般而言， $n$ 和 $N$ 是 $2$ 的幂次。例如，当 $n=4$ 、 $N=8$ 时，编号为 0、1、2、3、32、33、34、35 的内存块可以被存储在组 0 的任意缓存行中；编号为 4、5、6、7、36、37、38、39 的内存块可以被存储在组 1 的任意缓存行中。

题目描述

具体而言，给定要读取或写入的内存块编号，即可确定该内存块可能位于的缓存行组的编号。此时，可能存在的情况有两种：

该缓存行组的某个缓存行已经存储了该内存块的数据，即命中；
该缓存行组的所有缓存行都没有存储该内存块的数据，即未命中。

当发生命中时，处理器可以直接使用或修改该缓存行中的数据，而不需要实际读写内存。当发生未命中时，处理器需要从内存中读取数据，并将其存储到该缓存行组中的一个缓存行中，然后再使用或修改该缓存行中的数据。这个将内存中的数据读入到缓存的过程称为载入。

当执行载入操作时，如果该缓存行组中有尚未存储数据的缓存行，那么将数据存储到其中一个尚未存储数据的缓存行中，并在缓存行中记录所存储的数据块的编号；否则，按照一定方法，选择该组中的一个缓存行，并将数据存储到其中，这一过程称为替换。

当发生替换时，需要考虑被替换的缓存行是否发生过修改，即执行过写操作。如果发生过修改，则需要先将缓存行中的数据写入内存中的对应位置；然后忽略该缓存行中的数据、将新读入的数据存入其中，并记录所存储数据块的编号。

在一个缓存行组中选择被替换的缓存行的方法有很多种，该种处理器采用的是最近最少使用（LRU）方法。该方法将一个缓存行组中存有数据的缓存行排成一队，每次读或写一个缓存行时，都将该缓存行移动到队列的最前端。当需要替换缓存行时，选择队列的最后一个缓存行（最久没被读写）进行替换。

本题目中，将给出一系列的处理器运行时遇到的对内存的读写指令，并假定初始时处理器的缓存为空。你需要根据上文描述的缓存工作过程，给出处理器对内存的实际读写操作序列。

输入格式

从标准输入读入数据。

输入的第一行包含空格分隔的三个整数 $n, N, q$ ，分别表示组相联的路数 $n$ 和组数 $N$ ，以及要处理的读写指令的数量 $q$ 。

接下来 $q$ 行，每行包含空格分隔的两个整数 $o$ 和 $a$ 。其中， $o$ 表示读写指令的类型， $a$ 表示要读写的内存块的编号。 $o$ 为 $0$ 或 $1$ ，分别表示读和写操作。

输出格式

输出到标准输出。

输出若干行，每行包含空格分隔的两个整数 $o'$ 和 $a'$ ，表示实际处理器对内存的读写操作。 $o'$ 为 $0$ 或 $1$ ，分别表示读和写操作； $a'$ 表示要读写的内存块的编号。

input1

output1

样例 1 解释

该处理器的缓存为 4 路组相联，共有 8 组。初始时，处理器的缓存为空。共需要处理 8 条指令：

第 1 条指令为读取内存块 0，未命中，要实际读取内存块 0，并存储到组 0 的一个缓存行；
第 2 条指令为读取内存块 1，未命中，要实际读取内存块 1，并存储到组 0 的另一个缓存行；
第 3 条指令为写入内存块 2，未命中，要实际读取内存块 2，并存储到组 0 的第三个缓存行，然后根据指令在缓存中对其进行修改；
第 4 条指令为读取内存块 1，命中，直接从缓存中调取数据；
第 5 条指令为写入内存块 0，命中，直接修改缓存中的数据；
第 6 条指令为读取内存块 32，未命中，要实际读取内存块 32，并存储到组 0 的第四个缓存行；
第 7 条指令为写入内存块 33，未命中，此时组 0 中的 4 个缓存行都保存了数据：最近使用的是保存有内存块 32 的缓存行，其次是保存有内存块 0 的缓存行，然后是 1，最后是 2，因此选择替换保存有内存块 2 的缓存行。注意到该缓存行在执行第 3 条指令时被修改过，因此需要先将其写入内存，然后再读取内存块 33 的数据存储到该缓存行中；
第 8 条指令为读取内存块 34，未命中，此时组 0 中的 4 个缓存行都保存了数据，按照同样的办法，选择保存有内存块 1 的缓存行替换。注意到该缓存行未被修改过，因此可以直接读取内存块 34 的数据存储到该缓存行中。

子任务

对于 20% 的数据，有 $n = 1, N = 1$ ；

对于 40% 的数据，有 $n = 1$ ；

另外 20% 的数据，有 $N = 1, q \le n$ ；

对于 100% 的数据，有 $1 \le n, N, n \times N \le 65536$ ，且 $n, N$ 为 2 的幂次； $1 \le q \le 10^5$ ， $0 \le a < 2^{30}$ 。