小
面前有 堆石子排成一排,每堆石子的数量从左到右依次为 。小
面前有 堆石子排成一排,每堆石子的数量从左到右依次为 。两人面前的石子总数相同,即
。每个人都可以对自己面前的石子堆进行任意次合并操作,两个人的操作次数可以不同。
合并操作指将连续的若干堆相邻石子合并为一堆。
请你确定一个最大的整数 ,满足:
- 小 停止所有操作后,面前恰好有 堆石子,每堆石子的数量从左到右依次为 。
- 小 停止所有操作后,面前恰好有 堆石子,每堆石子的数量从左到右依次为 。
- 对于 , 均成立。
输出这个
的最大可能值。输入格式
第一行包含两个整数
。第二行包含
个整数 。第三行包含
个整数 。输出格式
一个整数,表示
的最大可能值。数据范围
前三个测试点满足
。所有测试点满足
, , 。
数据范围 全部和加起来 <=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; }