Posts

“深夜研究心理学”

车万碟佬的日常

大晚上的诗兴大发

小病一场，剥一个橘子，觉得日子也不坏

时隔一年的回归

生命在于折腾

基础的BFS

人生得意须尽欢，莫使金樽空对月

题目 D. Flipper 题意：给出一个 $ n $ 排列p[]，选择一个区间[l, r] (l <= r)，构造一个新的排列：a[r+1 : ] + a[l : r].reverse() + a[1 : l] (在这里我用 Python 切片表示，即左闭右开区间)，求能构造出的字典序最大的排列 分析 假设答案用 $ ans_i $ 表示 初步分析，当 $ r = n $ 时，$ans_1 = r_{n}$，否则 $ans_1 = r_{n+1}$。为了保证字典序最大，我们需要选取尽可能大的 $ r $ 易知当 $ p_1 = n $ 时，$ r $ 应选取 $ n-1 $，否则选取 $ n $ 确定 $ r $ 后再来看 $ l $，这里有个技巧：先输出a[r+1 : ] + a[r]，再从a[r-1]开始往前遍历，只要 a[i] < a[1]（说明如果 $ l $ 选 $ i $ 的话，操作之后字典序反而变小，所以 $ l $ 选 $ i+1 $），就马上输出 a[1 : i+1] (注意这里还是左闭右开区间) ...

不仅仅是 Hello world