P1432 倒水问题

admin

https://www.luogu.org/problemnew/show/P1432

题目描述
假定两个水壶 A 和 B ，供水量不限。可以使用三种方法装水：

给一个水壶装水；
把一个水壶倒空；
从一个水壶倒进另一个水壶。
当从一个水壶倒进另一个水壶时，如果第一个水壶倒空，或者第二个水壶装满就不能再倒了。例如，一个水壶 A 是 5 加仑和另一个水壶 B 是 6 加仑，水量是 8 加仑，则从水壶 A 倒进水壶 B 时，让水壶B充满水而水壶 A 剩 3 加仑水。

问题由3个参数： C_a， C_b和 N ，分别表示水壶 A 和 B 的容量，目标水量 N 。解决问题的目标是，给出一系列倒水的步骤，使水壶 B 中的水量恰好是 N 。

输入输出格式
输入格式：
第一行为数据组数 T 。

接下来的 T行，每行三个数字 C_a， C_b和 N ，意义如题目所示。
T 不超过 30 组， 0<C_a≤N≤C_b≤1000 ，且 C_a和 C_b 互质。

输出格式：
输出共为 T 行，第一个数字为要达成的完成次数 a_i（题目保证存在解）。
接下来 a_i 个数字，表示各种操作：

1操作: fill A 意为给 AA 灌满水
2操作: fill B
3操作: empty A 意为将 AA 中水倒空
4操作: empty B
5操作: pour B A 意为将 B 中水倒到 A 中（直到 AA 满或者 BB 中水没有剩余）
6操作: pour A B输入输出样例
输入样例#1：
2
3 5 4
5 7 3
输出样例#1：
6 2 5 3 5 2 5
6 1 6 1 6 4 6
输入样例#2：
1
26 29 11
输出样例#2：
22 1 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6
说明
开启了spj。

如果你的方案比答案优，会提示UKE，此时请联系管理员修改数据。

如果你的方案比答案差，分数会相应减损。

张笑宇

当从一个水壶倒进另一个水壶时，如果第一个水壶倒空，或者第二个水壶装满就不能再倒了。例如，一个水壶 A 是 5 加仑和另一个水壶 B 是 6 加仑，水量是 8 加仑，则从水壶 A 倒进水壶 B 时，让水壶B充满水而水壶 A 剩 3 加仑水。
什么意思啊？？？

张笑宇

为什么一个数据中第二个数据就都是0了呢？？？

1. #include<iostream>
   
2. using namespace std;
   
3. int t,i,j,k,v;
   
4. const int mx=100010;
   
5. const int mm=2010;
   
6. const int tt=35;
   
7. int n[mx],a[mx],b[mx],f[mm][mm];///n次数
   
8. int ka[tt],kb[tt],kn[tt];
   
9. bool bb[mm][mm],bbb;///f情况
   
10. int head,tail,va,vb,nn;
    
11. void cle()///clear
    
12. {
    
13.     for (int ic=0; ic<=mx-2; ic++)
    
14.     {
    
15.         a[ic]=0,b[ic]=0,n[ic]=0;
    
16.     }
    
17.     for (int ic=1; ic<=mm-2; ic++)
    
18.         for (int id=1; id<=mm-2; id++)
    
19.         {
    
20.             f[ic][id]=0,bb[ic][id]=0;
    
21.         }
    
22.     head=1,tail=2,bbb=true;
    
23. }
    
24. void pp()
    
25. {
    
26.     for (int ii=1; ii<=10; ii++)
    
27.         cout<<a[ii]<<" "<<b[ii]<<" "<<n[ii]<<endl;
    
28. }
    
29. void pp2()
    
30. {
    
31.     for (k=1;k<=10;k++)
    
32.         for (v=1;v<=10;v++) cout<<bb[k][v];
    
33. }
    
34. int main()
    
35. {
    
36.     cin>>t;
    
37.     for (int it=1; it<=t; it++)
    
38.     {
    
39.         cin>>ka[it]>>kb[it]>>kn[it];
    
40.         va=ka[it],vb=kb[it],nn=kn[it];///va,vb容量 nn B中目标水量
    
41.         cle();///pp2();
    
42.         ///cout<<head<<" "<<tail<<" "<<va<<" "<<vb<<" "<<nn<<" ";
    
43.         while (head<=tail&&bbb)
    
44.         {
    
45.             ///目前搜索head
    
46.             if (b[head]==nn)
    
47.             {
    
48.                 cout<<n[head]<<" ";
    
49.                 for (int ib=1; ib<=n[head]; ib++) cout<<f[head][ib]<<" ";
    
50.                 cout<<endl;
    
51.                 bbb=false;
    
52.             }
    
53.             for (i=1; i<=6&&bbb; i++)
    
54.             {
    
55.                 if (i==1&&a[head]!=va&&!bb[va][b[head]])
    
56.                 {
    
57.                     n[tail]=n[head]+1;
    
58.                     a[tail]=va;
    
59.                     b[tail]=b[head];
    
60.                     bb[va][b[head]]=true;
    
61.                     for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
    
62.                     f[tail][n[tail]]=i;
    
63.                     tail++;
    
64.                 }
    
65.                 if (i==2&&b[head]!=vb&&!bb[a[head]][vb])
    
66.                 {
    
67.                     n[tail]=n[head]+1;
    
68.                     b[tail]=vb;
    
69.                     a[tail]=a[head];
    
70.                     bb[a[head]][vb]=true;
    
71.                     for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
    
72.                     f[tail][n[tail]]=i;
    
73.                     tail++;
    
74.                 }
    
75.                 if (i==3&&a[head]!=0&&!bb[0][b[head]])
    
76.                 {
    
77.                     n[tail]=n[head]+1;
    
78.                     a[tail]=0;
    
79.                     b[tail]=b[head];
    
80.                     bb[a[head]][vb]=true;
    
81.                     for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
    
82.                     f[tail][n[tail]]=i;
    
83.                     tail++;
    
84.                 }
    
85.                 if (i==4&&b[head]!=0&&!bb[a[head]][0])
    
86.                 {
    
87.                     n[tail]=n[head]+1;
    
88.                     b[tail]=0;
    
89.                     a[tail]=a[head];
    
90.                     bb[a[head]][vb]=true;
    
91.                     for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
    
92.                     f[tail][n[tail]]=i;
    
93.                     tail++;
    
94.                 }
    
95.                 if (i==5&&b[head]!=0&&!bb[a[head]+b[head]][0])
    
96.                 {
    
97.                     bb[a[head]+b[head]][0]=true;
    
98.                     if (va-a[head]>=b[head])///B倒完了
    
99.                     {
    
100.                         n[tail]=n[head]+1;
     
101.                         b[tail]=0;
     
102.                         a[tail]=a[head]+b[head];
     
103.                         for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
     
104.                         f[tail][n[tail]]=i;
     
105.                         tail++;
     
106.                     }
     
107.                     else
     
108.                     {
     
109.                         n[tail]=n[head]+1;
     
110.                         a[tail]=va;
     
111.                         b[tail]=b[head]-(va-a[head]);
     
112.                         for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
     
113.                         f[tail][n[tail]]=i;
     
114.                         tail++;
     
115.                     }
     
116.                 }
     
117.                 if (i==6&&a[head]!=0&&!bb[0][a[head]+b[head]])
     
118.                 {
     
119.                     bb[0][a[head]+b[head]]=true;
     
120.                     if (vb-b[head]>=a[head])///A倒完了
     
121.                     {
     
122.                         n[tail]=n[head]+1;
     
123.                         a[tail]=0;
     
124.                         b[tail]=b[head]+a[head];
     
125.                         for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
     
126.                         f[tail][n[tail]]=i;
     
127.                         tail++;
     
128.                     }
     
129.                     else
     
130.                     {
     
131.                         n[tail]=n[head]+1;
     
132.                         a[tail]=a[head]-(vb-b[head]);
     
133.                         b[tail]=vb;
     
134.                         for (j=1; j<=n[head]; j++) f[tail][j]=f[head][j];
     
135.                         f[tail][n[tail]]=i;
     
136.                         tail++;
     
137.                     }
     
138.                 }
     
139.             }
     
140.             pp();
     
141.             head++;
     
142.         }
     
143.     }
     
144.     return 0;
     
145. }
     

复制代码