摘要
Title: 3511. 倒水问题
Tag: DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

3511. 倒水问题

题意

有三个杯子，容量分别为 A,B,C。
初始时，C 杯装满了水，而 A,B 杯都是空的。
现在在保证不会有漏水的情况下进行若干次如下操作：
将一个杯子 x 中的水倒到另一个杯子 y 中，当 x 空了或者 y 满了时就停止（满足其中一个条件才停下）。
请问，在操作全部结束后，C 中的水量有多少种可能性。
思路

思路：设置好初始状态，便开始DFS，每个状态都搜一下6个倒水动作，用哈希表储存状态，防止遍历多次
- 状态存储：因为A,B,C最多4000，所以可以用一个1e12的数来存储状态，也就是每4位存一个数，比如2,2,4，就是000200020004

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-08-09 20:41:11
* @FilePath: \Acwing\3511\3511.cpp
* @LastEditTime: 2022-08-09 21:44:52
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int B = 10000;

signed main()
{
    IOS;
    int a, b, c;
    while (cin >> a >> b >> c)
    {
        unordered_set<int> st; // 记录A,B,C状态
        unordered_set<int> s;  // 记录C的状态

        vector<int> x = {0, 0, c};      // 初始状态
        vector<int> bottle = {a, b, c}; // 瓶子容量

        function<int(vector<int>)> get = [&](vector<int> x) {
            return x[0] * B * B + x[1] * B + x[2];
        }; // 将瓶子的状态转换为long long 型

        function<void(vector<int>)> dfs = [&](vector<int> x) {
            st.insert(get(x));
            s.insert(x[2]);

            for (int i = 0; i < 3; ++i)
            {
                for (int j = 0; j < 3; ++j)
                {
                    if (i != j)
                    {
                        vector<int> tmp(x);
                        // 倒水，从i往j倒
                        int water = min(tmp[i], bottle[j] - tmp[j]);
                        tmp[i] -= water;
                        tmp[j] += water;
                        if (!st.count(get(tmp)))
                            dfs(tmp);
                    }
                }
            }
        };

        dfs(x);

        cout << SZ(s) << '\n';
    }
    return 0;
}

3511. 倒水问题

题意

思路

代码