[PA2021] Butelki 题解

Tjaweiof · 2024-10-19 13:42:21 · 题解

P9038 题解

题目传送门

容易发现一次操作之后必然有一个瓶子是满的或是空的，于是我们记 s=a+b+c，即橙汁的总量。假设满（空）的瓶子是第一个，则另外两个瓶子的橙汁的总量必为 s 或 s-a，故不同的状态数不超过 \max(A,B,C)，直接记忆化搜索即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout);
int A, B, C, a, b, c;
bool vis[100001][3][2];
int ans[100001];
struct Tjaweiof{
    int x, m;
    bool p;
    int t;
};
queue <Tjaweiof> q;
void pu(int a, int b, int c, int t){
    if (a + b <= A){
        q.push({c, 1, 0, t});
    }
    if (a + b >= A){
        q.push({a + b - A, 0, 1, t});
    }
    if (b + c <= B){
        q.push({a, 2, 0, t});
    }
    if (b + c >= B){
        q.push({b + c - B, 1, 1, t});
    }
    if (c + a <= C){
        q.push({b, 0, 0, t});
    }
    if (c + a >= C){
        q.push({c + a - C, 2, 1, t});
    }
    if (a + c <= A){
        q.push({a + c, 2, 0, t});
    }
    if (a + c >= A){
        q.push({b, 0, 1, t});
    }
    if (b + a <= B){
        q.push({b + a, 0, 0, t});
    }
    if (b + a >= B){
        q.push({c, 1, 1, t});
    }
    if (c + b <= C){
        q.push({c + b, 1, 0, t});
    }
    if (c + b >= C){
        q.push({a, 2, 1, t});
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> A >> B >> C >> a >> b >> c;
    memset(ans, -1, sizeof ans);
    ans[a] = 0;
    ans[b] = 0;
    ans[c] = 0;
    pu(a, b, c, 1);
    while (!q.empty()){
        auto u = q.front();
        q.pop();
        if (vis[u.x][u.m][u.p]){
            continue;
        }
        vis[u.x][u.m][u.p] = true;
        int na, nb, nc;
        if (!u.m){
            na = A * u.p;
            nb = u.x;
            nc = a + b + c - na - nb;
        } else if (u.m == 1){
            nb = B * u.p;
            nc = u.x;
            na = a + b + c - nb - nc;
        } else if (u.m == 2){
            nc = C * u.p;
            na = u.x;
            nb = a + b + c - nc - na;
        }
        if (ans[na] == -1){
            ans[na] = u.t;
        }
        if (ans[nb] == -1){
            ans[nb] = u.t;
        }
        if (ans[nc] == -1){
            ans[nc] = u.t;
        }
        pu(na, nb, nc, u.t + 1);
    }
    for (int i = 0; i <= C; i++){
        cout << ans[i] << " ";
    }
    return 0;
}