首页 > 代码库 > [数据结构暴力] zoj 3749 Chameleon

[数据结构暴力] zoj 3749 Chameleon

题目链接:

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3749

Chameleon

Time Limit: 6 Seconds      Memory Limit: 65536 KB

Given n groups of integers(all the integers are distinct). You should answer Q queries in this problem.

Each query contains a pair of integers (ij). For each query, you must perform below operations:

  1. List the i-th group and the j-th group in a line. These integers form an array ci.
  2. Sort ci in ascending order.
  3. Answer this question: how many i satisfy that GroupIDi-1  GroupIDi after sorting. Here GroupIDi equals to the group id which ci belongs to. That means the value of GroupIDmust be either i or j in this query.

Input

The input file contains multiple test cases.

Each case begin with an integer n which indicate the amount of group. The following n lines each describe a group of integers. The format of these lines is:

mi ai1 ai2 ai3 ... aimi (1 ≤ i ≤ n, 1 ≤ aij ≤ 109)

We guarantee that m1 + m2 + m3 + ... + mn ≤ 105

There is a number Q(1 ≤ Q ≤ 105) after these groups of integers. This number is followed by Q lines, each contains two numbers (ij)(1 ≤ ij ≤ n and i ≠ j) which describe a query.

Process to the End Of File.

Output

Output an integer in a line for each query.

Sample Input

2
3 1 5 8
3 2 6 7
1
1 2

Sample Output

4

Hint

In the sample, we get c = {1, 5, 8, 2, 6, 7}, GruopID = {1, 1, 1, 2, 2, 2}.

After sorting, it becomes c = {1, 2, 5, 6, 7, 8}, GruopID = {1, 2, 1, 2, 2, 1}.


Author: CHEN, Weijie
Source: ZOJ Monthly, January 2014
Submit    Status

题目意思:

给n个集合,每个集合有mi个元素,每个集合内的元素不一样,且集合间也不存在相同的元素。有q个查询,每次查询集合i和集合j合并排序后,有多少个相邻的元素在不同的原始集合里。

解题思路:

数据结构暴力。

对每个集合排序,对于查询的集合i和集合j,枚举个数少的集合元素,二分查找它在另外个集合里的位置,与前一个元素的位置比较,看是否增加统计个数。

代码:

//#include<CSpreadSheet.h>

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#include<cmath>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 110000

vector<int>myv[Maxn];
int n,q,num[Maxn];


int main()
{
   //freopen("in.txt","r",stdin);
   //freopen("out.txt","w",stdout);
   while(~scanf("%d",&n))
   {
       for(int i=1;i<=n;i++)
       {
           myv[i].clear();
           scanf("%d",&num[i]);
           for(int j=1;j<=num[i];j++)
           {
               int a;
               scanf("%d",&a);
               myv[i].push_back(a);
           }
           sort(myv[i].begin(),myv[i].end()); //对每个集合排序
       }
       scanf("%d",&q);
       while(q--)
       {
           int l,r;

           scanf("%d%d",&l,&r);
           if(num[l]>num[r])
                swap(l,r);

           vector<int>::iterator it=myv[l].begin();

           int pre=0,ans=0;
           //bool flag=true;

           for(;it!=myv[l].end();it++) //扫描短的集合
           {
                int now=lower_bound(myv[r].begin(),myv[r].end(),*it)-myv[r].begin();

                if(now!=pre) //如果和前一个元素所在位置不一样,
                {
                    if(it==myv[l].begin()) //flag=false; //第一个元素的话加一个
                        ans++;
                    else  //否则加两个
                        ans+=2;
                }
                //printf("it:%d now:%d pre:%d %d\n",*it,now,pre,ans);
                pre=now;
           }
           it--; //最后一个元素 是否有后增
           if(lower_bound(myv[r].begin(),myv[r].end(),*it)-myv[r].begin()!=num[r])
                ans++;
           //if(lower_bound(myv[r].begin(),myv[r].end(),*it)-myv[r].begin())
           printf("%d\n",ans);
       }

   }
   return 0;
}