HDU - 1495 非常可乐（BFS，数学）

HDU - 1495 非常可乐（BFS，数学）

巨佬的数学解法

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int a,b,c;while(cin>>a>>b>>c&&(a&&b&&c)){
    a/=gcd(b,c);if(a&1) cout<<"NO"<<endl;else cout<<a-1<<endl;}return 0;
}

BFS

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
int w[3];
struct node
{
    int a,b,c,cnt;
};
bool st[N][N][N];
void bfs()
{
    memset(st,false,sizeof st);st[w[0]][0][0] = true;queue<node>que;que.push({
    w[0],0,0,0});while(que.size()){
    node t = que.front();que.pop();int a = t.a,b = t.b,c = t.c;if(a == b && c == 0 || a == c && b == 0 || b == c  && a == 0) //当其中一种平分的状态出现直接输出{
    cout << t.cnt << endl;return ;}for(int i = 0; i < 3; i ++) //枚举每一种倒水的情况 i -> jfor(int j = 0; j < 3; j ++){
    int d[3] = {
    a, b, c};if(i != j && (d[i] != 0 || d[j] != w[j])) // 不能自己倒自己且i杯子不为空，j杯子不能为满{
    int h = min(w[j] - d[j],d[i]);//倒入j最多的水量d[j] += h,d[i] -= h;if(!st[d[0]][d[1]][d[2]])que.push({
    d[0],d[1],d[2],t.cnt + 1}),st[d[0]][d[1]][d[2]] = true;}}}cout << "NO" << endl;
}
int main()
{
    while(cin >> w[0] >> w[1] >> w[2], w[0] + w[1] + w[2])//用数组存方便后面的判断{
    if(w[0] & 1) cout << "NO" << endl;//奇数肯定不能平分else bfs();}return 0;
}