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

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


了解详情 >

CF490F Treeland Tour

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

动态 DP 学习笔记

前言 动态 dp 一般用来解决树上的 dp 问题,同时需要支持修改点权/边权的操作。 前置知识:矩阵乘法,树链剖分 模板题 题意 洛谷 P4719 【模板】动态 DP 带修改点权的树上最大独立集, n 点, m 次操作 不带修改操作 没有上司的舞会嘛不就是。令 f_{i,0} 表示 i 子树内不选 i...
OInotes

AtCoder Regular Contest 120 解题报告

ARC120A - Max Add 需要想一两分钟的贪心 ARC120B - Uniformly Distributed Description 给定 H \times W 的方格,其中一些涂了红色,一些涂了蓝色,一些什么都没涂。问对于剩余的格子,有多少种涂色的方案使得从 (1,1) 到 (H,W) ...

ARC069D Flags

题意 给定 n 个旗帜,每个旗帜要么放在 x_i 要么放在 y_i ,问两两旗帜间最小的间隔最大是多少。 n\le 10^4 , x_i\le 10^9 题解 “最小的最大”,考虑二分这个答案。 至于怎么判定,注意到要么选 x ...

CF1493D GCD of an Array

题意 给定 n 个数 a_{1\cdots n} ,进行 q 次单点乘法操作,满足 1\le n,q,a_i\le 2\times 10^5 ,求每次操作完后 \displaystyle\gcd_{i = 1}^na_i\...
OIsolcf

线段树进阶应用

维护较复杂信息 一般在维护较复杂信息的时候,为了代码的简介易懂,一般将线段树定义为一个结构体: 12345struct node{ int val, val2, tag;//........这里放信息} t[maxn << 2]; 然后可以重载加号,这样子方便需要返回一个节点的 query() 函数。 区间最大连续子段和 维护最大前缀和,后缀和和子段和。合并时注意跨越端点的...
OInotes

解题报告 P4198 楼房重建

题目内容 P4198 大意:维护一串序列,单点修改,在线查询 LIS 解题思路 首先这题要注意精度问题,有可能会出现玄学的精度错误 分析题意:考虑看到的楼房最高点 (i,H_i) ,不难发现能看到的楼房的最高点的斜率都是递增的,即 k_i=i/H_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