Atcoder Grand Contest 058
队友说板刷 agc 是最好的训练方法之一，于是我来了
A - Make it Zigzag
题意：给你一个长度为 \(2n\) 的排列，你最多可以做 \(n\) 次交换相邻元素的操作，最后要满足
\[p_i<p_{i+1} \ for\ each\ i=1,3,5,7...\\ p_i>p_{i+1} \ for\ each\ i=2,4,6,8... \]题解：
感觉我的思路有点蠢（
先把数列差分，即 \(p_i\) 变成 \(p_{i+1}-p_i\) 那么我们的目标数列满足正负交替出现即可
考虑一个操作之后差分数列会变成什么，例如交换 \(x\) 和 \(x+1\) （简称操作 \(x\) ）
差分数列 \(p_{x-1},p_x,p_{x+1}\) 会变成 \((p_{x-1}+p_x),-p_x,(p_x+p_{x+1})\)
那么可以这么操作，从前往后考虑，遇到第一个正负号不对的元素（显然它前一个元素正负号是对的）。
如果后面一个元素正负号不对，那就操作它与后一个元素绝对值更大的那一个
如果后面一个元素正负号是对的，那就操作它自己
这么做的话，它自己和它前后元素的正负号都能变成正确的。然后以此类推继续往后考虑。
然后就做完了
B - Adjacent Chmax
题意：给定一个排列，操作为将相邻两个元素变成他们中较大的那一个，你可以做任意次操作，问操作完了的排列会有多少种
题解：首先，结果的数字一定是成段出现的，不可能一个数字出现了两段，一定是连续的一段。每个数字有它能够覆盖的区间。
然后关键在于设状态，我设的是 \(f[i][j]\) 表示前 \(i\) 个位置已经确定，第 \(i\) 个位置放的是 \(j\) 。
讨论这个状态可以转移到哪些状态：
如果可以转移到 \(f[i+1][k]\)
分情况讨论
-
若 \(j\) 的初始位置在 \(i\) 之前，\(k\) 只需满足下列任意一个条件
- \(k=j\)
- \(k\) 的初始位置更靠近 \(i\) ，且 \(k<j\) ，且 \(k\) 可以覆盖到 \(i\) 位置
-
若 \(j\) 的初始位置在 \(i\) 之后，\(k\) 只需满足下列任意一个条件
- \(k=j\)
- \(k\) 的初始位置更远离 \(i\) ，且 \(k>j\) ，且 \(k\) 可以覆盖到 \(i\) 位置
然后有技巧的转移，就做完了
——
待更…
标签：元素,数列,位置,AGC,058,正负号,操作 From： https://www.cnblogs.com/xoslh/p/16777044.html