题解 P1360 【[USACO07MAR]黄金阵容均衡Gold Balanced L…】

· · 题解

看完下面的题解,真心想说,你们讲的是个X.(顺手举报一个错题解).这么好的一个题,真是浪费了.我估计下面的写题解的人也是一知半解,没有明白此题的细节.有些细节不写注释估计自己也不知道为啥这么写.

进入正题.初看此题毫无思路,可以尝试将给出的序列中的每一个数转换成二进制并求一下前缀和.用样例举个例子:

天数    今日数值(转换为二进制)    前缀和(假设不进位)
1       7->111                      111
2       6->110                      221
3       7->111                      332    
4       2->010                      342
5       1->001                      343
6       4->100                      443
7       2->010                      453

当区间满足是一个"均衡时期",必满足该区间中每项能力都提升X

.设区间为[L,R],即前缀和sum[R]-sum[L-1]的每一位都相等.

如样例中从第三天到第六天,前缀和为443-221=222.故每项能力都提升了2.

以此类推.设最长区间的起始天的前一天(因为要算前缀和)为L,末尾的一天为R.设L的每一位(从左向右数)为

L_{1},L_{2},L_{3}...L_{n}

R的每一位(从左向右数)为

R_{1},R_{2},R_{3}...R_{n}

则有

R_{1}-L_{1}=R_{2}-L_{2}=R_{3}-L_{3}...=R_{n}-L_{n}

移项得:

\left\{\begin{matrix}
 &R_{1}-R_{2} =L_{1}-L_{2} \\ 
 &R_{1}-R_{3} =L_{1}-L_{3} \\ 
 &R_{2}-R_{3} =L_{2}-L_{3} \\
 &...
\end{matrix}\right.

其实最后一个式子是没有意义的,因为用前N-1个式子可以推出来第N个式子.于是我们将这个式子用上.每次计算前缀和后可以减去第一位的值.之后如果得到的两个值相等.那么它们就是一个均衡区间.

算法:

.楼下用map的题解.每次转换成二进制时顺便就减了,减之前的判断(x&1)是在判断最后一位是否为1.(因为他要将每一位数减去最后一位数)

我觉得讲的够详细了,就不贴代码了.下面有.有兴趣可以看看耗时最少的人的代码,我表示看不懂.可能有什么快速的hash技巧.有什么错误请私信指出,谢谢.