网站开发用户功能分析,上海网络营销网站建设,企业短视频广告,wordpress综合类网站2022年信奥赛C提高组csp-s初赛真题及答案解析#xff08;完善程序第2题#xff09; 第2题
#xff08;容器分水#xff09; 有两个容器#xff0c;容器 1 的容量为为 a 升#xff0c;容器 2 的容量为 b 升#xff1b;同时允许下列的三种操作#xff0c;分别为#xf…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}。试补全程序。#includebits/stdc.husingnamespacestd;constintN110;intf[N][N];intans;inta,b,c;intinit;intdfs(intx,inty){if(f[x][y]!init)returnf[x][y];if(xc||yc)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);inttmin(a-x,y);f[x][y]min(f[x][y],①);tmin(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){coutFILL(1)endl;go(a,y);}elseif(f[x][y]dfs(x,b)1){coutFILL(2)endl;go(x,b);}elseif(f[x][y]dfs(0,y)1){coutDROP(1)endl;go(0,y);}elseif(f[x][y]dfs(x,0)1){coutDROP(2)endl;go(x,0);}else{inttmin(a-x,y);if(f[x][y]④){coutPOUR(2,1)endl;go(xt,y-t);}else{tmin(x,b-y);if(f[x][y]⑤){coutPOUR(1,2)endl;go(x-t,yt);}elseassert(0);}}}intmain(){cinabc;ans130;memset(f,127,sizeoff);init**f;if((ansdfs(0,0))init-1)coutimpossible;else{coutansendl;go(0,0);}}①处应填A. dfs(x t, y - t) 1B. dfs(x t, y - t) - 1C. dfs(x - t, y t) 1D. dfs(x - t, y t) - 1②处应填A. dfs(x t, y - t) 1B. dfs(x t, y - t) - 1C. dfs(x - t, y t) 1D. dfs(x - t, y t) - 1③处应填A. x c || y cB. x c y cC. x c || y cD. x c y c④处应填A. dfs(x t, y - t) 1B. dfs(x t, y - t) - 1C. dfs(x - t, y t) 1D. dfs(x - t, y t) - 1⑤处应填A. dfs(x t, y - t) 1B. dfs(x t, y - t) - 1C. dfs(x - t, y t) 1D. 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)转移到(xt, y-t)操作数加 1。对于POUR(1,2)倒水量t min(x, b - y)转移到(x-t, yt)操作数加 1。GO 过程根据f[x][y]的值逆向推导操作序列直到达到目标状态xc || yc。答案及题解①对应POUR(2,1)的状态转移应为dfs(xt, y-t) 1选A。②对应POUR(1,2)的状态转移应为dfs(x-t, yt) 1选C。③为递归终止条件即任一容器水量为c选A。④判断是否为POUR(2,1)转移而来应比较f[x][y] dfs(xt, y-t) 1选A。⑤判断是否为POUR(1,2)转移而来应比较f[x][y] dfs(x-t, yt) 1选C。专栏推荐信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html3、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
