題意

小明是一名算法工程師，同時也是一名鏟屎官。某天，他突發奇想，想從貓咪的視頻里挖掘一些貓咪的運動信息。為了提取運動信息，他需要從視頻的每一幀提取“貓咪特征”。一個貓咪特征是一個兩維的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么這倆是同一個特征。

因此，如果喵咪特征連續一致，可以認為喵咪在運動。也就是說，如果特征<a, b>在持續幀里出現，那么它將構成特征運動。比如，特征<a, b>在第2/3/4/7/8幀出現，那么該特征將形成兩個特征運動2-3-4 和7-8。

現在，給定每一幀的特征，特征的數量可能不一樣。小明期望能找到最長的特征運動。

輸入描述:

第一行包含一個正整數N，代表測試用例的個數。

每個測試用例的第一行包含一個正整數M，代表視頻的幀數。

接下來的M行，每行代表一幀。其中，第一個數字是該幀的特征個數，接下來的數字是在特征的取值；比如樣例輸入第三行里，2代表該幀有兩個貓咪特征，<1，1>和<2，2>
所有用例的輸入特征總數和<100000

N滿足1≤N≤100000，M滿足1≤M≤10000，一幀的特征個數滿足 ≤ 10000。
特征取值均為非負整數。

輸出描述:

對每一個測試用例，輸出特征運動的長度作為一行
輸入例子1:

1
8
2 1 1 2 2
2 1 1 1 4
2 1 1 2 2
2 2 2 1 4
0
0
1 1 1
1 1 1

輸出例子1:

3
例子說明1:

特征<1,1>在連續的幀中連續出現3次，相比其他特征連續出現的次數大，所以輸出3

題解

題目的題意還是比較清楚的，即找出最長連續出現的特征數量。

首先，對于題目當中的特征是用兩個int的pair對代表的，相同的pair被視為是同樣的特征。特征必須要連續出現才算，中間中斷則重新計算。

比較容易想到，我們可以使用map來存儲所有的特征以及它當前出現的最多次數。這樣我們雖然搞定了存儲問題，但還需要解決另外兩個問題。第一個問題是兩個int構成的特征如何作為map的key，第二個問題是，有一些pair在之前的幀中出現過，但是中途中斷了，我們如何快速清除？

使用pair

這兩個問題我們一個一個來看，先看第一個問題。這個問題很好解決，在C++當中有一個數據結構叫做Pair，它是兩個不同類型變量打包成的簡單結構體，它可以作為map的key。

具體的用法非常簡單，我們用pair<int, int>來聲明兩個int組成的特征，這里的類型可以根據自己的需要進行修改。當我們需要在map當中使用的時候， 我們采用同樣的方式來聲明map即可。比如可以寫成這樣：map<pair<int, int>, int>，由于這樣書寫比較麻煩，一般acmer會使用define宏定義將它進行簡化。比如pair<int, int>通常會簡化成pii，表示兩個int的pair。

這樣的話，我們聲明和使用pair就會簡單得多。

#define pii pair<int, int>

map<pii, int> mp;
pii p = pii(x, y);
臨時map

第二個問題稍稍麻煩一些， 對于一些之前出現的pair，我們需要實時清除。但是我們的map當中只會存儲特征連續出現的次數，并沒有辦法判斷每一個特征有沒有中斷過。

對于這個問題，我們有一個很好的辦法，就是使用兩個map。第一個map存儲的是歷史上一直連續出現至今的特征，我們叫它老map。第二個map是臨時map，用來儲存當前幀加入之后依然持續出現的特征。這樣我們只需要在當前幀處理結束之后，用臨時的map去更新老map，這樣就完成了map中內容的更新。

我這么說可能有一點抽象，大家可以參考一下代碼以及注釋，會好理解一些。這個技巧也是比賽當中非常常用的技巧，這樣通過兩個map的來回迭代，就省去了對key的清理工作，這樣節省了大量時間。

源碼

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <vector> #include <cmath> #include <cstdlib> #include <string> #include <map> #include <set> #include <algorithm> #include "time.h" #include <functional> #define rep(i,a,b) for (int i=a;i<b;i++) #define Rep(i,a,b) for (int i=a;i>=b;i--) #define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++) #define mid ((l+r)>>1) #define lson (k<<1) #define rson (k<<1|1) #define MEM(a,x) memset(a,x,sizeof a) #define L ch[r][0] #define R ch[r][1] #define pii pair<int, int> using namespace std; const int N=1000050; const long long Mod=1000000007; int x, y;int main() {int t;scanf("%d", &t);rep(z, 0, t) {int m;scanf("%d", &m);map<pii, int> mp, cur;int ret = 1;int k;// 讀入m幀rep(i, 0, m) {// 臨時map記得清空cur.clear();scanf("%d", &k);// 讀入k個特征rep(j, 0, k) {scanf("%d %d", &x, &y);pii p = pii(x, y);// 如果在老map中出現過，則更新臨時mapif (mp.count(p)) {cur[p] = mp[p] + 1;ret = max(ret, cur[p]);}else {cur[p] = 1;}}// 臨時map代替老mapmp = cur;}printf("%d\n", ret);}return 0; }

從代碼來看，這道題其實是不難的，也沒用到什么高深的算法和數據結構。但是對于新手來說還是很有挑戰的，主要是pair的應用很多人不熟悉，然后對于臨時map這樣的技巧可能也不一定能想得到。更何況這個還是筆試題，真正能在筆試的時候能寫上來的就更加困難了，很需要代碼能力。

建議大家最好能自己親手寫一下遇到問題之后再看標程，這樣的提升最明顯。

總結

以上是生活随笔為你收集整理的牛客网-数据结构笔试题目（一）-猫咪特征提取思路解析（附源码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。