P7032 [NWRRC2016]Boys and Girls
题目链接: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)。