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

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


了解详情 >

YangTY's Blog

王侯将相宁有种乎

本站导航

前言 你好,陌生人,这里是 YangTY。详细资料可以看关于页面。 该页面将列出一些比较值得看的文章(雾) 学习笔记 平衡树笔记:写了三种主流平衡树的写法以及详细实现。 Lucas 定理:已投稿洛谷日报,Lucas 定理相关。 动态 dp:动态 dp 的入门教程。 一些正在施工的 多项式合集:多项式全家桶,目前施工到多项式 \ln 。 后缀数组:后缀数组的实现已经...

2021年6月 OI学习记录

前言 不再颓废,再战一年 学习内容 状压 dp 动态 dp 做题记录 21/06/01 P3829 [SHOI2012]信用卡凸包 旋转函数横纵坐标写反了有 50pts。。。 21/06/02 P3303 [SDOI2013] 淘金 设 f_{i, j, 0/1} 表示从小到大第 i 位,当前乘积为 ...

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

P3959 [NOIP2017 提高组] 宝藏

题意 有 n 个点组成的图,可以选择一个点作为出发点,试找到一个生成树使得总代价最小。每加一条边产生的代价为起始点到边的一段的点的个数乘上边长 n\le 12 。 题解 这里是 O(3^nn) 的状压做法。分析这道题:很重要的一点就是代价是和树高息息相关的。所以有一些做法肯定是不行的。然...

AtCoder Regular Contest 120 解题报告

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

ABC202F - Integer Convex Hull

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

AGC010C Cleaning

Description 给定一棵树,每次操作选定两叶子节点并将路径上点权减一(操作前路径上的点权必须大于 0 ),问最后是否能使所有点权为 0 。 Solution 考虑一棵以 u 为根的子树。经过 u 节点的路径,无非两种:往上延伸的和内部配对的。我们设往上延伸的路径条数为 f_u ,内部消化的路径条...

AtCoder 做题记录

ABC202 A B C D 傻逼模拟,E 长链剖分,F 凸包 + dp ARC116 VP 已更新 A + B + C ARC117 参赛。 已更新 A + B + C + D ARC118 状态奇差,只做了 A 就跑路了。 已更新 A + B + C ARC119 状态挺不好的,只做出 A 和 B。 已更新 A + B + C + DD ARC120 参赛,A + B + C 已更新 A...

AtCoder Regular Contest 119 解题报告

ARC119A - 119 × 2^23 + 1 给定 n ( 1\le n\le 1\times 10^{18} ),将 n 分解为 a \times 2^b + c 的形式,求 a + b + c ...




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