2015廣工新生賽 Problem A: GG和女神

Problem A: GG和女神

Description

大家都知道，GG不僅長得帥，而且還長得帥，是以就連女神都喜歡他，這不，GG正打算跟女神出國旅遊。女神覺得一定要選最好的衣服跟GG出去，給他留個好印象。是以女神打算在新買的n件衣服裡面選k件帶出國，是以她打算問她的好朋友xdlove，但是xdlove暫時沒空回她，是以女神就自己選好了k件，把衣服标号寫在了一個筆記本上。等xdlove閑下來找女神的時候，發現女神不在家裡，隻看到一堆衣服，有強迫症的他就把衣服按照價格從低到高排了序。這時剛吃完飯的女神就來了，看到被xdlove弄亂了的衣服，當然不高興了，于是xdlove就跟她說，雖然我弄亂了，但我全都記得，然後跟女神說了k個編号之後說這就是你剛才選的k件（當然是假的）。GG知道了這件事之後，打算拆穿xdlove，畢竟他不容忍别人欺騙他的女神。于是他搜集了女神一開始的衣服價格序列，女神寫了編号的筆記本，以及xdlove随口說的k個編号，現在他想知道xdlove說的K件衣服裡面有多少件是女神挑好的，如果你能幫GG解決這個問題，那麼他将會送你一個獨家氣球。

Input

第一行輸入樣例個數T（T<=20）。

每個樣例格式如下

第一行兩個數字n（1<=n<=1e6）和k（1<=k<=n），n,k如題目所述。

第二行是n件衣服價格vi，保證每個vi都不相同（vi<=1e17）

第三行，k個數字A1-An，代表女神筆記本上的k個編号。

第四行，k個數字B1-Bn，代表xdlove随口說的k個編号。

Output

每一個樣例輸出一個答案，換行

Sample Input

1

2 1

4 3

1

2

Sample Output

1

題解

表示一開始連題目都讀不懂….

意思就是給你n個數，其中選了k個出來，可是後來被經過排序後，再告訴你k（下标）個數，問這k個中有多少個是原來選過的，資料量很大，如果普通的做法必然逾時到死，那麼自然想起了位運算…

輸入n個數後把它們全部左移一位，原來的大小關系是不會改變的，然後選了的在末尾标志1，然後&1就知道是不是原來選過的了

代碼

#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
using namespace std;
const int  MAX = +;
#define LL long long
int cas=,T;

LL cloth[MAX];
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for (int i = ;i<=n;i++)
        {
            scanf("%lld",&cloth[i]);
            cloth[i]<<=;
        }

        for (int i = ;i<=k;i++)
        {
            int temp;
            scanf("%d",&temp);
            cloth[temp]|= ;
        }

        sort(cloth+,cloth+n+);
        int ans = ;
        for (int i = ;i<=k;i++)
        {
            int temp;
            scanf("%d",&temp);
            /*if (cloth[temp]&1) //多加個判斷也會逾時..
                ans+=1;*/
            ans+=(cloth[temp]&);
        }
        printf("%d\n",ans);
        memset(cloth,,sizeof(cloth));
    }
    //freopen("in","r",stdin);
    //scanf("%d",&T);
    //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
    return ;
}