[ABC163E] Active Infants
题意:给定长度为 \(n(n \le 2 \times 10^3)\) 的序列 \(a\) ,重排使得 \(a_x \times |x-p_x|\) 之和最大。
独立完成。
从大到小地考虑 \(a_i\) ,贪心地使得 \(|x-p_x|\) 最大。那么 \(p_x\) 要么在最左,要么在最右。因此在左边和右边形成了一坨前/后缀,然后就能转移了。
[ABC282G] Similar Permutation
题意:定义两个排列 \(A,B\) 的相似度为满足 \((A_{i+1}-A_i)(B_{i+1}-B_i)>0\) 的 \(i\) 的个数。求有多少对长度为 \(n\) 的排列相似度为 \(K\)。
独立完成。
首先有弱化版 AT_dp_t 。具体做法是考虑最后一个数在前缀的相对位置,往里插就行了,与这道题无本质区别。直接枚举 \(A\) 和\(B\) 的最后一个符号是 \(>\) 还是 \(<\) 。然后记录当前相似度、\(A,B\)排列的最后一位在前缀中的相对位置就做完了。
[ABC281G] Farthest City
题意:构造 \(n\) 个点的图,使得 \(1\) 到 \(n\) 的距离严格大于 \(1\) 到其他点的距离。
独立完成。
直接根据 \(1\) 到该点的距离分层。层内随便连,层之间右边的每个点至少连一条边。随便转移一下就行了。
[ABC342F] Black Jack
题意:你和另一个人投 \(D\) 面的骰子。那个人一直摇色子直到大于等于 \(L\)。你可以任意时刻停止。求最右策略下获胜概率 \(x<=n \space and \space (y>x \space or \space x>y)\)
基本独立完成。
考虑 \(dp\) 。首先另一个人的方式与你无关,直接 \(dp\) 中最后在 \(i\) 的概率。然后到了一个位置 \(i\) 决策是否再摇色子会更优,也就是新跳到格子的期望胜率是否比当前胜率大。随便做一下就完事了。本来我在后面一次 \(dp\) 是顺序,然后期望胜率直接用第一次 \(dp\) 值算,但这样是不准确的,会 \(WA\) 掉3个点。因此应该倒着 \(dp\)。