Codeforces Round 951 (Div. 2) D. Fixing a Binary String 题解
文章目录
- Codeforces Round 951 (Div. 2) D. Fixing a Binary String 题解
- 题意
- 题目解析
- AC代码
Codeforces Round 951 (Div. 2) D. Fixing a Binary String 题解
题意
You are given a binary string
s
s
s of length
n
n
n, consisting of zeros and ones. You can perform the following operation exactly once:
- Choose an integer
p
p
p (1
≤
p
≤
n
1 \le p \le n
1≤p≤n). - Reverse the substring
s
1
s
2
…
s
p
s_1 s_2 \ldots s_p
s1s2…sp. After this step, the strings
1
s
2
…
s
n
s_1 s_2 \ldots s_n
s1s2…sn will becomes
p
s
p
−
1
…
s
1
s
p
+
1
s
p
+
2
…
s
n
s_p s_{p-1} \ldots s_1 s_{p+1} s_{p+2} \ldots s_n
spsp−1…s1sp+1sp+2…sn. - Then, perform a cyclic shift of the string
s
s
s to the leftp
p
p times. After this step, the initial strings
1
s
2
…
s
n
s_1s_2 \ldots s_n
s1s2…sn will becomes
p
+
1
s
p
+
2
…
s
n
s
p
s
p
−
1
…
s
1
s_{p+1}s_{p+2} \ldots s_n s_p s_{p-1} \ldots s_1
sp+1sp+2…snspsp−1…s1.
For example, if you apply the operation to the string 110001100110 with
p
=
3
p=3
p=3, after the second step, the string will become 011001100110, and after the third step, it will become 001100110011.
A string
s
s
s is called
k
k
k-proper if two conditions are met:
s
1
=
s
2
=
…
=
s
k
s_1=s_2=\ldots=s_k
s1=s2=…=sk;s
i
+
k
≠
s
i
s_{i+k}
eq s_i
si+k=si for anyi
i
i (1
≤
i
≤
n
−
k
1 \le i \le n – k
1≤i≤n−k).
For example, with
k
=
3
k=3
k=3, the strings 000, 111000111, and 111000 are
k
k
k-proper, while the strings 000000, 001100, and 1110000 are not.
You are given an integer
k
k
k, which is a divisor of
n
n
n. Find an integer
p
p
p (
1
≤
p
≤
n
1 \le p \le n
1≤p≤n) such that after performing the operation, the string
s
s
s becomes
k
k
k-proper, or determine that it is impossible. Note that if the string is initially
k
k
k-proper, you still need to apply exactly one operation to it.
Input
Each test consists of multiple test cases. The first line contains one integer
t
t
t (
1
≤
t
≤
1
0
4
1 \le t \le 10^4
1≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers
n
n
n and
k
k
k (
1
≤
k
≤
n
1 \le k \le n
1≤k≤n,
2
≤
n
≤
1
0
5
2 \le n \le 10^5
2≤n≤105) — the length of the string
s
s
s and the value of
k
k
k. It is guaranteed that
k
k
k is a divisor of
n
n
n.
The second line of each test case contains a binary string
s
s
s of length
n
n
n, consisting of the characters 0 and 1.
It is guaranteed that the sum of
n
n
n over all test cases does not exceed
2
⋅
1
0
5
2 \cdot 10^5
2⋅105.
Output
For each test case, output a single integer — the value of
p
p
p to make the string
k
k
k-proper, or
−
1
-1
−1 if it is impossible.
If there are multiple solutions, output any of them.
题目解析
- 我们先不管操作考虑一下什么形式的串是满足条件的。
s
[
i
]
s[i]
s[i] !=s
[
i
+
k
]
s[i+k]
s[i+k]s
[
i
]
=
s
[
i
+
1
]
=
.
.
.
=
s
[
i
+
k
−
1
]
s[i] = s[i+1] =…=s[i+k-1]
s[i]=s[i+1]=…=s[i+k−1]
- 要同时满足上述要求，答案的形式只有两种，要么从
1
1
1 开始，要么从0
0
0 开始。 - 我们再思考一下操作一次后，串本质上的变化是什么。
- 我们发现本质上就是把串
s
s
s 分为两段A
A
A 和B
B
B，在用B
B
B 和A
的逆序
A的逆序
A的逆序 拼起来。 - 答案只有两个，我们用
B
+
A
逆
B+A逆
B+A逆 是否等于a
n
s
ans
ans，你能想到什么？ - 字符串
h
a
s
h
hash
hash。
AC代码
注：我用的是
B
a
s
e
=
131
,
m
o
d
=
805306457
Base=131,mod=805306457
Base=131,mod=805306457 的单模hash，如果想要更保险，可以考虑使用多模hash。
import sys
input = lambda: sys.stdin.readline().rstrip("\r
")
out = sys.stdout.write
def S():
return input()
def I():
return int(input())
def MI():
return map(int, input().split())
def MF():
return map(float, input().split())
def MS():
return input().split()
def LS():
return list(input().split())
def LI():
return list(map(int, input().split()))
def print1(x):
return out(str(x) + "
")
def print2(x, y):
return out(str(x) + " " + str(y) + "
")
def print3(x, y, z):
return out(str(x) + " " + str(y) + " " + str(z) + "
")
def Query(i, j):
print3('?', i, j)
sys.stdout.flush()
qi = I()
return qi
def print_arr(arr):
out(' '.join(map(str, arr)))
out(str("
"))
# ----------------------------- # ----------------------------- #
base = 131
base1 = 13331
mod = 805306457
mod1 = 1610612741
def solve():
def get_hs(h, l, r):
return (h[r] - (h[l - 1] * pbase[r-l+1] % mod) + mod) % mod
n, k = MI()
s = S()
pre = [0]*(n+1)
pbase = [1]*(n+1)
for i in range(1,n+1):
pre[i] = (pre[i-1] * base + ord(s[i-1]) - ord('0')) % mod
pbase[i] = pbase[i-1] * base % mod
past = [0]*(n+1)
for i in range(1,n+1):
past[i] = (past[i-1] * base + ord(s[n - i]) - ord('0')) % mod
ans1,ans2 = 0,0
for i in range(n):
ans1 = (ans1*base + ((i//k) & 1)) % mod
ans2 = (ans2*base + ((i//k) & 1 ^ 1)) % mod
for p in range(1,n+1):
now = (get_hs(pre, p+1,n)*pbase[p] + get_hs(past, n + 1 - p, n)) % mod
if now == ans1 or now == ans2:
print1(p)
return
print1(-1)
for _ in range(I()):
solve()
