Ke2sen

题解

未归档(9) 笔记(6) 解题报告(4) 颓頽頽(1)

/ 注册

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

洛谷 P4427 [BJOI2018]求和

传送门洛谷P4427 题意：给你一个数，然后让你求这两个数之间的点的深度的k次方和. #思路：很容易想到lca.因为lca可以说是求树上两个点的距离的好方法.而且lca还能遍历每一个点. 然后我们可以用一个数组pre来存储每一个点到深度的多少次方. 处理的时候在求...

lca

2019-10-17

0 414

洛谷 P3398 仓鼠找sugar

传送门题目分析：就是给你两条路径的起点和终点，然后让你查找这两条路径有没有交点 if（有）puts("Y"); else puts("N"); 解题思路：很明显，是让我们求lca，我们先求出A与B的lca和C与D的lca，然后我...

lca 倍增 tarjan

2019-10-13

0 470

洛谷 P2010 回文日期

洛谷 \(P2010\) 传送门大体题意给定两个日期，然后让你求这两个日期中的日期有没有一个回文日期. 分析首先对于\(60%\)的数据\(data1 == data2\). 我们可以直接输出1或者输出0.每一个可以得到30分的高分. 我们直接暴力枚举的话应...

模拟

2019-10-09

0 533

洛谷 P1396 营救

P1396 传送门扯些题外话讲真的我刚看到这个题的时候真的傻fufu的..... 大体题意找出从s走到t的拥挤度最大值最小.. 思路说最大值最小可能就会有dalao开始二分了. 想我这种的蒟蒻只能打一些kruskal维持一下生活... 说...

图论二分答案

2019-09-30

0 588

洛谷 P1873 砍树

P1873 传送门题外话话说我们也要当一当光头强？？大体题意就是让你砍树，统一的高度，然后让你砍树，看看订什么高度合适. 思路：二分答案，对高度二分，如果砍得树长度不够，那就说明高度高了. 如果过长，那就说明高度设矮了（OK，开始看code）...

二分答案

2019-09-30

0 487

洛谷 P1195 【口袋的天空】

P1195 传送门大体题意：就是给你\(n\)个点\(m\)条边，然后让你把这几个点连成\(k\)个部分. 解题思路：很容易就可以想到生成树(别问我怎么想到的). 因为最小生成树中有一个判断 for (int i = 1; i <= m; ++i) {...

kruskal

2019-09-30

0 411

洛谷 P1825 【[USACO11OPEN]玉米田迷宫Corn Maze】

P1825 传送门简单的题意就是一个有传送门的迷宫问题（我一开始以为是只有1个传送门，然后我就凉了）. 大体思路先把传送门先存起来，然后跑一下\(BFS\)。然后，就做完了. 代码鸭 #include <iostream> #inclu...

BFS

2019-09-30

0 570

洛谷 P2872 【[USACO07DEC]道路建设Building Roads】

P2872 传送门首先题目概括：题目让着求使所有牧场都联通.需要修建多长的路. 显然这是一道最小生成树板子题（推荐初学者做）. 那我就说一下kruskal吧. Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。 ...

kruskal

2019-09-29

0 512

洛谷 P1967 货车运输

夏令营和济南培训的时候都讲过现在才开始刷我真的太颓了... 传送门先放个玄学东西: 思路: 先跑一下kruskal然后，LCA找最小值最大的那条路代码: #include <map> #include <set> #include &...

生成树图论 lca 倍增

2019-09-03

0 362

洛谷 P1454 圣诞夜的极光

最近做了，然后问了问学长做了没有，lfd是圣诞夜做的.... 有点后悔，我做早了. 我也想要圣诞夜有人陪我看极光...... 传送门思路：因为是曼哈顿距离小于2,就算在一个图中，那么中间的点为起点的话，那么一共有12与他相邻的点和他属于一个图案... like this：那...

搜索

2019-09-03

0 401