题解 P2383 【狗哥玩木棒】

· · 题解

这道题看似是\rm DFS，但是可以用\rm BFS做

——套用另一位某大^D法^F师^S \frak{Phaethon}\ \Omega的激情句式

前言

\rm{STL}\bold{\text{大法好！}}

思路

由于一个无趣的赌注以及对\rm BFS普适度的证明，在这里提供一个\rm BFS的解法。

大体思路（第一次尝试）

一看到本题，粗略的思路是使用结构体（当然最后没有用）来存放每一种木棒摆放状态：4条边上的已经填上的木棒总长，以及当前状态使用的最后一根木棒的序号。如果某条边上可以放上下一根木棒（每条边的长度可以提前算出），那就将放上该木棒的状态入队。如果最后每条边都被填满了，那就跳出并输出yes。如果队列空了也没有被填满，那就输出no。

一个非常明显的优化是预判断木棒能不能组成一个正方形，只需要提前求出木棒总长模4即可。另一个明显的优化是，因为每条边的次序不重要，所以我们将四条边类似于“优先级”的编号1,2,3,4，第一根木棒放在第一条边，第二根木棒可以放在第一、第二条边……第i根木棒可以放在第一、第二条边，并且如果第二条边已经有木棒了，那就也可以放在第三条边；如果第三条边已经有木棒了，那就也可以放在第四条边。这样，就可以避免存在冗余情况的出现（例如\{12,3,0,0\}与\{12,0,3,0\}并存），并且由于第一根木棒已经放在第一条边了，也可以避免状态的重复（这里指的重复是指对于木棒序号的重复，而非对于木棒长度，或者说每边木棒总长的长度）。

然后是实现。\rm BFS需要队列来实现（在这里套了\rm STL的queue，不知可百度）。前面说的用结构体存储状态，权衡再三（由于懒）还是用了嵌套pair来实现（如图示）。

定义是这样的：

#define pr4 pair<pair<int,int>,pair<int,int> >      //四条边
#define stix pair<pr4,int>  //四条边及最后木棒编号

所以，正方形的四条边分别是t.first.first.first，t.first.first.second，以此类推。

最后是代码。核心\rm BFS代码如下：

bool b=false;   //b:是否已完成
while(!q.empty) //q:BFS队列
{
    stix t=q.front();   //t:队首
    int v=t.second+1;   //v:需要添加的木棒编号，a数组用以存储木棒
    //第一、二条边
    if(t.边+a[v]<=s)     //s:边长
    {
        stix l=t;       //l:临时状态
        l.边+=a[v];      //添加木棒
        ++l.second;     //更新木棒编号
        if(win(l,s))    //如果已经填满每条边
        {
            cout<<"yes\n";
            b=true;
            break;      //跳出搜索
        }
        q.push(l);      //状态入队
    }
    //第三、四条边
    if(t.前一条边&&t.边+a[v]<=s)
    //↑=t.前一条边!=0，即前一条边已使用
    {
        ↑↑↑idem↑↑↑
    }
    q.pop();            //标准出队
}
if(!b)
    cout<<"no\n";

优化一（第二次尝试）

当我们满怀期待地把上面代码提交上去时，我们发现——

这不奇怪，queue的吞内存是出了名的。接下来我们需要进行优化。

第一个优化思路是，先将a数组进行从小到大的排序，然后在添加木棒是加一个判断——只有加入当前木棒时这条边刚好会被填满，或者加入木棒后这条边还能再添加下一条木棒，才可以加入这条木棒。这个思路还是较好理解的。因此，原先的长度判断就变成了这样：

    if(t.边+a[v]==s||(t.边+a[v]+a[v+1]<=s))
    ...

优化二（第三次尝试）

然而这个优化似乎对\rm MLE没什么补救（笑）可能是数据对\rm BFS太毒了吧。

通过几次数据撞击（为什么不公开数据……？），很可能数据中木棒长度重复次数相当多，这时我们的去重优化就不管用了。怎么办？上set。

（关于set可以参考我的另一篇题解，在这里只要知道set是一个（类）hash，支持insert()和count()操作就足够了。

我们先定义一个以stix状态为索引的set，然后每次加木棒后都判断这个状态有没有在这个set中出现过，没有的话才能入队，然后将这个状态加入set，这样就能更有效地去重了。修改部分入队代码如下：

    if(!r.count(l)) //r:判重set
    {
        q.push(l);
        r.insert(l);
    }

然后呢？然后就\color{#FFF}\colorbox{#5eb95e}A了啊。

代码实现

由于前面讲的够多了，那么不如直接上完整代码了：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<set>
#define pr4 pair<pair<int,int>,pair<int,int> >
#define stix pair<pr4,int>
using namespace std;

queue<stix> q;
set<stix> r;

int sread()                                 //慢读优化（？
{
    int a;
    cin>>a;
    return a;
}

stix crea(int a,int b,int c,int d,int i)    //构造一个stix状态，省代码
{
    return make_pair(make_pair(make_pair(a,b),make_pair(c,d)),i);
}

bool win(stix t,int s)                      //判断t状态下四条边（边长为s）是否已经填满
{
    return t.first.first.first==s&&t.first.first.second==s&&t.first.second.first==s&&t.first.second.second==s;
}

int main()
{
    ios::sync_with_stdio(0);
    int Phaethon_is_a_dalao=sread();    //读入测试组数
    while(Phaethon_is_a_dalao--)
    {
        while(!q.empty())   q.pop();    //每次清空BFS队列
        bool b=false;
        int n=sread(),s=0;              //n:木棒数
                                        //这里先把s作为木棒总长的计数，之后再/4
        int a[30];
        for(int i=0;i<n;++i)
        {
            a[i]=sread();
            s+=a[i];
        }
        if(s%4!=0)                      //判断是否能组成一个正方形
        {
            cout<<"no\n";
            continue;
        }
        s/=4;
        sort(a,a+n);
        q.push(crea(a[0],0,0,0,0));
        r.insert(crea(a[0],0,0,0,0));   //先将初状态入队、入set
        while(!q.empty())
        {
            stix t=q.front();
            int v=t.second+1;
            if(t.first.first.first+a[v]==s||(v<n-1&&t.first.first.first+a[v]+a[v+1]<=s))
            {
                stix l=t;
                l.first.first.first+=a[v];
                ++l.second;
                if(win(l,s))
                {
                    cout<<"yes\n";
                    b=true;
                    break;
                }
                if(!r.count(l))
                {
                    q.push(l);
                    r.insert(l);
                }
            }
            if(t.first.first.second+a[v]==s||(v<n-1&&t.first.first.second+a[v]+a[v+1]<=s))
            {
                stix l=t;
                l.first.first.second+=a[v];
                ++l.second;
                if(win(l,s))
                {
                    cout<<"yes\n";
                    b=true;
                    break;
                }
                if(!r.count(l))
                {
                    q.push(l);
                    r.insert(l);
                }
            }
            if(t.first.first.second&&(t.first.second.first+a[v]==s||(v<n-1&&t.first.second.first+a[v]+a[v+1]<=s)))
            {
                stix l=t;
                l.first.second.first+=a[v];
                ++l.second;
                if(win(l,s))
                {
                    cout<<"yes\n";
                    b=true;
                    break;
                }
                if(!r.count(l))
                {
                    q.push(l);
                    r.insert(l);
                }
            }
            if(t.first.second.first&&(t.first.second.second+a[v]==s||(v<n-1&&t.first.second.second+a[v]+a[v+1]<=s)))
            {
                stix l=t;
                l.first.second.second+=a[v];
                ++l.second;
                if(win(l,s))
                {
                    cout<<"yes\n";
                    b=true;
                    break;
                }
                if(!r.count(l))
                {
                    q.push(l);
                    r.insert(l);
                }
            }
            q.pop();
        }
        if(!b)
            cout<<"no\n";
    }
    return 0;
}

附言