icpc asia yokohama regional contest 2018 题解报告

Solved by dlgump. 00:44(+)
题意:
给你$n+1$个字符串，记录为$s_i(0leq ileq n)$，要求$s_i(1leq ileq n)$与$s_0$按照题目要求比较，输出当前字符串$s_i$应该位于$s_0$之前还是之后，分别输出$-$与$+$。

题解:
按照题目要求处理，遇到字符与数字比较则直接返回字符所处字符串大；字符与字符比较则直接按照ASCII编码比较；数字与数字比较则直接比较大小。最后依据返回结果按照题目要求输出即可。

Solved by Flaaaaaaaag. 01:26(+)
题意:
给予长度为$n$的数组（每个数字独立出现），从中随机挑选（可打乱顺序）组成等差序列，输出等差序列最长长度即为答案。

赛中解题题解:
由于题目给了$5000ms$，于是写了假算法，做法是将数组排序，枚举头两个数字$a_i$与$a_j$确认公差$d=a_j-a_i$，再用二分搜索$a_k+d$，一直循环直到搜索不到下一个$a_k+d$，则记录其结果，返回最大值即可，最终通过时用时$2s$。

题解:
$dp[i][j]$，$i$与$j$分别表示等差数列的最末尾两个数所在位置，易证前一个数$a[k]=2times a[i]-a[j]$，由此可以得到状态转移方程。

$$dp[i][j]= begin{cases} dp[pos[2times a[i]-a[j]]][i]+1 & text{(若能够在数组中找到}2times a[i]-a[j]text{)}\ 2 & text{(若无法找到)} end{cases}$$

时间复杂度$O(n^2logn)$

Solved by dlgump. 04:22(+2)
题意:
给予$r,s,p$分别代表行数、每边座位数、以及当前人数。所有人需要紧急撤离，中间过道只有一个座位的宽度，且每个位置一次只能有一个人占用，要求所有人中最晚的一个人离开车所需要花费的时间为多少。

题解:
模拟题，可以反着思考这道题目，将离开联想成入座。需要对入座顺序进行排序，远的位置优先入座，紧接着模拟过程即可得到答案。或者可以直接模拟离开也是可以的。

Unsolve.

Unsolve.

Unsolve.

Upsolved by Flaaaaaaaag.
题意:
给予一个长度为$n$且可以有重复数字的数组，让你用最少的操作将这个数组调整成山峰形状，即数组最大值的左边为非递减序列、右边为非递增序列，每个操作只能取相邻的两个数字进行交换，输出最少的操作数。

题解:
题目的意思很明确就是将某位数字，往左边或者右边移动，使得这个数组成为山峰形状。因此移动的操作数就与当前数的位置有关系，则使用树状数组计算当前这个位置左边比它大的数量有多少记为$l[i]$、右边比它大的数量有多少记为$r[i]$，最终对于每个数，往比它大的数最少的方向移动，则答案为

$$ans = sumlimits_{i=1}^nmin(l[i],r[i])$$

时间复杂度$O(n)$

Unsolve.

Unsolve.

Unsolve.

Unsolve.