萌新联赛2补题

目录题目链接D-切割立方体M-哈基米压缩B-不同的商题目链接河南萌新联赛2026第二场河南农业大学_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJD-切割立方体题目大意有一个长宽高分别为 w、x、h 的长方体由大量 1×1×1 的小方块组成接下来会进行 q 次挖洞操作每次给定一对对角坐标确定一个子长方体区域把该区域内所有小方块挖除重复被多次选中的方块只需挖除一次最后求还剩下多少个完整的小方块。解题思路因为题目给出长宽高最大只有 20总小方块数量最多是20*20*20可以直接暴力枚举。先创建一个三维数组用来记录每个坐标(x,y,z)的小方块有没有被挖掉初始全部标记为没被挖走。依次处理每一次切割操作根据给出的坐标范围遍历这个子长方体内所有小方块把对应的位置标记为已挖除。多次覆盖同一个方块时重复标记不会产生影响,全部切割处理完成后遍历所有小方块统计仍然标记为未被挖除的方块总数涉及知识点1.多维数组 内存初始化三维数组bool ans[21][21][21]存储三维空间每个格子状态memset()按字节批量初始化内存只能可靠置 0/-1不能随意赋其他数值局部数组默认不初始化内存是随机垃圾值必须手动清零2.暴力区间标记三维枚举三维嵌套循环遍历长方体区间[x1,y1,z1] ~ [x2,y2,z2]布尔标记true 被覆盖false 未覆盖实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; const ll N1e610; ll a[N]; int main() { IOS ll w,x,h,q; ll x1,y1,z1,x2,y2,z2,t0; cinwxh; cinq; bool ans[21][21][21];//三维标记数组anstrue代表该坐标被覆盖 memset(ans,0,sizeof(ans));//初始化三维数组 while(q--) { cinx1y1z1x2y2z2; //枚举长方体所有坐标标记为已覆盖 for(ll ix1;ix2;i) { for(ll jy1;jy2;j) { for(ll kz1;kz2;k) { ans[i][j][k]true; } } } t0;//遍历整个三维空间统计未覆盖个数 for(ll i1;iw;i) { for(ll j1;jx;j) { for(ll k1;kh;k) { if(!ans[i][j][k]) { t; } } } } } couttendl; // coutfixedsetprecision(x) ; return 0; }M-哈基米压缩题目大意题目把一长串数字压缩成好几段每段记录【数字 这个数字连续出现多少个】把这些段连起来就是完整长序列问原序列第 x 个数字是几解题思路先读取分段数量 n依次读入每段的数值与长度分别存入两个 vector接着构建前缀和数组sum [i] 保存前 i1 段的总长度。之后处理每组查询 x从头依次遍历前缀和数组找到第一个总和大于 x 的位置对应段上的数值就是原序列第 x 项直接输出。涉及知识点前缀和把每一段的长度依次累加记录每一段结束时对应原序列的总长度以此确定每一段覆盖的坐标区间不需要构建完整超长原序列节省空间。线性查找针对每一个查询位置从头遍历前缀和数组找到包含目标位置的分段取出对应数值容易超时分段映射思想原序列由多段连续相同数字拼接而成将原始坐标问题转化为寻找坐标落在哪个分段的问题是处理超长连续序列查询的通用模型。实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second using namespace std; ll n; const ll N1e610; ll a[N]; int main() { IOS ll T,x,i; ll k1,k2; cinn; vectorllv;// 存储每一段对应的数值 vectorlll; // 存储每一段的连续长度 for(int i1;in;i) { ll x,y; cinxy; v.push_back(x); l.push_back(y); } vectorllsum(n2,0); // sum数组存放前缀和记录前若干段总长度 sum[0]l[0]; for(ll i1;il.size();i) { sum[i]sum[i-1]l[i];// 累加计算前缀和sum[i]代表前i1段的总长度 } cinT; while(T--) { cinx; for(int i0;il.size();i) { if(xsum[i])// 找到第一个总长度大于x的分段说明x落在本段内 { coutv[i]endl; break; } } } // coutfixedsetprecision(x) ; return 0; }B-不同的商题目大意给定正整数xyi1到iy中x/i的和1x10^12,1y10^18解题思路题目要求计算和直接循环枚举 i 会因为 y 最大超时我们采用数论分块整除分块x/i在一段连续区间内数值不变把取值相同的区间合并一次性算出整个贡献再跳到下一块起点循环次数只有O(sqrt(x)可以通过超大范围数据。 每次确定当前区间左端点 l算出当前值kx/l再求出这段区间最远右端点 r区间内所有位置贡献都为 k总贡献为 k*(r-l1)最后令 lr1) 处理下一块直到 ly涉及知识点整除向下取整性质对固定 x连续多个 i 会使x/i取值相同这些 i 构成连续区间使整除分块可以合并计算整除分块算法不再逐个遍历 i而是按取值相同的区间整块计算贡献把暴力O(y)复杂度优化到O(sqrt(x))适配本题极大的数据范围区间批量贡献计算同一个区间内所有项的值相等用 “数值 * 区间内元素个数” 一次性累加避免逐个循环求和实现代码#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define YES coutYESendl; #define NO coutNOendl; using namespace std; const ll N1e610; ll a[N]; int main() { IOS ll x,y; cinxy; ll l1; ll ans0; while(ly) { ll kx/l;//出当前块所有i对应的统一值x/i ll r; if(k0) { ry; } else { rmin(x/k,y);//x/k是理论上这个k能延伸到的最远位置min保证右端点不能超过求和上y防止超出范围 } ansk*(r-l1);//一共有r-l1个数字每个数字贡献k批量累加整块总和代替逐个循环 lr1;//处理完当前块直接跳到下一块左边界跳过中间全部已经计算过的i } coutansendl; // coutfixedsetprecision(x) ; return 0; }