nagisa_菜鸡

分类

题解(34)

/ 注册

全部文章（共4篇）

2021牛客暑期多校训练营1-G.Game of Swapping Numbers（思维）

题目链接：https://ac.nowcoder.com/acm/contest/11166/G题目大意：给两个数组a,b，现在可以交换a中的数k次，求的最大值。看了题解。可以这样想：把要求的值看作对每个和前面放符号，满足总的+的数目=总的-的数目。那么，最后的结果就是a、b所有数*符号后的和。统...

贪心

2021-07-20

0 725

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

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

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

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

2020-05-04

0 656

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

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

每日一题背包贪心 dp

2020-04-28

0 1068