流锡

分类

题解(49)

/ 注册

全部文章（共49篇）

题解 | #游戏#

考虑用dp解决问题我们设li,jl_{i,j}li,j表示到第i个人最后一个人赢的选择为第j个选择的概率设ri,jr_{i,j}ri,j表示上一个人赢的选择为第j个选择并且它会一直赢到最后的概率那么就有转移方程（get(i,j)表示在第i个人中选择j的概率） li,j=li−1,j×(ge...

C++

2022-04-16

0 531

题解 | #爬塔#

思路：因为长度小于等于10，我们可以对于每个长度开一个set存每个长度中符合要求的两个下标i,j 之后用二分lowerbound对于每个长度去查找即可（还有这题数据也弱了，测了一下很多代码都是超时的） #include<bits/stdc++.h> using namespace s...

C++

2022-03-26

4 563

题解 | #免费馅饼#

思路：dp 开一个dp[i][j]数组，其中i代表位置,j代表时间然后在馅饼恰好收集到的时候dp[pos][t]+=val(pos代表馅饼位置,t代表下落到的时间,val代表馅饼价值) 之后我们按时间从后往前枚举位置与操作即可为什么不从前往后枚举？因为你一开始的位置你是知道是dp[w/2+1]...

C++ 动态规划

2021-10-19

2 678

题解 | #wyh的问题#

思路：区间dp 设dp[l][r]表示[l,r]区间人在左端点里最小的耗电值 dp[r][l]表示[l,r]区间人在右端点的最小值设起点为st 因为l<=st,r>=st所以这样设置dp不会有重叠的情况然后就推方程啦先用前缀和记录前i个电灯的每秒耗电量同时可以注意到人在左端点的...

C++ 动态规划

2021-10-14

3 851

题解 | #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...

C++ 动态规划

2021-09-24

0 499

题解 | #Lighting System Design#

紫书经典题目了思路就是dp这里有个点就是一个种类的灯泡要么不换，要么全换，因为你换一半的时候需要两个电源的费用，而且你要换的话肯定往便宜的换，那肯定全换先按电压从小到大排序令d[i]为前i个种类的灯泡的最小费用那怎么找呢我们可以先让d[i]为前i个种类的全部灯泡全部转化成第i个种类的灯泡则我们用一个...

dp

2021-08-11

0 533

题解 | #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大的数字是多少思路：两种做法一种是堆一种是二分看到这题的时候想到了这两种做法但又不知道具体咋做 - - 第一种...

二分堆

2021-07-03

9 623

题解 | #Calling Circles#

题目大意：如果两个人互相打电话（直接或者间接），则说他们在同一个电话圈里。例如，a打给b，b打给c，c打给d，d打给a，则这四个人在同一个圈里；如果e打给f但f不打给e，则不能推出e和f在同一个电话圈。输入n(n<=25)个人的m次电话，找出所有的电话圈。人名只包含字母，不超过25个字符，且不...

最短路

2021-06-19

0 482

题解 | #小石的妹子#

思路：线段树先对ai进行排序对于排序后的第 i 个妹子，她的排名就是 max{rk[j]}+1 (其中bj必须大于bi)，之后对于bi我们先去离散化后开个线段树让bi作为位置，重要程度ti作为树中的值我们就找从bi到n位置中最大的ti是多少找到后返回的值就是这个人的重要程度（就是开个线段树找比b大的...

线段树

2021-06-18

0 499

题解 | #Inspector's Dilemma#

题目大意：给你V,E,T三个数字每条边长度为T给你V个点，每个点都两两连接再给你E条边让你输出包括这E条边的最短路径思路：欧拉道路通过图G中每条边一次且仅一次的道路称作该图的欧拉道路。无向图G存在欧拉道路当且仅当G是连通的且奇数度顶点不超过2个连上这E条边看有几个连通块就补上连通块-1数量的边同时...

欧拉道路

2021-06-18

0 521