题意概括 寻找使各科复习天数相同的最长的区间长度 暴力算法（得分68）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const long long N=1e5+10;
long long n,m,k,a[N],b[N],ans,cnt;
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
		for(int y=1;y<=m;y++){
			b[y]=0;
		} 
		for(int j=i;j<=n;j++){
			long long x=a[j];
			for(int k=m;k>=1;k--){
				if(x&1){
					b[k]++;
				}
				x/=2;
				if(x==0)break;
			} 
			bool flag=0;
			for(int z=2;z<=m;z++){
				if(b[z]!=b[z-1]){
					flag=1;
					break;
				}
			} 
			if(flag==0){
				ans=max(ans,(long long)(j-i+1));
			}
		}
	} 
	printf("%lld",ans);
	return 0;
}

正解思路 考虑使用前缀和算法，如果一个区间的左端点到右端点每位的增加量相同，那么这个区间就满足各科复习天数相同的题意 考虑到1 2 3 和0 1 2对于本题目统计答案而言是等价的，并且后者更便于统计答案，因此可以考虑将其化简为0 1 2 这种有一位为0的形式。 对于本题答案的统计，考虑使用map映射，借助count()函数统计答案。 AC代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const long long N=1e5+10;
int n,m,k,a[N],b[N],ans,cnt;
map<vector<int> , int > mp; 
vector<int> v(34);
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]); 
	} 
	mp[v]=0;
	for(int i=1;i<=n;i++){
		int x=a[i],minn=0;
		for(int j=m;j>=1;j--){
			if(x&1)v[j]++;
			if(j==m)minn=v[j];
			else minn=min(minn,v[j]);
			x/=2;
		}
		if(minn>0){
			for(int j=m;j>=1;j--){
			v[j]-=minn;
		}
		} 
		if(mp.count(v)==1){
			ans=max(ans,i-mp[v]); 
		}
		else{
			mp[v]=i;
		}
	}
	cout<<ans;
	return 0;
}

暴力

预处理每一位出现个数的前缀和，枚举两个端点，时间复杂度$O(nlogn+n^2)$ $74pts$

code:

bool check(long long l,long long r){
	for(long long i = 2;i <= m; i++){
		if(w[r][i] - w[l-1][i] != w[r][i-1] - w[l-1][i-1]) return 0;
	}
	return 1;
}

void compute() {
	long long ans = 0;
	for(long long i = 1; i <= n; i++) {
		for(long long j = 1;j <= m; j++){
			w[i][j] = w[i-1][j] + ((a[i] >> (j - 1)) & 1);
		}
	}
	for(long long i = 1;i <= n; i++){
		for(long long j = i + ans - 1;j <= n; j++){
			if(check(i,j)) ans = max(ans,j-i+1);
		}
	}
	cout << ans;
	return ;
}

正解

我们要寻找最长的每一个位出现次数相同的区间，那么我们不妨考虑将每一次前缀和都减一下第一位的前缀和，只要使得差值相同，就是每一个位出现次数相同，这个可以用map记录每种状态第一次出现的位置,(注意要赋初值) 时间复杂度$O(nm)$ code:

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e5 + 10;

long long n, m;

long long a[N];

vector<long long> v(31);

map<vector<long long>,long long> mp;

void read(){
	cin >> n >> m;
	for(long long i = 1;i <= n; i++){
		cin >> a[i];
	}
	return ;
}

void compute(){
	mp[v] = 0;
	long long ans = 0, cnt = 0;
	for(long long i = 1;i <= n; i++){
		for(long long j = 0;j < m; j++){
			v[j] += ((a[i] >> j) & 1);
		}
		if(v[0] > 0){
			long long tmp = v[0];
			for(long long j = 0;j < m; j++){
				v[j] -= tmp;
			}
		}
		if(mp.count(v)) ans = max(ans,i-mp[v]);
		else mp[v] = i;
	}
	cout << ans;
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}

法一：暴力枚举每一个区间

时间复杂度 $O(n^2)$

用前缀和确定每一个区间中每一个科目的出现的次数

74pts 到手 （数据太水了）

int n,m,s[30][100005],ans;

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		int x; scanf("%d",&x);
		for (int j=1;j<=m;j++){
			if (x&(1<<(j-1))) s[j][i]=1;
			s[j][i]+=s[j][i-1];
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=i;j<=n;j++){
			bool flag=0;
			for (int k=1;k<m;k++){
				if (s[k][j]-s[k][i-1] != s[k+1][j]-s[k+1][i-1]){
					flag=1;
					break;
				}
			}
			if (!flag){
				ans=max(ans,j-i+1);
			}
		} 
	}
	printf("%d",ans);
	return 0;
}

正解：

我们来分析一下上面的暴力中的前缀和里面有什么

如果存在 $2\le i<j\le n$ ,使 $d_{i-1} = d_{j}$ 那么 $[i,j]$ 为一个平衡区间

小明的复习计划 题解

题意简述

求一个最长区间，满足每科复习天数都相等。

初步分析

最暴力的想法就是每枚举一个区间[l,r],就检查一下当前这个区间是否能满足“每科复习天数都相等”。

《算法竞赛进阶指南》在0x03中提到了一种思想：把对一个区间的操作转换为左右两个端点上的操作，再通过前缀和得到原问题的解。

eg

随便举个栗子🙌

0 0 0 1
	//1 0 1 1
1 0 1 0
	//1 1 1 2
0 1 0 1
    //2 1 2 2
1 0 1 0

前面的数是输入转成的二进制，注释的内容是前缀和。

那么这个区间[l,r]是否能满足题意，就只需要取前缀和的两个端点l,r对应的值，再检查每位的增长是否相同就可以了~~

优化

上述做法时间复杂度依然不过关，因为对于每一个区间还需要判断“ 每位的增长是否相同 ”。那么我们再次观察上面的栗子：

0 0 0 1
	//1 0 1 1
1 0 1 0
	//1 1 1 2
0 1 0 1
    //2 1 2 2
1 0 1 0

“1 0 1 1”和“2 1 2 2”非常相似，只不过每位都+1而已！废话这不就是要的答案吗

所以可以像“化简”那样，把最后一位都化成0，这样“1 0 1 1”-1变成“0 -1 0 0”，“2 1 2 2”-2变成“0 -1 0 0”，这两个化简完就一模(mu)一样了。

借助map，用count()去找之前有没有一样的，若有，则两个前缀和中间的区间是合法的，记得max更新最大值即可。

CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7,M=37;
int n,m,x,ans;
vector<int> add(M);
map<vector<int>,int>f;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	f[add]=0;//!!!
	for(int i = 1;i<=n;i++){
		cin>>x;
		for(int j = 0;j<m;j++)
			if(x&(1<<j))add[j]++;//前缀和 
		if(x&1)
			for(int j = 0;j<m;j++)
				add[j]--;//末尾都为0
		if(f.count(add))ans=max(ans,i-f[add]);
		else f[add]=i;
	}
	cout<<ans<<'\n';
	return 0;
}