C - 秋實大哥與快餐店

Time Limit: 3000/1000MS (Java/Others) ??? Memory Limit: 65535/65535KB (Java/Others)

Submit?Status

朝為田舍郎，暮登天子堂。秋實大哥從小就懷抱有遠大的理想，所以他開了一家快餐店。

秋實大哥根據菜的口感，給每一道菜一個唯一的CID，同時對于前來的客人，根據他們的口味喜好，秋實大哥會給每一個客人一個PID。

對于一個標號為PID的客人，他對標號為CID的菜的喜愛程度為PID∧CID(∧表示按位異或），該值越大表示越喜歡。

秋實大哥實在太忙了，現在他需要你來幫忙照看一下他的店鋪。

Input

第一行包含一個整數n，表示秋實大哥的餐館內現在有n道菜。

接下來一行包含n個整數，分別表示每一道菜的CID。

接下來一行包含一個整數m，表示接下來發生了m件事。

接下來的m行，每一行為以下兩種事件之一：

0 c : 表示秋實大哥最新研制出一道標號為c的菜 1 p : 表示來了一位標號為p的客人，請你在已有的菜中找出一道他最喜愛的菜

1≤n，m≤100000，0≤PID，CID≤1000000。

Output

對于每一個1?p事件輸出一個整數，表示該客人最喜歡的菜的標號。

Sample input and output

Sample InputSample Output

1 1 3 1 1 0 2 1 1	1 2

?

解題報告

首先注意到異或的特性是相同為0，不同為1。其次注意到二進制數的特點為最高位優勢，即對于任何一個二進制數，一旦其某個高位為1，那么自該高位之后的所有位皆為1也無法比其大.

因此我們采用字典樹來保存每個數的每位二進制數，離根近的為高位，查詢的時候采用貪心走法即可.

?

#include <iostream> #include <cstring> using namespace std;/* log2 1e6 向上取整為20,即樹的高度小于等于21,使用滿二叉樹來進行存儲，2^22 */ const int maxbit = 20;typedef struct data {char l,r; int id; };data tree[(1<<22) + 50],n;void insert(int x) {int ptr = 1,cur = 0;while(cur < maxbit){if (x >> (maxbit-cur-1) & 1){tree[ptr].r = 1;ptr = ptr*2+1;}else{tree[ptr].l = 1;ptr <<= 1;}cur++;}ptr <<= 1;tree[ptr].id = x; }int find(int x) {int ptr = 1 , cur = 0 , tar = ~x;while(cur < maxbit){if ( (tar >> (maxbit-cur-1) ) & 1){if (tree[ptr].r)ptr = ptr*2+1;elseptr <<= 1; }else {if (tree[ptr].l)ptr <<= 1;elseptr = ptr*2+1;}cur++;}ptr <<= 1;return tree[ptr].id; }int main(int argc,char *argv[]) {int n,m;memset(tree,0,sizeof(tree));scanf("%d",&n);for(int i = 0 ; i < n ; ++ i){int temp;scanf("%d",&temp);insert(temp);}scanf("%d",&m);while(m--){int i,j;scanf("%d%d",&i,&j);if (i & 1)printf("%d\n",find(j));elseinsert(j);}return 0; }

?

轉載于:https://www.cnblogs.com/Xiper/p/4470206.html

總結

以上是生活随笔為你收集整理的UESTC_秋实大哥与快餐店 2015 UESTC Training for Data StructuresProblem C的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。