发表于

题目描述

脸哥最近在玩一款神奇的游戏，这个游戏里有 $n$ 件装备，每件装备有 $m$ 个属性，用向量 $\mathbf{z_i}=(a_1, \ldots ,a_j, \ldots , a_m)$ 表示 ($1 \leq i \leq n, \ 1 \leq j \leq m$)，每个装备需要花费 $c_i$，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

阅读全文 »

发表于

问题描述

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 $ n $ 的字符串 $ s $，和 $ m $ 个问题。佳媛姐姐必须正确回答这 $ m $ 个问题，才能打开箱子拿到礼物，升职加薪，出任 CEO，嫁给高富帅，走上人生巅峰。每个问题均有 $a, b, c, d$ 四个参数，问你子串
$s[a \ldots b]$ 的所有子串和 $s[c \ldots d]$ 的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

算法讨论

首先二分一个答案$mid$，问题变为判定$[a,b-mid+1]$区间内的后缀与后缀$c$的ＬＣＰ是否$\ge mid$

阅读全文 »