sto Bronya19C.
A
题意：
一个长度为 \(n\) 的 \(01\) 串，其中只有 \(1\) 个数为 \(1\) 。每次将一个长度为 \(k\) 的字串翻转。
对于每个 \(i\) 询问 \(1\) 最少多少次操作可以将它翻转到 \(s\) 。另外有些位置任意时刻不能有 \(1\) 。
对于每个 \(i\) ，如果无法做到输出 \(-1\) 。
\(n \leq 10^5\)。
Solution:
一种简单的方法是直接BFS。
考虑 \(i\) 能转移到 \(j\) 的条件。
-
\(2 \times \max(i - k + 1) + k - u - 1 \leq j \leq \min(n - k + 1, u)\)
-
\(i - j \not\equiv k\space(\operatorname{mod}2)\)
考虑优化 BFS 。用 set 维护奇数和偶数未更新点的集合，每次更新完点后删除这些点，即可做到每个仅更新一次。时间复杂度 \(O(n\log{n})\)。
Code:
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<set>
using namespace std;
int flg[100005], n, k, m, s;
int f[100005];
bool inque[100005];
queue<int> q;
set<int> s1, s2;
int main(){
cin >> n >> k >> m >> s;
for(int i = 1; i <= n; i += 2)
s1.insert(i);
for(int i = 2; i <= n; i += 2)
s2.insert(i);
for(int i = 1, v; i <= m; i ++)
cin >> v, flg[v] = true;
if(k == 1 || n < k){
for(int i = 1; i <= n; i ++)
cout << (((i == s && (!flg[i]))) ? 1 : -1) << " ";
return 0;
}
if(flg[s]){
for(int i = 1; i <= n; i ++) cout << "-1 ";
return 0;
}
memset(f, -1, sizeof(f));
if(k == 2){
for(int i = s; i <= n; i ++)
if(flg[i])
break;
else f[i] = i - s;
for(int i = s; i >= 1; i --)
if(flg[i]) break;
else f[i] = s - i;
for(int i = 1; i <= n; i ++)
cout << f[i] << " ";
return 0;
}
f[s] = 0;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
if(((2 * max(u - k + 1, 1) + k - u - 1) % 2) == 1){
auto it = s1.lower_bound(2 * max(u - k + 1, 1) + k - u - 1);
auto it2 = it;
for(; it != s1.end() && *it <= 2 * (min(n - k + 1, u)) + k - u - 1; it ++)
if(f[*it] == -1 && !flg[*it]){
f[*it] = f[u] + 1;
q.push(*it);
}
if(it2 != it)
s1.erase(it2, -- it);
}
else{
auto it = s2.lower_bound(2 * max(u - k + 1, 1) + k - u - 1);
auto it2 = it;
for(; it != s2.end() && *it <= 2 * (min(n - k + 1, u)) + k - u - 1; it ++)
if(f[*it] == -1 && !flg[*it]){
f[*it] = f[u] + 1;
q.push(*it);
}
if(it2 != it)
s2.erase(it2, -- it);
}
}
for(int i = 1; i <= n; i ++)
cout << f[i] << " ";
return 0;
}
B
题意：
给定一个由通配符 ? 和括号组成的序列，求有多少个子串可以通过通配符替换为左右括号而变为括号序列。