流锡 - 个人主页动态 - 牛客网

发布(64) 刷题

2021-10-19 11:20

华南农业大学计算机类

题解 | #免费馅饼#

思路：dp 开一个dp[i][j]数组，其中i代表位置,j代表时间 然后在馅饼恰好收集到的时候dp[pos][t]+=val(pos代表馅饼位置,t代表下落到的时间,val代表馅饼价值) 之后我们按时间从后往前枚举位置与操作即可 为什么不从前往后枚举？ 因为你一开始的位置你是知道是dp[w/2+1][0]的 如果往后枚举那么就不知道最大的价值在哪个位置，就不好弄方案 往前枚举就让dp[w/2+1][0]这时候拥有的价值最大 再另外开个la[i][j]数组保存方案即可 具体见代码注释 AC代码： #define long long int using namespace std; int dp[...

0 点赞评论收藏

转发

2021-10-14 20:14

华南农业大学计算机类

题解 | #wyh的问题#

思路： 区间dp 设dp[l][r]表示[l,r]区间人在左端点里最小的耗电值 dp[r][l]表示[l,r]区间人在右端点的最小值 设起点为st 因为l<=st,r>=st所以这样设置dp不会有重叠的情况 然后就推方程啦 先用前缀和记录前i个电灯的每秒耗电量 同时可以注意到人在左端点的时候，可以是上一个左端点向左边走一步，也可以是右边的右端点走到了这个区间的左端点 那么方程就是 dp[l][r]=min(dp[l][r],dp[l+1][r]+(a[l+1]-a[l])×(sum[n]-sum[r]+sum[l]),dp[r][l+1]+(a[r]-a[l])×(sum[n]-s...

0 点赞评论收藏

转发

2021-09-24 10:27

华南农业大学计算机类

题解 | #To the Max#

题目大意：给你一个矩阵让你求长宽无限制的最大矩阵和 思路：对于二维数组我们可以这样考虑a[1][1],a[1][2],a[1][3]······a[2][1],a[2][2],a[2][3]······a[3][1],a[3][2],a[3][3]······、a[j][1],a[j][2],a[j][3]······我们设i<j，则我们可以转化第i行到第j行的二维数组为一维数组把相同列的数字都加起来即{a[i][1]+a[i][2]······,a[i+1][1]+a[i+1][2]······,a[j][1]+a[j][2]······}那么问题就转化一维数组成了求最大子段和然后直接...

0 点赞评论收藏

转发

2021-08-11 11:50

华南农业大学计算机类

题解 | #Lighting System Design#

紫书经典题目了思路就是dp这里有个点就是一个种类的灯泡要么不换，要么全换，因为你换一半的时候需要两个电源的费用，而且你要换的话肯定往便宜的换，那肯定全换先按电压从小到大排序令d[i]为前i个种类的灯泡的最小费用那怎么找呢我们可以先让d[i]为前i个种类的全部灯泡全部转化成第i个种类的灯泡则我们用一个j遍历1到i而前j个种类的灯泡我们就用d[j]表示最优解的时候让后面i-j个种类的灯泡都转化为第i号电源再相加方程就出来了d[i]=min(d[i],d[j]+(sum[i]-sum[j])*a[i].c+a[i].c) AC代码 #include <bits/stdc++.h> us...

0 点赞评论收藏

转发

2021-07-03 19:59

华南农业大学计算机类

题解 | #An Easy Problem#

题目大意：给你三个数n,m,k然后会根据n,m生成数列1×1,1×2,······,1×m2×1,2×2,······,2×m···n×1,n×2,······,n×m问你将这些数字中第k大的数字是多少 思路：两种做法一种是堆一种是二分看到这题的时候想到了这两种做法但又不知道具体咋做 - - 第一种堆思路设置一个pair类型的堆每次就插入从1×m到n×m的元素依次插入值与左边下标进入堆中然后算第k大的时候就每次找堆顶元素把堆顶元素减去一个下标再放入堆中（这样就代表了n*(m-1)的元素进入了堆中然后反复操作找第k大即可时间复杂度是 nlogn+klogn 堆代码： #include <b...

0 点赞评论收藏

转发

2021-06-19 16:14

华南农业大学计算机类

题解 | #Calling Circles#

题目大意：如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这四个人在同一个圈里；如果e打给f但f不打给e，则不能推出e和f在同一个电话圈。输入n(n<=25)个人的m次电话，找出所有的电话圈。人名只包含字母，不超过25个字符，且不重复。思路：(传递闭包)如果一个节点i与j相连，j与k相连，那么i与k相连就是计算两点是否相互连通求传递闭包就是把所有这样的点都弄出来可以用floyd去搞代码： #include <bits/stdc++.h> using namespace std; map<string,in...

0 点赞评论收藏

转发

2021-06-18 13:03

华南农业大学计算机类

题解 | #小石的妹子#

思路：线段树先对ai进行排序对于排序后的第 i 个妹子，她的排名就是 max{rk[j]}+1 (其中bj必须大于bi)，之后对于bi我们先去离散化后开个线段树让bi作为位置，重要程度ti作为树中的值我们就找从bi到n位置中最大的ti是多少找到后返回的值就是这个人的重要程度（就是开个线段树找比b大的数的p[i]是多少） AC代码： #include <iostream> #include <vector> #include <algorithm> #define mid (l+r>>1) using namespace std; const in...

0 点赞评论收藏

转发

2021-06-18 11:06

华南农业大学计算机类

题解 | #Inspector's Dilemma#

题目大意：给你V,E,T三个数字每条边长度为T给你V个点，每个点都两两连接再给你E条边让你输出包括这E条边的最短路径 思路：欧拉道路通过图G中每条边一次且仅一次的道路称作该图的欧拉道路。无向图G存在欧拉道路当且仅当G是连通的且奇数度顶点不超过2个连上这E条边看有几个连通块就补上连通块-1数量的边同时还要看连通块中奇数度数点是不是只有两个不是的话要给它补上(奇数度数点-2)/2条边注意这里奇数度数的点必定是偶数因为无向图中所有点度数之和都是偶数那么奇度数点之和也必定是偶数 AC代码： #include <iostream> #include <vector> #inclu...

0 点赞评论收藏

转发

2021-06-16 22:25

华南农业大学计算机类

题解 | #红球进黑洞#

思路：因为没有关于异或的公式能对区间进行操作的我们可以对于二进制的每一位都建一个线段树对于每一位的区间我们是可以进行操作的因为异或一个区间（区间中所有单点（叶子节点）的值是0或1）这个区间的区间和就等于这个区间的长度减去原本的区间和这样就能利用lazy对于每一位进行操作了设 i 为左移了多少位区间求和的时候就把答案加上每一位对应线段树的对应区间和乘上(1<<i)即可 AC代码： #include <iostream> #define mid (l+r>>1) using namespace std; typedef long long ll; const i...

0 点赞评论收藏

转发

2021-06-15 22:26

华南农业大学计算机类

题解 | #换个角度思考#

思路：看没人写莫队算法自己就写了一下写了一下发现和不同的莫队算法不一样普通的莫队算法不支持修改操作而这里因为询问的k会变你之前的区间的值都会受影响问了一下大佬结果学到了带修改莫队对于普通的莫队我们再加上一个变量t[a[x]]表示a[x]出现的次数再新增一个变量now，在每次询问中对于now<k的情况我们就让对于now>k的情况进行相反操作即可同时对于每个询问的排序要加第三关键字如果右边界处于同一块就按k大小进行排序这里分块size大小用的是n的2/3次方听说时间复杂度是 （但具体还没搞明白）之后这题就能过了（因为主席树也练了一下后面附上主席树代码（有注释）)树状数组也写了一下发现三...

0 点赞评论收藏

转发

2021-06-15 12:14

华南农业大学计算机类

题解 | #华华开始学信息学#

思路：分块，树状数组直接树状数组进行add操作for(int i=d;i<=n;i+=d))add(d,k)时间复杂度起码是O(n^m^)=1e10，肯定t这个时候我们可以考虑进行分块操作对于d小于等于√n的我们就存到一个lazy数组里大于√n的我们就直接进行树状数组的add操作这样的话根据上面那个循环我们add操作时间复杂度差不多是log^2^(n)(树状数组本身add操作为logn)而lazy操作为O1查询区间和的时候lazy操作为logn（直接扫一遍下标小于logn的数)得树状数组和也为logn这样就能大大优化时间复杂度得到答案了 AC代码： #include <iostre...

0 点赞评论收藏

转发

2021-06-13 19:32

华南农业大学计算机类

题解 | #背包#

题目链接：https://ac.nowcoder.com/acm/problem/17315题目：Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大Applese觉得这个题依然太菜，于是他把这个问题丢给了你当物品数量为偶数时，中位数即中间两个物品的价值的平均值 思路：堆+二分虽然题目说是背包但看数据范围1e5的数据明显不符合背包的时间复杂度并且中位数看着也不像用dp能解决的问题（有后效性）这时候我们可以这样想，既然我要求最大的中位数那么我...

0 点赞评论收藏

转发

2021-06-03 17:01

华南农业大学计算机类

题解 | #魏迟燕的自走棋#

题目链接：https://ac.nowcoder.com/acm/contest/9984/F 题目大意：给你n个人与m件装备，其中每个人都只能对应配一件装备，每件装备也只能配对应一个人。每件装备可能对应的人有一个或者两个同时每件装备具有wi点战斗力问你最大能获得多少战斗力思路：感觉有点类似最大生成树把每件装备的战斗力都当作边值，人的编号当作点因为是要最大战斗力那么肯定要排序先最大的边进行合并利用并查集来合并点，再利用辅助数组v[]判断点是否用过同时要考虑一下自环的情况（就是每件装备只能对应一个人的时候）如果这个点没用过就把它选上AC代码： #include <iostream&gt...

0 点赞评论收藏

转发

2021-06-03 10:58

华南农业大学计算机类

题解 | #简单瞎搞题#

思路：因为数据量小，我们可以利用桶取储存每个数最终能不能被选出的方案那么可以采用dp的方法,f[i][j]中的i表示第i层（输入给的第i行)j表示Σ(xi×xi)，我们看f[i][j]是否等于1判断j是否是存在于答案之中的那么如果我们设l<=k<=r，状态转移方程就是f[i][j]=f[i-1][j+k×k]表示在下一层当中，上一层1的位置再加上k×k就是下一层新的1的位置但这么做 j 是从1到1e6循环的，很明显会超时这时候因为采取的是01串，我们可以利用bitset进行优化因为f[i][j]=f[i-1][j+k×k]就相当于f[i]|=f[i-1]<<(k×k)（...

0 点赞评论收藏

转发

2021-06-02 19:57

华南农业大学计算机类

题解 | #新比赛，在眼前。#

链接：https://ac.nowcoder.com/acm/contest/16806/A来源：牛客网 题目描述我们刚刚学了二分查找——所谓二分查找就是在一堆有序数里找某个符合要求的数。在学完二分查找之后如果让你玩猜数游戏（裁判选定一个目标数字，你说一个数裁判告诉你是高了还是低了直到你猜到那个数）的话，显然你会用二分的方式去猜。但是不是每一个玩猜数游戏的人都知道二分是最好，甚至一个健忘的玩家都有可能在得到裁判回答的下一个瞬间就忘了他之前问了什么以及裁判的回答），而现在更可怕的是，这个告诉你猜的数是高还是低的裁判他也很健忘，他总是薛定谔的记得这个目标数字，也就是说他的回答有可能出错。我们已经不...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务