Description:
给你2个长度为n的01串
从中选出\(n/2\)个,使得选出的数中第一排1的个数等于未选出数中第二排1的个数
输出一种方案即可,没有输出-1
Hint:
\(n \le 5000\)
Solution:
这题比赛的时候傻逼了
后面发现其实就是暴力枚举解方程
\(AuBao\)想出一个O(n)做法力碾标算,这里放出来%一%:
设\(a_i\)为所选第一排是1的数
\(b_i\)表示其对应第二排的数
设\(sum\)表示第二排1的个数
有:
\[\sum a_i = sum- \sum b_i
\]
移过去用d数组代替
\[\sum d_i = sum
\]
现在考虑d的取值,显然有0,1,2三种
\[cnt0*0+cnt1*1+cnt2*2=sum
\]
\[cnt0+cnt1+cnt2=n/2
\]
\[cnt1*1+cnt2*2=sum
\]
\[cnt0+cnt1+cnt2=n/2
\]
O(n)枚举即可
另附被爆踩的官方\(n^2\)的做法:
#include