0

長さ N の N 本の棒で正方形を作れるかどうかを調べるプログラムを書いています。私はビットマスクを使用したので、そこに入れる大きな入力が簡単になりました。何らかの理由で、私のバックトラッキング コードは何も返さず、この行の「bitmask & (1 << vec[i])」には入りません。最近知ったのですが、情報がありません。

PD: 私は英語を話せません。文法と構文の問題で申し訳ありません。

ありがとう

// 10364 - Square.cpp: archivo de proyecto principal.
#include "stdafx.h"
#include <stdio.h>
#include <vector>

using namespace std;

vector<int> vec;
int bitmask,casos,palitos,suma,maximo;
bool analiza(int analizado,int lados)// lados =cantidad lados analizados, contador
{
    if (analizado==maximo)
    {
        analizado=0;
        lados++;
    }
    if(lados==4)
    {
        printf("yes\n");
        return true;
    }

        for (int i=0;i<palitos;i++)
        {
            if (!(bitmask & (1 << i)))
            {
                if (analizado+vec[i]<=maximo)
                {
                    bitmask | (1 << i);
                    if(analiza(analizado+1,lados))
                        return true;
                    bitmask & ~(1 << i);

                }
            }

        }
        return false;
        //prender: bitmask | (1 << indice)
        //apagar: bitmask & ~(1 << indice)
        /*comparar: bitmask & (1 << indice)*/
}
int main()
{
    freopen("in.txt","rt",stdin);
    freopen("out.txt","wt",stdout);

    scanf("%d\n",&casos);
    for(int i=0;i<casos;i++)
    {
        scanf("%d",&palitos);
        vec.clear();
        vec.resize(palitos);
        suma=0;
        for(int j=0;j<palitos;j++)
        {
            scanf("%d",&vec[j]);
            suma+=vec[j];
        }
        if(suma%4!=0)
            printf("no\n");
        else{
            bitmask=0;
            maximo=suma/4;
            analiza(0,0);
            }


    }


    return 0;
}
4

1 に答える 1

2

ビットマスクを初期化したことがないようです。ビットマスクがたまたま 0 の場合、ループに入ることはありません。これは問題の一部のようです。bitmask が 0 で、 bitwise を使用しているため、単に '0' に単純化すること
もできます。したがって、常に true と評価されるため、その条件全体を排除できます。 さらに、ビットマスクを正しい方法で使用しているようには見えません。ビットマスクを使用してベクトルを作成する場合、関連するビットのみを保持するように、ビットマスクのビットの少なくとも 1 つを 1 に等しくする必要があります。次に、ビットシフトすると、ベクトル内の対象ビットがオンかオフかがわかります。(bitmask & (1 << i)andif
and

于 2012-10-23T04:21:41.547 に答える