Readme

3614.Process-String-with-Special-Operations-II

很显然，构造完全之后的字符串非常长，我们不可能在此基础上定位第k个元素。此题极大概率是递归反推。

我们分类思考每种操作下的第k个字符（注意是1-index）是什么情况：

1. 添加一个字符，使得长度从a变成了a+1. 如果k=a+1，那么答案就是最新添加的字符。否则，递归求原字符串里的第k个。
2. 删减最后一个字符，使得长度从a变成了a-1. 这种情况下k不可能是a（否则无解），因此等效于递归求原字符串里的第k个。
3. 将字符串copy+append，使得长度从a变成了2a. 显然如果k<=a，递归求原字符串里的第k个。如果k>a，递归求原字符串里的第k-a个。
4. 将字符串反转，长度依然是k。显然，递归求原字符串里的第a+1-k个。

综上，只要知道每个回合的操作和长度变化，我们就可以把“求当前字符串的第k个元素”，逆推为“求前一个回合字符串的第k'个元素”，其中k'的计算如上。

注意，这个题可能无解。逆推的前提是正向的变化合法存在。所以我们必须先正向走一遍，记录下每个回合的字符串长度，最后检查k是否在最终长度的范围内。