P7032 [NWRRC2016]Boys and Girls

P7032 [NWRRC2016]Boys and Girls

yzxoi

2022-11-13 (Updated: 2022-11-13)

oi

构造

题目链接：P7032

你有一个大小为 n 的环，环上的元素分别为 0/1 两种。

现已知有 A 个元素旁边存在 0（即与之相邻的两个元素中有至少一个为 0），有 B 个元素旁边存在 1（即与之相邻的两个元素中有至少一个为 1）。

要求构造一组可能的情况，或判断无解。

2\leq n\leq 10^5，0\leq A,B\leq n。

Tutorial

考虑一段长度为 x 的 0 对 A 的贡献为 x+2-[x=1]。

但这样会算重，比如 010，而算重的部分为长度为 1 的连续段数。

记 a 表示 0 的个数，m_i 表示 0 的第 i 个连续段长度，K_{0/1} 表示连段段为 0/1 且长度为 1 的个数。

。

同理，

两式相减，可得

两式相加，可得 K_0+K_1=a+2i-A。

于是暴力枚举 i，考虑解 K_0,K_1。

注意到 K_0 \in[ \max {a-2i,0},i-[i!=a]]，同理也可得 K_1 范围。

必要性得证。

容易证明在此范围内的解均可构造得到。

具体的，交替放 0/1 段，在前 K_0 段 0 之中放 0，之后除了最后一次放 00，最后一次全放，1 同理。

合法性显然，充分性得证。

O(N)。

93893466