小 A 面前有 n 堆石子排成一排,每堆石子的数量从左到右依次为 a1,a2,,an

小 B 面前有 m 堆石子排成一排,每堆石子的数量从左到右依次为 b1,b2,,bm

两人面前的石子总数相同,即 a1+a2++an=b1+b2++bm

每个人都可以对自己面前的石子堆进行任意次合并操作,两个人的操作次数可以不同。

合并操作指将连续的若干堆相邻石子合并为一堆。

请你确定一个最大的整数 k,满足:

  • 小 A 停止所有操作后,面前恰好有 k 堆石子,每堆石子的数量从左到右依次为 a1,a2,,ak
  • 小 B 停止所有操作后,面前恰好有 k 堆石子,每堆石子的数量从左到右依次为 b1,b2,,bk
  • 对于 1ikai=bi 均成立。

输出这个 k 的最大可能值。

输入格式

第一行包含两个整数 n,m

第二行包含 n 个整数 a1,a2,,an

第三行包含 m 个整数 b1,b2,,bm

输出格式

一个整数,表示 k 的最大可能值。

数据范围

前三个测试点满足 1n,m10

所有测试点满足 1n,m1051ai,bi106a1+a2++an=b1+b2++bm106


数据范围   全部和加起来 <=10e6这里很重要,不是很大所以我们可以用哈希(桶排序思想)来做,记录每一次 si  出现的数,出现两次即可以形成一次合并。
还有一点就是nm  <=  10e5,最开始我还在暴力=.=, 这样看,我们不能使用n^2复杂度,只能考虑n或nlogn  这里之前讲过复杂度问题。
上代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100005],b[100005]; 
ll s1[100005],s2[100005];
ll s[1000005];
ll n,m;
int main()
{
	int i,j,k,l,ans=0,t;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		s1[i]=s1[i-1]+a[i];
		s[s1[i]]++;
	}
	for(i=1;i<=m;i++)
	{
		cin>>b[i];
		s2[i]=s2[i-1]+b[i];
		s[s2[i]]++;
	}
	for(i=1;i<1000005;i++)
	{
		if(s[i]==2)	ans++;
	}
//	t=1;
//	for(i=1;i<=n;i++)
//	{
//		for(j=t;j<=m;j++)
//		{
//			if(s1[i]==s2[j])
//			{
//				ans++;
//				t=j+1;
//				break;
//			}
//		}
//	}
	cout<<ans;
}