胡乱刷题

题号	代码
1842C	代码1
1838C	代码2
1569C	代码3
1547E	代码4
1551C	代码5
1542B	代码6

题1

思路

简单dp，设状态\(f_i\)为前\(i\)个位置最多能删除元素的个数，对于位置\(i\)，状态为\(f_i=max(f_{i-1},f_{j-1}+i-j+1),a_j=a_i\),对于一个数\(x\),维护\(mx_x=max(f_{j-1}-j+1),a_j=x\)，所以\(f_i=max(f_{i-1},mx_{a_i}+i)\)。

题2

思路

如果n不是质数，就按行1234...排下去，m不是质数就按列排下去。
两个都是质数的话，假设原始阵列为\(a_{ij}=(i-1)*m+j\)，则合法的一个阵列为先排奇数行，再排偶数行。

题3

思路

这个很有意思。首先分两种情况，最大数唯一和不唯一。不唯一的话最后就只剩下这几个原本的最大数互相作用了，所以方案数为\(n!\)。否则要看最大数和次大数的差值，如果大于1就是0，因为当其他数都为0时原本的最大数至少为2，那么将至少连续两轮是它。
当最后只剩下最大数和次大数时，如果最大数在最后，那么它就会连续重复，所以不能排最后，所以思路是这样：先放置次大数，方案有\(c_1=cnt_{lmx}!\) ，然后根据插板法，最大数能放的地方只有\(c_2=cnt_{lmx}\)个，之后就是其他数随便放了，方案为\(c_3=\prod_{i=cnt_{lmx}+2}^{n}i=\frac{n!}{(cnt_{lmx}+1)!}\)

题4

思路

对于\(min(t_j+|a_j−i|),1≤j≤k\)，一般对于这种题，都是尝试把绝对值符号去掉，所以从左到右弄一遍，再从右到左弄一遍就ok了。维护与当前位置无关的值，如果是从左到右，那么公式为\(min(t_j+i-a[j])=i+min(t_j-a[j]))\),同理右到左为
\(min(t_j-i+a[j])=-i+min(t_j+a[j]))\).