抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

CF490F Treeland Tour

题意 求树上严格 LIS 的长度。 n\le 6000 。 题解 比较平凡的 O(n^2\log n) 做法这里不考虑。 假定一个最朴素的 dp 状态: f_{u, 0/1, x} 表示 u 子树中往...
OIsol

ABC202F - Integer Convex Hull

Description 平面内 N 个坐标均为整数的点,其中任意三点不共线,令所有点 P_i 构成一个全集 U ,子集 S\subseteq U 且 |S|\ge 3 。问凸包面积为整数的子集 S 的个数模 10^9 + 7 ...

2019 CSP-S 题解

前言 这场没来打,但看上去很不好打的样子。 D1T1 格雷码 Description 略 Solution 直接按照题意递归模拟即可,注意 2^{64} 超出了 long long 的范围,需要特判。 123456789101112131415161718192021222324252627#include <cstdio>#define FOR...
OIsoloi

DP 优化合集

斜率优化 模板题 P3195 [HNOI2008]玩具装箱 题意:将一段序列 c_i 分成若干段,每一段的代价为 (j-i+\sum_{k=i}^jc_k-L)^2 ,求最小总代价。 不难发现状态转移方程为 f_i=\min_{j<i}\lbrac...
OInotes

BZOJ1009/洛谷P3193 [HNOI2008]GT考试

题意 求构造出长度为 n 的满足不出现 A 的字符串的方案数。字符集为数字, A\le 20 , n\le 10^9 思路 考虑 dp。 定义状态 f_{i,j} 表示构造到第 i 位,匹配到 A 的第...

解题报告 P2224 [HNOI2001]产品加工

Description 某加工厂有A、B两台机器,来加工的产品可以由其中任何一台机器完成,或者两台机器共同完成。由于受到机器性能和产品特性的限制,不同的机器加工同一产品所需的时间会不同,若同时由两台机器共同进行加工,所完成任务又会不同。某一天,加工厂接到n个产品加工的任务,每个任务的工作量不尽一样。 你的任务就是:已知每个任务在A机器上加工所需的时间t1, B机器上加工所需的时间t2及由两台...

解题报告 P5017 摆渡车

题意 有 n 名同学要乘坐摆渡车从人大附中前往人民大学,第 i 位同学在第 t_i 分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费 m 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大...

解题报告 P5664 Emiya 家今天的饭

题意 Emiya 会 n 种烹饪方法和处理 m 种主要食材。Emiya 做菜一定会用一种烹饪方法和一种主要食材,具体地,用第 i 种方法处理 j 号主要食材可以做出 a_{i,j} 种菜。现在他要做 k 道菜,需要满足: k\ge1 ...

解题报告 P1099 树网的核

题意 给定一棵边带权的树,在直径上取一条长度小于等于 s 的路径(可以退化成点)最小化树上其他点到路径上的最大距离。 思路 观察直径的性质 首先一棵树可以有很多条直径,但是他们分别必定关于他们的交点对称。 所以我们可以只考虑一条直径,不妨设两个端点分别为 P_1 , P_2 。下面指的路径全部为直径上的路径 然后,对于一个路径上的一...

解题报告 P1850 换教室

题意 对于 n 个时间段中的每一个时间段 i ,都有两门内容相同的课程分别在 c_i 和 d_i 教室上课,一开始被默认分到 c_i 上课,对于每个时间段 i 可以提交一个申请将教室从 c_i 换到 d_i ,申请通过的概率...




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme