题目

https://www.hackerrank.com/challenges/two-strings-game/problem

题意

有字符串 A & B，以及 A 的子串 A'，B 的子串 B'。两个人轮流在 A' 或 B' 后追加字符，同时保证为对应串的子串， 无法继续追加则失败。问先手的所有必胜态 (A', B') 中，字典序第 K 小的。

题目

https://www.hackerrank.com/challenges/letter-islands/problem

题意

​对于一个字符串 \(s\) 的子串 \(s'\)，\(f(s')\) 的值就是把 \(s\) 中所有 \(s'\) 完整出现过的位置中 \(s'\) 的每一个字符出现过的位置全部拿出来，所得到的线段条数（如 ababaewabaq 中把 aba 出现过的位置标记出来就是 XXXXXewXXXq ，那么答案是 2）。

求满足 \(f(s')=k\) 的 \(s'\) 的个数。

题目

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

题意

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