萌新联赛2补题
目录
题目链接
D-切割立方体
M-哈基米压缩
B-不同的商
题目链接
河南萌新联赛2026第（二）场：河南农业大学_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ
D-切割立方体
题目大意：
有一个长宽高分别为 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= 未覆盖
实现代码：
#include<bits/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 N=1e6+10; ll a[N]; int main() { IOS ll w,x,h,q; ll x1,y1,z1,x2,y2,z2,t=0; cin>>w>>x>>h; cin>>q; bool ans[21][21][21];//三维标记数组，ans=true，代表该坐标被覆盖 memset(ans,0,sizeof(ans));//初始化三维数组 while(q--) { cin>>x1>>y1>>z1>>x2>>y2>>z2; //枚举长方体所有坐标，标记为已覆盖 for(ll i=x1;i<=x2;i++) { for(ll j=y1;j<=y2;j++) { for(ll k=z1;k<=z2;k++) { ans[i][j][k]=true; } } } t=0;//遍历整个三维空间，统计未覆盖个数 for(ll i=1;i<=w;i++) { for(ll j=1;j<=x;j++) { for(ll k=1;k<=h;k++) { if(!ans[i][j][k]) { t++; } } } } } cout<<t<<endl; // cout<<fixed<<setprecision(x)<< ; return 0; }M-哈基米压缩
题目大意：
题目把一长串数字压缩成好几段，每段记录【数字 + 这个数字连续出现多少个】，把这些段连起来就是完整长序列，问原序列第 x 个数字是几
解题思路：
先读取分段数量 n，依次读入每段的数值与长度，分别存入两个 vector；接着构建前缀和数组，sum [i] 保存前 i+1 段的总长度。之后处理每组查询 x，从头依次遍历前缀和数组，找到第一个总和大于 x 的位置，对应段上的数值就是原序列第 x 项，直接输出。
涉及知识点：
前缀和：把每一段的长度依次累加，记录每一段结束时对应原序列的总长度，以此确定每一段覆盖的坐标区间，不需要构建完整超长原序列，节省空间。
线性查找：针对每一个查询位置，从头遍历前缀和数组，找到包含目标位置的分段，取出对应数值，容易超时
分段映射思想：原序列由多段连续相同数字拼接而成，将原始坐标问题转化为寻找坐标落在哪个分段的问题，是处理超长连续序列查询的通用模型。
实现代码：
#include<bits/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 N=1e6+10; ll a[N]; int main() { IOS ll T,x,i; ll k1,k2; cin>>n; vector<ll>v;// 存储每一段对应的数值 vector<ll>l; // 存储每一段的连续长度 for(int i=1;i<=n;i++) { ll x,y; cin>>x>>y; v.push_back(x); l.push_back(y); } vector<ll>sum(n+2,0); // sum数组存放前缀和，记录前若干段总长度 sum[0]=l[0]; for(ll i=1;i<l.size();i++) { sum[i]=sum[i-1]+l[i];// 累加计算前缀和，sum[i]代表前i+1段的总长度 } cin>>T; while(T--) { cin>>x; for(int i=0;i<l.size();i++) { if(x<sum[i])// 找到第一个总长度大于x的分段，说明x落在本段内 { cout<<v[i]<<endl; break; } } } // cout<<fixed<<setprecision(x)<< ; return 0; }B-不同的商
题目大意：
给定正整数x，y，i=1到i=y中（x/i）的和，1<=x<=10^12,1<=y<=10^18
解题思路：
题目要求计算和，直接循环枚举 i 会因为 y 最大超时，我们采用数论分块（整除分块）：x/i在一段连续区间内数值不变，把取值相同的区间合并，一次性算出整个贡献，再跳到下一块起点，循环次数只有O(sqrt(x)，可以通过超大范围数据。 每次确定当前区间左端点 l，算出当前值k=x/l；再求出这段区间最远右端点 r，区间内所有位置贡献都为 k，总贡献为 k*(r-l+1)；最后令 l=r+1) 处理下一块，直到 l>y
涉及知识点：
整除向下取整性质：对固定 x，连续多个 i 会使x/i取值相同，这些 i 构成连续区间，使整除分块可以合并计算
整除分块算法：不再逐个遍历 i，而是按取值相同的区间整块计算贡献，把暴力O(y)复杂度优化到O(sqrt(x))，适配本题极大的数据范围
区间批量贡献计算：同一个区间内所有项的值相等，用 “数值 * 区间内元素个数” 一次性累加，避免逐个循环求和
实现代码：
#include<bits/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 cout<<"YES"<<endl; #define NO cout<<"NO"<<endl; using namespace std; const ll N=1e6+10; ll a[N]; int main() { IOS ll x,y; cin>>x>>y; ll l=1; ll ans=0; while(l<=y) { ll k=x/l;//出当前块所有i对应的统一值x/i ll r; if(k==0) { r=y; } else { r=min(x/k,y);//x/k是理论上这个k能延伸到的最远位置，min保证右端点不能超过求和上y，防止超出范围 } ans+=k*(r-l+1);//一共有r-l+1个数字，每个数字贡献k，批量累加整块总和，代替逐个循环 l=r+1;//处理完当前块，直接跳到下一块左边界，跳过中间全部已经计算过的i } cout<<ans<<endl; // cout<<fixed<<setprecision(x)<< ; return 0; }