RainAir
My OI Blog
RainAir


文章归档

「SDOI2010」魔法猪学院

题目描述 给定一个有向图,要求前K短路的路径和小于等于M,求K的值。 链接 题目分析 这一题是A* 模板题。 ~~我才不会告诉你A*在Luogu被卡成了92分呢~~ 对于A*,我们首先要知道一个叫估价函数的东西:$ f(x) = g(x) + h(x) $ $ f(x) $表示总估价值,$ g(x) $表示当…

   107   2018-02-24 去围观

最近公共祖先

题目描述 给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 数据范围:$ N,M <= 500,000 $ 求解方法 我们可以使用树上倍增的方法。设$ f[u][i] $表示u结点学向上爬2^i层后到达的点。 那么预处理方程显而是$ f[v][i] = f[f[v][i-1]][i-1], f[v][0] =…

   224   2018-02-24 去围观

「NOI2002」银河英雄传说

题意描述 有 300,000 个元素,每种元素初始时以单独队列存在,支持下面两种操作: 1.合并两个队列,即将x元素所在队列首部接至y元素所在队列的尾部。 2.查询两个元素x,y是否在同一队列,如果是,则求两元素的间隔元素的数量 操作 500,000 次 链接 洛谷 题解 …

   94   2018-02-20 去围观

「SCOI2005」互不侵犯King

在清北学堂DP&Graph班里学到了这一题,状压DP的入门题目 题目描述 题目背景 在N×N的棋盘里面放K个King,使他们互不攻击,共有多少种摆放方案。King能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 输入输出格式 输入格式…

   149   2018-02-09 去围观
文章归档