[USACO20JAN] Farmer John Solves 3SUM

一道很新的题 题目链接

话说20JAN的USACO我没打

后来看到这题才知道$luogu$主题库5000+了$emmmmmm$

看到这种3sum的题，我们联想到之前做过的一道题SPOJ1296

这道题是把区间都存起来，然后二分

我们在这道题上考虑这个做法就很简单了

我们先处理出来$a[i]$，$a[j]$和在$(i,j)$区间内的一个$k$的和是0的情况，然后跑一边前缀和就可以了

处理方法很简单，就是把所有权值开一个$vector$存储他在哪里出现过，然后我们在$vector$上二分即可

复杂度$O(n^{2}logn)$

# include <cstdio>
# include <algorithm>
# include <cstring>
# include <cmath>
# include <climits>
# include <iostream>
# include <string>
# include <queue>
# include <stack>
# include <vector>
# include <set>
# include <map>
# include <cstdlib>
# include <ctime>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;
const int N=5005;
const int Zero=1e6+5;
const double eps=1e-7;
template <typename T> void read(T &x){
	x=0;int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
	x*=f;
}

# define int long long

int n,q;
int a[N];
int f[N][N];

vector<int> v[Zero<<1];

int getval(int l,int r,int tar){
	if(abs(tar)>1e6)return 0;
	int ntar=tar+Zero;
	return upper_bound(v[ntar].begin(),v[ntar].end(),r)-v[ntar].begin()-(upper_bound(v[ntar].begin(),v[ntar].end(),l)-v[ntar].begin());
}

signed main()
{
	read(n),read(q);
	Rep(i,1,n)read(a[i]),v[a[i]+Zero].push_back(i);
	Rep(i,1,n)
		Rep(j,1,n){
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]; 
			if(j-i>=2)f[i][j]+=getval(i,j-1,-a[i]-a[j]);
		}
	
	Rep(i,1,q){
		int l,r;
		read(l),read(r);
		printf("%lldn",f[r][r]-f[l-1][r]-f[r][l-1]+f[l-1][l-1]);	
	}
	return 0;
} 

但是这个代码交上去只有51分

为什么呢？$N\le 6000$不是显然$n^{2}logn$死了

我们再看题，已知的最快算法是$O(n^2)$

所以我们想$n^2$算法

大概是因为受了上面那个SPOJ的题的影响吧，后来做这题的时候一直在和$n^{2}logn$较真

后来才发现这个$n^2$算法这么简单…

看代码就知道了——无需解释

# include <cstdio>
# include <algorithm>
# include <cstring>
# include <cmath>
# include <climits>
# include <iostream>
# include <string>
# include <queue>
# include <stack>
# include <vector>
# include <set>
# include <map>
# include <cstdlib>
# include <ctime>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;
const int N=5005;
const int Zero=1e6;
const double eps=1e-7;
template <typename T> void read(T &x){
	x=0;int f=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
	x*=f;
}

# define int long long

int n,q;
int a[N];
int f[N][N];
int cnt[Zero*2+5];

signed main()
{
	read(n),read(q);
	Rep(i,1,n)read(a[i]),a[i]+=Zero;
	Rep(i,1,n){
		Rep(j,i+1,n){
			if(a[i]+a[j]<=3*Zero&&a[i]+a[j]>=Zero)f[i][j]=cnt[Zero*3-a[i]-a[j]];
			cnt[a[j]]++;
		}
		Rep(j,i+1,n)cnt[a[j]]--;
	}
	Rep(i,1,n)
		Rep(j,1,n)
			f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
	while(q--){
		int l,r;
		read(l),read(r);
		printf("%lldn",f[r][r]-f[l-1][r]-f[r][l-1]+f[l-1][l-1]);	
	}
	return 0;
}

最后

以上就是忧郁皮带为你收集整理的[USACO20JAN] Farmer John Solves 3SUM的全部内容，希望文章能够帮你解决[USACO20JAN] Farmer John Solves 3SUM所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。