nagisa_菜鸡

题解

/ 注册

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

2021寒假算法基础集训营6（A.C.D.水 I.BFSJ.MST B.F.推式子 E.dp G.dp(TSP)/贪心）

写给自己：主要要看的是B.F.E.G总结：1.对TSP问题认识不足。2.B题模3这个条件的性质不清楚。3.复数快速幂？不敢往复数想。注意：为了阅读效果，我把头文件、快读快写删了。需完整代码可以看我提交 A.回文括号序列计数 ll solve(){ if(n==0)return 1; ...

数论贪心 dp

2021-02-26

0 657

2020年牛客算法入门课练习赛3 解题报告(A最短路 B容斥 C线段树 D DP E 思维)

打开博客发现上次咕咕咕了写一半。。想想还是补完，顺便复习下。 A、胖胖的牛牛好像bfs也行。我这里用的是dfs，后来用了最短路解。这里主要说最短路。将每个点分成上下左右四个点，用点，其中i、j是点坐标，k为其方向：0为左，1为上，2为右，3为下，(因为当i=n,j=n时，，所以是)然后用0点作为超...

搜索 dp 数据结构

2020-07-15

1 664

传球游戏(记忆化搜索/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

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

NC14704 美味菜肴解题报告（DP(01背包)、贪心）

思路分析看到每一道菜有选和不选两种决策，我们想到了01背包。但是，和普通的01背包相比有个区别，就是做每一个决策是具有后效性的：选了i道菜会影响i+k道菜的价值，也就是说，菜的价值会和选的顺序有关。因此，我们需要利用一个贪心确定一个选择的顺序，令按照这一顺序选择答案最优。通过证明我们可以得到可以按...

每日一题背包贪心 dp

2020-04-28

0 1068