题目大意
就是说,用一个二进制数描述一个奶牛,如果该位是 1,表示奶牛有这个特征,如果为 0,表示没有。所有奶牛站成一排,你要找出其中一串奶牛,对于每一个特征,这一串奶牛中拥有该特征的奶牛数相同,求这一串奶牛最长的长度。
输入格式
n 表示奶牛数量(n<=100000)
k 表示特征数量(n<=30)
然后有 n 个数,用一个十进制的数描述这个奶牛的特征(你要转换为二进制数)
输出格式
答案,最长的那一串符号要求的奶牛的长度
思路
恩,首先我想,如果用 f[i][j] 来表示前 i 个奶牛中拥有 j 特征的奶牛数量,这样的话,只要枚举起点 s 和终点 t,假如 f[s-1][1]-f[t][1]=f[s-1][2]-f[t][2]=…=f[s-1][k]-f[t][k]. 为什么是 s-1 呢,是因为 s 处和 t 处的奶牛都要考虑。就像你求从 6 到 10 有几个数,答案不是 4 个而是 5 个一样,因为 6 和 10 都要包括。
然后我枚举起点和终点,然后绝对 TLE 啊有木有!!!!
于是我搜了题解…… 惊奇地发现假如 f[s-1][1]-f[t][1]=f[s-1][2]-f[t][2]=…=f[s-1][k]-f[t][k] 的话,那么 f[t][2]-f[t][1]=f[s-1][2]-f[s-1][1],f[t][3]-f[t][1]=f[s-1][3]-f[s-1][1]… 以此类推,把前一串式子变形就可以得到了。我们让 ff[i][j]=f[i][j]-f[i][1]。
啊!这样的话,我们只要哈希对于每个 i 值的 f[i][2…k]-f[i][1] 就可以了!
不过,要怎么写哈希呢?
如果你直接取模的话,百分之一百二会重复有木有!!!!
所以我们要用链表哈希。
然后就神奇地过了。
代码:
0 条评论