Difference between revisions of "2019 ECNU XCPC March Selection 4"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 15: Line 15:
 
显然补题不只有这个作用。
 
显然补题不只有这个作用。
  
要是补题还是不明显,以后可能还会这么搞。
+
要是补题还是不明显,以后可能还会这么搞。(我出我自己)
  
 
[[https://acm.ecnu.edu.cn/blog/entry/239/ 题解]]
 
[[https://acm.ecnu.edu.cn/blog/entry/239/ 题解]]
Line 21: Line 21:
 
== Problem B ==
 
== Problem B ==
  
 +
显然贪心。
  
 +
排序以后插入堆。
 +
 +
最小的必须放在当前结点,无法选择。
 +
 +
要使得字典序最大,大的一半给左节点,小的一半给右节点。
  
 
== Problem C ==
 
== Problem C ==
Line 60: Line 66:
  
 
== Problem F ==
 
== Problem F ==
 +
 +
因为是最小的代价,所以到最后的序列中的每个数字肯定在原先的序列中出现过。
 +
 +
我们用一个 $c$ 数组拷贝原先的 $a$ 数组,然后进行从小到大排序。
 +
 +
那么之后我们考虑 dp ,因为是 $5000$ 的数据,考虑 $O(n^2)$ 做法。设 $dp[i][j]$ 表示前 $i$ 个已经符合要求,而且最大数不大于原序列第 $j$ 个元素最小需要的代价。
 +
 +
那么我们可以得出转移方程 $dp[i][j]=min(dp[i][j−1],dp[i−1][j]+abs(a[i]−c[j])$ 。

Latest revision as of 14:01, 28 March 2019

ECNU XCPC March Selection #4

可能是 dp 专场了。

推荐资料

dp 没啥好推荐的资料。

打开 codeforces ,搜索 tag 为 dp 的,刷题。

Problem A

了解一下补题的重要性?

显然补题不只有这个作用。

要是补题还是不明显,以后可能还会这么搞。(我出我自己)

[题解]

Problem B

显然贪心。

排序以后插入堆。

最小的必须放在当前结点,无法选择。

要使得字典序最大,大的一半给左节点,小的一半给右节点。

Problem C

经典盒子装球问题中的一种。

可以 dp ,状态为:

$f[i][j]$ 表示 $i$ 个球放入 $j$ 个盒子的方案数。

搜索也是可以的:

$dfs(n,k,x)$ 表示将 $n$ 分成 $k$ 份,最小的一份 $\ge x$ 的方案数。

显然答案是 $dfs(m,n,0)$ 。记忆化搜索一下。

Problem D

经典大背包问题。

折半搜索。

考虑枚举 $20$ 个物品的时候的情况。

也就是把 $40$ 个物品分成两半枚举出所有情况,针对其中的一边,二分最优解的位置。

题解过于见解看不懂的。出门左转[大背包问题分析]

Problem E

感觉也是比较基本的 dp 。

看到数都不是很大,于是我们考虑从这点入手设计状态。

$f[i][j]$ 表示从第 $i$ 位开始,消成 $j$ 所需要的位置数量(显然,一定是连续的一段)。

考虑状态转移,如果 $f[i][j-1]>0$ 而且 $f[i+f[i][j-1]][j-1]>0$ ,也就是出现了两段消完以后连续的两个数一样,那么可以继续消,也就是 $f[i][j]=f[i+f[i][j-1]][j-1]+f[i][j-1]$ 。

Problem F

因为是最小的代价,所以到最后的序列中的每个数字肯定在原先的序列中出现过。

我们用一个 $c$ 数组拷贝原先的 $a$ 数组,然后进行从小到大排序。

那么之后我们考虑 dp ,因为是 $5000$ 的数据,考虑 $O(n^2)$ 做法。设 $dp[i][j]$ 表示前 $i$ 个已经符合要求,而且最大数不大于原序列第 $j$ 个元素最小需要的代价。

那么我们可以得出转移方程 $dp[i][j]=min(dp[i][j−1],dp[i−1][j]+abs(a[i]−c[j])$ 。