CSU-ACM Home Page

2017年8月月赛题解

Update Time: 2017-08-12 16:10:10     Recent Editor: Scanf     Create Time: 2017-08-12 16:08:04     Creator: Scanf    


搬运工小明

题目大意

给M个数字,要求最多分成连续的N段,使得每段的和的最大值尽量小

问题分析

这是个经典的二分模型,可以根据答案的单调性想到

具体实现

首先我们二分答案(即袋子的大小),题目要求每个袋子里装的东西必须是连续的,所以直接模拟将物品装入袋子就行了。最后统计一下使用的袋子个数,根据袋子数和N的大小关系更新二分的上下界

复杂度

二分的范围明显是在[物品体积最大值,物品体积和]之间,体积和最多1e14,每次二分后的模拟是O(n),所以总的复杂度是O(nlog(∑a[i]))

Bit-reversal Permutation

题目大意

模拟实现DFT的第一步:将数组元素重新按位逆序排列。

输入:a0,a1,a2,a3,a4,a5,a6,a7 二进制下标 000,001,010,011,100,101,110,111

输出:a0,a4,a2,a6,a1,a5,a3,a7 二进制下标 000,100,010,110,001,101,011,111

问题分析

如果我们能够将输出的二进制下标按顺序生成出来,那么只要依次输出下标对应的元素即可,因此我们要找出位逆序排列的规律。

其实位顺序排列和位逆序排列是同样的一串字符从不同的方向来看罢了,完全可以按顺序生成二进制后反向转换成十进制即可。

具体实现

方法一DFS:每一层循环从0到1,按顺序生成二进制,生成后反向转换成十进制输出对应元素。

方法二位运算交换 (FFT模板节选):

      // 原地快速bit reversal
      for(i = 0, j = 0; i < n; i++) {
        if(j > i) swap(a[i], a[j]);
        int k = n;
        while(j & (k >>= 1)) j &= ~k;
        j |= k;
      }

时空复杂度

O(NlogN)

LXX的图论题

题目大意:

问是否能在图中找到一个环,满足环上所有边权的乘积小于1。

解题思路:

考虑到对数能够把连乘变成累加,所以对所有边权取对数,然后判断图中是否存在负环即可。

时间复杂度:

O(n*m)

古怪的行列式

题目大意

   按照行列式的值的定义去计算行列式,计算过程中,如果连续三行中遇到83,83,82的顺序的元素,他们的乘积变为1,计算这样计算的行列式的值。

做法

   暴力,n最大只有8,dfs随便搜索一下就好了。。。

   搜索的时候记录上一行的元素的值,上上一行元素的值,以及当前累乘的值,一直到每行都选取了一个元素,自我感觉出的还不错,dfs传递值,取了元素的标记和去除,基本的八皇后的小变形,也不难。

   行列式一共有n!个项,然后求逆序数是两两比较,虽然用归并排序或者其他数据结构求逆序数也可以,但是常数太大,这里没有必要,所以我写的程序的复杂度是O(n!*n2)的,求逆序数优化的话可以变成O(n!*nlogn),但是常数会有点大,没必要。

   最后累加下求个结果输出就行了。

不堪重负的树

题意:

  • 一棵树由N个节点组成,编号为i的节点有一个价值Wi。
  • 假设从树根出发前往第i个节点(可能是树根自己),一共需要经过Di个节点(包括起点和终点),那么这个节点对这棵树产生的负担就是Di与Wi的乘积。
  • 对于一棵树而言,这棵树的负担值为所有节点对它产生的负担之和。

给出一棵二叉树的中序遍历以及每个节点的价值,求这棵二叉树可能的最小负担值。
20组数据,N为200。

解题思路:

值得特别注意的是,这道题首先需要选手弄明白二叉树的中序遍历的意义。
二叉树的中序遍历是,先中序遍历左子树,再访问根,再中序遍历右子树。
如果我们知道了根,那么我们就明确了左子树和右子树,也就可以递归(分治)处理左、右子树。
一个区间[i...j]可以认为对应着一棵树的中序遍历结果。
另一方面,我们关心每个节点对应的价值,为了方便后续处理,我们记一个A[i]=W[p[i]],表示中序遍历中第i个节点的对应价值。

使用动态规划来解决这个问题。
这其实是一个区间dp。
定义状态dp[i][j],表示区间[i...j]对应的(二叉)树的可能的最小负担。
初始化为dp[i][i]=A[i](1 ≤ i ≤ N)dp[i][j]=0(1 ≤ j < i ≤ N),其他状态的值为未知,可预设为自定义的无穷大。
状态转移方程是 $dp[i][j]=\max_{k=i}^{j} \{dp[i][k-1]+dp[k+1][j]\}+\sum_{p=i}^{j} A[p],(i<j)$
即枚举该区间的根,用左子树和右子树的最小负担加上该区间的价值和来更新dp[i][j]。
因为对于根来说,它对这棵树的负担贡献为自身的价值,而对左子树和右子树的每一个节点而言,它们对现在这棵树的负担值的贡献增加了自身的价值那么多(考虑负担值的定义,因为现在多了一个根,那么它们到根的距离也就都多了1)。
答案为 dp[1][n]
式子里的这一部分$\sum_{p=i}^{j} A[p]$可以对A数组求一个前缀和预处理来解决。
dp的具体过程为区间dp的一般过程,最外层枚举区间长度,中间层枚举起点,内层枚举区间分割点。

时间复杂度为

O( $ N^3 $ )。

最后,注意这个题需要使用long long。
这个题的出题意图,是想让大家来实现“最优二叉检索树”,因为这个算法在大学的算法课内会讲,大家应该会觉得比较熟悉、简单。
这个题的本质就是“最优二叉检索树”,不过,利用“中序遍历”这个概念稍微进行了一点转化。

关键字:

区间dp、最优二叉检索树 。