Spoj-陣列的最大子集

我正在解決這個spoj問題。 http://www.spoj.com/problems/MAXSUB/ 我所有的測試工作正常，但我在錯誤的答案錯誤。我試圖改變我的代碼很多，但仍然得到了WA。當即時通訊添加總和，以防止溢出我採取mod.Should我這樣做？Spoj-陣列的最大子集

> my algorithm: 
> sum of all +ve num will be the maximum sum. 
> if there is no +ve number after sorting take the last element as the max number. 
> case 1: last element is -ve. 
>  number of subsets=number of times it occurs 
> case 2: last element is 0. 
>  cnt=number of 0's. 
>  number of subsets=2^cnt-1(excluding the null set)

任何人都可以幫忙嗎？

#include<iostream> 
#include<cstdio> 
#include<deque> 
#include<algorithm> 
#include<math.h> 

#define MOD 1000000009 


using namespace std; 
typedef long long int L; 
int main(){ 
int t; 
L n; 
scanf("%d",&t); 
while(t--){ 
    scanf("%lld",&n); 
    L arr[51000],sum=0LL; 
    L cnt=1LL; 

    for(int i=0;i<n;i++){ 
     scanf("%lld",&arr[i]); 
     if(arr[i]>0){ 
      sum+=(long long)arr[i]; 
      sum%=MOD; 
     // f=1; 
     } 
    } 
     sort(arr,arr+n); 
     if(sum==0){//this is to check if there is no +ve num 
      sum=arr[n-1]; 
      for(int j=n-2;j>=0;j--){ 
       if(sum==arr[j]) 
        cnt++; 
       else 
        break; 
      } 
      if(sum==0){//this is to check if the maximum num is 0 
       L num=1; 
       for(int k=0;k<cnt;k++){ 
        num=(L)(num*2)%MOD;//if sum==0 then num of subset is 2^cnt-1 
       }//decrementing 1 from 2^cnt coz we do not include null set 
       cnt=num-1; 
       } 
      } 
      cnt=cnt%MOD; 
    printf("%lld %lld\n",sum,cnt); 
}

}

來源

2013-08-25 KenAdams

這是一個編程問題，或在spoj.com有關馬虎英語的問題？ –

我沒有逐行讀取你的代碼行，但我認爲你錯過了一個情況下，至少 -

在那裏可以輸入正數和零，這種情況下的答案應該是2^(# of zeros)。

來源

2013-08-25 09:06:14 RoBa

謝謝!!我的代碼被接受了:) – KenAdams

Spoj-陣列的最大子集

回答

相關問題