计蒜客 ACM-ICPC 2018 徐州赛区网络预赛 F. Features Track(unordered_map+模拟)

Description:

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$x, $y$y>. If $x_i$xi​ = $x_j$xj​ and $y_i$yi​ = $y_j$yj​, then < $x_i$xi​, $y_i$yi​> < $x_j$xj​, $y_j$yj​> are same features.

So if cat features are moving, we can think the cat is moving. If feature < $a$a, $b$b> is appeared in continuous frames, it will form features movement. For example, feature < $a$a , $b$b > is appeared in frame $2,3,4,7,8$2,3,4,7,8, then it forms two features movement $2-3-4$2−3−4 and $7-8$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\le T\le 10)$T(1≤T≤10) , giving the test cases.

Then the first line of each cases contains one integer $n$n (number of frames),

In The next $n$n lines, each line contains one integer $k_i$ki​ ( the number of features) and $2k_i$2ki​ intergers describe $k_i$ki​ features in ith frame.(The first two integers describe the first feature, the $3$3rd and $4$4th integer describe the second feature, and so on).

In each test case the sum number of features $N$N will satisfy $N\le 100000$N≤100000 .

Output:

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

Sample Input:

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

Sample Output:

3

题目链接

每一帧有k个动作，每个动作有两个属性，当且仅当两个属性都相同时动作相同，求动作最大连续帧数。

使用两个unordered_map(不需要有序)，key为动作，value为连续帧数，两个map循环更新每一帧所有动作的连续帧数，维护最大值。

AC代码:

#include <bits/stdc++.h>
using namespace std;

struct Vector {
    long long X, Y;
    bool operator == (const Vector &A) const {
        return A.X == X && A.Y == Y;
    }
};

struct Hash {
    size_t operator() (const Vector &A) const {
        return hash<long long>()(A.X) + hash<long long>()(A.Y);
    }
};

unordered_map<Vector, long long, Hash> mp[3];

int main(int argc, char *argv[]) {
    int T;
    scanf("%d", &T);
    for (int Case = 1, N; Case <= T; ++Case) {
        scanf("%d", &N);
        long long Ans = -1;
        for (long long i = 0, K; i < N; ++i) {
            scanf("%lld", &K);
            if (i == 0) {
                mp[1].clear();
                for (long long j = 0, X, Y; j < K; ++j) {
                    scanf("%lld%lld", &X, &Y);
                    mp[1].emplace(Vector{X, Y}, 1);
                }
                Ans = 1;
            }
            else if (i & 1) {
                mp[2].clear();
                for (long long j = 0, X, Y; j < K; ++j) {
                    scanf("%lld%lld", &X, &Y);
                    if (mp[1].find(Vector{X, Y}) != mp[1].end()) {
                        long long Temp = mp[1][Vector{X, Y}] + 1;
                        mp[2].emplace(Vector{X, Y}, Temp);
                        Ans = max(Ans, Temp);
                    }
                    else {
                        mp[2].emplace(Vector{X, Y}, 1);
                    }
                }
            }
            else {
                mp[1].clear();
                for (long long j = 0, X, Y; j < K; ++j) {
                    scanf("%lld%lld", &X, &Y);
                    if (mp[2].find(Vector{X, Y}) != mp[2].end()) {
                        long long Temp = mp[2][Vector{X, Y}] + 1;
                        mp[1].emplace(Vector{X, Y}, Temp);
                        Ans = max(Ans, Temp);
                    }
                    else {
                        mp[1].emplace(Vector{X, Y}, 1);
                    }
                }
            }
        }
        printf("%lld\n", Ans);
    }
    return 0;
}