Gym - 100203A Ariel 暴力+位运算

题意：第i种生物有k[i]个特征，分数是score[i]，现在要参加竞赛，报出一种生物a，和一些特征h[i]，参加竞赛的所有生物在这些h[i]上面的特征是一样的，a生物有h[i]，则所有竞赛的生物都必须有h[i]，a生物没有，竞赛的生物也没有，没有提到的则不用管。问你在竞赛中a的排名

思路：特征最多只有10中，所有可以用二进制的每一位表示特征的状态，并记录下每种状态下的生物的类型。现在给你生物的状态，首先要求出能参加竞赛的生物的种类。当 (i&p == t[a]&p) 时，所有拥有i状态的生物就是可以参加竞赛的。再用二分找到在这些类型中a的位置，加起来便是排名了

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define eps 1e-8

 #define INF 0x3f3f3f3f

 #define MAXN 10005

 using namespace std;

 int G[][MAXN];

 int s[MAXN], t[MAXN];

 vector<int> f[];

 int main()

 {

 #ifndef ONLINE_JUDGE

     freopen("in.txt", "r", stdin);

     //freopen("out.txt", "w", stdout);

 #endif // OPEN_FILE

     int n, k, m;

     scanf("%d%d", &n, &k);

     int x, y, p;

     for(int i = ; i < ; i++){

         G[i][] = ;

     }

     for(int i = ; i <= n; i++){

         scanf("%d%d", &s[i], &y);

         p = ;

         for(int j = ; j <= y; j++){

             scanf("%d", &x);

             p |=  << (x - );

         }

         f[p].push_back(s[i]);

         t[i] = p;

         G[p][]++;

         G[p][G[p][]] = s[i];

     }

     for(int i = ; i <= ; i++){

         sort(G[p], G[p] + G[p][]);

         sort(f[i].begin(), f[i].end());

     }

     scanf("%d", &m);

     int q;

     int ans;

     for(int i = ; i <= m; i++){

         scanf("%d%d", &x, &y);

         p = ;

         for(int j = ; j <= y; j++){

             scanf("%d", &q);

             p |=  << (q - );

         }

         ans = ;

         for(int i = ; i <= ; i++){

             if((i & p) != (t[x] & p))continue;

             ans += f[i].size() - (upper_bound(f[i].begin(), f[i].end(), s[x]) - f[i].begin());

             continue;

             int left = , right = G[i][];

             while(left < right){

                 int mid = (left + right) >> ;

                 if(G[i][mid] > s[x]){

                     right = mid;

                 }

                 else{

                     left = mid + ;

                 }

             }

             if(G[i][left] == s[x]) continue;

             //ans += left - 1;

             //continue;

             if(G[i][left] > s[x]){

                 ans += left;

             }

             else if(G[i][left] < s[x]){

                 ans += left - ;

             }

             //ans += left;

             //if(G[i][left] == s[x])

             //ans += left -1;

         }

         printf("%d\n", ans);

     }

 }