题目描述
在Google,我们很乐意彼此传授新技能!
Google有 N 名员工,编号从 1 到 N。
共有 S 种不同的技能,编号从 1 到 S。
每个员工最多掌握 5 种不同的技能。
如果第 i 名员工掌握第 j 名员工不会的技能,则第 i 名员工可以指导第 j 名员工。
请问共有多少个数对 (i,j) 满足第 i 名员工可以教导第 j 名员工?
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 N 和 S。
接下来 N 行,每行包含若干个整数,用来描述每个员工掌握的技能。在第 i 行中,首先包含一个整数 Ci 表示第 i 名员工掌握的技能的数量,接下来包含 Ci 个整数,其中的第 j 个整数 Aij 表示第 i 名员工掌握的第 j 个技能的编号。数据保证同一名员工掌握的Ci个技能编号各不相同。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为“Case #x: y”,其中x是组别编号(从1开始),y为满足条件的数对数量。
数据范围
1≤T≤100,
1≤S≤1000,
1≤Ci≤5,
1≤Aij≤S,
2≤N≤500
考虑时限原因,本题N的取值范围按小数据执行。
样例
2
4 100
4 80 90 100 5
1 90
1 80
3 80 90 100
3 30
4 10 11 12 13
4 10 11 12 13
5 25 26 27 28 29
算法1
(Hash) $O(2^5 * N)$
1.考虑到只有5个数,且范围为1到1000, 将每个数的值减一,可以用1000进行hash
比如 20 39 40 可以写为 20 * 1000 +39 * 1000000 + 40 * 1000000000
考虑到后面枚举子集,需要先对每个人的技能数组进行排序
2.对于每个人,考虑其他人能够教他的不好操作,反过来思考,统计每个人能教的,然后减去就可以了.对于每个人的
技能数组,最多只有5个,枚举该数组的非空子集,然后hash该子集,再统计总和,最后减去即可
C++ 代码
//代码可以通过kickstart大数据
#include<bits/stdc++.h>
using namespace std;
const int maxn = 50005;
int T, S, C, N, A;
vector< int > v[ maxn ];
map< long long, int > Index;
int main()
{
cin >> T;
for( int Case = 1; Case <= T; Case ++ )
{
Index.clear();
cin >> N >> S;
for( int i = 1; i <= N; i ++ )
{
v[ i ].clear();
cin >> C;
long long sum = 0;
for( int j = 1; j <= C; j ++ )
{
cin >> A;
A --;
v[ i ].push_back( A );
}
sort( v[ i ].begin(), v[ i ].end() );
long long tmp = 1;
for( auto x: v[ i ] )
{
sum += ( x * tmp );
tmp *= 1000;
}
Index[ sum ] ++;
}
long long goal = 0;
for( int i = 1; i <= N; i ++ )
{
C = v[ i ].size();
long long same = 0;
for( int j = 1; j < ( 1 << C ); j ++ )
{
long long sum = 0;
long long tmp = 1;
long long cnt = 0;
int jj = j;
while( jj )
{
if( jj & 1 )
{
sum = sum + v[ i ][ cnt ] * tmp;
tmp *= 1000;
}
jj >>= 1;
cnt ++;
}
same += Index[ sum ];
}
goal += ( N - same );
}
cout << "Case #" << Case << ": " << goal << endl;
}
return 0;
}