P7032 [NWRRC2016]Boys and Girls
yzxoi
2022-11-13 (Updated: 2022-11-13)
oi
构造
题目链接：P7032
你有一个大小为 n 的环，环上的元素分别为 0/1 两种。
现已知有 A 个元素旁边存在 0（即与之相邻的两个元素中有至少一个为 0），有 B 个元素旁边存在 1（即与之相邻的两个元素中有至少一个为 1）。
要求构造一组可能的情况，或判断无解。
2leq nleq 10^5，0leq A,Bleq 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
