1

我正在解决这个 spoj 问题。 http://www.spoj.com/problems/MAXSUB/ 我所有的测试用例都能正常工作，但我在 spoj 中得到了错误的答案。我试图改变我的代码很多，但仍然得到了 WA。当我添加总和以防止溢出时，我正在服用 mod。我应该这样做吗？

> 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);
}

}

4

1 回答 1

0

I didn't read your code line by line, but I think you missed one case at least -

There can be both positive numbers and zeros in the input, in such case the answer should be 2^(# of zeros).

于 2013-08-25T09:06:14.950 回答