T1
逆天高精，跳！
T2
逆天回文串，跳。。。。。跳个屁。。。。。
将每个字符要跳到的位置与它的起始位置看成一段区间 :
（以下的 \(1,2,3\) 均称为方案 \(1,2,3\)）
-
对于从左向右跳与从右向左跳有交的两端区间有交的情况下，不论谁先跳贡献均相同。
-
对于两个字符向同一方向跳的情况：若一段区间包含另一段区间，顺序无影响；若相交但不包含，则终点远的先跳，
（错误）因为这样会让终点近的少跳一个位置。（正确）因为这样若先让终点位置近的跳还让终点位置远的多跳一个位置。 -
对于不两段不相交的情况，互相不会影响。
-
补：其实结合一下就会发现我们每次跳的区间根本不会因为顺序而减少，只会增多，所以只要保证终点远的先跳就行！！！不用管哪个先跳！！！。。。
接下来考虑怎么确定每个字符的位置：
（以下的 \(1,2,3\) 均称为位置 \(1,2,3\)）
-
若长度为奇数，则肯定让出现字数为奇数的字母做中间的分界。
-
从两侧逐渐向里面确定位置，这样一定是最优的。我们的一个字母如果要跳到最靠外的未确定字母的位置，在符合上面说的方案 \(2\) 中说的让终点位置远的先跳，所以符合最优。
-
不会出现可以先选一个不是当前最优但是会造成全局最优的情况吗？答：显然不会，因为。。。所以因为什么啊？我也不知道QAQ。
-
证明：就像 \(2.\) 说的：
(错误)不产生贡献的不用考虑，只考虑两个同一方向跳的情况。当我们选择了一个跳的更远的（花费跟多）的序列时，我们包含的终点就多了，我们每多花费一个位置的长度，我们的终点就多了一个，但是我们多的终点不一定会让我们总的贡献（正确）我们总是让终点远的先跳，所以意味着我们总是不会多产生花费（即方案 \(2\)），而我们每次都是找跳到本位置最小花费的跳，那就意味着我们的花费和总是最小的。
所以现在问题又来了，我们怎么找哪个字符到最外侧未确定位置的贡献最：
- 按昨天 \(T4\) 的思路处理就行了。
那么 \(T2\)，启动！！！（PS：球球了，千万不要假QAQ）
坏了，实现寄了，不会 \(26 \cdot len\) 的，QAQ九敏九敏。
完蛋了，只会 \(O(26 \cdot Len \cdot log_2len)\)
好了，现在空间也寄了，好哎T_T。
等等，也许我们每次向前走的字母并不会影响剩下字母的排名？？
等等，也许它根本就不会减去。。。？？但是它会加！！QAQ
急急急，全都寄寄寄，我要寄。
上面两个"等等"全是错的_(:з」∠)_
赛后：
关于T2
emmmm其实不论怎么样，我们若是每次都将左边固定找到对应的字母就行
我就是个jb
关于T1
得亏没写，是一道大坑
标签：终点,QAQ,16,花费,54,字母,位置,联测,我们 From： https://www.cnblogs.com/jueqingfeng/p/17761804.html