在編程競賽和高效數據處理場景中，時間戳技巧是一種極其高效的標記方法，常用于避免頻繁清空數組或 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樹中處理多組關鍵詞判重；
• 模擬題中清空操作頻繁的場景。

---

八、總結

時間戳技巧是一種在競賽中非常實用的優化手段，尤其適用于：

• 大規模判重
• 頻繁使用多個數據組
• 替代耗時的數組清空操作

---