sunrise__sunrise - 个人主页动态 - 牛客网

发布(392) 评论刷题收藏

2020-07-10 18:25

中国海洋大学 C++

【每日一题】7月10日矩阵取数游戏

题目描述 给出n行m列的矩阵，每次要取出每一行行头或者行位去掉，得到的价值为这个数加上2的第几次取次方。问最大的价值是多少 解题思路 很容易发现每一行都是同一个处理办法去处理，行与行之间不会相互影响，那么在一行中，可以用上动态规划，要么取队头加上后面的len-1个数，要么取队尾加上len-1个数，这个求解过程中还可以用上记忆化搜索。数据很大，也只是60分，选择简单的Python搞定高精度）Java不会。。 def dfs(l, r): len = r - l + 1 k = m - len + 1 #第几次选数 if f[l][r]: return f[l][r] ...

0 点赞评论收藏

分享

2020-07-10 12:09

中国海洋大学 C++

【每日一题】7月7日题目最短路

题目意思 给出n个点，最多只会有n+100条边，问给出q次询问，每次询问的两个点最短距离是什么，规模都是1e5 解题思路 第一想法：floyd算法，再看下问题规模，1e5，因为floyd基于邻接矩阵存储而且要On^3空间时间都不满足。 换个方向，题目给出的数据范围要仔细琢磨，最多的只有n+100条边说明就说在一颗树上添加了一点点边而已，那么我们就知道，如果不看这100条边，把他当成一颗树来看就可以用倍增的LCA去求树上最短距离，这里不展开可以去百度或者看看代码，那么还有就是剩下的100条边如何处理，它们在什么情况下会更新答案？我们在处理边信息的时候如果一条边的左右点都有同一个父亲说明这条边不是...

0 点赞评论收藏

分享

2020-07-09 20:51

中国海洋大学 C++

【每日一题】7月6日平衡二叉树

题目意思 题目规定的还是比较正统的BST，那么就左右子树差值不超过给定的第二个数字，高度为第一个数字 解题思路 直接动态规划是最简单的解法：我们想想假设待求得状态为，代表高度为i的所求节点个数那么就有代表着高度为和得左右子树所求节点个数之和再加上根节点最终就有左子数为满二叉树，右子树为满足题目高度只差不超过m的二叉树，减掉即可！注意别取到负数的下标了 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #in...

0 点赞评论收藏

分享

2020-07-10 16:58

已编辑

中国海洋大学 C++

【每日一题】7月3日毒瘤xor

题目意思 给出的个数，给出次询问，每次询问都会给出两个左右区间，问我们为什么时候异或区间全部数之后答案最大。 解题思路 异或基本思想，所以统计这个区间中这一位共有几个1，如果大于0的个数那么这一位就取0，否则0个数大于1个数就取1在的这一位。有关区间各个位数统计可以用前缀和预处理，把时间复杂度降为 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h&gt...

0 点赞评论收藏

分享

2020-06-09 22:54

中国海洋大学 C++

题目意思 乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。 解题思路 参考秃头大太阳题解深度优先搜索加减枝。首先我们从第一根木棍的长度开始枚举，一直递归判断是否可以全部合成即可，这个比较暴力不好时间复杂度可能达到立方阶。想想优化，首先可以对全部木棍排序，从大的长度开始枚举判断，这样可以减少很多不正确的判断，最大到全部木棍之和。如果当前长度不能被n整除直接跳过。那么如果可以被整除，看看能不能找方法把这些木棍填满。具体的填棍...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-09 19:20

中国海洋大学 C++

题目意思 存在格子规定方向，存在格子随意走动，不存在不能走的格子，只需要输出可以到达终点的某一条路径即可。 解题思路 BFS，直接对地图剖解，把方向字母用数字代替）其实也可以不换后面明显一点就是了，后面通过BFS记录当前走的方向，走到终点。再一次方向走图，记录每个点是如何过来的。再输出答案就行了！ #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h>...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-09 16:48

中国海洋大学 C++

【每日一题】6月10日失衡天平

题目意思 给你一个天平，你可以使用无数次，每次只要放上去的物品相差绝对值小于等于m就可以把左右两边物品带走，问最大带走的物品质量是多少？ 解题思路 二维dp，首先看到题目范围100以内的数据，除了二进制枚举三次方也可以满足复杂度。那么一个思维模型，使用代表前i个数中差值在j以内的最大重量。可以发现每次对于一个物品，可以选择放在前i-1个物品差距在+a[i]或-a[i]的情况放在对面情况选最大值即可。就是如果你去找的最大值，那么就可以把当前i这个物品可以放在对面的秤上。同理可能负数，记得带个绝对值。一样放在对面之后保持差距在j。那么再去找差距在的最小值输出即可。 #pragma GCC tar...

0 点赞评论收藏

分享

2020-06-09 14:13

中国海洋大学 C++

题目意思 给出地图，星号是无法走的格子，不能同时踏过F和和M两个格子，也就是走进一个格子没有影响。 解题思路 广度优先搜索，居然我们可以走一个特殊房间，那我们直接把某一个特殊房间直接当成空地即可，分别两次bfs，跑出去到终点的最短距离，再换个房间再跑一遍bfs，跑出另外一条路去终点的最短路径，如果都是不存在说明无法到达，如果一条路不存在选择可以走的那一条，如果都可以去选择小的那一条路。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loop...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-09 09:06

已编辑

中国海洋大学 C++

题目意思 给出一个n * m的地图，起始点是S，终点E，中途#代表障碍物，无法走过。问能不能从起点走到终点。 解题思路 BFS走图题，别用dfs，规模一大就会暴毙。用了bfs的化应该就很简单了，这个题目本身没有难度，就是一个裸的模板题，如果还有不会的康康代码应该就懂了 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespac...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-09 00:36

中国海洋大学 C++

【每日一题】6月9日Steps to One

题目意思 给出一个空数列a，从1到m随机选一个数进入a数组，当a数组中全部数的gcd是1的时候退出程序，问平均期望长度。 解题思路 数论，期望dp [参考1，zzugzx大佬](https://blog.nowcoder.net/n/6fc91cc5671f457d9389dc3bd9303aa1) [参考2，superj7大佬](https://blog.nowcoder.net/n/fb90d1cb191a4432bb908a53857c8a25) 和gcd有关显然加入数据不会把当前最小的gcd减小，只会不变和变小，...

0 点赞评论收藏

分享

2020-06-08 20:35

中国海洋大学 C++

小琛和他的学校

解题思路 题目都很明显告诉你这是一棵树了，那你就老老实实的建个树跑每条路的花费就行了。 先找到每条路的人流量，再计算一次的花费，这些人还要原路返回一次，最终输出乘一个二就行了 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 7; struct Node { int dst,&n...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-08 20:30

中国海洋大学 C++

解题思路 三维bfs的模板题，没什么大坑，注意还是老话，走图题，千万千万别写dfs，会死的很惨很惨，MLE究极暴毙。。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 105; struct Node { int x, y, z, s; }; queue<Node> qu...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-08 20:26

中国海洋大学 C++

「金」点石成金

题目意思 给出的n块石头，可以把他变成黄金，增加a的财富，减少b的魔法，也可以不变黄金，增加c的魔法，减少d的财富。 问如何安排才可以使得最后的财富最大。 n小于等于15。 解题思路 先看题目范围，本题的n非常非常小，很明显就是叫你二进制枚举。学聪明点，先观察数据范围。 那么二进制枚举每个物品拿和不拿最终的取值取到最大就可。当然用系统的函数栈写的dfs应该会更香一点点。 #include <bits/stdc++.h> using namespace std; type...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-08 20:20

已编辑

中国海洋大学 C++

幸运数字Ⅱ

E、幸运数字Ⅱ 戳我传送 解题思路 可以通过观察在一段区间内的值是相同的 1-3->4;4-6->7。 我们通过预处理将可能的值升序放在一个容器内，注意一点要把放进去，<-当输入1e9时。 给定l,r；我们通过lower_bound(it,it,l)，查找l在容器中的位置。一步步往下去取区间，注意特判临界情况，即第一个区间的右边界>r，最后一个区间左边界是不是要全拿。 时间复杂度 O(N) Code #include <bits/stdc++.h> using namespace std; #d...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-08 20:13

中国海洋大学 C++

题意 给出n个人m个关系，并且每个关系，给出关系u，v两个人之间的仇恨值。问最大的仇恨值是多大。 解题思路 很明显如果a，b之间存在最大的仇恨，那么肯定把a，b分隔开监狱放。那么如果b，c存在第二大仇恨，那么c就只能放到a一个监狱去了。那么后面如果出现了a，c存在仇恨那就是不可避免的最大仇恨了。 所以可以看出a->b,b->c==a->c，敌人的敌人就是朋友这个样子，使用并查集去合并集合，一个数组记录A监狱中的人物关系，再一个数组记录B监狱的人物关系。最终去判断在A监狱会不会存在冲突即可。 所以综上可得，第一步先按...

牛客算法竞赛入门课

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务