題目鏈接：點擊查看

題目大意：給出一個均勻分布，長度為 n 的數(shù)列，再給出 m 次詢問，每次詢問給出一個 y ，詢問數(shù)列中是否存在 x 與 y 相似，相似的定義如下：

x,y相似當(dāng)且僅當(dāng)x xor y的二進(jìn)制表示中1的個數(shù)小于等于3個。

題目分析：這個題目確實很巧啊，首先 n 和 m 都是 1e6 級別的，所以每個查詢需要在常數(shù)級別的時間復(fù)雜度內(nèi)完成，而 n 是 1e6 ， 且每個數(shù)的范圍是 2^64 ，且所有數(shù)字類似于隨機(jī)數(shù)一樣均勻分布，這里先提一下，下面要用

然后是需要根據(jù)題意轉(zhuǎn)換一個結(jié)論，若 x 和 y 相似，需要滿足 xor 后不同的位置小于等于 3 ，也就是說，將 2^64 分成四組，每一組的長度為 2^16 ，如果 x 和 y 相似的話，那么至少有一組是完全相同的，根據(jù)這一性質(zhì)，可以將 1e6 個數(shù)分為四組，而正因為是均勻分布，1e6 ≈ 2^20 個不同的數(shù)，每一組的長度為 2^16 ，即每一組最多有 2^16 個不同的數(shù)，故最 n 個數(shù)中最多有 (2^20)/(2^16)=2^4=16 個數(shù)在某一組的同一個位置，這樣我們對于每個詢問 y 查詢的時間復(fù)雜度也就變?yōu)榱?4 * 16 * 3 了，其中的 3 是需要進(jìn)行三次 lowbit 運算

可能我解釋的有一些不好，原題解如下：

代碼：

?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef uint64_t ull;const int inf=0x3f3f3f3f;const int N=110;const int mod=998244353;vector<ull>p[4][(1<<16)+100];uint64_t G(uint64_t x) {x^=x<<13;x^=x>>7;x^=x<<17;return x; }void add(ull x) {ull temp=x;for(int i=0;i<4;i++){p[i][temp%(1<<16)].push_back(x);temp>>=16;} }ull lowbit(ull x) {return x&(-x); }bool check(ull x) {for(int i=0;i<3;i++)x-=lowbit(x);return x==0; }int cal(ull x) {ull temp=x;for(int i=0;i<4;i++){for(int j=0;j<p[i][temp%(1<<16)].size();j++)if(check(p[i][temp%(1<<16)][j]^x))return 1;temp>>=16;}return 0; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);ull k;scanf("%llu",&k);for(int i=1;i<=n;i++){add(k);k=G(k);}LL ans=0;while(m--){ull y;scanf("%llu",&y);ans=(ans*2+cal(y))%mod;}printf("%lld\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 小V的序列(思维+位运算)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。