在编程竞赛和高效数据处理场景中，时间戳技巧是一种极其高效的标记方法，常用于避免频繁清空数组或 map，提高算法运行效率。本文将从定义、应用场景、模板代码、技巧细节等方面系统整理时间戳的使用方式。

---

一、时间戳技巧是什么？

时间戳技巧的本质：

用一个全局变量 timer 表示“当前时间戳”，数组 vis[x] 存储每个元素 x 的“上一次访问的时间戳”。通过比较 vis[x] == timer 来判断该元素是否已经被访问，无需每次清空整个数组。

---

二、为什么需要时间戳技巧？

清空数组或 map 可能非常耗时，尤其是在以下场景中：

• 需要多次处理不同的数据组（如多组测试数据）；
• 访问标记数组下标空间较大（如 $10^6$）；
• 频繁使用 memset(vis, 0, sizeof vis) 等清空操作性能瓶颈。

通过时间戳技巧，避免每次清空数组或 map，只需递增一次全局时间戳变量 timer，达到同样的效果，且时间复杂度为 $O(1)$。

---

三、典型应用场景

1. 多组数据判断访问状态（替代清空）
2. 图论中的 BFS / DFS 判重
3. Trie 树判重、离线查询
4. 模拟题中记录状态是否访问
5. 哈希计数问题中清空频繁的 unordered_map

---

四、模板代码讲解

模板 1：数组版本

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;int vis[N];    // 记录每个点上一次被访问的“时间”
int timer = 0; // 当前的时间戳void solve() 
{timer++;   // 每次处理新数据前只需 +1int n;cin >> n;for (int i = 0; i < n; i++) {int x;cin >> x;// 判断当前 x 是否在“本轮”被访问过if (vis[x] == timer) {cout << x << " 重复\n";} else {vis[x] = timer; // 标记为“本轮”访问}}
}

模板 2：map/unordered_map + 时间戳

#include <bits/stdc++.h>
using namespace std;unordered_map<string, int> mp;
int timer = 0;void solve() 
{timer++; // 新一轮处理int n;cin >> n;for (int i = 0; i < n; i++) {string name;cin >> name;if (mp[name] == timer) {cout << name << " 重复\n";} else {mp[name] = timer;}}
}

---

五、技巧总结

操作	时间戳技巧优化点
判重数组	不需要清空 vis[]
判重 map	用 map<string, int> 记录时间戳
多组数据	只需 ++timer 替代 memset 或 clear()
空间大数据	时间戳替代清空，性能提升明显

---

六、注意事项

• 时间戳不能回退，防止混淆。
• vis[] 或 map 初始值默认为 0，因此第一轮 timer = 1。
• timer 是 全局变量，防止误覆盖。
• 时间戳上限：如最多有 $10^5$ 次操作，timer 开 int 足够。

---

七、常见题目举例

• 牛客网、洛谷比赛中多组数据重复判断；
• BFS 中防止重复访问节点；
• Trie树中处理多组关键词判重；
• 模拟题中清空操作频繁的场景。

---

八、总结

时间戳技巧是一种在竞赛中非常实用的优化手段，尤其适用于：

• 大规模判重
• 频繁使用多个数据组
• 替代耗时的数组清空操作

---