/*
暴力查分 n*n
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 100010
using namespace std;
int n,m,a[maxn],ans,p[maxn][],r[];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if((<<j-)&a[i])p[i][j]=p[i-][j]+;
else p[i][j]=p[i-][j];
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
int falg=;
for(int k=;k<=m;k++)
r[k]=p[j][k]-p[i-][k];
for(int k=;k<=m;k++)
if(r[k]!=r[k-]){falg=;break;}
if(!falg)ans=max(ans,j-i+);
}
printf("%d\n",ans);
return ;
}
/*
还是差分
因为对于符合条件的序列
有 sj0 - si0 = sj1 - si1 =...= sjk-1 - sik-1
也就是说 如果存在i j 满足
sj1 - sj0 == si1 - si0
sj2 - sj0 == si2 - si0
......
sjk-1 - sj0 == sik-1 - si0
我们定义c[i,j]=s[i,j]-s[i,0]
问题就转化成了 找隔得最远的ij 满足c[i] 和 c[j] 一样
这里用hash加速查找 给每个c[i] 搞一个hash值 放到hash表里
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#define maxn 100010
#define mod 999997
using namespace std;
int n,m,a[maxn],ans,p[maxn][],c[maxn][],has[maxn*];
int Get_hash(int *a)
{
int r=;
for(int i=;i<m;i++)
r=r%mod+a[i]<<;
if(r<)r=-r;
return r%mod;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=;j<m;j++)
if((<<j)&a[i])p[i][j]=p[i-][j]+;
else p[i][j]=p[i-][j];
for(int i=;i<=n;i++)
for(int j=;j<m;j++)
c[i][j]=p[i][j]-p[i][];
memset(has,-,sizeof(has));
has[]=;
for(int i=;i<=n;i++)
{
int k=Get_hash(c[i]);
while(has[k]!=-)
{
int falg=;
for(int j=;j<m;j++)
if(c[has[k]][j]!=c[i][j])
{
falg=;break;
}
if(!falg&&i-has[k]>ans)
{
ans=i-has[k];break;
}
k++;
}
if(has[k]==-)has[k]=i;
}
printf("%d\n",ans);
return ;
}

最新文章

  1. 嵌入式C语言代码的调试技巧
  2. RabbitMQ 异常与任务分发
  3. 内置函数----整理、例题 、xmin
  4. java实验一 20135104刘帅
  5. [LeetCode] Wildcard Matching 字符串匹配,kmp,回溯,dp
  6. Virtio:针对 Linux 的 I/O 虚拟化框架
  7. htmlparser日记
  8. Java NIO1
  9. Django admin site(三)InlineModelAdmin
  10. MySQL指令记录(Wampserve环境)
  11. leetcode第一刷_Unique Paths
  12. Tomcat 使用过程中的一些技巧
  13. 基于.netstandard的权限控制组件
  14. 使用Dockerfile构建镜像
  15. 【HDU - 4927】Series 1
  16. 生产redis client 连接无法释放
  17. Redis集群官方推荐方案 Redis-Cluster
  18. Dirichlet分布深入理解
  19. POJ3635 Full Tank?
  20. 笨方法学python学习笔记

热门文章

  1. Lambda表达式中的表达式lambda和语句lambda区别
  2. 首页重定位到mian.action上
  3. WebKit JavaScript Binding添加新DOM对象的三种方式
  4. Dp解决数组中连续子数组的最大和
  5. 【Linux】鸟哥的Linux私房菜基础学习篇整理(四)
  6. 数学 ZJOI 2012 数列
  7. 开源库CImg 数据格式存储之二(RGB 顺序)
  8. Elasticsearch教程之基础概念
  9. SCU 4436 Easy Math 2015年四川省赛题
  10. 暴力求解——除法 Division,UVa 725