P7032 [NWRRC2016]Boys and Girls
题目链接：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$ 的个数。
由于是在环上，$0/1$ 的连续段数一定相等，不妨设为 $i$。
$$
A=\sum_{i} (m_i+2-[m_i=1]) - K_1 = a+2i-K_0-K_1
$$
同理，
$$
B=n-a+2i-K_0-K_1
$$
两式相减，可得 $a = \frac{A-B+n}2$。
两式相加，可得 $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)$。