18华南理工校赛 K 小马哥的超级盐水

https://www.nowcoder.com/acm/contest/94/K

sum(ai)/sum(bi) = x/y

<=>

sum(ai*yi-bi*x) = 0

跟这题有点类似 https://www.nowcoder.com/acm/contest/93/I

总值分成两部分，x+y=k。(这里k=0)

求出前半部分值为x的情况，求出后半部分值为y的情况。

c++ map 记录

时间复杂度

原来：2^n

现在：

分成大小最接近的两部分，每部分分别有(n+1)/2 , n/2 个数

2^( (n+1)/2 ) + 2^(n/2) + 对于第二部分的每个值y，得找第一部分值为k-y的情况数目，其中第一部分的值是排序的，寻找需要O(log( 2^( (n+1)/2 ) )=O( (n+1)/2 ) ，总共需要 O( (n+1)/2 * 2^(n/2) )。

所以第一部分的数目为(n+1)/2比较好，否则部分时间复杂度：O( n/2 * 2^((n+1)/2) )

关于结果是否使用高精度：

假设最坏的情况，35个数中，ai*yi-bi*x=1的数有18个，ai*yi-bi*x=-1的数有17个，如y=2,x=3,b=3,a=4或5。

则结果为：

　　　C(18,17)*C(17,17) + C(18,16)*C(17,16) + … + C(18,0)*C(17,0)

<=　　C(18,18)*C(18,18) + C(18,17)*C(18,17) + … + C(18,0)*C(18,0)

<=　　( C(18,18)+C(18,17)+…+C(18,0) ) ^ 2

= 2^36

long long 能解决

这数值比我想象中的要小

也许这个方案不是值最大的方案，但感觉这就是值最大的方案……

dfs：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <list>
 6 #include <stack>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <algorithm>
12 #include <iostream>
13 using namespace std;
14 
15 map<long,long long> f;
16 long p[35],q[35],n,m,x,y;
17 long long sum;
18  
19 void dfs(long step,long a,long b)
20 {
21     if (step==m)
22         f[a*y-b*x]++;
23     else
24     {
25         dfs(step+1,a,b);
26         dfs(step+1,a+p[step],b+q[step]);
27     }  
28 }
29  
30 void DFS(long step,long a,long b)
31 {
32     if (step==n)
33         sum+=f[-a*y+b*x];
34     else
35     {
36         DFS(step+1,a,b);
37         DFS(step+1,a+p[step],b+q[step]);
38     }  
39 }
40  
41 int main()
42 {
43     map<long,long long>::iterator j;
44     long t,i;
45     long long total;
46     scanf("%ld",&t);
47     while (t--)
48     {
49         scanf("%ld%ld%ld",&n,&x,&y);
50         for (i=0;i<n;i++)
51             scanf("%ld%ld",&p[i],&q[i]);
52         m=(n>>1)+1;
53         f.clear();
54         sum=0;
55         dfs(0,0,0);
56         DFS(m,0,0);
57         printf("%lld
",sum-1);
58     }
59     return 0;
60 }

位运算：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <list>
 6 #include <stack>
 7 #include <vector>
 8 #include <set>
 9 #include <map>
10 #include <queue>
11 #include <algorithm>
12 #include <iostream>
13 using namespace std;
14 
15 map<long,long long> f;
16 long p[35],q[35],n,m,mm,x,y;
17 long long sum;
18  
19 int main()
20 {
21     long t,i,j,pp,qq;
22     scanf("%ld",&t);
23     while (t--)
24     {
25         scanf("%ld%ld%ld",&n,&x,&y);
26         for (i=0;i<n;i++)
27             scanf("%ld%ld",&p[i],&q[i]);
28         f.clear();
29         sum=0;
30         m=(n+1)>>1;
31         for (i=0;i<(1<<m);i++)
32         {
33             pp=0; qq=0;
34             for (j=0;j<m;j++)
35                 if (((i>>j) & 1)==1)
36                 {
37                     pp+=p[j];
38                     qq+=q[j];
39                 }
40             f[pp*y-qq*x]++;
41         }
42          
43         mm=n>>1;
44         for (i=0;i<(1<<mm);i++)
45         {
46             pp=0; qq=0;
47             for (j=0;j<mm;j++)
48                 if (((i>>j) & 1)==1)
49                 {
50                     pp+=p[m+j];
51                     qq+=q[m+j];
52                 }
53             sum+=f[-pp*y+qq*x];
54         }
55         printf("%lld
",sum-1);
56     }
57     return 0;
58 }

超时：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <set>
 7 #include <map>
 8 #include <queue>
 9 #include <stack>
10 #include <algorithm>
11 #include <iostream>
12 using namespace std;
13  
14 //actually a=3,b=4,5 ; x=2,y=3 ÐèÒª¸ß¾«¶È
15 //10000*10000*35
16 map<unsigned long,long long> f;
17 stack<pair<unsigned long,long long> > st;
18  
19 int main()
20 {
21     map<unsigned long,long long>::iterator j;
22     long t,n,x,y,i,a,b,c;
23     scanf("%ld",&t);
24     while (t--)
25     {
26         scanf("%ld%ld%ld",&n,&x,&y);
27         f[0]=1;
28         for (i=1;i<=n;i++)
29         {
30             scanf("%ld%ld",&a,&b);
31             c=a*y-b*x;
32             while (!st.empty())
33                 st.pop();
34             for (j=f.begin();j!=f.end();j++)
35                 st.push(make_pair(j->first,j->second));
36             while (!st.empty())
37             {
38                 f[st.top().first+c]+=st.top().second;
39                 st.pop();
40             }
41         }
42         printf("%lld
",f[0]-1);
43     }
44     return 0;
45 }

内存超限：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <vector>
 6 #include <set>
 7 #include <map>
 8 #include <queue>
 9 #include <stack>
10 #include <algorithm>
11 #include <iostream>
12 using namespace std;
13  
14 //actually a=3,b=4,5 ; x=2,y=3 ÐèÒª¸ß¾«¶È
15 //10000*10000*35
16 map<unsigned long,long long> f,f1;
17 stack<pair<unsigned long,long long> > st;
18  
19 int main()
20 {
21     map<unsigned long,long long>::iterator j;
22     long t,n,x,y,i,a,b,c;
23     long long total;
24     scanf("%ld",&t);
25     while (t--)
26     {
27         scanf("%ld%ld%ld",&n,&x,&y);
28         f[0]=1;
29         for (i=1;i<=n/2;i++)
30         {
31             scanf("%ld%ld",&a,&b);
32             c=a*y-b*x;
33             while (!st.empty())
34                 st.pop();
35             for (j=f.begin();j!=f.end();j++)
36                 st.push(make_pair(j->first,j->second));
37             while (!st.empty())
38             {
39                 f[st.top().first+c]+=st.top().second;
40                 st.pop();
41             }
42         }
43          
44         f1[0]=1;
45         for (i=1;i<=(n+1)/2;i++)
46         {
47             scanf("%ld%ld",&a,&b);
48             c=a*y-b*x;
49             while (!st.empty())
50                 st.pop();
51             for (j=f1.begin();j!=f1.end();j++)
52                 st.push(make_pair(j->first,j->second));
53             while (!st.empty())
54             {
55                 f1[st.top().first+c]+=st.top().second;
56                 st.pop();
57             }
58         }
59         total=0;
60         for (j=f1.begin();j!=f1.end();j++)
61             total+=f1[j->second]*f[-f1[j->first]];
62         printf("%lld
",total-1);
63     }
64     return 0;
65 }