Morgana is learning computer vision, and he likes cats, too. One day he wants to find the cat movement from a cat video. To do this, he extracts cat features in each frame. A cat feature is a two-dimension vector <x,?y>. If xi?= xj??and yi??=?yj?, then <xi?,?yi?> <xj?,yj?> are same features.

So if cat features are moving, we can think the cat is moving. If feature <aa,?bb> is appeared in continuous frames, it will form features movement. For example, feature <aa?,?bb?> is appeared in frame?2,3,4,7,8then it forms two features movement?2-3-4 and?7-8.

Now given the features in each frames, the number of features may be different, Morgana wants to find the longest features movement.

Input

First line contains one integer?T(1≤T≤10), giving the test cases.

Then the first line of each cases contains one integer?nn?(number of frames),

In The next?nn?lines, each line contains one integer ki??( the number of features) and 2ki ?intergers describe ki??features in ith frame.(The first two integers describe the first feature, the?33rd and?44th integer describe the second feature, and so on).

In each test case the sum number of features?N?will satisfyN≤100000?.

Output

For each cases, output one line with one integers represents the longest length of features movement.

樣例輸入復制

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

樣例輸出復制

3

題目來源

ACM-ICPC 2018 徐州賽區網絡預賽

【題目大意】有N個幀，每幀有K個動作特征，每個特征用一個向量表示（x,y）。兩個特征相同當且僅當他們在不同的幀中出現且向量的兩個分量分別相等。求最多連續相同特征的個數？

?

【題解】用一個map來維護幀中特征的信息，map中的鍵即讀入的向量，因此用一個pair<int , int>表示，鍵的值也是一個pair，需要記錄它當前已經連續了多少次，還需要記錄它上一次出現的幀的位置。如果它上一幀沒有出現過，那么它的連續次數就要被置成1；如果上次出現了，則繼續累加。用ans維護某個鍵最大連續出現次數。

map<pair<int ,int> , pair<int ,int>>

map[ pair（x,y）].first為該特征（x.y）連續次數??

map[ pair（x,y）].second為該特征上一次出現的幀序號，用于下一次判斷連續性

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}typedef pair<int,int> pii; map<pii,pii> mp; int main() {int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);int ans=-1;for(int i=1; i<=n; i++){int k;scanf("%d",&k);for(int j=1; j<=k; j++){int x,y;scanf("%d%d",&x,&y);if(mp[pii(x,y)].second==i-1)mp[ pii(x,y) ].first++;else if(mp[pii(x,y)].second==i)continue;else mp[ pii(x,y) ].first = 1;ans=max(ans,mp[pii(x,y)].first);mp[pii(x,y)].second=i;}}printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的ACM-ICPC 2018 徐州赛区网络预赛 Features Track（STL二维map）的全部內容，希望文章能夠幫你解決所遇到的問題。

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