傳送門
題意： 給一個(gè)二進(jìn)制串aaa，讓后定義兩個(gè)串相似為有至少一個(gè)相同位置相等。現(xiàn)在讓你找一個(gè)字典序最小的長(zhǎng)度為kkk的串使其與aaa中每個(gè)長(zhǎng)度為kkk的字串相似。
思路： 首先我們知道所有可能的串一共有2k2^k2k，我們把aaa串全部取反，這樣aaa的所有長(zhǎng)度為kkk的串都是不符合條件的，除去這n?k+1n-k+1n?k+1個(gè)串，其他的串都是符合條件的，那么我們從000開(kāi)始枚舉到n?k+1n-k+1n?k+1轉(zhuǎn)換成二進(jìn)制一定可以找到一個(gè)符合條件的串。但是我們不一定有n?k+1n-k+1n?k+1個(gè)，上限為2k2^{k}2k個(gè)情況，二者取min即可。如果到最后都沒(méi)找到那說(shuō)明不存在。
二進(jìn)制串的話整個(gè)哈希就好了，能很快的得到hash值，白嫖lc哥的板子。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<LL
,LL
> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int k
,n
;
int a
[N
],ans
,tot
;
LL now1
,now2
;
char ss
[N
];
map
<LL
,int>mp1
,mp2
;struct Hash
{char s
[N
];LL hash
[N
][2],base
[2],mod
[2],f
[N
][2],ban
;int n
;void init(int id
){ban
=id
;base
[0]=233333;base
[1]=23333333;mod
[0]=1e9+7;mod
[1]=1e9+9;for(int k
=0;k
<2;k
++){hash
[0][k
]=0;f
[0][k
]=1;for(int i
=1;i
<=n
;i
++){f
[i
][k
]=f
[i
-1][k
]*base
[k
]%mod
[k
];hash
[i
][k
]=(hash
[i
-1][k
]*base
[k
]+s
[i
])%mod
[k
];}}}pair
<LL
,LL
>get_hash(int l
,int r
){if(l
<=0||r
>n
) return make_pair(ban
,ban
);return make_pair((hash
[r
][0]-hash
[l
-1][0]*f
[r
-l
+1][0]%mod
[0]+mod
[0])%mod
[0],(hash
[r
][1]-hash
[l
-1][1]*f
[r
-l
+1][1]%mod
[1]+mod
[1])%mod
[1]);}
}s
,t
;void get(int ans
)
{string ss
;while(ans
) ss
+=ans
%2+'0',ans
/=2;while(ss
.size()<k
) ss
+='0';now1
=now2
=0;for(int i
=ss
.length()-1;i
>=0;i
--) now1
=(now1
*s
.base
[0]+ss
[i
])%s
.mod
[0],now2
=(now2
*s
.base
[1]+ss
[i
])%s
.mod
[1];
}bool check()
{for(int i
=0;i
<=min(n
-k
+1,(1<<(min(26,k
)))-1);i
++){get(i
);if(mp1
[now1
]||mp2
[now2
]) continue;ans
=i
;return true;}return false;
}string
solve()
{string s
;while(ans
) s
+=ans
%2+'0',ans
/=2;while(s
.size()<k
) s
+='0';reverse(s
.begin(),s
.end());return s
;
}int main()
{
int _
; scanf("%d",&_
);while(_
--){scanf("%d%d",&n
,&k
); scanf("%s",s
.s
+1); s
.n
=n
;for(int i
=1;i
<=n
;i
++) s
.s
[i
]=((s
.s
[i
]-'0')^1)+'0';s
.init(1); mp1
.clear(); mp2
.clear();for(int i
=k
;i
<=n
;i
++){PII t
=s
.get_hash(i
-k
+1,i
);mp1
[t
.X
]=1; mp2
[t
.Y
]=1;}if(check()) printf("YES\n%s\n",solve().c_str());else printf("NO\n");}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Educational Codeforces Round 101 (Rated for Div. 2) F. Power Sockets 哈希 + 乱搞的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
