题意

之后补充。

分析

这是一条很好的考察递归（或者说搜索）的题目。它的两个过程（建立初步解，验证）都用到了递归（或者说运用递归可以相当程度的减少代码量）。

具体实现见代码。注意，为了使用std::pair的比较操作符，代码交换了x、y的位置。

代码

/*

ID: samhx1

LANG: C++14

TASK: wormhole

*/

#include <bits/stdc++.h>

#define MP make_pair

#define PB push_back

#define fi first

#define se second

#define ZERO(x) memset((x), 0, sizeof(x))

#define ALL(x) (x).begin(),(x).end()

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

using namespace std;

using ll = long long;

using ull = unsigned long long;

using pi = pair<ll,ll>;

using pii = pair<ll, pi>;

// Need to write editorial about it.

template<typename T>

T readint()

{

    T tmp; cin>>tmp;

    return tmp;

}

int n,ans=0;

pi pnt[15];

ll nxt[15],partner[15];

int vis[15];

bool check(int spnt)

{

    if(vis[spnt]>=2) return true;

    vis[spnt]++;

    if(nxt[spnt]==-1) return false;

    else

    {

        vis[nxt[spnt]]++;

        rep(i,1,n)

        {

            if(i!=nxt[spnt] && partner[nxt[spnt]]==partner[i])

            {

                return check(i);

                break; // should not be executed.

            }

        }

    }

    return false;

}

bool check()

{

    for(int nowpnt=1;nowpnt<=n;++nowpnt)

    {

        memset(vis,0,sizeof(vis));

        if(check(nowpnt)) return true;

    }

    return false;

}

void solve(int dep)

{

    if(dep==n/2)

    {

        rep(i,1,n) if(partner[i]==-1) return;

        if(check())

        {

            //rep(i,1,n) cout<<partner[i]<<" ";

            //cout<<endl;

            //cout<<"Success!"<<endl;

            ans++;

        }

    }

    else

    {

        rep(i,1,n)

        {

            if(partner[i]==-1)

            {

                partner[i]=dep+1;

                rep(j,i+1,n)

                {

                    if(partner[j]!=-1) continue;

                    partner[j]=dep+1;

                    //printf("i=%d, j=%d: ",i,j);

                    //rep(k,1,n) cout<<partner[k]<<" ";

                    //cout<<endl;

                    solve(dep+1);

                    partner[j]=-1;

                }

                partner[i]=-1;

                break;

            }

        }

    }

}

int main()

{

    freopen("wormhole.in","r",stdin);

    freopen("wormhole.out","w",stdout);

    cin>>n;

    rep(i,1,n)

    {

        int x,y; cin>>x>>y;

        pnt[i]=MP(y,x); // WARN: x,y has been swapped.

    }

    sort(pnt+1,pnt+n+1);

    memset(nxt,-1,sizeof(nxt));

    rep(i,1,n)

    {

        if(i==n) continue;

        if(pnt[i+1].fi==pnt[i].fi) nxt[i]=i+1;

    }

    memset(partner,-1,sizeof(partner));

    solve(0);

    cout<<ans<<endl;

    return 0;

}

巴特西

「日常训练」「小专题·USACO」 Wormholes（1-4）

题意

分析

代码

最新文章

热门文章