Done
F solution2
题目链接
E
看成26进制运算,从低位到高位模拟。
F
题意
给出一个长度为n的序列,问是否可以在不改变的相对顺序的情况下,把序列分层一个严格递增一个严格递减的序列,空集也是合法的。给出每个数字属于那个集合。$(a_i,n \le 2·10 ^ 5)$
分析
solution1: 贪心
- 显然对于每个数字一定放在递增或者递减序列中的一个。
- 如果当前位置 $i$ 的 $a_i$,既可以放在递增也可以放在递减序列里。
- 考虑位置 $i+1$,如果$a_{i+1} > a_i$,那么i放在递增序列不会使得情况变差;反之,放在递减序列不会使得情况变差。
solution2: dp