YZOJ P3484 子树求和

YZOJ P3484 子树求和

时间限制:2000MS      内存限制:262144KB      出题人:lgj

难度: \(6.0\)

  • 题目描述

已知一棵树有 \(n\) 个节点,并且根节点是固定的。

每个节点上都有一个权值 \(w_i\) ,记 \(s_i\) 为 以 \(i\) 为根的子树中,所有节点的 \(w_i\) 的和。

由于询问 \(s_i\) 太简单了,不能将 AKIOI 的你的高智商体现出来,所以每次询问给定 \(l, r\) ,求 \(\sum\limits_{i=l}^{r}{s_i}\) 。

为了避免此题难度太低,不能将 AKIOI 的你的高智商体现出来,所以的询问的过程中还可能修改某个节点的 \(w_i\) 。

为了将 AKIOI 的你的高智商体现出来,你要写一个程序来实时给出询问的答案。

  • 输入格式

第一行为两个整数 \(n\) 和 \(q\),分别表示节点数和操作的次数;

第二行 \(n\) 个正整数,表示序列 \(w\) ;

接下来 \(n\) 行,第 \(i\) 行两个正整数 \(u_i\) 和 \(v_i\),描述一条树上的边。特别地,\(u_i=0\) 时,表示 \(v_i\) 为树的根节点;

接下来 \(q\) 行,每行三个正整数 \(op, l, r\) 。描述 \(q\) 组操作。 \(op=1\) 表示 \(w_l\) 修改为 \(r\),\(op=2\) 表示询问 \(\sum\limits_{i=l}^{r}{s_i}\) 的值。

  • 输出格式

对于每组询问操作,你需要依据当前树的情况输出该组询问的标准答案,每次询问的答案独占一行。

  • 样例输入


Read the rest

浅谈斜率优化——截距优化

浅谈斜率优化——截距优化

最近(两个月前)学习了斜率优化 —— 一种优化 1D1D 动态规划转移方程的高效方法,在较高难度的比赛中是一种十分常见的 DP 优化手段。鉴于我之前(一年前)也稍微接触过一点相关方面的知识,但是完全没有搞懂(太菜了),最近(两个月前)再配合 orzCJK学长 提出的截距优化的思想理念才对于斜率优化问题有了深刻的见解,故在这里对 orzCJK学长 的 斜率优化_截距优化!.pdf 进行详细的解释说明。

 

首先,1D1D 指的是状态数 \(O(n)\) 转移 \(O(n)\) 的动态规划方程。在满足一些条件的情况下,斜率优化可以将转移的 \(O(n)\) 优化至 \(O(logn)\) 甚至可以到 \(O(1)\) 。这样时间复杂度就由 \(O(n^2)\) 变为 \(O(nlogn)\) 甚至是 \(O(n)\) ,可见斜率优化的高效性。

如果有一个 DP 方程的某个状态为 \(f_i\) ,如果能推导出类似于 \(f_i=c_i + \min\limits_{j<i \land \cdots}{\{a_j + w_i \cdot b_j\}}\) ,那么这个转移方程就可以使用斜率优化进行优化。

然而普通的转移方程并没有什么特殊的地方,使用经典的方法(我也不会)略显繁琐,所以现在我们要赋予它以几何意义。(时刻注意,这个转移方程的意义是对于一个 \(i\) 在 \(j < i\) 范围内寻找 \(j\) 使 \(a_j + w_i \cdot b_j\))最小。)

换一下变量名,设 \(y_j=a_j, k_i=-w_i, x_j=b_j\) ,那么这样需要最小化的式子就变为 \(\underbrace{a_j}_{y_j} – \underbrace{-w_i}_{k_i} \cdot \underbrace{b_j}_{x_j}\) 。这不就是截距 \(b = y – kx\) 吗?!!也就是说,要最小化的就是一条过 \(\left(x_j, y_j\right)\)斜率为 \(k_i\) 的直线的截距

换句话说,把所有对于当前 \(i\) 可转移的 \(j\) 都表示为二维平面上的一个点 \(p_j=\left(x_j, y_j\right)\) ,我们需要做的就是在所有这样的点中,找到一个点,使经过它且斜率为 \(k_i\) 的直线的截距最小!这也是为什么斜率优化就是截距优化的原因,它其实优化的是截距!

现在想象一条斜率固定的直线从下往上平移,当它第一次经过某个点 \(p_j\) 时,这时的截距肯定取到最小值。那么这个点 \(p_j\) 在什么地方呢?显然,它会在所有 \(p\) 组成的下凸壳上。

那么现在只要维护这个下凸壳,每次在上面找点使得截距最小,拿来更新 …

[FJWC2019 Day3] 签到题

[FJWC2019 Day3] 签到题

时间限制: 1000ms               内存限制:256MB

难度: \(4.5\)

  • 题目描述

作为一道签到题,自然只能包含最基本的算法。本题的任务很简单,给定一个长度为 \(n\) 的序列 \(a\),你要将其排序。

由于出题人很菜,不会排序算法,他决定自己编一个。他想找到一个数 \(x\),使得序列中的所有数字都异或上 \(x\) 后序列恰好按从小到大排列。

顺带,这个序列会被进行若干次修改,每次修改后你需要回答当前是否存在一个 \(x\) 满足序列中数字异或上 \(x\) 后按从小到大排列,如果有,请你给出最小的 \(x\) 。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个非负整数,表示序列 \(a\) 。

第三行一个非负整数 \(q\) ,表示修改次数。

接下来 \(q\) 行,每行一个正整数 \(x\) 和一个非负整数 \(y\),表示将序列中第 \(x\) 个元素修改为 \(y\) 。

  • 输出格式

输出 \(q+1\) 行,每行一个整数,第一行表示一开始最小的合法 \(x\) ,之后 \(q\) 行依次表示每次修改后最小的合法 \(x\),如果不存在则这一行输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(20\%\) 的数据,\(n,m \le 500\),所有数字不超过 \(2^9\) ​​。

对于 \(50\%\) 的数据,\(n,m \le 1000\) 。

对于 \(100\%\) 的数据,\(n,m \le {10}^6\)​​,所有数字不超过 \(2^{30}\) ​​。

 

 

YZOJ P4263…

[FJWC2019 Day2] 直径

[FJWC2019 Day2] 直径

时间限制:1000MS      内存限制:524288KB

难度: \(4.0\)

  • 题目描述

你需要构造一棵至少有两个顶点的树,树上的每条边有一个非负整数边权。树上两点 \(i,j\) 的距离 \(dis(i,j)\) 定义为树上连接 \(i\) 和 \(j\) 这两点的简单路径上的边权和。

我们定义这棵树的直径为,所有满足 \(1 \leq i < j \leq n\) 的 \((i,j)\) 中,\(dis(i,j)\) 最大的。如果有多个这样的 \((i,j)\),那么均为直径。

作为一个构造题,你需要构造一个恰有 \(k\) 个直径。可以证明在给定的限制下一定有解。

  • 输入格式

一行一个正整数 \(k\),表示你需要构造出一个恰有 \(k\) 个直径的树。

  • 输出格式

第一行一个正整数 \(n\),表示你构造的树的点数。

接下来 \(n-1\) 行,每行三个整数 \(i,j,w\),表示一条连接点 \(i\) 和 \(j\) (点的编号为 \(1,2, \cdots, n\))的树边,边权为 \(w\) 。

  • 样例输入

  • 样例输出

  • 样例说明

这只是一种符合题意的输出,可能还有其他输出。在这个输出中,直径为 \((1,5),(3,5),(4,5)\) 。

  • 数据规模与约定

注意,你需要构造出的树必须满足 \(2 \leq n \leq 5000, 0 \leq w \leq 10^5\)

对于 \(30pts\) 的数据,\(1\leq k \leq 2000\) ;

对于 \(100pts\) 的数据,\(1\leq k \leq 5 \times 10^6\) 。

 

 

YZOJ P4260…

[FJWC2019 Day1] 全连

[FJWC2019 Day1] 全连

时间限制:1000MS      内存限制:262144KB

难度: \(4.5\)

  • 题目描述

给定两个长度为 \(n\) 的序列 \(a\) 和 \(t\),可以在其中选择一些元素构成集合 \(S\) ,使得 \(\sum\limits_{i \in S}{a_i \times t_i}\) 最大。

同时,集合 \(S\) 还要满足 \(\forall i \in S, \forall j \in (i-t_i, i+t_i)\) , \(j \notin S\) 。

  • 输入格式

第一行一个整数 \(n\) ;

第二行 \(n\) 个整数表示序列 \(t\) ;

第三行 \(n\) 个整数表示序列 \(a\) 。

  • 输出格式

一行一个整数,即答案。

  • 样例输入

  • 样例输出

  • 样例说明

\(S=\{1,3,5\}\),答案 \(=2 \times 3 + 2 \times 2 + 2 \times 4 = 18\) 。

  • 数据规模与约定

保证 \(t_i \leq n\) , \(a_i \leq 10^9\) ,\(1 \leq n \leq 10^6\) 。

 

 

YZOJ P4257, YZOJ P3993…

YZOJ P3840 [2018省队集训]序列

YZOJ P3840 [2018省队集训]序列

时间限制:2000MS      内存限制:524288KB

难度: \(8.0\)

  • 题目描述

给定一个长度为 \(n\) 的序列 \(x\) 。

你需要从序列中选出一些位置。对于第 \(i\) 个位置,如果它被选中,你会获得 \(x_i\) 的收益;否则找到最小的 \(j\) 使得第 \(j\) 个位置到第 \(i\) 个位置都没有被选中,你需要付出 \(i-j+1\) 的代价。

此外,你选出的位置必须满足 \(x_i\) 是单调不下降的。

最大化收益减去代价的结果。

  • 输入格式

第一行一个正整数 \(n\),第二行 \(n\) 个整数 \(x_1\) ~ \(x_n\) 。

  • 输出格式

输出一行一个整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 样例 1 说明

选择第 \(1, 3, 5, 7\) 个位置,获得收益 \(1+2+3+4=10\) ,第 \(2, 4, 6\) 个位置的代价分别为 \(1, 1, 1\) ,收益减去代价为 \(10-3=7\) 。

  • 样例 2 输入

  • 样例 2 输出

  • 数据规模与约定

对于 \(5\%\) 的数据, \(1 \leq n \leq 5\) 。…

[CEOI2017]Building Bridges

[CEOI2017]Building Bridges

时间限制:1000MS      内存限制:131072KB

难度: \(7.2\)

  • 题目描述

有 \(n\) 根柱子依次排列,每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\) 。

现在想要建造若干座桥,如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间,那么需要 \((h_i-h_j)^2\) 的代价。
在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)​,注意 \(w_i\) 不一定非负,因为可能政府希望拆除某些柱子。

现在政府想要知道,通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个空格隔开的整数,依次表示 \(h_1, h_2, \cdots, h_n\) 。

第三行 \(n\) 个空格隔开的整数,依次表示 \(w_1, w_2, \cdots, w_n\) 。

  • 输出格式

输出一行一个整数表示最小代价,注意最小代价不一定是正数。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(30\%\) 的数据,有 \(1 \leq n \leq 1000\) ;

对于另外 \(40\%\) 的数据,有 \(\left| w_i \right| \leq 20\) ,保证存在一种最优方案,除了头尾两根柱子外,最多只保留两根柱子;

对于 \(100\%\) 的数据,有 \(2 \leq n \leq 10^5\),\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。

数据来源 LOJ 2483

 

 

已搬至 YZOJ P4254 。…

[SDOI2012]任务安排

[SDOI2012]任务安排

时间限制:1000MS      内存限制:131072KB

难度: \(7.1\)

  • 题目描述

按顺序给定 \(N\) 个子任务,每个任务用时 \(t_i\) ,费用系数 \(f_i\)。

可以把连续的若干个(或一个)子任务合成为一个大任务,大任务的用时和费用系数分别为其中每个子任务的用时之与费用系数之。开始一个大任务之前需要准备时间 \(S\),一个大任务的费用为他的 完成时刻 \(\times\) 费用系数 ,问按顺序执行完所有的大任务后,最小的费用和为多少。

形式化的,将 \(N\) 个任务划分成若干个块,每一组任务 \(M_i\) 花费代价 \((T+\sum{t_j}+S) \times \sum{f_j}\),\(j \in M_i\),\(T\) 为执行到这个任务之前花费的时间,求执行完所有任务的最小代价和。

  • 输入格式

第一行一个整数 \(N\) ;

而后 \(N\) 行中,第 \(i\) 行包含一个可能为负的整数 \(t_i\) 和一个非负整数 \(f_i\) 。

  • 输出格式

一个整数,表示最小的代价和。

  • 样例输入

  • 样例输出

  • 样例说明

如果分组方案是 \(\{1,2\}\)、\(\{3\}\)、\(\{4,5\}\),则完成时间分别为 \(\{5,5,10,14,14\}\),费用 \(C=\{15,10,30,42,56\}\),总费用就是 \(153\) 。

  • 数据规模与约定

对于 \(20\%\) 的数据,\(1 \leq N \leq 1000\) ;

对于另外 \(40\%\) 的数据, \(1 \leq N \leq 300000\) ;

对于前 \(60\%\) 的数据,\(0 \leq t_i \leq 2^8\) ;

对于后 \(40\%\) 的数据,\(1 \leq N \leq 100000\),\(-2^8 \leq t_i \leq 2^8\)

对于 \(100\%\) 的数据, \(0 \leq S, f_i …

YZOJ P2021 [APIO2014]sequence

YZOJ P2021 [APIO2014]sequence

时间限制:2000MS      内存限制:131072KB

难度: \(5.7\)

  • 题目描述

给定一个长度为 \(N\) 的非负整数序列 \(a\) ,现要把它分割成 \(k+1\) 个连续非空的子序列。

每次分割可以选择一段剩余长度超过 \(1\) 的序列,并在其中选择一个位置,把它分割成两个连续非空的子序列。这样做可以得到一些 \(Bonus\),为分割出的两个新序列中元素和乘积

现要找到一种方案,使得经过 \(k\) 次分割后,能得到的 \(Bonus\) 最多。

  • 输入格式

第一行包含两个整数 \(n,  k\) ;

第二行包含 \(n\) 个非负整数,表示序列 \(a\) 。

  • 输出格式

第一行包含一个整数,为最大 \(Bonus\) 。

第二行包含 \(k\) 个 \(1\) 到 \(n-1\) 的整数,表示最优方案。其中第 \(i\) 个数 \(x_i\) 表示在该方案中,进行第 \(i\) 次操作时,应该选择第 \(x_i\) 个数后面的位置,并将这个数所在的序列分成两部分。

如果有多个最优方案,输出其中任意一种即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

数据满足 \(2 \leq n \leq 100000\),\(1 \leq k \leq min\{n-1,200\}\) 。

 

 

 …

YZOJ P3199 [FJSC2017D8T1]飙车一时爽,一直飙车一直爽

YZOJ P3199 [FJSC2017D8T1]飙车一时爽,一直飙车一直爽

时间限制:2000MS      内存限制:524288KB

难度: \(4.5\)

  • 题目描述

最近 \(mnihyc\) 喜欢上了飙车,他甚至飙到了 \(40km/h\) ,这已经是严重的超速了!因此,只要他飙车时连续通过超过 \(K\) 段道路,那么他就会被交警抓走!不过幸好的是,他骑的是共享单车,所以他可以在某些路口更换他的自行车,这样交警就不会发现之前那个飙车的是他了!

简单来说,城镇中有 \(N\) 个路口,\(M\) 条双行道连接着两个不同的路口。这些路口中总共有 \(P\) 个有共享单车停靠点,分别分布在 \(a_1, a_2, \cdots, a_P\) 上。

现在 \(mnihyc\) 想知道,从 \(S\) 出发到 \(T\) ,他至少可以飙上多少段连续的道路?如果太少的话,他会选择蹲在家里推游戏的(好可怜)。

形式化的,给定一张无向图,\(\left| V \right| = N\),\(\left| E \right| = M\),边权均为 \(1\),找出一条从 \(S\) 到 \(T\) 的可重路径使得路径上相邻的关键点(\(S, T, a_1, a_2, \cdots, a_P\))之间的最大距离 \(K\) 最小

  • 输入格式

第一行一个正整数 \(CAS\) 表示测试数据组数。

每组测试数据第一行有三个数 \(N, M, P\)  如上文所述,第二行 \(P\) 个数表示 \(a_1, a_2, \cdots, a_P\) 。

接下来 \(M\) 行,每行两个数表示一条边。

最后 \(S\) 和 \(T\) 表示开始节点和的目标节点。

  • 输出格式

对于每组数据:若始终都无法找到合法的路径,输出 \(-1\),否则输出最的小的 \(K\) 。

  • 样例输入


Read the rest