nagisa_菜鸡

分类

题解(34)

/ 注册

全部文章（共34篇）

Forsaken喜欢数论解题报告(素数筛求最小值因子)

这道题需要了解素数筛的原理，而不是只是套模板。需要明白一点，我们在欧拉筛中筛掉合数用的是这个合数的最小值因子。还记得那一步if(i%primes[j]==0) break;吗？这一步就保证我们用的是最小值因子筛掉所有的合数。我们可以这么理解，当i%primes[j]的时候，i=k*primes[j]...

每日一题数论

2020-06-23

1 659

传球游戏(记忆化搜索/dp)

默认的dp原问题是问最后回到1点的可能方法。子问题是已知上一部传到各点的方法数，求这一步传到某一点的方法数。设状态dp[i][j]为在第j步的时候，求传到i的方法数状态转移方程为dp[i][j]=dp[left][j-1]+dp[right]j+1.这里给出两种写法。 #include <io...

dp

2020-06-14

0 725

合唱队形解题报告(LIS)

思路很简单，就是枚举最高点，然后两边分别lis再求len1+len2+1的最大值，主要是lis的nlogn写法。 #include <iostream> #include <map> #include <ctime> #include <vector>...

dp

2020-06-14

0 691

牛客算法周周练10 解题报告(A.签到 B.贪心 D.暴力 E.二分答案 F.树形dp)

A.论如何出一道水题签到题，注意下特殊情况 n=input() n=int(n) if n==1: print(2) else: print(2*n-1) B.暴力出奇迹感觉好难想。。这道题的方法是：按位把ai分解，然后，按照二进制位，纵向的看各个ai，若在一段中ai在某一位上都是1...

dp

2020-06-14

0 780

after与迷宫解题报告(BFS 地图预处理)

这道题的解法非常妙。一开始，我的想法是：在bfs是搜索过程中带着状态变量con(表示是否遇到过墨菲斯托或莉莉丝，两个都遇到了这个路线就不成立，可以pop掉。)但是发现这样vis数组会其冲突，压缩起来会比较麻烦。参考大佬的解法：分两次bfs第一次，将墨菲斯托的位置全部设为无法进入，莉莉丝设为空房间，b...

搜索

2020-06-08

1 807

牛客算法周周练8 题解 A(dp) B(dfs) C(线段树维护差分数组+gcd性质) D(暴力) E(思维)

A.小A买彩票一开始想到排列组合，但是发现太菜不会写orz。看到数据范围小，想直接暴力，TLE，然后，联想到记忆化搜素减少搜索，所以应该是dp。但是菜鸡并不会设计状态（划掉），所以，只能写dfs+记忆化搜索。 #include <iostream> #include <map&g...

2020-05-27

1 730

2020年牛客算法入门课练习赛1 题解A(快速排序求第k小数/STL)B(STL)C(三分)D(差分+离散化)E(乱搞)

本来不想打的，结果看着看着自己就打进去了（笑哭） A.第k小数记得上课讲过。这道题卡排序（但听说有人排序过了？？） #include <iostream> #include <map> #include <ctime> #include <vector&g...

二分 dp 数据结构树状数组

2020-05-27

0 573

NC16655 过河解题报告(dp)(离散化)

思路首先，这道题还是比较容易能想到可能可以用dp解决的，因为最终的结果可以由前面的问题的解推出，具有最优子结构的特点。然而，问题是桥长度长达1e9，开不了这么大的dp数组。对于数据范围较大导致暴空间，我们的一个处理方法就是离散化。但是这里需要怎么离散化呢？看了大佬的题解(膜拜一下orz)，由于s和...

dp

2020-05-18

1 925

NC53683 「火」皇家烈焰结题报告(dp)

这道题还是比较容易能看得出是dp的。但是这个状态设计我不会，参考了大佬们的题解。这个状态的设计需要考虑到：由于每个格子的状态和前后都有关，所以，单纯一个维度是不足以准确表示状态然后进行状态转移的。俗话说得好：表达不准确？再来一维（我自己编的23333），我们可以考虑多维表示状态。因为想到：我们要确定...

dp

2020-05-16

0 637

[SCOI2012]滑雪与时间胶囊结题报告（最小生成树）

看到这道题，发现不会最小生成树，遂昨晚熬夜补了prim算法，今天来写这道题。看到时间胶囊能回溯，因此确实可以想得到是最小生成树，其实就是最小生成树后求路径长度和最小的问题。这道唯一特别一点的地方就是只能从高处到低处，并且要保证能去的地方最多，所以贪心策略需要加一条：以边终点高的优先选择，保证高度高（...

最小生成树每日一题图论贪心

2020-05-04

0 656