1247 排排站 USACO(查分+hash)
2024-10-20 07:41:13
/*
暴力查分 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 ;
}
最新文章
- 嵌入式C语言代码的调试技巧
- RabbitMQ 异常与任务分发
- 内置函数----整理、例题 、xmin
- java实验一 20135104刘帅
- [LeetCode] Wildcard Matching 字符串匹配,kmp,回溯,dp
- Virtio:针对 Linux 的 I/O 虚拟化框架
- htmlparser日记
- Java NIO1
- Django admin site(三)InlineModelAdmin
- MySQL指令记录(Wampserve环境)
- leetcode第一刷_Unique Paths
- Tomcat 使用过程中的一些技巧
- 基于.netstandard的权限控制组件
- 使用Dockerfile构建镜像
- 【HDU - 4927】Series 1
- 生产redis client 连接无法释放
- Redis集群官方推荐方案 Redis-Cluster
- Dirichlet分布深入理解
- POJ3635 Full Tank?
- 笨方法学python学习笔记