Zerol's Notes

题目

https://www.hackerrank.com/challenges/matrix/problem

题意

在一棵有边权的树上，要求去掉一些边，使得给定的若干个点之间两两不连通，求这些边的最小边权和。

题目

https://www.hackerrank.com/challenges/brick-tiling/problem

题意

给定一个有若干个障碍的棋盘，求用 2*3 的 L 型砖头填满的方案数。

基本思想

游戏可以等效为一个有向图，每一个状态相当于图中的一个节点，而可能的状态转移是图中的边。如果必胜态的后继中存在必败态，而必败态的后继全是必胜态。

SG函数

\[ SG(u) = mex\{ SG(v)|u \to v \} \] 函数值为 0 代表必败态，不为 0 代表必胜态。（也就是说，0 只能转移到非 0，而非 0 一定能转移到 0。） 一个组合游戏的 SG 和等于所有子游戏的异或和。

题目

http://acm.ecnu.edu.cn/problem/3479/

题意

在一个有向图中，求从结点 1 出发经过结点 2 最后回到结点 1 最少经过几个点。

题目

https://www.hackerrank.com/challenges/rust-murderer/problem

题意

求一个简单无向图的单源最短路（没有边权），但是题目给出的是该图的补图（也就是说，该图是在完全图的基础上去掉若干条边的结果）。

题目

https://www.hackerrank.com/contests/hourrank-25/challenges/the-strange-function

题意

对于给定的一列数，对于所有区间，求 f(l, r) 的最大值。

f(l, r) = (区间 gcd 绝对值) * (区间和 - 区间最大值)

题目

http://acm.hdu.edu.cn/showproblem.php?pid=4455

题意

给定一个数组，对于每次询问，求所有长度为给定值的区间的不同数字个数之和。

题目

http://acm.ecnu.edu.cn/problem/3438/

题意

给定一个由 n 条高度不等的列组成的棋盘，其中所有列的底边位于同一水平线上。求放置 k 个互不攻击的車的方案总数。（車能互相攻击当且仅当能通过棋盘上连续的一行或一列格子直接连在一起）

题目

https://www.hackerrank.com/challenges/jeanies-route/problem

题意

给一棵有边权的树，输出任意选定起点，经过给定的 k 个点的最短距离。

题目

https://www.hackerrank.com/challenges/coprime-paths/problem

题意

给一棵树，树上的每一个点都有一个至多有三个素因子的数，询问路径上互质点对个数。