\(\mathbf{P1360}\) 题解

设\(sum[t][i]\)为截至第t天第i项能力的提升总次数。

由题意可知一个时期为均衡时期\([t_1,t_2]\)，当且仅当 \(\forall\;1\leq i \leq m，sum[t_2][i]-sum[t_1-1][i]\)都相等。

1. 由上，对于每个\(t\)，可以将序列\(sum[t]\)的每个数减去\(sum[t][1]\)，得到一个序列\(f\)（长为\(m\)），它对应值\(t\)。
2. 也可以用差分的方法构造序列\(f\)，使\(f[i]=sum[t][i]-sum[t][i-1](1\leq i\leq m-1)\)。

这样得到一个序列集合，由这个序列集合就可以统计答案了。

可以用一个map或者Hash表维护。

根据贪心思想，在相同的\(f\)中最先出现的一定最优，所以对于每个\(t\)，如果\(f\)出现过，那么更新答案\(ans=\max(ans,t-h[f])\)，否则加入\(f\)。

代码一：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#define N 100010
#define M 50
#define P 13331
using namespace std;
typedef unsigned long long ull;

int n,m;
int f[M];
map<ull,int>mp;

int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
    return x*f;
}

ull Hash(){
    ull a=0;
    for(int i=1;i<=m;i++) a=a*P+f[i];
    return a;
}

int main(){
    n=read(),m=read();
    int ans=0;
    mp[Hash()]=0;
    for(int i=1;i<=n;i++){
        int a=read();
        for(int j=0;j<m;j++)
            if(a&(1<<j)) ++f[j+1];
        if(a&1)
            for(int j=1;j<=m;j++) f[j]--;
        ull H=Hash();
        if(mp.find(H)!=mp.end()) ans=max(ans,i-mp[H]);
        else mp[H]=i;
    }
    printf("%d\n",ans);
    return 0;
}

代码二：

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
int n,m,sum[32],ans;
vector<int>b;
map<vector<int>,int>h;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<m;i++)
        b.push_back(0);
    h[b]=0;
    for(int i=1,a;i<=n;i++)
    {
        scanf("%d",&a);
        b.clear();
        for(int j=0;j<m;j++)
        {
            if(a&(1<<j))    sum[j]++;
            if(j)   b.push_back(sum[j]-sum[j-1]);
        }
        if(h.find(b)!=h.end())  ans=max(ans,i-h[b]);
        else    h[b]=i;
    }
    printf("%d",ans);
    return 0;
}