给出一个长度为n的01序列，只有s位置为1，其余为0.
可以通过选择一个长度为k的序列进行翻转，对于每个位置求出至少多少次能够成为1.
有m个位置在任何时候都不能为1。
对于所有数据，有1 <=n <=105; 1 <= S; k <= n; 0 <= m <= n.
保证S不是禁止位置，但禁止位置可能有重复。
一开始看成区间取反了。。。
可以看出就是最短路，而且边权为1，所以可以bfs求。
但是不可能每次都把区间枚举出来，所以考虑优化。
对于左端点在i的区间，x能翻到的位置是2*i+k-x-1
所以发现能到的位置奇偶性相同且连续，所以想到原来用到的一种方法：并查集
将用过的位置y连向y+2，下次就不会找到他。
边界是真的难受
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=100005; int n,m,k,s; int fa[maxn],dis[maxn]; bool no[maxn]; template<class T>inline void read(T &x){ x=0;int f=0;char ch=getchar(); while(!isdigit(ch)) {f|=(ch==‘-‘);ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x = f ? -x : x ; } int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);} void bfs(){ queue<int> q; memset(dis,-1,sizeof(dis)); dis[s]=0; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); int y,r; if(x-k+1<0) y=find(k+1-x); else y=find(x-k+1); if(x+k-1>n) r=2*n-k-x+1; else r=x+k-1; for(;y<=r;y=find(y+2)){ if(dis[y]==-1&&!no[y]){//no不判好像也行 dis[y]=dis[x]+1; q.push(y); fa[y]=find(y+2); } } } } int main(){ freopen("reverse.in","r",stdin); freopen("reverse.out","w",stdout); read(n);read(k);read(m);read(s); for(int i=1;i<=n+2;i++) fa[i]=i; for(int i=1;i<=m;i++){ int x;read(x); if(!no[x]) no[x]=true,fa[x]=find(x+2); } bfs(); for(int i=1;i<=n;i++) printf("%d ",dis[i]); }
还有线段树建边或者set维护也行。
原文：https://www.cnblogs.com/sto324/p/11625944.html
