/*    dfs实际上是个模拟 */ //len表示判断的是哪一位 ll dfs(ll len,int maxi,int k,int f){     //dp[len][k][f]存储的是到长度为len为止,第k位为0和第k位为1的数是多少     //maxi标志的是上一位模拟的数是不是等于num的这一位的数     /*        我们还是拿100来举例子,因为最高位我们得到的一定为1,所以传进来的时候maxi就是1        那么我们第一位既可以模拟0也可是模拟1        模拟0的时候,i != a[len]所以maxi = false,之后也都是false        我们下一位就可以模拟00X跟01X,剩下的类似        模拟1的时候,i == a[len]所以maxi = true        我们就可以模拟1XX        但是由于这时a[2] = 0所以只能模拟10X        差不多就已经很清楚了     */     //dp[len][k][f]这里其实就是记忆化搜索,如果之前出现过,就直接返回结果就好。     if(dp[len][k][f] != -1 && maxi == 0)         return dp[len][k][f];     //只有当第k位为1的情况这里才会加上1     if(!len)         return f;     ll cnt = 0;     int maxn = maxi ? a[len] : 1;     //i这里代表着第len位的数字是多少     //那么f||len == k && i就是判断这次模拟的数的第k位是否为1     for(int i = 0;i <= maxn;i++){         cnt += dfs(len - 1,maxi && i == a[len],k,f||len == k&&i);     }     //只有当maxi等于false的时候,我们模拟了下一位为0,1的全部情况,此时才更新dp的值     //表示不受之前的数的限制,所求的只是[0,1 << (len) - 1]]满足条件的数     return maxi ? cnt : dp[len][k][f] = cnt; } //二进制拆分数位,返回的结果是第k位为1的数总共有几个 ll div(ll num,int k){     memset(a,0,sizeof(a));     int index = 0;     while(num){         a[++index] = num % 2;         num /= 2;     }     return dfs(index,1,k,0); } E题最简单数位DP标程,本菜鸡的一点个人解读,希望可以帮到跟我一样的萌新新理解,个人一点愚见,如果有不正确的地方,还请大佬们们斧正ORZ

相关推荐

1.自我介绍2.介绍一下mcp,&nbsp;skills3.了解react哪些状态管理库4.对话是sse还是什么?是用fetch还是EventSource?5.ts中的any&nbsp;和&nbsp;unknown讲一讲6.是直接用组件库的组件还是自己封装了一些别的7.代码输出题1function&nbsp;main()&nbsp;{{var&nbsp;a&nbsp;=&nbsp;1let&nbsp;b&nbsp;=&nbsp;2}console.log(a);console.log(b);}main()console.log(a);8.什么是块级作用域&nbsp;全局作用域&nbsp;函数作用域9.代码输出题2for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(i);},&nbsp;100);}10.代码输出题3for&nbsp;(var&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;&amp;lt;&nbsp;5;&nbsp;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}11.代码输出题4for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{var&nbsp;temp&nbsp;=&nbsp;isetTimeout(()&nbsp;=&amp;gt;&nbsp;{console.log(temp);},&nbsp;100);}printText(i)}12.代码输出题5for(var&nbsp;i&nbsp;=&nbsp;0;i&nbsp;&amp;lt;&nbsp;5;i++){function&nbsp;printText(temp)&nbsp;{setTimeout(()&nbsp;=&amp;gt;&nbsp;{var&nbsp;temp&nbsp;=&nbsp;iconsole.log(temp);},&nbsp;100);}printText(i)}13.点击控制台输出题export&nbsp;default&nbsp;function&nbsp;App()&nbsp;{const&nbsp;[count,&nbsp;setCount]&nbsp;=&nbsp;useState(0)console.log('render',count)return&nbsp;(&lt;div&gt;&lt;h1&gt;{count}&lt;/h1&gt;{setCount(count&nbsp;+&nbsp;1)setTimeout(()&nbsp;=&amp;gt;&nbsp;console.log('setTimeout',&nbsp;count),&nbsp;1000)}}&amp;gt;+1&lt;/div&gt;)}//这个组件点击按钮后,控制台的输出顺序和值如下://&nbsp;1.&nbsp;render&nbsp;1&nbsp;(组件重新渲染,&nbsp;count&nbsp;更新为&nbsp;1)//&nbsp;2.&nbsp;setTimeout&nbsp;0&nbsp;(1秒后输出,注意这里是&nbsp;0&nbsp;而不是&nbsp;1)14.算法:给有序数组arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5],返回平方后的排序//&nbsp;有序数组平方后排序const&nbsp;arr&nbsp;=&nbsp;[-4,&nbsp;-1,&nbsp;0,&nbsp;3,&nbsp;5]function&nbsp;solution(arr)&nbsp;{const&nbsp;len&nbsp;=&nbsp;arr.lengthconst&nbsp;result&nbsp;=&nbsp;new&nbsp;Array(len)let&nbsp;left&nbsp;=&nbsp;0let&nbsp;right&nbsp;=&nbsp;len&nbsp;-&nbsp;1let&nbsp;index&nbsp;=&nbsp;len&nbsp;-&nbsp;1while&nbsp;(left&nbsp;&amp;lt;=&nbsp;right)&nbsp;{if&nbsp;(arr[left]&nbsp;*&nbsp;arr[left]&nbsp;&amp;gt;&nbsp;arr[right]&nbsp;*&nbsp;arr[right])&nbsp;{result[index]&nbsp;=&nbsp;arr[left]&nbsp;*&nbsp;arr[left]left++}&nbsp;else&nbsp;{result[index]&nbsp;=&nbsp;arr[right]&nbsp;*&nbsp;arr[right]right--}index--}return&nbsp;result}console.log(solution(arr));15.反问
查看14道真题和解析
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务