JZOJ 2019.11.02 总结
赛时T1 一看暴力分是之前做过的原题，所以就粘写完了 $O(n^2logn)$ 的暴力， T2 想了想，发现每次一定要把最小值移动到左边或右边，然后可以递归成子问题去做了 T3 建出来树之后只会暴力 dp。 最后 40+100+25 第三题挂了 20 分完美省三。题解A. Game$O(n^2logn)$ 的做法是显然的：我们先贪心找出得分最高是多少，然后二分每一位放什么，贪心 check ...
赛时T1 一看暴力分是之前做过的原题，所以就粘写完了 $O(n^2logn)$ 的暴力， T2 想了想，发现每次一定要把最小值移动到左边或右边，然后可以递归成子问题去做了 T3 建出来树之后只会暴力 dp。 最后 40+100+25 第三题挂了 20 分完美省三。题解A. Game$O(n^2logn)$ 的做法是显然的：我们先贪心找出得分最高是多少，然后二分每一位放什么，贪心 check ...
题目大意把 $n$ 个数分成 $k$ 个区间，每个区间的价值为区间内不同数字的个数，问价值和最大为多少。题解简单 dp：设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量，那么有转移朴素的转移是 $O(n^3)$ 的，我们观察这个式子，如果固定 $j$ ，我们用线段树维护 $f_k+cn...
题目描述：给你若干条形如 $x+y=c$ 或 $x-y=c$ 的直线，这些直线与坐标轴的夹角是 45 度，问在矩形 $(0,0) \to (W,H)$ 中，有多少个子矩形。图片示意：上图有 $19$ 个子矩形。$n \leq 10^5$首先这一题目 $O(n^3)$ 的复杂度十分好做：就是枚举三条边 去 map 找一下第四条边就好了。我们考虑如何做到 $O(n^2logn)$:我们可以考虑先...
DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。 我们来找一道简单的题目入手：给定一棵树，点有点权，每次可以修改一个点的权值，每次修改后求这棵树的最大独...
题目描述题目链接 小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子，每个瓶子有一个容量vi。每次别人来加油，他会让 别人选连续一段的瓶子。他可以用这些瓶子装汽油，但他只有三种操作： 1. 把一个瓶子完全加满； 2. 把一个瓶子完全倒空； 3. 把一个瓶子里的汽油倒进另一个瓶子，直到倒出瓶子空了或者倒进的瓶子满了。 当然，为了回馈用户，小Z会时不时选择连续一段瓶子，给每个瓶子容积都增加...