竞赛题解

【AHOI 2008】逆序对

题目描述给定一个由 $[1,k]$ 之间的数字组成的长度为 $n$ 序列，其中有一些位置上的数不可见，标记为 $-1$，求这个序列的最少逆序对数。 $n\le 10000$，$k\le 100$。算法分析首先需要发现一个结论：要使逆序对数最少，从前到后依次填写的不可见的数字一定单调不下降。 ......

Posted by WHZ0325 on 2019-03-24

【CF 981D】Bookshelves

题目描述给定一个长度为 $n$ 的数列 $a_i$，将其划分为 $k$ 个连续的子段，每一段和相与的值最大是多少。 $1\le k\le n\le 50$，$0\lt a_i\le 2^{50}$。算法分析看到相与的值最大，考虑按位贪心，定义 $f_{i,j}$ 表示将前 $i$ 个数划分为......

Posted by WHZ0325 on 2019-03-23

【ZJOI 2012】波浪

题目描述由 $[1,n]$ 组成的排列，求其波动强度大于 $m$ 的概率，结果保留 $k$ 位小数。定义波动强度为每个数与其相邻数的差的绝对值之和。 $n\le 100$，$k\le 30$，$m\le 2147483647$。算法分析求波度强度大于 $m$ 的概率，我们可以求出每个波度强度......

Posted by WHZ0325 on 2019-03-23