「日常训练」Equation（HDU-5937）

时间：2024-06-14 11:36:14

题意与分析

时隔一个月之后来补题。说写掉的肯定会写掉。

题意是这样的：给1~9这些数字，每个数字有\(X_i\)个，问总共能凑成多少个不同的等式\(A+B=C\)（\(A,B,C\)均为1位，\(1+2=3\)和\(2+1=3\)视为不同等式）？

这题的搜索稍微有一些技巧：先暴力再搜索，而不是起手就搜索。怎么个暴力呢？把所有能够构成\(A+B=C\)的情况先全部穷举出来，然后看先有的这些bricks的数目能不能够实现这些情况——这就是基础搜索了。两种情况：a)当前情形能够用，答案+1；b)当前情况无效，遍历下一个，答案不变。

然后就没有然后了，过了.jpg

场上竟然队伍没几个写这个的。。。被带榜了啊

代码

/*

 * Filename: hdu5937.cpp

 * Date: 2018-11-11

 */

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

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

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

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

#define MS(x,y) memset(x, y, sizeof(x))

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

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

struct Node

{

    int x,y,z;

    Node(int _x, int _y, int _z):

        x(_x), y(_y), z(_z) {}

};

vector<Node> vec;

void init()

{

    for(int i=1;i<=8;++i)

        for(int j=1;i+j<=9;++j)

            vec.PB(i,j,i+j);

}

int brick[15],ans=0;

void dfs(int pnt, int nans)

{

    if(pnt==vec.size()) { ans=max(nans, ans); return; }

    if(nans+vec.size()-pnt<=ans) return;

    int x=vec[pnt].x,

        y=vec[pnt].y,

        z=vec[pnt].z;

    if(brick[x]>0 && brick[y]>0 && brick[z]>0)

    {

        brick[x]--; brick[y]--; brick[z]--;

        if(brick[x]>=0 && brick[y]>=0 && brick[z]>=0) dfs(pnt+1, nans+1);

        brick[x]++; brick[y]++; brick[z]++;

    }

    dfs(pnt+1,nans); // This is important!

}

int

main()

{

    init(); //cout<<vec.size()<<endl;

    int T; cin>>T;

    rep(kase,1,T)

    {

        rep(i,1,9) cin>>brick[i];

        ans=0;

        dfs(0,0);

        cout<<"Case #"<<kase<<": "<<ans<<endl;

    }

    return 0;

}

相关文章