秋招每日一题T21——倒水问题

题目描述

有三个杯子，容量分别为 A,B,C。

初始时，C 杯装满了水，而 A,B 杯都是空的。

现在在保证不会有漏水的情况下进行若干次如下操作：

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

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

输入格式
输入包含多组测试数据。

每组数据占一行，包含三个整数 A,B,C。

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

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

思路

〇本题是上海交通大学考研复试上机题。
①注意读题，可以进行的操作是：将一个杯子 x 中的水倒到另一个杯子 y 中，当 x 空了或者 y 满了时就停止（满足其中一个条件才停下）。x和y可以是a、b、c当中的任意一个。
②因此可以使用暴力搜素的方法解题，最后的答案是杯子C中的水的状态有多少种，因此可以用一个集合set来记录状态。
③进行搜索时，需要判重，判重的方法是当前的状态是否已经被记录过了。注意，进行判重时看的是a和b的状态是否已经被记录过了，因为相同的c仍然可能对应不同的状态。
④剩下的就是模拟倒水的过程进行搜索，即，如果x杯中有水，判断其他两个杯子是否能够被它倒满，倒不满就倒一部分。

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
int A,B,C;
typedef pair<int,int> PII;
set<int> cV;
set<PII> ab;
void dfs(int a,int b,int c){//A,B,C代表当前杯中容量 
	if(ab.count({a,b})){
		return;
	}
	ab.insert({a,b});
	cV.insert(c);
	if(a){
		if(a+b <= B){
			dfs(0,a+b,c);
		}
		else{
			dfs(a-B+b,B,c);
		}
		
		if(a+c <= C){
			dfs(0,b,a+c);
		}
		else{
			dfs(a-C+c,b,C);
		}
	}
	if(b){
		if(a+b<=A){
			dfs(a+b,0,c);
		}	
		else{
			dfs(A,b-A+a,c);
		}
		
		if(b+c<=C){
			dfs(a,0,b+c);
		}
		else{
			dfs(a,b-C+c,C);
		}
	}
	if(c){
		if(a+c<=A){
			dfs(a+c,b,0);
		}
		else{
			dfs(A,b,c-A+a);
		}
		
		if(b+c<=B){
			dfs(a,b+c,0);
		}
		else{
			dfs(a,B,c-B+b);
		}
	}	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>A>>B>>C){
		dfs(0,0,C);
		cout<<cV.size()<<endl;
		cV.clear();
		ab.clear();
	}
	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
65
66
67
68
69
70
71
72
73
74