阿里嘎多懒羊羊桑_

分类

未归档(1) 题解(36)

/ 注册

TA的专栏 36篇文章 2人订阅

15天大厂真题带刷Go题解

36篇文章 103人学习

全部文章（共105篇）

15天大厂真题带刷 - ZT27平均数为k的最长连续子数组来自专栏

题意给定n个正整数组成的数组，求平均数正好等于 k 的最长连续子数组的长度。思路某个连续子数组的平均数等于k可以转化为区间和等于k*(j-i+1)如果用前缀和维护的话就是sum[j] - sum[i-1] = k * (j-i+1)这里有个很巧妙的地方就是把每个数都减去k，这样就变成了sum[j]-...

2024-11-23

1 36

15天大厂真题带刷 - ZT25 小红的子序列逆序对来自专栏

题意给出一个数组，求该数组所有的子序列中的逆序对数量之和是多少数组长度1e5思路这种求所有子序列/子数组xxx值的和一般都是考虑单个元素的贡献，这里考虑的是单个逆序对的贡献，对于每个逆序对来说，剩下的n-2个元素每个元素都有选或不选两种选择，可以构成的子序列个数为2^(n-2)，那么如果有x个逆序对...

2024-11-23

2 66

15天大厂真题带刷 - ZT26小球投盒 | Go 二分来自专栏

题意有n个盒子，可以进行m次操作，每次操作有2种向编号为x的盒子里放一个小球向除了编号x的其他n-1个盒子里放一个小球求第几次操作后，所有盒子里至少都有一个小球思路答案是具有单调性的，因为每次都是往盒子里放小球，第x次操作后，所有的盒子里至少有一个小球的话，那么第x+1操作后，也肯定满足这个条件。而...

2024-11-22

1 45

15天大厂真题带刷 - ZT24小红结账 | Go

思路数组a[i]表示编号为i+1的人要转给小红的钱数，要注意每次转账的钱是上取整，这里用的方法是判断了下c%k的值，如果不为0则答案再+1 Go代码 package main import ( "fmt" ) func main() { var n, m, k, c, x...

2024-11-22

1 35

15天大厂真题带刷 - ZT23 小美的蛋糕切割 | Cpp 来自专栏

题意给出n*m的矩阵，可以横着切一刀或是竖着切一刀，问切完后两块和的差值的最小值思路1：暴力枚举首先能想到的是O(n^3)的暴力，以横着切一刀为例，枚举切的位置是i，那么1~i 行的元素之和就是第一块的值s1，i+1~n行的元素之和就是第二块的值s2，大概的代码如下 for i := 1; i ...

2024-11-22

0 52

15天大厂真题带刷 - ZT22 小美走公路 | Go 来自专栏

题意环形的公路，a[i]表示从第i个站点到第i+1个站点的距离，a[n]表示第n个站点到第1个站点的距离，求第x个站点到第y个站点的最短距离。思路这里先假设x小于y，如果不满足的话就交换x和y有两种路径可以从x到y，一是从x直接走到y，二是从y经过n走到x。用前缀和可以快速求出两个站点之间的距离，这...

2024-11-22

2 47

15天大厂真题带刷 - ZT20【模板】静态矩阵和 | Go 来自专栏

题意给出n行m列的矩阵，每次查询求左上角为 (x1,y1) 、右下角为 (x2,y2) 的子矩阵的元素之和思路二维前缀和维护 Go代码 package main import ( "fmt" ) func main() { var n,m,q,x1,y1,x2...

2024-11-22

0 23

15天大厂真题带刷 - ZT19【模板】线段树1 | Go 来自专栏

题意给出长度为1e5的数组和1e5次操作，每次操作可能为单点修改，也可能为区间查询思路数据范围是1e5，考虑用数据结构维护，树状数组或线段树都可以树状数组是一种支持单点修改和区间查询的代码量小的数据结构，维护的信息和运算必须要满足结合律而且可差分，比如加法、乘法、异或等。结合律：(x # y )#...

2024-11-22

0 35

15天大厂真题带刷 - ZT21【模板】差分 | Go 来自专栏

题意给出一个长度为n的数组和m次修改，每次修改都要把a[l~r]加上k，输出全部操作完成之后的数组数据范围是n,m<=1e5,a[i]<=1e9思路考虑使用差分数组，对于数组a构造差分数组d，使得d[i] = a[i] - a[i-1]那么对于每一次操作，给区间[l,r]全部加上k以后，...

2024-11-21

0 32

15天大厂真题带刷 - ZT18【模板】静态区间和 | Go 来自专栏

题意给出一个长度为n的数组和q次询问，每次询问求区间[l,r]的数组的元素和。思路数据范围n和q都是1e6，数组元素<=1e9，暴力的做法会超时，考虑用前缀和优化。在输入的时候维护sum数组，要注意用long long / int64 ，对于每次询问直接输出sum[r] - sum[l-1]即...

2024-11-21

1 35