本文主要是介绍AtCoder Beginner Contest 366(D~E题解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
闲来无事去vp了一下之前放假没打的比赛,感觉需要总结的也就这两题吧,a,c都是水题,b只不过是实现有一点难,并不是很难写,d是一个需要自己推的三维前缀和,e也是一种前缀和,我当时没想到,看了大犇的代码才知道还能这么做
D - Cuboid Sum Query
题意:给你一个三维数组,然后给你q次询问,每次询问有一个起始位置和终止位置,然后问你这个的三维前缀和是什么
思路:用容斥原理推出三维前缀和的预处理式子和后面的结果式子
预处理的式子:
sum[i][j][k] = a[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]
- sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j - 1][k - 1]
+sum[i - 1][j - 1][k - 1];
处理两个点前缀和的式子
int ans = sum[rx][ry][rz]
-sum[lx - 1][ry][rz]-sum[rx][ly - 1][rz]-sum[rx][ry][lz - 1]
+ sum[lx - 1][ly - 1][rz] +sum[lx - 1][ry][lz - 1] + sum[rx][ly - 1][lz - 1]
-sum[lx - 1][ly - 1][lz - 1];
#include <bits/stdc++.h>
using namespace std;
int a[105][105][105];
int sum[105][105][105];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = 1; k <= n; k++){cin >> a[i][j][k];}}}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){for (int k = 1; k <= n; k++){sum[i][j][k] = a[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]- sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j - 1][k - 1] +sum[i - 1][j - 1][k - 1];}}}int q;cin >> q;while (q--){int lx, rx, ly, ry, lz, rz;cin >> lx >> rx >> ly >> ry >> lz >> rz;int ans = sum[rx][ry][rz] -sum[lx - 1][ry][rz]-sum[rx][ly - 1][rz]-sum[rx][ry][lz - 1] + sum[lx - 1][ly - 1][rz] +sum[lx - 1][ry][lz - 1] + sum[rx][ly - 1][lz - 1] -sum[lx - 1][ly - 1][lz - 1];cout << ans << '\n';}return 0;
}
E - Manhattan Multifocal Ellipse
题意:就是给你n个点,然后问你,整个平面上,有多少个点,到这个n个点的总距离不超过d
思路:脑子里迅速出现的思路是纯暴力,看到数据,纯暴力肯定是不行的,时间复杂度巨高,那么我们就该换一种思路,想一想时间复杂度简单的,我看有些大犇是拿线段树做的,有的是前缀和做的,我还是更偏向于前缀和,线段树太冗长了
因为此题是曼哈顿距离,曼哈顿距离有个好处就是横纵坐标可以分开来计算,因此我们只需要先用pre数组去统计前 i 个点的横坐标之和,然后去统计可能出现的到n个点的距离,如果这个距离小于d,我们就用dist数组去统计其出现次数
然后我们要将dist数组变为累加和的形式,然后对y进行处理,用ans去统计可能的点数
如果有点到y的距离小于d,那么ans+dist(d-len)即可
#include<bits/stdc++.h>
using namespace std;
#define int long long int n, d; signed main()
{ cin >> n >> d; vector<int> x(n + 1), y(n + 1); for (int i = 1; i <= n; i++) { cin >> x[i] >> y[i];} sort(x.begin() + 1, x.end()); sort(y.begin() + 1, y.end()); vector<int> pre(n + 1); vector<int> dist(d + 1); // 定义用于存储距离的数组 for (int i = 1; i <= n; i++) // 计算 x 坐标的前缀和 { pre[i] = pre[i - 1] + x[i]; // pre[i] 记录从 1 到 i 的 x 坐标和 } for (int i = x[1] - d, j = 1; i <= x[n] + d; i++) // 遍历可能的 x 坐标 ,类似于扫描线,将可能出现的x的坐标都扫了一遍 { while (j <= n && i == x[j]) // 处理与当前 i 坐标相等的点 { j += 1; } // 计算所有点到当前i的距离 int len = (pre[n] - pre[j - 1] - (n-j+1) * i) + ((j - 1) * i - pre[j - 1]); // 如果当前距离小于等于 d,增加对应的计数 if (len <= d) { dist[len] += 1; } } // 计算不超过 d 的距离的累积和 for (int i = 1; i <= d; i++) { dist[i] += dist[i - 1]; } for (int i = 1; i <= n; i++) // 计算 y 坐标的前缀和 { pre[i] = pre[i - 1] + y[i]; // pre[i] 记录从 1 到 i 的 y 坐标和 } int ans = 0; // 初始化答案为 0 for (int i = y[1] - d, j = 1; i <= y[n] + d; i++) // 遍历可能的 y 坐标 { while (j <= n && i == y[j]) // 处理与当前 i 坐标相等的点 { j += 1; } // 计算所有点到当前i的距离总和 int len = (pre[n] - pre[j - 1] - (n - j + 1) * i) + ((j - 1) * i - pre[j - 1]); // 如果当前距离小于等于 d,增加对应的计数到答案 if (len <= d) { ans += dist[d - len]; // 累加符合条件的点对数量 } } cout << ans << endl; // 输出结果 return 0;
}
这篇关于AtCoder Beginner Contest 366(D~E题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!