【NOIP Round #6】排序 - 题目

今天是 YQH 的生日，她得到了一个 $1\sim n$ 的排列作为礼物。

YQH 是一个有强迫症的女孩子，她希望把这个排列从小到大排序，具体的，她可以进行这样的操作：

把 $[1,n]$ 分成若干个区间，假如是 $m$ 段，依次为 $[l_1,r_1],[l_2,r_2],\dots,[l_m,r_m]$，其中 $l_1=1,r_m=n,l_{i+1}=r_i+1,l_i\le r_i$。
假如原来的排列为 $a_{1,\dots,n}$，那么把排列变为 $a_{l_m},a_{l_m+1},\dots,a_{r_m},a_{l_{m-1}},a_{l_{m-1}+1},\dots,a_{r_{m-1}},\dots,a_{l_1},a_{l_1+1},\dots,a_{r_1}$，即把每一段看作一个整体，然后把这个排列进行 reverse。

YQH 希望进行尽可能少的操作，把序列从小到大排序。但是她太笨了，所以她找到你帮忙。注意，你不需要得到最小操作数。

第一行一个正整数 $n$，表示排列长度。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示 YQH 获得的排列，我们保证 $a_{1,\dots,n}$ 是 $1\sim n$ 的排列。

第一行一个整数表示你进行的操作次数，假设为 $p$。

接下来 $p$ 行，每行第一个整数 $m$ 表示你这次操作把排列分成 $m$ 段，接下来 $m$ 个整数 $len_i$ 分别表示第 $i$ 段的长度，即 $r_i-l_1+1$ 为 $len_i$，你需要保证 $\sum_{i=1}^m len_i=n$。

4
3 1 2 4

2
2 3 1 
3 1 1 2

第一次操作，把序列分为 $[3,1,2],[4]$，操作完变为 $[4,3,1,2]$。

第二次操作，把序列分为 $[4],[3],[1,2]$，操作完变为 $[1,2,3,4]$。

6
6 5 4 3 2 1

1
6 1 1 1 1 1 1

第一次操作，把序列分为 $[6],[5],[4],[3],[2],[1]$，操作完变为 $[1,2,3,4,5,6]$。

1
1

原序列已经有序，无需操作。

本题采用评分参数进行评分，具体的，对于每个测试点，我们有评分参数 $p_0,p_1,p_2,p_3,p_4$，保证 $p_i\ge p_{i+1}$。假如你的操作数为 $p$，你在该测试点的得分为

$$ \frac{[p\le p_0]+\sum_{i=0}^3 \max(\frac{p_i-\max(p,p_{i+1})}{p_i-p_{i+1}},0)}{5} $$

其中定义 $0/0=1,-1/0=-\infty$ 。

对于每个子任务，假如该子任务分值为 $w$，则你的得分为该子任务所有测试点得分的最小值乘上 $w$。

$\text{subtask1 10pts},n\le8,p_0=p_1=p_2=p_3=p_4=10^6$。

$\text{subtask2 20pts},n\le200,p_0=p_1=p_2=p_3=p_4=40000$。

$\text{subtask3 70pts},n=20000,p_0=1000,p_1=500,p_2=240,p_3=140,p_4=90$。

Public Judge