题解 P2383 【狗哥玩木棒】

· · 题解

首先这是一道dfs深度优先搜索的题目，非常好做，和入门模板dfs差不多……主要是搜四次，确定能否拼成正方形。这里是搜索每一根木棒，看能不能拼成木棍。因为题目要求每一根都要用，所以没有死路，不会浪费时间。看代码和注释吧：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<iomanip>//库多调一点总是好的
#define ll long long
#define ld long double
using namespace std;
ll l[1001],n,m,c=0,maxx=0,bj[1001],dd;
//bj用于标记这根木棍是否用于组成正方形的一条边，组成了其他边就不能用来组成这条边了。maxx用来存储木棍总长，每条边的边长自然就是(maxx/4)。l记录长度，dd用于dfs时判断是否拼成边
void f(ll x,ll k)//x是一条边还剩多少没拼,已经用了几条棒
{
    if(x==0)//如果拼成边了就退出去，并记录已经拼好
    {
        c=1;//表示是否拼成边
        dd=1;//也是表示是否拼成边……
        return;
    }
    for(ll i=k+1;i<=m;i++)//从上次k条木棒往后搜，可以省下时间
    {
        if(l[i]<=x&&bj[i]==0)
        //如果可以用来拼而不会超出每边的长度，且没在其它边用过
        {
            bj[i]=1;
            //先记下来用过。“是不是没必要啊，已经从k往后搜了啊？”别急，往后看
            f(x-l[i],k+1);//搜索，剩下的边长，以及下一根木棒（其实是我打程序时用来调试的23333）
            if(dd==1)return;
            //如果已经拼成了就退出整个搜索，并保留之前用过的木棒的标记
            bj[i]=0;//如果没拼成，回溯时标记这根木棒没用过
        }
    }
}

int main()
{
    cin>>n;
    for(ll i=1;i<=n;i++)
    {
        memset(bj,0,sizeof(bj));//每组数据都要初始化bj，l和maxx
        memset(l,0,sizeof(l));
        maxx=0;
        cin>>m;
        for(ll o=1;o<=m;o++)
        {
            cin>>l[o];
            maxx+=l[o];//记下木棒长度和
        }
        if(floor(((ld)maxx)/4)*4!=maxx)
        //如果木棒总长除以4后取整，再乘4，和原来的木棒总长不符，即表示木棒总长不是4的倍数，所以无法拼成正方形（题目要求用上每根木棒）
        {
            cout<<"no"<<endl;
            continue;//输出“no”后跳过这组数据的剩下内容
        }
        for(ll o=1;o<=4;o++)//循环4次，拼4条边
        {
            c=0;
            dd=0;//初始化一下是否拼成边
            f(maxx/4,0);//搜索一条边的长，还没有用过棒
            if(c==0)//如果没有拼成，就退出去
            {
                break;
            }
        if(c==1)//如果拼成
        {
            for(ll o=1;o<=m;o++)
            {
                if(bj[o]==0)
                {
                    cout<<"no"<<endl;
                    //如果有任何一根木棒没有用过
                    break;
                }
            }
            cout<<"yes"<<endl;
        }
        else cout<<"no"<<endl;
    }
    return 0;
}