ACWing每日一题.3511

ACWing每日一题.3511

题目：

有三个杯子，容量分别为 A,B,C。初始时，C杯装满了水，而 A,B杯都是空的。现在在保证不会有漏水的情况下进行若干次如下操作：

将一个杯子 x中的水倒到另一个杯子 y 中，当 x 空了或者 y满了时就停止（满足其中一个条件才停下）。

请问，在操作全部结束后，C中的水量有多少种可能性。

输入格式

• 输入包含多组测试数据。
• 每组数据占一行，包含三个整数 A,B, C。

输出格式

• 每组数据输出一个结果，占一行。

数据范围

• 0≤A,B,C≤4000。
• 每个输入最多包含 100 组数据。

输入样例：

0 5 5
2 2 4
1
2

输出样例：

2
3
1
2

题解：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

typedef long long LL;

const LL B = 10000; // 每个水桶最大4000，所以采用一个LL类型的数来存储三个水桶的状态

int C[3];
unordered_set<LL> states; // 三个桶的状态
unordered_set<int> cs;    // 桶C的状态

LL get(int c[])
{
        return c[2] * B * B + c[1] * B + c[0];
}

void pour(int c[], int i, int j)
{
        int t = min(c[i], C[j] - c[j]);
        c[i] -= t, c[j] += t;
}

/*
        深度搜索：
                输入：三个水桶内已经装水的容量 数组
                功能：
                        1. 将三个水桶的状态加入states;
                        2. 将C水桶此时所装水的容量加入cs;
                        3. 三个水桶之间互相倒水，如果出现不在states内的状态，就对此时的状态进行fds;
*/
void dfs(int c[])
{
        states.insert(get(c));
        cs.insert(c[2]);

        int a[3];
        for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                        if (i != j)
                        {
                                memcpy(a, c, sizeof a);
                                pour(a, i, j); // i水桶给j水桶倒水
                                if (!states.count(get(a)))
                                        dfs(a);
                        }
}

int main()
{
        while (cin >> C[0] >> C[1] >> C[2])
        {
                states.clear();
                cs.clear();
                int c[3] = {0, 0, C[2]}; // 三个桶内水的容量
                dfs(c);
                cout << cs.size() << endl;
        }

        return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64