UVA291 The House Of Santa Claus题解

· · 题解

题解

本题题面较简单，总结起来就是一个“一笔画”问题，涉及到欧拉的某个图论定理（除起点和终点以外其他的点的度数都为偶数的无向图可以被不重复地“一笔画”），了解这个定理后使用 DFS 可以很轻松地切掉，题目时间限制很松所以基本啥 乱七八糟的 方法都能过。

但我今天要同时提供一种更奇特的方法——打表，时间复杂度 O(1)，如有更高效的解法请联系作者（我自己都不信）。

代码

上次没写生成代码被打回来了，其实 DFS 代码就是生成代码。 DFS 代码（你还别说，这玩意还真能过）：

#include<bits/stdc++.h>
using namespace std;
int n=5,m=8,a[15][15],b[25],c[15][15];
void f(int x,int y)
{
    a[x][y]=a[y][x]=1;
}//这个函数用于连接两条边
void dfs(int v,int q)//DFS部分
{
    int i;
    if(v>m)
    {
        for(i=1;i<=m+1;i++)
            cout<<b[i];
        cout<<endl;
        return;
    }//输出部分
    for(i=1;i<=n;i++)
    {
        if(!c[q][i]&&a[q][i])
        {
            b[v+1]=i;
            c[q][i]=c[i][q]=1;
            dfs(v+1,i);
            c[q][i]=c[i][q]=0;
        }
    }//搜索部分
}
int main()
{
    f(1,2);f(1,5);f(1,3);f(2,3);f(2,5);f(3,4);f(3,5);f(4,5);//维护图
    b[1]=1;
    dfs(1,1);
    return 0;
}

极简 2 行打表代码：

#include<cstdio>
int main(){puts("123153452\n123154352\n123451352\n123453152\n123513452\n123543152\n125134532\n125135432\n125315432\n125345132\n125431532\n125435132\n132153452\n132154352\n132534512\n132543512\n134512352\n134512532\n134521532\n134523512\n134532152\n134532512\n135123452\n135125432\n135215432\n135234512\n135432152\n135432512\n152134532\n152135432\n152345312\n152354312\n153123452\n153125432\n153213452\n153254312\n153452132\n153452312\n154312352\n154312532\n154321352\n154325312\n154352132\n154352312");}

后半部分为娱乐题解，请勿模仿！