【题解】EOJ - 棋盘上的車 (bzoj 2616 - SPOJ PERIODNI)
题目
http://acm.ecnu.edu.cn/problem/3438/
题意
给定一个由 n 条高度不等的列组成的棋盘,其中所有列的底边位于同一水平线上。求放置 k 个互不攻击的車的方案总数。(車能互相攻击当且仅当能通过棋盘上连续的一行或一列格子直接连在一起)
http://acm.ecnu.edu.cn/problem/3438/
给定一个由 n 条高度不等的列组成的棋盘,其中所有列的底边位于同一水平线上。求放置 k 个互不攻击的車的方案总数。(車能互相攻击当且仅当能通过棋盘上连续的一行或一列格子直接连在一起)
https://www.hackerrank.com/challenges/coprime-paths/problem
给一棵树,树上的每一个点都有一个至多有三个素因子的数,询问路径上互质点对个数。
https://www.hackerrank.com/contests/w34/challenges/recurrent-on-tree
给一棵树,每个点有一个值。求任意两个顶点(可以相同)路径上的值的和经过 f 函数后的和。f(x) 是斐波那契数列第 x 项。
https://www.hackerrank.com/challenges/lena-sort
题目中用伪代码给出一个排序算法,要求构造 1~n 的一个排列,使得排序过程中恰好比较了 k 次。
https://www.hackerrank.com/challenges/synchronous-shopping/problem
有 k 种商品,简单图上每个点上有若干种商品,购买商品不需要时间,两个人同时从 1 出发最后在 n 汇合,使得两人购买的商品囊括了所有的 k 种。 注意数据范围。
https://www.hackerrank.com/challenges/unique-colors
给定一棵树,树上每一个点都有一种颜色。定义一条路径的价值为路径上不同颜色的点的个数。对于树上的每个结点,输出从该结点出发的所有路径的价值之和。
代码详见模板库。模板题 EOJ 3389-3393。
Q: 要不要把 n 补成 2 的幂?
A: 这个无所谓,但如果要写成自底向上,那么还是需要的,否则无法直接定位叶节点。
Q: pushdown 之后要不要立即 maintain?
A: 不用立即 maintain,但迟早是要的。但是立即 maintain 很可能会重复 maintain,增加超时风险。
Q:query 的时候要不要 pushdown?
A: 如果不要的话,查询时应该把之前访问到的结点的标签的效果累加起来,并作为参数递归下去。如果要的话,代码会更加具有普适性(比如 treap 只能选择 pushdown 标签,因为结点之间相对位置会改变)。
Q: maintain 的时候是否考虑当前结点的标签?
A: 都可以。如果考虑了,那么查询的时候就不要考虑当前结点的标签了,反之亦然。
Q: query 的时候先考虑 set 标签还是先考虑查询区间包含当前区间?
A: 都可以,但是先考虑 set 会快一些。
Q: 根节点是 0 还是 1?
A: 都可以,但好像 1 比较符合人性。
Q: 听说空间开三倍就够了?
A: 那可能就 GG 了,实测 4 倍是必要的。
其他注意事项:
https://www.hackerrank.com/challenges/counting-on-a-tree
给一棵树,树上的每一个点都有一个数字,询问对于给定的两条树上路径,有多少对不同的且分别属于两条路径的点满足对应数字相等。