Couple Cover

Time Limit:?3000MS

?

Memory Limit:?524288KB

?

64bit IO Format:?%I64d & %I64u

Description

方寶寶有n個籃球，每個籃球上寫有一個值ai。他第一次從n個籃球中取出1個，不放回。第二次再在剩余的籃球中取出一個。 （每個球被取概率相同）。如果這兩個球上的值的乘積大于等于p，他會變得高興，然后請大家吃飯。否則方寶寶會不高興， 然后暴食暴飲變得更胖。 當(dāng)然為了方寶寶的健康（被請吃飯），我想取一個合適的p值，使方寶寶高興。 那么問題來了，現(xiàn)在有m個數(shù):p1，p2……pm.對于每個p值有多少種選法使方寶寶高興。 于是善（毒）良（瘤）的出題人把這個問題交給了你們。

Input

第一個行的數(shù)是n，第二行是個籃球上面的值ai，第三行是m，第四行p1,?p2,?p3……pm. 1<=n<=10^6,1<=m<=10^6,1<=pi<=3*10^6,1<=ai<=10^6

Output

第i行輸出對于當(dāng)前pi值，方寶寶能贏的方案數(shù)。

Sample Input

輸入: 5 4 2 6 1 3 4 1 3 5 8 輸出： 20 18 14 10 輸入： 2 5 6 2 30 31 輸出： 2 0

Source

Educational Codeforces Round 14 好不容易看到一道CF的中文題（原題是英文的） 果斷就做了…… 題意： 有n個籃球 不放回取出兩個球a b 對于m組提問 問對每個pi a*b>=pi的取法有多少種 思路： 根據(jù)樣例可以分析出來(a=5,b=6)和(a=6,b=5)是兩種方法 所以算出來的正常值應(yīng)該乘2 而且時間限制3000ms 內(nèi)存限制也很大 就想到暴力了 開兩個3e6的數(shù)組 計算之前先預(yù)處理一下 最后輸出n*(n-1)-sum[n-1] ?這個式子就已經(jīng)是乘2的了 1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<math.h> 5 #include<string.h> 6 #include<string> 7 #include<map> 8 #include<set> 9 #include<vector> 10 #include<queue> 11 #define M(a,b) memset(a,b,sizeof(a)) 12 using namespace std; 13 typedef long long ll; 14 const int maxn=3e6+5; 15 ll cnt[maxn]; 16 ll sum[maxn]; 17 ll n,m,a,max_=-1; 18 int main(){ 19 scanf("%I64d",&n); 20 for(int i=0;i<n;i++){ 21 scanf("%d",&m); 22 cnt[m]++; 23 if(m>max_) max_=m; 24 } 25 for(int i=0;i<=max_;i++){ 26 for(int j=0;j<=max_;j++){ 27 if(i*j>maxn) break; 28 sum[i*j]+=cnt[i]*cnt[j]; 29 if(i==j) sum[i*j]-=cnt[j]; 30 } 31 } 32 for(int i=1;i<=maxn;i++) 33 sum[i]+=sum[i-1]; 34 scanf("%I64d",&m); 35 for(int i=0;i<m;i++){ 36 scanf("%d",&a); 37 printf("%I64d\n",n*(n-1)-sum[a-1]); 38 } 39 return 0; 40 } 41 /* 42 43 5 44 4 2 6 1 3 45 4 46 1 3 5 8 47 48 2 49 5 6 50 2 51 52 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/general10/p/5767346.html

總結(jié)

以上是生活随笔為你收集整理的[ An Ac a Day ^_^ ] CodeForces 691F Couple Cover 花式暴力的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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