黄金阵容分割[luogu1360] [usaco2007]

发表于 | 分类于 | 阅读次数: |

黄金阵容均衡[luogu1360] [usaco2007]

题意：有个人有m种能力，然后有n天，每天会提升m种能力中的几种，如果第n天提升能力是6，换成二进制就是00110，那么从右到左为一的位置就是那天提升了一次能力，6的话就是提升了第二、三种能力，我们把[l,r]这个区间内m种能力提升的次数相同的区间叫做均衡区间。求最大均衡区间。说到底就是给你一串数，这串数化成二进制之后，每个二进制数位的1的个数要相等。

example:
第一天：7 00111
第二天：6 00110
第三天：7 00111
第四天：2 00010
第五天：1 00001
第六天：4 00100
第七天：2 00010

这串数的最大均衡区间是第3天到第6天，这4天的和是00222；
这个题主要就是判断区间[l,r]是否合法；
首先位运算每一位的前缀和，然后判断是否合法；
假设[1,L]的区间为a1-a29,[1,r]的区间为b1-b29;
区间合法就是b1-a1=b2-a2…b29-a29;
移项之后就是
b1-b2=a1-a2
…
b28-b29=a28-a29可以用一个数组存这个式子
arr[i]={a1-a2,…,a28-a29};
这个问题就转换成了对于数组arr[i]，间距最远的两个相等的arr[i],arr[j]的距离了。
排序可解决：nlogn30
hash可解决：nlogn+n30

贴个hash方法（针对字符串，别的类推就可以了）

1
2
3
4
5
6
7
8
9
//字符串hash
//对字符串进行编码 id(s[i])=s[i]-‘A’。
//单hash
unsigned long long hash[maxn];
hash[i]=hash[i-1]*p+id(s[i])%mod  //p,mod为质数，且p<mod;
//双hash
Hash1[i]=(hash1[i-1])*p+id(s[i])%mod1;
Hash2[i]=(hash2[i-1])*p+id(s[i])%mod2;
//Hash结果为<hash1[n],hash2[m]>

AC hash 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<map>
#include<set>
using namespace std;

int n,m,ans;
int a[100005][35];
int head[1000005],nextt[1000005];
int add[100005][35];
int vis[100005];
int p=0;
void push(int x,int y)
{
    nextt[++p]=head[x];
    head[x]=p;
    vis[p]=y;
    for(int j=1;j<=m;j++)
        add[p][j]=a[y][j];
}
int main()
{
    int x;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        for(int j=1;j<=m;j++)
        {
            a[i][j]=x%2;
            x/=2;
        }
        for(int j=1;j<=m;j++)
            a[i][j]+=a[i-1][j];
    }
    p=0;
    push(0,0);
    for(int i=0;i<=n;i++)
    {
        int sum=0,j,k;
        for(j=2;j<=m;j++)
            sum=((sum+a[i][j]-a[i][1])*j%1000005+1000007)%1000007;
        for(j=head[sum];j!=0;j=nextt[j])
        {
            for(k=2;k<=m;k++)
                if(add[j][k]-a[i][k]!=add[j][1]-a[i][1])
                    break;
            if(k>m)
            {
                ans=max(ans,i-vis[j]);
                break;
            }
        }
        if(j==0)
            push(sum,i);
    }
    cout<<ans<<endl;
    return 0;
}