【题解】HackerRank-Two Strings Game
题目
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/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
对于一个字符串的每个前缀,求不同构的子串个数。
两个串同构定义为可以通过字符的双射变成相同的串。
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 台机器,最多持有一台机器。每台仅能够在 Di 天购买,价格 Pi,可以在之后任意一天以 Ri 卖出,从购入次日起每天产生 Gi 的收益,卖出当天无法获得收益,但是可以立刻购入另一台机器。在 D + 1 天卖出手中机器并结账。
https://www.hackerrank.com/challenges/bst-maintenance/problem
按照给定顺序往二叉查找树中添加结点,回答每次添加结点后的所有结点对的距离和。