Problem 1 bfs+set

$des$

小G有一个长度为 $n$ 的 01 串 T ，其中只有 $T_S = 1$，其余位置都是 $0$。现在小G可以进行若干
次以下操作：
选择一个长度为 $K$ 的连续子串（K是给定的常数），翻转这个子串。
对于每个 $i,i ∈ [1,n]$，小G想知道最少要进行多少次操作使得 $T_i = 1$. 特别的，有 $m$ 个 “禁
止位置”，你需要保证在操作过程中 $1$ 始终不在任何一个禁止位置上。

$sol$

考虑当前在每个点时可以通过一次翻转转移到哪些点，直接遂遆道即可算出每个点的所需步
数。然而边数会达到 $O(n ^ 2)$ 级别。
可以发现转移到的点一定是一段区间内的奇数或者偶数点，于是一种简单的优化
方法是在 BFS 时开两个 SET 维护当前有哪些奇数点和偶数点还未被 BFS 到，转移时直接
在 SET 上 lower_bound，就不会访问已经 BFS 到过的点了。$O(nlogn)$

$code$

#include <bits/stdc++.h>

#define Rep(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 1e5 + ;

int n, K, m, S;

int dis[N];

bool ban[N];

set<int> add1, even2;

void BFS() {

    memset(dis, -, sizeof dis);

    queue<int> q;

    dis[S] = , q.push(S);

    while (!q.empty()) {

        int o = q.front(); q.pop();

        int L = max(, o - K + ), R = min(n, o + K - );

        L = L + (L + K - ) - o, R = R + (R - K + ) - o;

//        cout << o << " " << L << " " << R << "\n";

        set<int> &p = L &  ? add1 : even2;

        for (set<int> :: iterator i = p.lower_bound(L); i != p.end() && *i <= R; p.erase(i++))

            dis[*i] = dis[o] + , q.push(*i);

    }

}

int main() {

    scanf("%d%d%d%d", &n, &K, &m, &S);

    Rep(i, , m) {

        int x;

        scanf("%d", &x);

        ban[x] = true;

    }

    Rep(i, , n) if (!ban[i] && i != S) i &  ? add1.insert(i) : even2.insert(i);

    BFS();

    Rep(i, , n) printf("%d ", dis[i]);

    return ;

}

巴特西

Problem 1 bfs+set

最新文章

热门文章