呱呱咕

分类

题解(37)

/ 注册

全部文章（共37篇）

图的遍历

每次走2步，然后要求每个点都要去遍历到，那么转换一下思想就是判断奇数环，比如1-2-3-1；那么就是可以全部遍历到每个点，首先是1然后是3然后是2，那么我们是不是就是去找这个图的联通分量，然后去判断是否有奇环，如果有一个奇环，那么就是所有的联通分量-1，如果没有答案那就是所有的联通分量，手动枚举一下...

2020-05-31

0 622

maze题解

我看很多大佬都是最短路做的，然后我最短路学的不好，然后偶然间看到一个大佬和我一样想法，首先直接BFS，但是这个bfs要开一个dis数组，代表该点的最短距离是多少，然后每次去更新，分别去入队每次正常走和进入传送门的，然后每次更新。 #include <bits/stdc++.h> #d...

2020-05-22

0 645

加分二叉树题解记忆化搜索

根据中序遍历特性，在根节点前面的节点，一定在左子树；根节点后面的节点，一定在右子树。我们可以根据这个特性，结合递归的方式确定出最高加分的二叉树。我们每次查询的过程中，查询max(dp[l][i-1]*dp[i+1][r]+ans[i]); #include <bits/stdc++.h>...

2020-05-20

0 642

模拟战役题解搜索

这道题其实就是找一个连通块的个数，就是直接找八个方向，然后比较两个人的3*3范围的扩散开连通块的个数，利用DFS都跑一下两个人的连通块个数，然后就是直接贪心一下，用齐齐连通块里面个数最少的去攻打司机，最后剩下的连通块加起来就是ans了； #include <bits/stdc++.h>...

2020-05-18

0 610

Moovie Mooving题解状压DP

这题如果一看我们首先会想贪心，但是之后我们却不能找到一个合适的时间去替换，如何再看完时间的条件下，找到最少的电影次数，那么贪心不行那就只有想想DP了，这题就是用状压来过，所谓状压其实就是以二进制来处理各种位置的关系这是雨状压有关的二进制的处理。言归正传。dp[k]代表什么呢就是k在二进制下，有多少...

Moovie

2020-05-18

0 565

过河题解

这道题上手一看其实就可以很明确的感觉是DP,据说有人DFS干翻这题，%%%%，我觉得就是dp好理解一点。首先我们可以很明确的写出这个方程dp[i]=min(dp[i],dp[i+j]+vis[i]);i是当前的位置,j是我要走的步数,vis这个地方是否有石头，这个处理我们是要从后面处理到前面，因为，...

2020-05-16

0 607

codeJan与旅行题解

读题要仔细，人家说了可以重复走每个城市。然后，仔细一想可以发现，当m足够大，是不是最后一定是在2个城市徘徊，这样子才会保证答案最优，只是需要特别注意的是 hack的那组.3 10 21 10 14 答案是42那么这个就是先去了1然后再去10，然后再去14，最后徘徊在10，14。所有我们需要每次判断...

2020-05-15

0 624

皇家烈焰题解

我感觉这题就是一个模拟，但是又要用到一个DP思想，因为dp无后效，其实就是每个情况讨论一下就好，，主要判断是否有雷无雷的情况，然后设计dp状态mdp[i][0/1]；就是第i个无雷和有雷情况，这个大佬给了我很好的思路，主要模拟好就可以过。我看大佬理解的，主要还是搞清楚自己模拟的是什么，就是分类讨论...

2020-05-14

0 507

[SCOI2009]粉刷匠题解

这道题你猛的一看呢没什么头绪，但你仔细一看呢，就会发现还不如猛的一看，嘿嘿，蒟蒻自己的理解如下；看题的范围我们可以想到DP，很合适，50502500，然后就是我们dp定义的状态，看了很多大佬的四维是真的想不到，理解的很难啊，还是太菜，蒟蒻定义一个三维一个二维，二维的很容易理解就是一个分组背包，那么...

2020-05-08

0 654

滑雪与时间胶囊题解

题解：其实看到这句话a180285喜欢用最短的滑行路径去访问尽量多的景点，就很明显是一个最小生成树了，但是有点区别的是每个点只可以由高到低，而且每个点是从开始，那么我们就可以先处理每个表，首先以他们的高度从高到底排序，然后在以他们的边权由低到高排序，是不是一个克鲁斯就出来啦，套上你的板子就直接搞。P...

2020-05-08

0 632