P1360 [USACO07MAR]Gold Balanced Lineup G题意：思路：

66 阅读 0 评论 44 点赞

我是靠谱客的博主现实云朵，最近开发中收集的这篇文章主要介绍P1360 [USACO07MAR]Gold Balanced Lineup G题意：思路：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

传送门

题意：

有n天，m种能力，每天给你一个数x，每天提升的能力用该数的二进制表示，1为提升，反之则不，问你最长的连续几天提升的每种能力相同的天数。

思路：

对于每一种能力值，可以通过前缀和来计数，而如果第l天到第r天满足要求，设bit[i][j]表示第i天第j种能力值的前缀和，那么显然可以得到： $b i t [r] [1] - b i t [l - 1] [1] = b i t [r] [2] - b i t [l - 1] [2] = . . . . . . b i t [r] [m] - b i t [l - 1] [m]$ 。进行一个简单的移向，可以得到： $b i t [r] [i] - b i t [r] [1] = b i t [l - 1] [i] - b i t [l - 1] [1]$ ，那么思路就明了了：对于每一天，先得到它的位前缀和，然后让这一天的位前缀和的每一位都减去它的第一位的位前缀和，再判断结果是否在之前出现过，若出现过，则更新答案。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl 'n'
#define pb push_back 
#define p push
const int mod = 1e8;
ll n,m;
vector<ll>now[100010];
map<vector<ll>,int>vis;

int main()
{
//	freopen("C:\Users\76004\Downloads\P1360_1.in","r",stdin);
	cin>>n>>m;
	int ans = 0;
	for(int i = 0; i < m; i++)
	{
		now[1].pb(0);
		vis[now[1]] = 1;
	}
	for(int i = 2; i <= n+1; i++)
	{
		ll x;
		cin>>x;
		for(int j = 0; j < m; j++)
		{
			int b = x%2;x>>=1;
			now[i].pb(b);
//			if(i>2)
			now[i][j]+=now[i-1][j];
//			cout<<now[i][j]<<" ";
		}
//		cout<<endl;
		vector<ll>p;
		for(int j = 0; j < m; j++)
		p.pb(now[i][j]-now[i][0]);
		if(vis[p])ans = max(ans,i-vis[p]);
		else vis[p] = i;
	}
	cout<<ans<<endl;
}