2016年3月12日 星期六

[CodeChef XORSACK]Hououin Kyouma and Xorsack

English version

這題目不好找,附上題目連結

說明:
$bit_{i}$為某數字或某數字集合$\oplus$起來的數字,它的第$i$個$bit$ ($\oplus$為$XOR$的符號)
$X_{i}$為數字$X$的$bit_{i}$

我們可以嘗試一個$bit$一個$bit$慢慢維護符合目前條件的數字集合們

可是數字集合的數量實在太多了 ($2^N$),該怎麼辦呢?
沒關係,我們先存下這$N$個數字 (稱$s$,$s$代表了這$2^N$種數字集合),這樣至少以後會知道枚舉$s$裡面每個數字的選或不選就可以得到每一種數字集合

第一步就是維護出所有會讓$bit_{1}=K_{1}$的數字集合

假設$K_{1}=0$
我們知道,$s$中$bit_{1}=0$的那些數字選或不選都沒有影響
重點是要怎麼挑出那些包含偶數個$bit_{1}=1$的數字的集合 (因為這樣它們的$bit_{1}$才會$=0$)
考慮$s$中$bit_{1}=1$的數字為$v_{1},v_{2},v_{3},...,v_{n}$
可以證明,$s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$恰可以代表所有選擇偶數個$bit_{1}=1$的數字的集合!(想一想,為甚麼XD)

因此,我們只要將$s$取代成$\{{原本s裡面bit_{1}=0的數字},s'\}$,就可以繼續維護$(bit_{i}=K_{i},\forall 1\leq i\leq 2)$、$(bit_{i}=K_{i},\forall 1\leq i\leq 3)$...的數字集合!

如果$K_{1}=1$呢?
我們知道,$s$中$bit_{1}=0$的那些數字選或不選都沒有影響
重點是要怎麼挑出那些包含奇數個$bit_{1}=1$的數字的集合 (因為這樣它們的$bit_{1}$才會$=1$)
考慮$s$中$bit_{1}=1$的數字為$v_{1},v_{2},v_{3},...,v_{n}$
剛剛我們知道了,$s'=\{v_{1}\oplus v_{2},v_{2}\oplus v_{3},v_{3}\oplus v_{4},...,v_{n-1}\oplus v_{n}\}$恰可以代表所有選擇偶數個$bit_{1}=1$的數字的集合
那麼,把所有沒選到$v_{1}$的集合改成有選到$v_{1}$,選到$v_{1}$的集合改成沒選到$v_{1}$就好了!

因此,我們只要將$s$取代成$\{\{原本s裡面bit_{1}=0的數字\},修改v_{1}選擇狀態後的s'\}$,就可以繼續維護$(bit_{i}=K_{i},\forall 1\leq i\leq 2)$、$(bit_{i}=K_{i},\forall 1\leq i\leq 3)$...的數字集合!

問題來了,要怎麼修改$s'$中所有集合的$v_{1}$選擇狀態?
我們知道,同一個數字選兩次等於沒選
因此,我們就強迫多選一個數字$v_{1}$,實作上將$K\oplus v_{1}$就好了!(不過我是另外用一個變數$now$來儲存$K$的變化)

當發現需要$v_{1}$它卻不存在時,答案為$No$
否則如果算到最後一個$bit$仍然還沒出錯 (代表還是存在符合條件的數字選擇方案),答案為$Yes$

時間複雜度:$O(31N)$ (枚舉了$31$個$bit$)

code:
#include<cstdio>
#include<cassert>
#include<vector>
using namespace std;
bool Solve(vector<int>s,const int K)
{
    int now=0;
    for(int bit=30;bit>=0;bit--)
    {
        static vector<int>tmp[2];
        for(const int v:s)tmp[(v&(1<<bit))>>bit].push_back(v);
        s.swap(tmp[0]);
        if((now^K)&(1<<bit))
        {
            if(tmp[1].empty())return false;
            now^=tmp[1][0];
        }
        for(int i=1;i<(int)tmp[1].size();i++)s.push_back(tmp[1][i-1]^tmp[1][i]);
        for(int d=0;d<2;d++)vector<int>().swap(tmp[d]);
    }
    return true;
}
int main()
{
//    freopen("in.txt","r",stdin);
    int N,K;
    scanf("%d%d",&N,&K);
    vector<int>s;
    for(int i=0,v;i<N;i++)scanf("%d",&v),s.push_back(v);
    puts(Solve(s,K)?"Yes":"No");
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原