发布时间: 2017年7月3日 10:23 时间限制: 3000ms 内存限制: 128M
描述XJTU校园内新开一家商店，可是来了一位刁钻的顾客要购买商品A和商品B。关于商品的质量，共有n个评分，每个评分即一个整数来表示该产品在某一方面的质量。商品A的评分表示为a1~an，商品B表示为b1~bn。
令店老板为难的是，这个刁钻的顾客要求商品A的总评分比商品B的总评分多2的正整数幂，这样他才会购买。好在店老板可以任意定义每个评分的重要性，也就是赋予这个评分一个权值（所有商品采用同一套权值）。重要性只有三档：不重要、一般和重要，它们的权值分别是1，3，5。商品的总评分就是它们在n个方面的评分乘以相应权重之和。店老板能否找到一组权重，使得商品A的总评分比商品B的总评分多2的正整数幂？
对于第一组样例，权重{1,5}是一个可行解，此时A总分为22，B总分为6，22-6=16。
输入多组数据。 第一行是一个整数n，商品评分的数量。 第二行是n个整数a1~an，表示商品A的评分。 第三行是n个整数b1~bn，表示商品B的评分。 其中： 2<=n<=20 1<=ai,bi<=10000000
输出如果可以找到一组满足要求的权重，输出“Yes”，否则输出“No”，不包括引号。
样例输入1 复制 2 2 4 1 1 2 3 2 3 1 样例输出1 Yes No对于这道题目，直接暴力枚举，时间复杂度是O(3^(20))是会爆掉的，而如果我们采用折半枚举地方法，时间复杂度只有O(3^20 * LOG(3^20))
详细解释bai's白书上有例子。直接附AC代码：
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long LL; LL a[22],b[22],mi[33]; LL sa[int(1e7)]; LL sb[int(1e7)]; int cnta; int cntb; int n; LL pow(LL x,LL p){ LL ans = 1; while(p){ if(p & 1){ ans *= x; } x *= x; p >>= 1; } return ans; } void sp(LL arr[],int& cnt,int l,int r){ int n = r - l + 1; for(int S = 0;S < pow(3,n);S++){ int tmpS = S; int ans = 0; for(int i = 0;i < n;i++){ int w = tmpS%3; ans += (2*w+1)*(a[i + l] - b[i + l]); tmpS /= 3; } arr[cnt++] = ans; } } int main(){ mi[0] = 1; for(int i = 1;i <= 30;i++){ mi[i] = mi[i-1] * 2; } while(~scanf("%d",&n)){ cnta = cntb = 0; for(int i = 0;i < n;i++){ scanf("%lld",&a[i]); } for(int i = 0;i < n;i++){ scanf("%lld",&b[i]); } sp(sa,cnta,0,n/2); sp(sb,cntb,n/2+1,n-1); sort(sb,sb + cntb); for(int i = 0 ;i < cnta;i++){ for(int t = 1;t <= 30;t++){ LL t_mi = mi[t]; int f = 0; if((sa[i] == t_mi && cntb == 0 )|| *lower_bound(sb,sb+cntb,t_mi - sa[i]) == t_mi - sa[i]){ f = 1; } if(f){ puts("Yes"); goto end; } } } puts("No"); end:; } return 0; }
