Rooobin

Rooobin : 数据结构 1047 密码碰撞题解
1 年,8 月前

题意简要来说就是给定若干个字符串,判断任意一对字符串$(s_i, s_j)$,其中满足$s_j是s_i$的子串的对数,题中所说的有序只是为了避免重复计算,比如 5 mir mirta ta ir t 其中满足题意的有 6 对 ( mir , ir ) ( mirta , mir ) ( mirta , ta ) ( mirta , ir ) ( mirta , t ) ( ta , t ) 首先第一想法肯定是暴力的记录每一 ...查看全文
Rooobin : 数据结构 1013 欣赏书法题解
1 年,10 月前

1013 欣赏书法题解 需要维护一个双向队列 从左往右遍历作品编号依次加入队列中,包括了所有大师的作品即停止,然后队首元素不断出队直到某队首元素出队后会导致队列不再包含所有大师的作品,这时形成一个最短的基础队列。(易知,如果队首出队一些元素仍符合题意条件,那么队列一定变小) 在此基础上,继续从左往右遍历,将新的作品入队,每入队一次,队首元素不断出队直到不包含所有大师的作品,如此反复直到遍历完所有作品,每进行入队-出队操作后,更新队列的头尾对应的下标 由于始终从左往右遍历,那么一定得到的是队首 ...查看全文