sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

全部文章 / 题解（共372篇）

[SDOI2016]齿轮

Solution 前言：相比于前向星，我更喜欢vector，码量更小。根据题目意思，构建一个无向图，无向图的花费部分需要记录两个变量，一个是自己的x，一个是终点的y。这里要记得换起点要换x和y。那么这里把深度优先搜索遍历全部节点，把从未遍历过的节点定义成1.0，其余节点去根据x，y去确定第一次来到的...

2020-04-29

0 715

阶乘

Solution 题面简洁明了，（就喜欢这种题面）。首先我们需要知道的前导知识，任何一个数，都可以分解为一些素数的幂之积，又叫唯一分解定理，那么对于阶乘这样一个乘积运算，自然也可以进行多次分解质因数。写成素数幂之积。这里给出阶乘求解质因数幂的算法 ll factory(ll n, ll s) { /...

2020-04-28

0 905

装备合成来自专栏

Solution 根据题意已知有2种合成方法，假设A方法合成a件，B方法合成b件成品。那么可以得到对应式子约束条件为：a>=0；b>=0；2a+4a<=x；3a+b<=y **（注意a,b才是未知数x,y是已知的，并且）**求解: z = a...

2020-04-28

2 734

【每日一题】4月28日美味菜肴来自专栏

Solution 题面把意思说的比较清楚，其实可以比较明显的知道，这是一个从n件物品选一些出来，需要收益最大。挺明显的01背包，但是直接按照01背包来做确实错误的。想想为什么？没错，背包问题，是动态规划的过程，动态规划需要满足两个性质，最优子结构和无后效性。显然这个题目直接做不满足无后效性，改变做菜...

2020-04-27

1 850

牛客练习赛62

这次练习赛难度有点裂开。。 A、牛妹的游戏解题思路：其实题意比较简单，我们假设给出的点，没有被蓝色方占领的边全部被绿色方战领。这样我们就可以得出一个结论，只有三条边成一个环，才可能被控制，否则四个条边的话，如果中间存在自己家的边，就会形成三边环，否则就不构成控制区域。现在题目就转变成求图或者补...

2020-04-25

1 795

【每日一题】4月24日子序列来自专栏

讲到子序列，而且有大小关系，应该可以第一时间想到和动态规划有关系，带着这个思路，我们再看下题目。对于每个位置（i，j），都要存在两边同时取对数，再相除得到题目就变成了求以为判断条件的递增子序列问题，问题规模比较小，可以直接二重循环遍历，也可以发现只和单个变量有关系，可以通过离散+树状数组取优化...

2020-04-24

2 815

【每日一题】4月23日边的染色来自专栏

解题思路，这道题目看题解才看出来的，先看边权其实不好操作，那么我们可以调整一下，一条边连接2个点，把边权，改成它连接2点的异或值，一个环的异或值需要为0，对于环中的点，开头的点任意取1，或者0，对于整个环的异或值 =0恒成立。所以对于连通块，首先对于给定0，1值的边，保存起来，通过我们...

2020-04-23

1 679

数学

wnm喜欢的数学题解题思路比较明确，也没啥难的，除了一个比较弱的考点，两数最小公倍数等于两数乘积除以最大公约数。一个数等于两个数乘积一定能被小于等于的数整除，比如9被1整除（1，9）9被3整除（3，3）平方根3只能算一个因子，所以因子个数就更少了，所以我们直接把全部的因子保存起来，再通过二重循环...

2020-04-23

2 669

牛客算法周周练3

A、Jelly 给定三维地图，并且给出不能走的位置）星号，问从到的最短路径是多长。挺裸的题目，这里提醒一下走图最好别用DFS会爆内存死的很惨。规定移动方向，判断是否越界，在判断这个点是否走过，在判断这个点是不是不能走的位置，如果都不是，就把这个点进队，位移长度是前一个走法加一，一直到，因为...

2020-04-22

0 580

【每日一题】4月22日K-th Number 来自专栏

题目大意从给定的A数组，选择全部的长度大于等于K连续子集，构成新的集合，并且从这个集合里面每个拿出第K大加入到B数组中，最后要求B数组中给定的第M大元素。解题思路其实这个题目看了挺久都没什么思路和想法，想过去模拟，或者全部保存。。不过空间复杂度和时间复杂度都是，有点难顶。走投无路的时候...

2020-04-22

1 854