P1360 [USACO07MAR]Gold Balanced Lineup G (前缀和+思维)

前言

题目链接

本题作为一道Stl练习题来说，还是非常不错的，解决的思维比较巧妙

算是一道不错的题

思路分析

第一眼看到这题，我还以为是数据结构题，看来半天没看出来数据结构咋做(我还是太菜了)

我们对\(m\)种能力有\(n\)次操作，需要找到对每种能力提升相同的最大操作区间的长度，求最大

区间，我们考虑维护这\(m\)种技能提升值的前缀和，假设第\(l+1\)次操作到第\(r\)次操作对\(m\)个

能力的提升相同，那么一定有一个重要的性质，任取\(m\)种操作中的一种操作\(q\)，执行第\(l\)

次操作后，每一种技能提升值的前缀和与q的提升值前缀和的差值与执行

\(r\)操作后相等，该性质是很显然的，

因为区间操作后对每种技能提升相同，所以差值也一定相同。所以\(l\)到

\(r\)就是一个均横时期，根据此性质我们就可以解决该题了。

我们先选定一种能力，用vector维护所有能力与其的差值，执行某一次操作后，若发现此时的

差值与过去某一次操作后差值相等(用map维护)，那么从过去的那次操作(不包含其本身)到当

前操作就是一个均衡时期。我们扫一遍操作，找到最大长度即可。

代码

我的代码借鉴了楼上那篇用map实现的超短的题解

orz太强了，在此我对其进行部分解释

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<string>

#include<vector>

#define int long long

using namespace std;

const int maxn=1e5+10;

inline int read(){

	int ret=0;

	int f=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')

			f=-f;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		ret=ret*10+(ch^'0');

		ch=getchar();

	}

	return ret*f;

}

int n,m;

int ans,q;

map<vector<int>,int>a;

signed main(){

	n=read();

	m=read();

	vector<int>p(m+10);

	a[p]=0;//记得初始化，不然会wa

	for(int i=1;i<=n;i++){

		q=read();

		for(int j=0;j<m;j++){

			if(q&(1<<j)){

				p[j]++;//维护前缀和

			}

		}

        if(q&1)

        	for(int j=0;j<m;j++){

        		p[j]--;

			}

/*上述操作是在维护差值，我们选取第一种能力作为标准值，也就是上述

的q,如果本次操作对第一种能力有提升，因为我们要获得差值，所以就要把所给所有能力减1；

            */

        if(a.count(p)){//count函数，获得相同判断过去的操作是否有相同差值

        	ans=max(ans,i-a[p]);//获取最大长度，为什么不+1，应为不包含左端区间

		}

        else a[p]=i;

	}

	cout<<ans<<endl;

	return 0;

}

如果对此有疑惑，欢迎评论。

巴特西

洛谷 P1360 [USACO07MAR]Gold Balanced Lineup G (前缀和+思维)

P1360 [USACO07MAR]Gold Balanced Lineup G (前缀和+思维)

前言

思路分析

代码

最新文章

热门文章