Reverse

Source and Judge

雅礼noip模拟题

Problem

小G有一个长度为n的01串T,其中只有TS=1,其余位置都是0。
现在小G可以进行若干次以下操作:
选择一个长度为K的连续子串(K是给定的常数),左右翻转这个子串。
对于每个i,小G想知道最少要进行多少次操作使得Ti=1.
特别的,有m个禁止位置,你需要保证在操作过程中1始终不在任何一个禁止位置上。
n<=1e5

Record

2h

Analysis

请先思考后再展开

发现每个点可以去的点,分奇偶讨论后是连续的一段区间(虽然边界计算有点麻烦)
方法一:线段树优化建图,在上面用deque跑bfs,时间为nlogn
方法二:用set维护没有被更新的点,找区间用lowerbound,这样每次找到的都是没有被更新过的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans;
}
void qwrite(ll num)
{
if(num>=10) qwrite(num/10);
putchar('0'+num%10);
}
void qwriteln(ll num) {qwrite(num);puts("");}
const int MAX_N=110000;
int n,k,m,st;
int f[MAX_N];
queue<int> q;
void push(int pos,int t) {if(t<f[pos]) f[pos]=t,q.push(pos);}
set<int> bt[2];
void bfs()
{
f[st]=0;q.push(st);
for(int i=1;i<=n;i++) if(i!=st) bt[i&1].insert(i);
while(!q.empty())
{
int now=q.front();q.pop();
int l=max(now-k+1,k+1-now),r=min(now+k-1,2*n-now-k+1);
int wt=(now&1)^(k%2==0);
while(1)
{
set<int>::iterator it=bt[wt].lower_bound(l);
if(it==bt[wt].end()) break;
int fd=(*it);
if(fd>r) break;
push(fd,f[now]+1);
bt[wt].erase(it);
}
}
}
void main()
{
memset(f,63,sizeof f);
scanf("%d%d%d%d",&n,&k,&m,&st);
for(int i=1;i<=m;i++) {int t;scanf("%d",&t);f[t]=-1;}
bfs();
for(int i=1;i<=n;i++) if(f[i]==INF) f[i]=-1;
for(int i=1;i<=n;i++) printf("%d ",f[i]);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/37e8.html
转载请注明出处,谢谢!