AtCoder Beginner Contest 366(D~E题解)

2024-08-29 17:44

本文主要是介绍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题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1118537

相关文章

2014 Multi-University Training Contest 8小记

1002 计算几何 最大的速度才可能拥有无限的面积。 最大的速度的点 求凸包, 凸包上的点( 注意不是端点 ) 才拥有无限的面积 注意 :  凸包上如果有重点则不满足。 另外最大的速度为0也不行的。 int cmp(double x){if(fabs(x) < 1e-8) return 0 ;if(x > 0) return 1 ;return -1 ;}struct poin

2014 Multi-University Training Contest 7小记

1003   数学 , 先暴力再解方程。 在b进制下是个2 , 3 位数的 大概是10000进制以上 。这部分解方程 2-10000 直接暴力 typedef long long LL ;LL n ;int ok(int b){LL m = n ;int c ;while(m){c = m % b ;if(c == 3 || c == 4 || c == 5 ||

2014 Multi-University Training Contest 6小记

1003  贪心 对于111...10....000 这样的序列,  a 为1的个数,b为0的个数,易得当 x= a / (a + b) 时 f最小。 讲串分成若干段  1..10..0   ,  1..10..0 ,  要满足x非递减 。  对于 xi > xi+1  这样的合并 即可。 const int maxn = 100008 ;struct Node{int

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

AtCoder Beginner Contest 370 Solution

A void solve() {int a, b;qr(a, b);if(a + b != 1) cout << "Invalid\n";else Yes(a);} B 模拟 void solve() {qr(n);int x = 1;FOR(i, n) FOR(j, i) qr(a[i][j]);FOR(i, n) x = x >= i ? a[x][i]: a[i][x];pr2(