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

题意：

给定一个由通配符 ? 和括号组成的序列，求有多少个子串可以通过通配符替换为左右括号而变为括号序列。

Solution:

Subtask 1: 括号串中只有 ?

暴力枚举括号串长度即可。

Subtask 3、4: \(|S| \leq 2000\)

递推。设 \(f_{i,j}\) 表示 \([i, j]\) 是否能变成合法的的括号串。

假设当前状态为 \(f_{i,j}\) ，那么它能成为合法的括号串，即取值为 \(1\) 需满足以下条件任一：

• \(f_{i+1, j-1}=1\) 且 \(i + 1\) , \(j + 1\) 两个位置的字符可以配成一对括号。
• 存在一个位置 \(x\) 满足 \(f_{i, x} = 1\) 且 \(f_{x + 1, j} = 1\)

按照这两个条件递推即可。

通过一些显而易见的剪枝可以跑过这个 Subtask 。

	for(int i = 0; i <= n; i ++)
		f[i + 1][i] = 1;
	for(int l = 2; l <= n; l += 2)
		for(int i = 1; i + l - 1 <= n; i ++){
			int j = i + l - 1;
			if((a[i] == '(' && a[j] == ')') || (a[i] == '?' && a[j] == ')') || (a[i] == '(' && a[j] == '?') || (a[i] == '?' && a[j] == '?'))
			f[i][j] = (f[i][j] || f[i + 1][j - 1]);
			for(int k = i + 1; k < j; k += 2)
					if(f[i][k] && f[k + 1][j]){
					f[i][j] = 1;
					break;
				}
	}
	for(int i = 1; i <= n; i ++)
		for(int j = i; j <= n; j ++){
			ans += f[i][j];
		}
	cout << ans;

Subtask 2: 括号串中没有 ?