-2

オンラインジャッジで古典的な部分和問題を試しています。ただし、今回の違いは、n<=30 であるため、最大操作は 30*2^30 まで可能です。私はすでに以下の作業コードを持っています。ただし、プログラムの制限時間は 1 秒で、私のプログラムは 0.5 秒から 1.1 秒の間で動きます。できる限りコードを高速化しようとしましたが、これにより TLE が発生します。コードをさらに高速化および最適化する方法について何かヒントはありますか? 前もって感謝します。

#include <iostream>
#include <cstdio>
using namespace std;

unsigned power(unsigned x, unsigned y){        //pow function
    unsigned sum=x;
    for (int i=1;i<=y-1;i++)
        sum*=x;
    return sum;
}

int main(){
    unsigned t, n, p, sum, sum2, tmpsum=0;
    unsigned bars[32];
    bool found;
    scanf("%u", &t);
    while (t--){
        tmpsum=0;
        found=false;
        scanf("%u %u", &n, &p);
        for (int i=0;i<p;i++){
            scanf("%u",&bars[i]);
            tmpsum+=bars[i];
        }
        if (tmpsum<n)found=false;
        unsigned end=power(2,p)-1;          //counting from the end and from the start
        for (unsigned i=0;i<power(2,p)&&tmpsum>=n;i++){       //counting from 1 to 2^n in binary
            sum=0;
            sum2=0;
            for (unsigned j=0;j<p;j++){
                if (i&(1<<j))
                    sum+=bars[j];
                if (end&(1<<j))     //counting from the end and start at the same time
                    {sum2+=bars[j];end--;}
            }
            if (sum==n||sum2==n)
                {found=true;break;}
        }
        cout<<(found==true?"YES":"NO")<<endl;
    }
}
4

7 に答える 7

3

power(2,p)ループの外に移動します。

for (unsigned i=0;i<power(2,p)&&tmpsum>=n;i++)
                      ^^^^
于 2013-02-18T08:57:48.050 に答える
3

2 の次数を計算するためにビット シフトを使用します。

于 2013-02-18T08:58:39.610 に答える
2

醜いコードを書いても高速にはなりません。ステートメントを別の行に分けます。つまり、次のように置き換えます{sum2+=bars[j];end--;}。

{
    sum2 += bars[j];
    --end;
}

質問に移ります: あなたの主要な時間の損失はおそらくここにあります:

for (unsigned i=0;i<power(2,p)&&tmpsum>=n;i++){

power(2, p)特に優れたコンパイラがない限り、ループのサイクルごとに1回計算する必要がありますが、これはまったく必要ありません。事前に計算します。

int pow2p = power(2, p);
for (unsigned i=0;i<pow2p&&tmpsum>=n;i++){

また、この方法で 2 のべき乗を行うのは非常に遅いため、<<代わりに ( 1<<p == power(2, p)) を使用します。

編集これは受け入れられたので、他の回答/コメントからマイナーポイントをまとめます。

  1. Nim が指摘しているように、ループ中に変更も変更tmpsum>=nも行われないため、ループごとにチェックを行う必要はありません。ntmpsum

  2. Karthik T が指摘しているように、この行if (tmpsum<n)found=false;は冗長であり、この時点でfoundしかあり得ません。false

于 2013-02-18T09:00:39.237 に答える
1

他の人が言ったことに加えて、分岐を避けてください。例えば：

if (i&(1<<j))
    sum+=bars[j];

次のように書くことができます

sum+=bars[j] * ((i&(1<<j))>>j);

確かに、コードを読むのはさらに難しくなります。

于 2013-02-18T09:30:15.417 に答える
0 
if (tmpsum<n)found=false;

この行は何も達成せず、foundすでにfalse.

1<<j

2回計算されているのですが、結果を保存することで1回に減らすことができます。

于 2013-02-18T09:00:01.480 に答える
0

power(2,p)まず、for ループから抜け出すことができます

for (unsigned i=0, end=power(2,p); i<end && tmpsum>=n; i++)
于 2013-02-18T09:01:11.813 に答える
-1
  1. power(2, p) は 1 << p に等しい

  2. sum と sum2 をレジスタ変数として定義します。

    符号なし合計、sum2 を登録します。

于 2013-02-18T09:01:52.357 に答える