题解 洛谷P13778 「o.OI R2」=+#-

居然没有题解？我来写一下我的抽象做法。

---

题解

手玩一下，随便画个他信心的折线图，如下：

可以发现，如果我们知道终止节点，那么我们就可以知道中间有多少个上升长度。（因为它只能 $+1$ 或者 $-1$）

然后可以发现一个性质，如果我们把连续的有出现的值在值域上看成一个联通块，如图：

其中的线段表示这一段的值有出现过。显然，$k$ 只能往左跳，不能跨过段往右跳。

那么可以考虑枚举从右往左枚举 $k$ 能否停在这个段内。

具体的，如图：

此时我们是在判断区间 $[5,8]$ 是否合法，那么本质就是看 $k$ 能否停在区间 $[5,8]$ 前面一个区间右端点 $+1$ 往右的位置。

容易发现，红色区间内的所有数又是有用的，可以作为 $+1$ 使用。

那么 $k$ 最终停在的位置就是 $k+c-(n-c)$

其中 $c$ 是红色区间的可用 $+1$ 数量。

判断结果是否比左边界大，即可判定有没有解。

另外有特殊情况，例如如图，算出来 $k$ 最终的位置比 $8$ 大。

这意味着红色区间内可用 $+1$ 比其它 $-1$ 多。

那么就需要这些 $+1$ 两两低消。而我们进入一个区间 $[l,r]$ 后，所能到达的右端点最大就是 $r+1$。

但是具体是不是 $r+1$ 呢？可以发现最终所停位置一定和 $n+k$ 的奇偶性相同，根据这个，对 $r$ 或者 $r+1$ 取一个 $\min$ 即可。

具体维护可以使用并查集。

当然还有一些小细节需要处理，具体地可以看代码。

代码

int n,k;
int c[N],cnt[N],fa[N],l[N],r[N],uur[N];
inline int ga(int x){return x==fa[x]?x:fa[x]=ga(fa[x]);
}
int vis[N];
void uni(int x,int y){int Fx=ga(x),Fy=ga(y);if(Fx==Fy)return ;fa[Fx]=Fy;l[Fy]=min(l[Fx],l[Fy]);r[Fy]=max(r[Fx],r[Fy]);c[Fy]+=c[Fx];
}
struct rrrr{int l,r,id;
}line[N];
void solve(){for(int i=1;i<N;i++)fa[i]=l[i]=r[i]=i,vis[i]=0,cnt[i]=0,c[i]=0,uur[i]=0;cin>>n>>k;for(int i=1;i<=n;i++){int x;cin>>x;cnt[x]++;c[x]++;}for(int i=1;i<=N-2;i++){if(cnt[i]&&cnt[i+1])uni(i,i+1);}int lid=0;for(int i=1;i<=N-2;i++){if(cnt[i]){int fi=ga(i);if(!vis[fi]){++lid;line[lid]={l[fi],r[fi],lid};uur[fi]=lid;vis[fi]=1;}}}for(int i=1;i<=N-2;i++)vis[i]=0;int id=0;int	resc=0;int ans=0;for(int i=k;i>=1;i--){if(cnt[i]){int fi=ga(i);if(vis[fi])continue;resc+=c[fi];//	cout<<fi<<":   \n";//	cout<<resc<<" ";int Lid=k+resc-(n-resc);//	cout<<Lid<<" ";if(Lid>line[uur[fi]-1].r){ans=min(Lid,((n+k)%2==(line[uur[fi]].r%2))?line[uur[fi]].r:line[uur[fi]].r+1);//	cout<<ans<<" ";cout<<(n-(k-ans))/2<<"\n";return ;}vis[fi]=1;}}cout<<resc<<"\n";
}