Powered by:NEFU AB-IN

Link

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;
  }