首页 > itarticle > acm

acm

admin 1月 23, 2021 0

Features Track

题面：

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 $x_i$ =$ x_j$ and $y_i$ =$ y_j$, then <$x_i$, $y_i$> <$x_j$, $y_j$> are same features.

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

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

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

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

output:

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

题解：

1 2	求同一特征出现在连续frame中最大次数，multimap用一下，set去重一下，简单模拟一下就行下边是AC代码


using namespace std;
#define Max 100005
typedef pair<int,int> P;
multimap<P,int>mp;
set<P>st;
int T;
int n,k;
int a,b;
multimap<P,int>::iterator beg,End,Beg,m;
int (void)
{
    scanf("%d",&T);
    while(T--)
    {
        mp.clear();
        st.clear();
        int ans=1;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&k);
            for(int j=0;j<k;j++)
            {
                scanf("%d%d",&a,&b);
                mp.insert(make_pair(P(a,b),i));
                st.insert(P(a,b));
            }
        }
        set<P>::iterator it=st.begin();
        for(;it!=st.end();it++)
        {
            beg = mp.equal_range(*it).first;
            End = mp.equal_range(*it).second;
            int temp=(*beg).second;
            beg++;
            int sum=1;
            for(m = beg; m != End; m++)
            {
                if((*m).second-temp==0)
                {
                    temp=(*m).second;
                }
                else if((*m).second-temp==1)
                {
                    sum++;
                    temp=(*m).second;
                    ans=max(ans,sum);
                }
                else
                {
                    ans=max(ans,sum);
                    sum=1;
                    temp=(*m).second;
                }
            }
        }
       printf("%dn",ans);
    }
    return 0;
}