暴力

6分思路

先暴力一下，如果说第$a_i$个数的值是$x_j$，那么暴力找出来剩下每一个数的值是多少，如果是幸运数字，就$sum++$，最后用$sum$更新$ans$即可，$O(K^2N^2)$ 6分TLE

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],b[15],n,m;
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
	int ans=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	{
		int sum=1;
		for(int k=i-1,now=b[j];k>=1;k--)
		{
			now=a[k]-now;
			for(int dfs=1;dfs<=m;dfs++)if(now==b[dfs])sum++;
		}
		for(int k=i+1,now=b[j];k<=n;k++)
		{
			now=a[k]-now;
			for(int dfs=1;dfs<=m;dfs++)if(now==b[dfs])sum++;
		}
		ans=max(ans,sum);
	}
	printf("%lld\n",ans);
	return 0;
}

AC思路

注意到这样可能会有很多次重复计算，秉着算过了就不要再算的理念，我们尝试优化一下。对于一种相同的情况，$a_1$的值一定是固定的，我们只需要开一个map存储当$a_1$为$i$的时候有多少个数是幸运数字。很明显直接求的常数复杂度大约$1\times10^9$左右……但是我们可以反着算，枚举每一个数，当他是每一种幸运数字的时候$a_1$是多少，每一次更新$ans$即可。$O(NM)$满分AC

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],b[15],x[N],n,m;
map<int,int>v;
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
	for(int i=1;i<n;i++)x[i+1]=a[i]-x[i];//当a1是0的时候ai是多少 
	int ans=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
	{
		if(i&1)v[b[j]-x[i]]++,ans=max(ans,v[b[j]-x[i]]);//如果说他是奇数位上的，他和a1是减法的关系，即a1-ai==x 
		else   v[x[i]-b[j]]++,ans=max(ans,v[x[i]-b[j]]);//反之是加法关系 
	}
	printf("%lld\n",ans);
	return 0;
}

甚至比暴力还短……