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

看完下面的题解,真心想说,你们讲的是个X.(顺手举报一个错题解).这么好的一个题,真是浪费了.我估计下面的写题解的人也是一知半解,没有明白此题的细节.有些细节不写注释估计自己也不知道为啥这么写. 进入正题.初看此题毫无思路,可以尝试将给出的序列中的每一个数转换成二进制并求一下前缀和.用样例举个例子: ```cpp 天数 今日数值(转换为二进制) 前缀和(假设不进位) 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的每一位(从左向右数)为 ```math L_{1},L_{2},L_{3}...L_{n} ``` R的每一位(从左向右数)为 ```math R_{1},R_{2},R_{3}...R_{n} ``` 则有 ```math R_{1}-L_{1}=R_{2}-L_{2}=R_{3}-L_{3}...=R_{n}-L_{n} ``` 移项得: ```math \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个式子.于是我们将这个式子用上.每次计算前缀和后可以减去第一位的值.之后如果得到的两个值相等.那么它们就是一个均衡区间. **算法**: - 哈希:保存每个状态和它对应的天数,每次插入之前查询这个状态是否在之前出现过.如果有,用现在的天数减去之前的天数.不断求ans=max(ans,天数差),就行了.可以手写,也可以用map .楼下用map的题解.每次转换成二进制时顺便就减了,减之前的判断(x&1)是在判断最后一位是否为1.(因为他要将每一位数减去最后一位数) - 排序,自定义比较,将状态相同的排在一起.然后扫一遍打擂台求出最大值.(最好用结构体存状态和对应的天数)有一点细节:要多加一个0天.否则有数据可以hack掉.如1 3这组数据.会输出0而不是1. 我觉得讲的够详细了,就不贴代码了.下面有.有兴趣可以看看耗时最少的人的代码,我表示看不懂.可能有什么快速的hash技巧.有什么错误请私信指出,谢谢.