给定一个字符串, 给定一个特定操作方式: 该字符串前半段 + 该字符串自己 + 该字符串后半段求next(每一个字符向后移动一个), 组成一个新字符串, 求经过10^100次这样的操作后, 新字符串的后m位是什么
题意说明了字符串一定是偶数长度的, 根据给定的数据范围, 可以确定最终的答案只与后半段字符串有关, 那么我们可以在一开始直接截取原字符串的后半段, 通过模拟该变化, 当字符串长度达到m后, 计算距离10^100次变化还差多少次变化即可. 由于每26次求next后都会变为其本身, 那么我们只要知道10^100 MOD 26的大小, 即可直接求出最终答案
有a个原料, 通过b个原料可以生成一个产品, 有两种buff: p%的概率同样的原料生成2个, q%的概率在生成后拿回一个原料, 每次生成只能选择一个buff, 求最终生成产品个数的期望
很显然是个dp, 定义dp[i]为有i个原料时生成产品个数的期望, 那么转移公式为: dp[i] = max(dp[i - b] + (1 * p%), 1 + q% * dp[i - b + 1] + (1 - q%) * dp[i - b]), 表示每次取两种buff的最大值: 多生成一个, 从dp[i - b]转移而来, 和有q%从dp[i - b + 1]转移而来的概率和1 - q%从dp[i - b] 转移而来. 然而, 还需要考虑一种特殊情况: b == 1时, 会有一种: 每次都有q%的概率不用消耗原料就可以生成结果的情况, 对于这种情况应当修改q部分的公式, 那么对于使用1个原料可以生成的结果的期望为1 / (1 - q%), 因此对于这种情况q部分的公式应当为1 / (1 - q%) + dp[i - b].
两个字符串s和t, 一次修改可以把从某个位置到最后的所有字符向后位移若干位, 求从s修改为t的最少操作次数.
难度仅次于签到题的题目, 对每一位进行判断, 计算s和t相应位上的差值, 如果差值和前一位变化, 那么就需要一次操作, 记录次数即可.
一个电梯有n个人, 每个人都有一个想去的楼层, 共有m个楼层需要停靠, 求一层楼最多想去的人数.
签到题. 对于其他m - 1个楼层每层1个人, 那么一层楼最多的想去人数为n - (m - 1) = n - m + 1.
每组样例有n个字符串, 求任意两个字符串中相同子串的最长长度.
仅次于仅次于签到题题目的难度. 数据范围很小, 直接枚举所有子串即可. 开一个set记录之前所有子串， 开一个set记录当前字符串所有的子串, 如果当前的子串存在于之前的set中, 更新答案, 子串枚举完成后把所有子串放入前一个set即可.
上一题反过来, 给定字符串个数, 给定最长相同子串长度, 给定字符串长度, 生成字符串满足要求.
首先生成两个字符串, 使得他们的相同子串长度满足要求, 所以让一个全是a, 一个为aaabbb, 那么相同子串的长度就确定了. 然后生成剩下的字符串: 两重循环生成长度为2的字符串: cd ce cf...yz zz长度不够循环自身即可. 需要判断的特殊情况: 1. 最长长度大于等于要求的字符串的长度 2. m == 1时, 如果要求的字符串个数大于26, 那么就无法满足生成个数要求.