26-05-29思维周赛题解

周赛地址https://hydro.ac/d/codingSunday/contest原题链接T2:https://leetcode.cn/problems/container-with-most-water/description/T3:https://leetcode.cn/problems/unique-paths/description/T4:https://www.luogu.com.cn/problem/P15656周赛题解 2026/5/28A 题进制转换思路这题就是让你把一个十进制数转成二进制、四进制、八进制然后分别统计一些东西。具体看代码。代码#includeiostream#includestringusingnamespacestd;intmain(){longlongn;cinn;// 转二进制统计1的个数string bin;longlongtempn;while(temp0){binchar(0temp%2)bin;temp/2;}intcnt10;for(charc:bin){if(c1)cnt1;}// 转四进制计算数位之和string qua;tempn;while(temp0){quachar(0temp%4)qua;temp/4;}intsum0;for(charc:qua){sumc-0;}// 转八进制统计7出现的次数string oct;tempn;while(temp0){octchar(0temp%8)oct;temp/8;}intcnt70;for(charc:oct){if(c7)cnt7;}coutcnt1 sum cnt7endl;return0;}B 题最佳围栏思路这题是经典的盛水容器问题的变体。核心思想是用双指针从两边往中间逼指针 left 从 0 开始right 从 n-1 开始计算当前围栏能装的水width × min(height[left], height[right])更新最大答案关键移动高度较小的那一端的指针为什么移动较小的那个因为如果移动较高的那个新围栏的高度不会增加因为最短的还是原来较小的那个而宽度还变小了面积只会更小。所以必须移动较短的那边才有可能找到更大的面积。代码#includeiostream#includevector#includealgorithmusingnamespacestd;intmain(){intn;cinn;vectorinth(n);for(inti0;in;i){cinh[i];}intleft0;intrightn-1;intmax_area0;while(leftright){intwidthright-left;// 两根围栏的距离intheightmin(h[left],h[right]);// 取较短的那根作为高度intareawidth*height;// 计算容量max_areamax(max_area,area);// 更新最大容量// 移动高度较小的指针这样才有可能遇到更高的围栏if(h[left]h[right]){left;}else{right--;}}coutmax_areaendl;return0;}暴力做法子任务1// 双重循环枚举所有两根围栏的组合n ≤ 100 时能过intmax_area0;for(inti0;in;i){for(intji1;jn;j){intarea(j-i)*min(h[i],h[j]);max_areamax(max_area,area);}}C 题机器人路径思路机器人从左上角走到右下角总共需要向下走 (m-1) 步向右走 (n-1) 步总共走 (m-1)(n-1) mn-2 步所以问题变成从 mn-2 步中选 m-1 步向下走或者 n-1 步向右走方案数就是Cmn−2m−1(mn−2)!(m−1)!(n−1)!C_{mn-2}^{m-1} \frac{(mn-2)!}{(m-1)!(n-1)!}Cmn−2m−1​(m−1)!(n−1)!(mn−2)!​答案需要对 1e97 取模。由于 m, n 可以达到 1e5直接计算会溢出需要用逆元。代码#includeiostream#includevectorusingnamespacestd;constintMAXN200005;constlonglongMOD1000000007;longlongfact[MAXN];// 阶乘longlonginv_fact[MAXN];// 阶乘的逆元// 快速幂longlongpow_mod(longlongbase,longlongexp){longlongresult1;while(exp0){if(exp1){result(result*base)%MOD;}base(base*base)%MOD;exp1;}returnresult;}// 预处理阶乘和逆元voidprecompute(){fact[0]1;for(inti1;iMAXN;i){fact[i]fact[i-1]*i%MOD;}inv_fact[MAXN-1]pow_mod(fact[MAXN-1],MOD-2);for(intiMAXN-2;i0;i--){inv_fact[i]inv_fact[i1]*(i1)%MOD;}}// 计算组合数 C(n,k)longlongcomb(intn,intk){if(k0||kn)return0;returnfact[n]*inv_fact[k]%MOD*inv_fact[n-k]%MOD;}intmain(){precompute();intm,n;cinmn;longlongresultcomb(mn-2,m-1);coutresultendl;return0;}复杂度时间 O(max(m,n))空间 O(max(m,n))。预处理后每次查询 O(1)。暴力做法子任务12当 m1 或 n1 时只有一条路径答案就是 1。当 m2 或 n2 时如果 m2答案是 n如果 n2答案是 m// m2 的情况答案是 nif(m2){coutnendl;return0;}// n2 的情况答案是 mif(n2){coutmendl;return0;}一般情况用二维 DP 的话是 O(m×n)m,n ≤ 100 时能过但 m,n ≤ 100000 就会超时。D 题燃烧的木块思路这题的核心思想是模拟火焰从两边向中间燃烧的过程。核心观察火焰从最外层开始燃烧左边、右边、顶部对于第 i 摞木块火焰会同时从左边和右边蔓延过来第 i 摞最终燃烧完的时间取决于从左边烧过来需要的时间从右边烧过来需要的时间木块本身的高度算法步骤pre[i]表示从左边烧到第 i 摞需要的时间不超过木块高度nxt[i]表示从右边烧到第 i 摞需要的时间不超过木块高度答案对于每个位置 i取 min(pre[i], nxt[i]) 的最大值注意对于只有一堆的情况n1所有木块都是最外层顶部和左右都没有木块一开始就同时被点燃1分钟全部烧完。这个情况已经被算法自动处理了。代码#includebits/stdc.husingnamespacestd;constintMAXN200005;inta[MAXN];intpre[MAXN];// 从左边烧到第i摞的时间intnxt[MAXN];// 从右边烧到第i摞的时间intmain(){intn;cinn;for(inti1;in;i){cina[i];}// 从左边烧for(inti1;in;i){pre[i]min(pre[i-1]1,a[i]);}// 从右边烧for(intin;i1;i--){nxt[i]min(nxt[i1]1,a[i]);}// 取每个位置的最小值然后找最大值intans0;for(inti1;in;i){ansmax(ans,min(pre[i],nxt[i]));}coutansendl;return0;}复杂度时间 O(n)空间 O(n)。暴力做法小数据对于 N 5W 2 的情况可以用 BFS 模拟燃烧过程// BFS模拟燃烧过程intsolve_bfs(vectorintw){intnw.size();queuepairint,intq;// (位置, 层数)vectorvectorboolburned(n,vectorbool(*max_element(w.begin(),w.end())1,false));// 初始化所有最外层木块for(inti0;in;i){if(w[i]0){q.push({i,0});burned[i][0]true;}}inttime0;while(!q.empty()){intszq.size();time;for(inti0;isz;i){auto[pos,layer]q.front();q.pop();// 向上烧if(layer1w[pos]!burned[pos][layer1]){burned[pos][layer1]true;q.push({pos,layer1});}// 向左烧if(pos0layerw[pos-1]!burned[pos-1][layer]){burned[pos-1][layer]true;q.push({pos-1,layer});}// 向右烧if(posn-1layerw[pos1]!burned[pos1][layer]){burned[pos1][layer]true;q.push({pos1,layer});}}}returntime-1;}样例解释以样例 1 为例输入5 2 3 4 2 3从左边烧pre[1] min(01, 2) 1pre[2] min(11, 3) 2pre[3] min(21, 4) 3pre[4] min(31, 2) 2pre[5] min(21, 3) 3从右边烧nxt[5] min(01, 3) 1nxt[4] min(11, 2) 2nxt[3] min(21, 4) 3nxt[2] min(31, 3) 3nxt[1] min(31, 2) 2每个位置的 min(pre[i], nxt[i])min(1, 2) 1min(2, 3) 2min(3, 3) 3min(2, 2) 2min(3, 1) 1最大值是 3所以答案是 3。