2019年信奥赛C提高组csp-s初赛真题及答案解析完善程序第2题第2题取石子Alice 和 Bob 两个人在玩取石子游戏。他们制定了 n条取石子的规则第 i条规则为如果剩余石子的个数大于等于 a[i]且大于等于 b[i]那么他们可以取走 b[i] 个石子。他们轮流取石子。如果轮到某个人取石子而他无法按照任何规则取走石子那么他就输了。一开始石子有 m个。请问先取石子的人是否有必胜的方法输入第一行有两个正整数分别为规则个数 n(1n64), 以及石子个数 m(≤10 7 10^7107)。接下来 n行。第 i行有两个正整数 a[i] 和 b[i]。(1≤a[i]≤10 7 10^7107,1≤b[i]≤64)。如果先取石子的人必胜那么输出 Win否则输出 Loss。提示可以使用动态规划解决这个问题。由于 b[i]不超过 64 ,所以可以使用 64位无符号整数去压缩必要的状态。status 是胜负状态的二进制压缩trans 是状态转移的二进制压缩。试补全程序。代码说明~表示二进制补码运算符它将每个二进制位的 0 变为 1、1 变为 0;而^表示二进制异或运算符它将两个参与运算的数中的每个对应的二进制位一一进行比较若两个二进制位相同则运算结果的对应二进制位为 0 ,反之为 1。ull 标识符表示它前面的数字是 unsigned long long 类型。#includecstdio#includealgorithmusingnamespacestd;constintmaxn64;intn,m;inta[maxn],b[maxn];unsignedlonglongstatus,trans;boolwin;intmain(){scanf(%d%d,n,m);for(inti0;in;i)scanf(%d%d,a[i],b[i]);for(inti0;in;i)for(intji1;jn;j)if(a[i]a[j]){swap(a[i],a[j]);swap(b[i],b[j]);}status①;trans0;for(inti1,j0;im;i){while(jn②){③;j;}win④;⑤;}puts(win?Win:Loss);return0;}①处应填 )A.0B.~0ullC.~0ull^1D.1②处应填 )A.a[j] iB.a[j] iC.a[j] !iD.a[j]1③处应填 )A.trans |1ull (b[j] - 1)B.status |1ull (b[j] - 1)C.status 1ull (b[j] - 1)D.trans 1ull (b[j] - 1)④处应填 )A.~status| transB.status transC.status | transD.~status trans⑤处应填 )A.trans status | trans ^ winB.status trans 1 ^ winC.trans status ^ trans | winD.status status 1 ^ win答案及题解①处应填C因为初始状态需要将第0位对应dp[0]设为0其余位对应负索引设为1以避免非法取子影响即~0ull ^ 1。②处应填B由于规则已按a排序每次循环只需将a[j]恰好等于当前i的规则加入即a[j] i。③处应填A将新规则的取子数b[j]对应的位在trans中置1即trans | 1ull (b[j] - 1)。④处应填D当前石子数i的胜负由是否存在一个可用规则使得取后状态为必败决定即~status trans非零则胜。⑤处应填D每计算完一个i需要将当前结果win移入status的最低位同时丢弃最旧位即status status 1 ^ win。专栏推荐信奥赛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;}