跳至内容
Smokey_Days - Blog
Smokey_Days – Blog

Smokey_Days – Blog

蒟蒻信息学学习笔记

  • 首页
  • 博客
  • 我
  • 关于
  • 斗骰子
  • 友情链接

分类:题解

各种题目的心得和解法。

发布于2019年11月14日

lp3225 HNOI2012 矿场搭建

这实际上是一个 Tarjan 求割点的裸题。 具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后 …

继续阅读“lp3225 HNOI2012 矿场搭建”

发布于2019年11月13日

lp4430 猴子打架/Prufer 序列

额…看起来是一道找规律题,实际上还是挺有门道的。 题目的题意就是,求 n 个点的点、边均有标号的生 …

继续阅读“lp4430 猴子打架/Prufer 序列”

发布于2019年11月6日2019年11月7日

lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。 对于序列上的情况,我们维护一个集合 ​ ,其中 ​ 表示,长度为 ​ 的 …

继续阅读“lp4577 FJOI2018 领导集团问题”

发布于2019年11月1日

CF102268C

贪心构造即可。 具体来说,如果把a依次标成-n…-1,那么只会有三种数:0(贡献是下标-1),n(贡献是0)以 …

继续阅读“CF102268C”

发布于2019年10月29日

CF1009F Dominant Indices

首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。 它本质上就是一种优化的暴力:对 …

继续阅读“CF1009F Dominant Indices”

发布于2019年10月15日

lp1341 无序字母对

仔细观察这题:考虑到字母对可以反向,我们不妨把它们看作无序数对。这就把题意转化为了,给你n个无序数对,让你找到 …

继续阅读“lp1341 无序字母对”

发布于2019年10月12日2019年10月12日

lp4027 NOI2007 货币兑换

我们观察到,整个行为一定能被拆分为全买和全卖。 略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖, …

继续阅读“lp4027 NOI2007 货币兑换”

发布于2019年10月8日

lp2564 SCOI2009 生日礼物

尺取法即可。 开一个桶维护珍珠的颜色,然后扫一遍。每一次将最前端的点弹出,然后移动至下一个合法点。

发布于2019年10月8日2019年10月8日

lp2219 HAOI2007 修筑绿化带

我们知道,如果我们确定了每个大矩形包含的权值最小的小矩形,那么我们只需要枚举一遍每一个大矩形并比较它们的回形部 …

继续阅读“lp2219 HAOI2007 修筑绿化带”

发布于2019年10月4日

lp3313 SDOI2014 旅行

虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。 树链剖分后我们考虑对每一 …

继续阅读“lp3313 SDOI2014 旅行”

发布于2019年10月3日

lp3285 SCOI2014 方伯伯的OJ

题目要求维护一个编号序列和一个排名序列,并支持四种操作: 1.按照编号修改编号,并返回该编号的排名。 2.将一 …

继续阅读“lp3285 SCOI2014 方伯伯的OJ”

发布于2019年10月2日

lp4768 NOI2018 归程

克鲁斯卡尔重构树模板题。 我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点; …

继续阅读“lp4768 NOI2018 归程”

发布于2019年10月2日2019年10月2日

lp3168 CQOI2015 任务查询系统

观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么 …

继续阅读“lp3168 CQOI2015 任务查询系统”

发布于2019年10月1日

lp3302 SDOI2013 森林

我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出 …

继续阅读“lp3302 SDOI2013 森林”

发布于2019年9月22日2019年9月22日

lp5395 【模板】第二类斯特林数·行

第二类斯特林数,指的是一组表示「将n个不同的元素划分为m个非空不相交集的方案数」的组合数。有时写作\(S(n, …

继续阅读“lp5395 【模板】第二类斯特林数·行”

发布于2019年8月15日

lp2501 HAOI2006 数字序列

我们分别考虑一二问。 对于第一问,我们思考一个子序列是合法的「不用修改」的子序列的充要条件。 容易想到的,这个 …

继续阅读“lp2501 HAOI2006 数字序列”

发布于2019年8月8日2019年8月8日

lp3233 HNOI2014 世界树

让我们来分析这道题。 我们很容易地可以发现,如果一个节点是末端节点,那么它肯定是由它祖先中的第一个节点管辖更优 …

继续阅读“lp3233 HNOI2014 世界树”

发布于2019年7月27日

lp4717 【模板】快速沃尔什变换

快速沃尔什变换是一种类似于快速傅里叶变换的操作。它是用来处理子集卷积的有效工具。 我们依次考虑操作符为and …

继续阅读“lp4717 【模板】快速沃尔什变换”

发布于2019年7月20日

lp2622 关灯问题II

显然,对于某个状态,按下某个按钮之后,一定会得到另一个状态。 而灯的状态最大只有\(2^10\)。 故而考虑建 …

继续阅读“lp2622 关灯问题II”

发布于2019年7月15日

lp2519 HAOI2011 problem a

我们为每个考生设置一个可能的区间。这个区间的左端点是l=a+1,右端点是r=n-b。 仔细观察,会发现,这个可 …

继续阅读“lp2519 HAOI2011 problem a”

文章导航

页 1 页 2 … 页 8 下一页

搜索

分类目录

  • 日志 (32)
    • 初赛 (2)
    • 站点搭建 (7)
  • 游记 (2)
  • 算法 (151)
    • 位运算 (1)
      • 线性基 (1)
    • 分块 (3)
      • 莫队 (2)
        • 回滚莫队 (1)
    • 前缀和 (2)
    • 动态规划 (23)
      • 图上动态规划 (8)
        • 树形动态规划 (7)
      • 斜率优化 (3)
      • 状压动规 (5)
      • 贪心 (2)
    • 图论 (60)
      • 二分图 (10)
        • 匈牙利算法 (7)
      • 仙人掌 (2)
      • 拆点 (2)
      • 拓扑排序 (5)
      • 最短路 (5)
        • SPFA (1)
      • 树论 (33)
        • Prufer 序列 (1)
        • tarjan缩点 (2)
        • 圆方树 (4)
        • 最小公共祖先 (4)
        • 最小生成树 (2)
          • 克鲁斯卡尔重构树 (1)
        • 树链剖分 (17)
          • 实链剖分/动态树 (6)
          • 树上启发式合并 (5)
          • 重链剖分 (7)
          • 长链剖分 (1)
        • 点分治 (3)
        • 虚树 (1)
      • 深度优先搜索 (5)
      • 点双连通分量 (2)
        • 割点 (1)
    • 多项式 (6)
      • 快速傅里叶变换 (5)
        • 快速数论变换 (3)
          • 任意模数快速数论变换 (1)
      • 快速沃尔什变换 (1)
    • 字符串 (5)
      • KMP (1)
      • 后缀自动机 (2)
      • 麻辣烫/manacher (2)
    • 尺取法 (1)
    • 差分 (4)
    • 技巧 (1)
      • 卡常 (1)
    • 搜索 (7)
      • 启发式搜索/IDA* (1)
      • 记忆化搜索 (2)
    • 数学 (32)
      • 博弈论 (5)
        • Min-Max对抗搜索 (1)
      • 排列组合 (4)
        • Polya定理 (1)
        • 斯特林数 (1)
          • 第二类斯特林数 (1)
      • 数论 (17)
        • 中国剩余定理 (3)
          • 扩展中国剩余定理 (2)
        • 数论分块 (3)
        • 欧拉函数 (1)
        • 狄利克雷卷积 (1)
        • 莫比乌斯反演 (2)
        • 逆元 (4)
      • 条件约束 (1)
      • 构造 (1)
      • 概率与期望 (5)
      • 矩阵 (2)
        • 矩阵快速幂 (2)
      • 递推式 (2)
    • 数据结构 (24)
      • 二叉搜索树 (7)
        • 平衡树 (5)
          • Splay (5)
      • 堆 (2)
      • 并查集 (2)
      • 树状数组 (1)
      • 线段树 (13)
        • 主席树 (3)
        • 动态开点线段树 (1)
        • 权值线段树 (4)
      • 队列 (1)
        • 单调队列 (1)
    • 模拟 (10)
    • 网络流 (15)
      • 最大流 (8)
      • 最小割 (2)
        • 最大权闭合子图 (1)
      • 费用流 (5)
    • 随机化 (1)
      • 模拟退火 (1)
  • 题解 (150)
    • APIO (3)
    • AtCoder (5)
      • AtCoder Beginner Contest (1)
      • AtCoder Grand Contest (1)
      • AtCoder Regular Contest (2)
    • CodeForces (18)
    • CTSC (1)
    • NOI (13)
    • NOIP (18)
    • POI (1)
    • SPOJ (2)
    • USACO (2)
    • YNOI (1)
    • 国家集训队 (5)
    • 洛谷题库 (86)
    • 清华集训 (1)
    • 省选 (41)
    • 网络流24题 (6)

页面

  • 关于
    • 友情链接
  • 博客
  • 我
  • 首页

日历

2021年二月
一 二 三 四 五 六 日
« 11月    
1234567
891011121314
15161718192021
22232425262728

信息概览

作者:Smokey_Days

代码编写人:Smokey_Days

文章发布者:Smokey_Days

活跃人员列表:

  • Smokey_Days
  • ReActor

功能

  • 注册
  • 登录
  • 文章RSS
  • 评论RSS
  • WordPress.org

活跃

  • Smokey_Days
  • ReActor

关于本站

作者:Smokey_Days

代码编写人:Smokey_Days

文章发布者:Smokey_Days

搜索

  • Yelp
  • Facebook
  • Twitter
  • Instagram
  • 电邮
自豪地采用WordPress