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

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


了解详情 >

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 ...

2019 CSP-S 题解

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




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