首页 > 代码库 > [数据结构暴力] zoj 3749 Chameleon
[数据结构暴力] zoj 3749 Chameleon
题目链接:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3749
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 (i, j). For each query, you must perform below operations:
- List the i-th group and the j-th group in a line. These integers form an array ci.
- Sort ci in ascending order.
- 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 (i, j)(1 ≤ i, j ≤ 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
题目意思:
给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; }