自动搬运

查看原文

来自洛谷，原作者为

	karma **

搬运于2025-08-24 21:24:11，当前版本为作者最后更新于2017-11-10 08:51:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看完下面的题解,真心想说,你们讲的是个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个式子.于是我们将这个式子用上.每次计算前缀和后可以减去第一位的值.之后如果得到的两个值相等.那么它们就是一个均衡区间.

算法:

• 哈希:保存每个状态和它对应的天数,每次插入之前查询这个状态是否在之前出现过.如果有,用现在的天数减去之前的天数.不断求ans=max(ans,天数差),就行了.可以手写,也可以用map

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

• 排序,自定义比较,将状态相同的排在一起.然后扫一遍打擂台求出最大值.(最好用结构体存状态和对应的天数)有一点细节:要多加一个0天.否则有数据可以hack掉.如1 3这组数据.会输出0而不是1.

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