UVa 1152 4 Values whose Sum is 0-白红宇

UVa 1152 4 Values whose Sum is 0

阅读量：5305 次

发布时间：2019-06-14

本文共 949 字，大约阅读时间需要 3 分钟。

题意：给出n，四个集合a,b,c,d每个集合分别有n个数，分别从a,b,c,d中选取一个数相加，问使得a+b+c+d=0的选法有多少种

看的紫书，先试着用hash写了一下，

是用hash[]记录下来a[i]+b[j]的值，

如果a[i]+b[j]>0,hash[a[i]+b[j]]=1

如果a[i]+b[j]<0,hash[-(a[i]+b[j])]=-1

再用一个hash0[]去储存c[i]+d[j] 这样只需要满足hash[i]==1||hash0[i]==-1或者hash[i]==-1,hash0[i]==1就可以了

可是这样写过不了样例，因为在选择的过程中，不一定只有一种选择的和为i，最后可能会将本应该符合题意的hash值覆盖掉

然后学习的lrj的代码，记录下所有a[]+b[]的值，在这个序列里面找-c[i]-d[j] 有多少个

1 #include
      
          2 #include
       
           3 #include
        
           4 #include 
         
            5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 #define mod=1e9+7;12 using namespace std;13 14 typedef long long LL;15 const int maxn=4000+5;16 int s[maxn*maxn];17 int a[maxn],b[maxn],c[maxn],d[maxn];18 19 int main(){20 int t,n,i,j,cnt;21 scanf("%d",&t);22 while(t--){23 scanf("%d",&n);24 for(i=0;i

View Code

转载于:https://www.cnblogs.com/wuyuewoniu/p/4367570.html

你可能感兴趣的文章

解决升级系统导致的 curl: (48) An unknown option was passed in to libcurl