2022年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第2题）
2022年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第2题）
第2题
（容器分水）有两个容器，容器 1 的容量为为 a 升，容器 2 的容量为 b 升；同时允许下列的三种操作，分别为：
- FILL(i)：用水龙头将容器 i(i∈1,2)灌满水；
- DROP(i)：将容器 i 的水倒进下水道；
- POUR(i,j)：将容器 i 的水倒进容器 j（完成此操作后，要么容器 j 被灌满，要么容器 i 被清空）。
求只使用上述的两个容器和三种操作，获得恰好 c 升水的最少操作数和操作序列。上述 a、b、c 均为不超过 100 的正整数，且 c≤max{a,b}。
试补全程序。
#include<bits/stdc++.h>usingnamespacestd;constintN=110;intf[N][N];intans;inta,b,c;intinit;intdfs(intx,inty){if(f[x][y]!=init)returnf[x][y];if(x==c||y==c)returnf[x][y]=0;f[x][y]=init-1;f[x][y]=min(f[x][y],dfs(a,y)+1);f[x][y]=min(f[x][y],dfs(x,b)+1);f[x][y]=min(f[x][y],dfs(0,y)+1);f[x][y]=min(f[x][y],dfs(x,0)+1);intt=min(a-x,y);f[x][y]=min(f[x][y],①);t=min(x,b-y);f[x][y]=min(f[x][y],②);returnf[x][y];}voidgo(intx,inty){if(③)return;if(f[x][y]==dfs(a,y)+1){cout<<"FILL(1)"<<endl;go(a,y);}elseif(f[x][y]==dfs(x,b)+1){cout<<"FILL(2)"<<endl;go(x,b);}elseif(f[x][y]==dfs(0,y)+1){cout<<"DROP(1)"<<endl;go(0,y);}elseif(f[x][y]==dfs(x,0)+1){cout<<"DROP(2)"<<endl;go(x,0);}else{intt=min(a-x,y);if(f[x][y]==④){cout<<"POUR(2,1)"<<endl;go(x+t,y-t);}else{t=min(x,b-y);if(f[x][y]==⑤){cout<<"POUR(1,2)"<<endl;go(x-t,y+t);}elseassert(0);}}}intmain(){cin>>a>>b>>c;ans=1<<30;memset(f,127,sizeoff);init=**f;if((ans=dfs(0,0))==init-1)cout<<"impossible";else{cout<<ans<<endl;go(0,0);}}①处应填（）
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
②处应填（）
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
③处应填（）
A. x == c || y == c
B. x == c && y == c
C. x >= c || y >= c
D. x >= c && y >= c
④处应填（）
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
⑤处应填（）
A. dfs(x + t, y - t) + 1
B. dfs(x + t, y - t) - 1
C. dfs(x - t, y + t) + 1
D. dfs(x - t, y + t) - 1
分析：
本题使用记忆化搜索（DFS）计算最少操作数，并通过递归输出操作序列。
- 状态定义：
f[x][y]表示两个容器当前水量分别为x和y时，达到任一容器水量为c的最少操作数。 - DFS 过程：对每种操作（FILL、DROP、POUR）进行状态转移，取最小值。
- 对于
POUR(2,1)，倒水量t = min(a - x, y)，转移到(x+t, y-t)，操作数加 1。 - 对于
POUR(1,2)，倒水量t = min(x, b - y)，转移到(x-t, y+t)，操作数加 1。
- 对于
- GO 过程：根据
f[x][y]的值逆向推导操作序列，直到达到目标状态（x==c || y==c）。
答案及题解：
- ①对应
POUR(2,1)的状态转移，应为dfs(x+t, y-t) + 1，选A。 - ②对应
POUR(1,2)的状态转移，应为dfs(x-t, y+t) + 1，选C。 - ③为递归终止条件，即任一容器水量为
c，选A。 - ④判断是否为
POUR(2,1)转移而来，应比较f[x][y] == dfs(x+t, y-t) + 1，选A。 - ⑤判断是否为
POUR(1,2)转移而来，应比较f[x][y] == dfs(x-t, y+t) + 1，选C。
专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}