刁鉆的顧客

發(fā)布時間: 2017年7月3日 10:23?? 時間限制: 3000ms?? 內(nèi)存限制: 128M

描述

XJTU校園內(nèi)新開一家商店，可是來了一位刁鉆的顧客要購買商品A和商品B。關(guān)于商品的質(zhì)量，共有n個評分，每個評分即一個整數(shù)來表示該產(chǎn)品在某一方面的質(zhì)量。商品A的評分表示為a1~an，商品B表示為b1~bn。

令店老板為難的是，這個刁鉆的顧客要求商品A的總評分比商品B的總評分多2的正整數(shù)冪，這樣他才會購買。好在店老板可以任意定義每個評分的重要性，也就是賦予這個評分一個權(quán)值（所有商品采用同一套權(quán)值）。重要性只有三檔：不重要、一般和重要，它們的權(quán)值分別是1，3，5。商品的總評分就是它們在n個方面的評分乘以相應(yīng)權(quán)重之和。店老板能否找到一組權(quán)重，使得商品A的總評分比商品B的總評分多2的正整數(shù)冪？

對于第一組樣例，權(quán)重{1,5}是一個可行解，此時A總分為22，B總分為6，22-6=16。

輸入

多組數(shù)據(jù)。
第一行是一個整數(shù)n，商品評分的數(shù)量。
第二行是n個整數(shù)a1~an，表示商品A的評分。
第三行是n個整數(shù)b1~bn，表示商品B的評分。
其中：
2<=n<=20
1<=ai,bi<=10000000

輸出

如果可以找到一組滿足要求的權(quán)重，輸出“Yes”，否則輸出“No”，不包括引號。

樣例輸入1?復(fù)制 2 2 4 1 1 2 3 2 3 1 樣例輸出1 Yes No

對于這道題目，直接暴力枚舉，時間復(fù)雜度是O(3^(20))是會爆掉的，而如果我們采用折半枚舉地方法，時間復(fù)雜度只有O(3^20 * LOG(3^20))

詳細(xì)解釋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; }

總結(jié)

以上是生活随笔為你收集整理的2017西安交大ACM小学期 刁钻的顾客[3进制+折半枚举]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。