SGU 552 Database optimization

题意：

n个物品  每个物品有最多4个属性  m次询问  每次询问最多问4个属性  输出包含这些属性的物品个数

思路：

如果一个物品的属性是 a b c d 那么它能对如下询问做贡献a、b、c、d、ab、ac、ad、bc、bd、cd、abc、abd、acd、bcd、abcd  那么只需要每个物品对它贡献的询问++即可  注意要保持abcd是有序排列的

然后就是做个map  把字符串hash成数  再把数的组合hash成方案  记录方案的数量

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<bitset>
using namespace std;
typedef unsigned long long LL;
#define seed 133331ULL

int n;
LL id;
map<string, LL> fzc;
map<LL, int> ans1;
map<LL, int> ans2;
map<LL, int> ans3;
map<LL, int> ans4;
LL a[5];
string str;

int main() {
	int i, j, k, f1, f2, f3, f4;
	id = 1;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> k;
		for (j = 0; j < k; j++) {
			cin >> str;
			if (fzc[str] == 0)
				fzc[str] = id++;
			a[j] = fzc[str];
		}
		if (k > 1)
			sort(a, a + k);
		for (f1 = 0; f1 < k; f1++) {
			ans1[a[f1]]++;
			if (k >= 2) {
				for (f2 = f1 + 1; f2 < k; f2++) {
					ans2[a[f1] * seed + a[f2]]++;
					if (k >= 3) {
						for (f3 = f2 + 1; f3 < k; f3++) {
							ans3[(a[f1] * seed + a[f2]) * seed + a[f3]]++;
							if (k >= 4) {
								for (f4 = f3 + 1; f4 < k; f4++)
									ans4[((a[f1] * seed + a[f2]) * seed + a[f3])
											* seed + a[f4]]++;
							}
						}
					}
				}
			}
		}
	}
	cin >> n;
	while (n--) {
		cin >> k;
		for (j = 0; j < k; j++) {
			cin >> str;
			if (!fzc.count(str))
				a[j] = 0;
			else
				a[j] = fzc[str];
		}
		//for (j = 0; j < k; j++)
		//	printf("%llu ", a[j]);
		//cout << ((a[0] * seed + a[1]) * seed + a[2]) * seed + a[3] << endl;
		//printf("\n");
		if (k > 1)
			sort(a, a + k);
		if (a[0] == 0) {
			cout << 0 << endl;
			continue;
		}
		if (k == 1)
			cout << ans1[a[0]] << endl;
		else if (k == 2)
			cout << ans2[a[0] * seed + a[1]] << endl;
		else if (k == 3)
			cout << ans3[(a[0] * seed + a[1]) * seed + a[2]] << endl;
		else
			cout << ans4[((a[0] * seed + a[1]) * seed + a[2]) * seed + a[3]]
					<< endl;
	}
	//cout << (*ans4.begin()).first << " " << (*ans4.begin()).second << endl;
	return 0;
}