题解 P1360 【[USACO07MAR]黄金阵容均衡Gold Balanced L…】

查看原图请戳这里

首先明确一点，题目求的是最长的每项能力提升大小都相等的区间，所以我们是不用关心一段区间每项能力到底提升了多少，只需要去记录每项能力的大小关系即可。即如果第i天能力x比能力y多k，第j天能力x比能力y也多k，那么在i~j天中x和y的变化量都相等。

所以我们就可以先维护一个二维前缀和来记录每一天每个能力的能力值，再用相邻两行做差来记录大小关系。于是，我们只需要去寻找x，y，使得第x天的大小关系与第y天相同且y-x尽可能大。我们可以发现，如果暴力枚举去寻找，复杂度是$O(n^2)$的，所以我们可以先对这个表示大小关系的二维矩阵的列排序，再去$O(n)$统计答案。

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define re register
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define qwq printf("qwq\n");

using namespace std;

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

int n,m,x,y,ans,cnt,flag,f[37][1000015],h[37][1000015],e[100005];

struct two{
	int num[47],p;
}g[1000015];

void broke(int x,int i)
{
	int cnt = 0;
	while(x > 0)
	{
		f[++cnt][i] = x & 1;
		x >>= 1;
	}
}

void init()
{
	n = read(); m = read();
	for(int i = 1; i <= n; i++)
	{
		y = x;
		x = read();
		e[i] = x;
		if(x != y && x > 1) flag = 1;
		broke(x,i);
	}
}

void make1()
{
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++)
			f[i][j] = f[i][j - 1] + f[i][j];
}

int mysort(two a,two b)
{
	int k = 1;
	while(a.num[k] == b.num[k] && k <= m) k++;
	if(k <= m) return a.num[k] < b.num[k];
	return a.p < b.p;
}

void make2()
{
	for(int i = 2; i <= m; i++)
		for(int j = 1; j <= n; j++)
			g[j].num[i] = f[i][j] - f[i - 1][j],g[j].p = j;
	sort(g, g + n + 1,mysort);
}

bool cmp(int a,int b)
{
	for(int i = 1; i <= m; i++) if(g[a].num[i] != g[b].num[i]) return false;
	return true;
}

void find()
{
	ans = 0;
	int head = 0;
	while(head < n)
	{
		int k = head;
		while(cmp(k + 1,head) && k < n) k++;
		if(k <= n) ans = max(ans,g[k].p - g[head].p);
		head = k + 1;
	}
}

int main()
{
	init();
	if(flag == 0)
	{
		int k = 0;
		while(e[k + 1] == 0 && k < n) k++;
		printf("%d\n",k);
		return 0;
	}
	make1();
	make2();
	find();
	printf("%d\n",ans);
    return 0;
}