首页 > 其他 > 详细

UVa-1152 4 Values Whose Sum Is 0

时间:2018-07-17 20:58:27      阅读:161      评论:0      收藏:0      [点我收藏+]

一道学校里div2 的训练题

题目大意是给出n(<=4000)行四列的数字(<=2^28),我们需要从每列中选取一个数字使得四个数字之和恰好为0,问有多少种选取方案。

所有组合是4000的4次方直接爆掉了,但是可以二分。(O(N)=N^2logN)

左边2列(4000*4000种)中各取一个数字求和,右边同理,排序后一个从小到大,另一个从大到小找。开始错的地方是没有考虑类似 "1 1 1 1"与 "-1 -1 -1 " 这种应该加 3*4 而不是++,于是就用了结构体数组将相同的和存在一起并计数。

技术分享图片
 1 #include<bits/stdc++.h>
 2 #define EPS 1e-9
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int INF=0x3f3f3f3f;
 7 const int MAXN=16000000+6;
 8 
 9 long ans;
10 long Bin[2][MAXN];
11 int cnt[2];
12 int tot[2];
13 int raw[4][4003];
14 int N;
15 
16 struct Node{
17     int dat,num;
18 }BN[2][MAXN];
19 
20 void getBin(int t){
21     for(int i=0;i<N;++i){
22         for(int j=0;j<N;++j){
23             Bin[t][cnt[t]++]=raw[2*t][i]+raw[2*t+1][j];
24         }
25     }
26 }
27 
28 int main(){
29     //freopen("data.out","w",stdout);
30     int Test;
31     scanf("%d",&Test);
32     for(int cntT=1;cntT<=Test;++cntT){
33         ans=0;cnt[0]=cnt[1]=0;
34         tot[0]=tot[1]=0;
35         scanf("%d",&N);
36         for(int i=0;i<N;++i){
37             for(int j=0;j<4;++j){
38                 scanf("%d",&raw[j][i]);
39             }
40         }
41         getBin(0);
42         getBin(1);
43         sort(Bin[0],Bin[0]+cnt[0]);
44         sort(Bin[1],Bin[1]+cnt[1]);
45 
46         for(int i=0;i<2;++i){
47             BN[i][tot[i]].dat=Bin[i][0];
48             BN[i][tot[i]++].num=1;
49             for(int j=1;j<cnt[i];++j) {
50                 if(Bin[i][j]==BN[i][tot[i]-1].dat)
51                     BN[i][tot[i]-1].num+=1;
52                 else{
53                     BN[i][tot[i]].dat=Bin[i][j];
54                     BN[i][tot[i]++].num=1;
55                 }
56             }
57         }
58 
59         for(int i=0,j=tot[1]-1;i<tot[0];++i){
60             while(BN[0][i].dat+BN[1][j].dat>0&&j>=1) j--;
61             if(BN[0][i].dat+BN[1][j].dat>0) break;
62 
63             if(BN[0][i].dat+BN[1][j].dat==0) ans+=BN[0][i].num*BN[1][j].num;
64             else if(BN[0][i].dat+BN[1][j].dat<0) continue;
65         }
66         printf("%ld\n",ans);
67         if(cntT!=Test) puts("");
68     }
69     return 0;
70 }
View Code

数据会爆而且又是求和的性质啥的就应该往二分想。

UVa-1152 4 Values Whose Sum Is 0

原文:https://www.cnblogs.com/Kiritsugu/p/9325766.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!