题目

https://www.hackerrank.com/challenges/pseudo-isomorphic-substrings/problem

题意

对于一个字符串的每个前缀，求不同构的子串个数。

两个串同构定义为可以通过字符的双射变成相同的串。

• \(k\) 项线性递推求第 \(n\) 项的 \(O(k^2\log n)\) 的算法。
• 已知线性递推数列的前若干项，求递推式。
• 结合以上两者可以由线性递推数列的起始若干项得到任意一项。

题目

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

题意

求树 T 的子树（联通块） T' 的个数 ，满足 T 与 T - T' 之间至多有 K 条边相连。

反正是用来卷的。

整体二分

资料

具体见 2013 年集训队论文《浅谈数据结构题的几个非经典解法》（作者：许昊然）。
本文假设读者已经读过这篇论文中整体二分的部分。

限制

• 需要离线
• 可以二分答案
• 修改操作，要求对于一次查询，前面的修改操作可以交换顺序而不影响查询结果
• 贡献可以累加
• 注意将操作（包括询问）分离到两个新的答案区间这个过程的复杂度应该和操作数的个数相关，而不能和以下两项相关：
  • 总的区间（就是最初的答案区间）
  • 尤其是序列总长，通常指的是询问区间的长度

题目

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

WF 2011 数据

题意

\(D​\) 天，初始资金 \(C​\)，\(n​\) 台机器，最多持有一台机器。每台仅能够在 \(D_i​\) 天购买，价格 \(P_i​\)，可以在之后任意一天以 \(R_i​\) 卖出，从购入次日起每天产生 \(G_i​\) 的收益，卖出当天无法获得收益，但是可以立刻购入另一台机器。在 \(D+1​\) 天卖出手中机器并结账。

题目

https://www.hackerrank.com/challenges/coloring-tree/problem

题意

询问子树结点中的出现过的颜色总数。

题目

https://www.hackerrank.com/challenges/bst-maintenance/problem

题意

按照给定顺序往二叉查找树中添加结点，回答每次添加结点后的所有结点对的距离和。

题目

https://www.hackerrank.com/challenges/number-game-on-a-tree/problem

题意

给一棵树，求有多少结点的有序对使得先手必胜。

对于一个有序点对，在路径上的边权集上玩一个游戏，轮流移除一个数字，要求比不超过之前移除的所有数字，无法操作者为败者。

题目

https://www.hackerrank.com/contests/w38/challenges/cargo-delivery

题意

给一个简单无向图，有 k 个人要依次从 1 到 n。一开始边权为 0，每经过一次边权 +1。有 t 次机会使一条边边权 -1。最小化所有人每个人经过的边权的最大值的最大值。