【题解】CF1421C Palindromifier

题目

CF1421C Palindromifier

题解

此题刚看到时会因为构造方法的不确定性而无从下手,然而,题目限制的最终序列的长度与原序列长度相差很大,因此构造方法可以放弃最优解(长度最短或次数最少)而使用一种相对暴力的方法(见代码)。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年10月30日 下午3:42

【小白解析】
设s=a1 a2 a3 a4…an, 任何ai为char类型。
当操作为:
3
L 2
R 2
R 2n-1(即s.length()*2-1)时,s的变化为:

  1. a1 a2 a3 a4…an->a2 a1 a2 a3…an,此时n=s.length()+1;
  2. a2 a1 a2 a3…an->a2 a1 a2 a3…an-1 an an-1 an-2…a2 a1,此时n=s.length()*2
  3. a2 a1 a2 a3…an-1 an an-1 an-2…a2 a1->a2 a1 a2 a3…an-1 an an-1 an-2…a2 a1 a2

完成。
*好家伙,我直接见代码