Bitmask函数

Question

我正在编写一个程序，以查找是否可以用N个长度为N的木棍制作一个正方形。我已经使用了Bitmask，因为它可以轻松实现我要输入的大量输入。由于某种原因，我的回溯代码不返回任何内容，在“ 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;
}

Answer 1

似乎没有初始化位掩码。如果位掩码恰好为0，那么您将永远不会进入循环。这似乎是问题的一部分。此外，由于位掩码为0，并且您正在使用按位(bitmask & (1 << i)，因此and可以简化为仅0。因此，可以消除整个if条件，因为它将始终评估为true。此外，您似乎没有以正确的方式使用位掩码。您希望位屏蔽的位中至少有一个等于1，这样，当您使用位屏蔽and一些矢量时，您将只保留相关位。然后，如果您进行了位偏移，则可以确定向量中有趣的位是打开还是关闭。