阿里嘎多懒羊羊桑_ - 个人主页动态

2024-11-22 17:35

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

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-22 14:48

鲁东大学 golang

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。用前缀和可以快速求出两个站点之间的距离，这种环形问题一般是加一倍变成直线来处理。从x直接走到y的结果是sum[y-1] - sum[x-1] ，这里用sum[y-1]的原因是因为a[i]表示的是第i个站点到第i+1个站点的距离，所以同理推到前缀和的话，也是从y-1个站点到第y个站点的前缀和，我们最后要到达的是第y个站点，所以用y-1同理如果...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-22 13:58

鲁东大学 golang

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

题意给出n行m列的矩阵，每次查询求左上角为 (x1,y1) 、右下角为 (x2,y2) 的子矩阵的元素之和思路二维前缀和维护 Go代码 package main import ( "fmt" ) func main() { var n,m,q,x1,y1,x2,y2 int fmt.Scan(&n,&m,&q) a := make([][]int,n+1) sum := make([][]int,n+1) for i := 0 ; i <= n ; i ++ { sum[i]...

15天大厂真题带刷Go题...

0 点赞评论收藏

2024-11-22 10:10

鲁东大学 golang

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

题意给出长度为1e5的数组和1e5次操作，每次操作可能为单点修改，也可能为区间查询思路数据范围是1e5，考虑用数据结构维护，树状数组或线段树都可以 树状数组是一种支持单点修改和区间查询的代码量小的数据结构，维护的信息和运算必须要满足结合律而且可差分，比如加法、乘法、异或等。结合律：(x # y )# z = x # (y # z)，其中#为二元运算符，比如+ * ^可差分：具有逆运算的运算，即已知 x # y 和 x 可以求出y需要注意的是：mod 意义下的乘法如果要差分，需要保证每个数都存在逆元（模数为质数时一定存在逆元）gcd、max这些信息不可差分树状数组解决的是线段树解决的问题的子集，...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-21 20:31

鲁东大学 golang

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以后，a[l] - a[l-1] 就增加了k，因为a[l]变大了但是a[l-1]没变，所以相当于d[l]+=k 。同理，a[r]变大了但是a[r+1]没变，相当于d[r+1]变小了k最后再把差分数组还原即可Go代码 package main import ( "fmt" ) ...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-21 18:12

鲁东大学 golang

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

题意给出一个长度为n的数组和q次询问，每次询问求区间[l,r]的数组的元素和。思路数据范围n和q都是1e6，数组元素<=1e9，暴力的做法会超时，考虑用前缀和优化。在输入的时候维护sum数组，要注意用long long / int64 ，对于每次询问直接输出sum[r] - sum[l-1]即可。C++代码 #include <iostream> using namespace std; const int maxn = 1e6+10; int main() { long long n,q,l,r,x,sum[maxn]; cin>>n>...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-21 17:08

鲁东大学 golang

15天大厂真题带刷 - ZT17小欧安排座位 | Go

题意给出一个长度为n的字符串，请构造一个数组，具体要求如下：当这一位是1时，要求 a[i]=i 当这一位是0是，要求 a[i]!=i尽可能多的满足要求思路先把所有字符串里是0的位置填上a[i]=i，并且记录下字符串里1的位置的数值tmp。再填字符串里是1的位置的时候，可以考虑每一个元素都等于tmp数组的下一个元素，这样可以尽量满足a[i] != i Go代码 package main import "fmt" func main() { var n int var s string fmt.Scan(&n, &s) //第i个表示第i个小朋友的位...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-21 16:49

鲁东大学 golang

15天大厂真题带刷 - ZT16小欧的括号嵌套 | Go

题意构造一个长度为2*n的合法括号序列，最大的嵌套深度是r。思路考虑先把最大嵌套深度的合法括号构造出来，即放r个左括号，再放r个右括号，最后用单个括号补全到2n的长度Go代码 package main import "fmt" func main() { var n, r int fmt.Scan(&n, &r) for i := 0; i < r; i++ { fmt.Print("(") } for i := 0; i < r; i++ { fmt.Print(")") } f...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-21 09:51

鲁东大学 golang

15天大厂真题带刷 - ZT15小红的区间查询 | Go

题意给出一个数组，有2种操作，把第i个位置的数变为x，求前i个位置的数里等于x的数有多少个？思路考虑数据范围，n和q都只有200，直接暴力维护就可以。对于操作1，把数组idx-1的值变为x；对于操作2，从0遍历到idx-1，如果当前数等于x，答案加1。是idx-1的原因是数组下标从0开始。扩展：本质是一个单点修改区间查询的问题，如果n,q <=1e5，可以考虑用数据结构维护Go代码 package main import ( "fmt" ) func main() { var n, q, op, idx, x int fmt.Scan(&n, &am...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-21 09:35

鲁东大学 golang

15天大厂真题带刷 - ZT14小红的好数 | Go

题意求从0到9999满足每个数位各不相同的第k大的数，如果一个数不足5位，补全前导零使其超过5位思路从9999倒序遍历，判断当前的数是否满足条件，满足的话k=k-1，当k=0的时候当前数就是答案。要注意输出的是一个五位的数，需要补前导零代码 package main import ( "fmt" "strconv" ) func check(x int) (string,bool) { s := strconv.Itoa(x) for len(s) < 5 { s = "0" + s ...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-20 22:15

鲁东大学 golang

15天大厂真题带刷 - ZT13小红的数字删除 | Go

题意小红拿到了一个正整数，她每次可以删除其中一个数位，但必须保证每次删除后，该正整数都是3的倍数且大于0。小红想知道，自己最多可以进行多少次这样的删除操作？思路先说一个错误的思路，先计算出正整数的数位和，然后从头遍历字符串，如果删除这位后满足条件，就删除。这样无法得到最优解。正解是根据数位和sum % 3 的值以及所有的数位里%3 的值的个数来讨论的，其实就是个思维题，但是边界条件太多了！假设正整数的每一个数位%3等于1的个数为cnt1，数位%3等于2的个数为cnt2，数位%3等于0的个数为cnt0题目要求删除后这个正整数是3的倍数，就说明删除后的sum%3一定为0如果sum%3一开始就是0的...

0 点赞评论收藏

2024-11-20 21:01

鲁东大学 golang

15天大厂真题带刷 - ZT12 小欧的数组修改 | Go

题意最多可以做一次操作，这次操作会把数组里的任意一个元素改为任意值，求出现次数最多元素的最多出现次数思路要使得出现次数最多的元素出现的次数尽可能的多，首先要找到最多的出现次数，这里用哈希表维护了每个元素的出现次数，取最大值为ans最后判断如果ans不等于n的话，说明可以做一次操作使得某个元素变为该值，出现次数+1Go代码 package main import ( "fmt" ) func max(a,b int) int { if a > b { return a } return b } func main()...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-20 20:53

鲁东大学 golang

15天大厂真题带刷 - ZT11 压缩二维码 | Go

题意给出一个矩阵，#表示1，.表示0，每4位看作二进制，求十进制思路直接模拟即可，这里是先把矩阵转化为只有0和1的数组，然后从头开始遍历，每次取4位按照1 2 4 8 的数位求出十进制数字的值Go代码 package main import ( "fmt" "math" ) func main() { var n int fmt.Scan(&n) var s string tmp := make([]int,0,n) for i := 0; i < int(math.Pow(2,float...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-20 20:14

鲁东大学 golang

15天大厂真题带刷 - ZT10 游游的除2操作 | Go

题意每次操作可以给数组里的某个元素除以2，向下取整，问最少需要多少次操作可以使得所有元素相等思路感觉这个题的数据范围应该没有很强，算是水过去了枚举了a[i]所以可以变成的值，其中mp[x]表示可以变成x的数的个数，cnt[x]表示变成x全部所需要的操作数。最后在所有mp[x]=n的值里，取一个cnt[x]的最小值Go代码 package main import ( "fmt" "math" "sort" ) func min(a,b int) int { if a < b { return a ...

15天大厂真题带刷Go题... 牛客创作赏金赛

0 点赞评论收藏

2024-11-20 19:57

鲁东大学 golang

15天大厂真题带刷 - ZT9 游游的字母翻倍 | Go

题意给出一个长度为n的字符串和q次询问，每次询问把区间[l,r]的字母各重复一次，插入到原字母的后面。思路模拟即可，每次循环都把s字符串遍历一遍，假设字符串tmp为新的字符串，先将当前字符加到tmp里，如果说当前下标在区间[l-1,r-1]里，就重复加一次。[l-1,r-1]的原因是数组的下标从0开始Go代码 package main import ( "fmt" ) func main() { var n,q,l,r int fmt.Scan(&n,&q) var s string fmt.Scan(&...

15天大厂真题带刷Go题...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：