RainAir

分类

学习笔记(12) 题解(9)

/ 注册

全部文章（共21篇）

一种最小割建模方法

网络流题目中，如果一种物品有两种状态（选或不选），告诉你每一种状态产生的收益/代价，我们就可以通过使用最小割模型来解决这个问题。但是如果物品的状态扩展到了种，我们就需要用一种新的建图方法。我们拿两道题目举例： RatingProgressAward *TCO2017 Semifinal题目链接如...

最小割

2020-02-28

0 954

轮廓线 dp 学习笔记

轮廓线 dp 也是一种状压，适用于一维特别大而另一维特别小的情况。我们来从一道经典例题入手：求的骨牌填满的矩形的方案数。如果那么当然可以轻松状压了，但是如果，我们就要考虑使用轮廓线 dp 了。设表示我们填到第行，我们在状压的状态中记录下图红线上的格子的状态。（圆圈为现在要...

轮廓线dp

2020-02-28

0 2068

「NOI2017」游戏

建议大家去 UOJ 交题题目描述有场游戏和三种车，每个游戏可以选择用一种车，每个游戏可能要求不能使用某种车，也可能没有要求。给出个要求，表示如果第个游戏用了车，那么第个游戏要用车。求一种合法方案。，没有要求的游戏个数不超过。题解前置小知识：2-SAT链接建图...

2-SAT

2020-02-28

0 622

2-SAT 学习笔记

定义 SAT 维基百科——Boolean_satisfiability_problem 2-SAT SAT 的简化版本：每个等式中只有两个变量参与。有个变量和个等式，每个等式形如，其中是一个位运算。你要求出一组可行解。求解将每个拆成两个点和表示取值情况。每个限制...

2-SAT

2020-02-28

0 874

「八省联考2018」林克卡特树

主要是为了学习一波 wqs 二分。首先发现这个题目等价于把树切成 k+1 块每块内选个直径加起来，也就等价于在树上找条不相交的链使得收益最大。考虑树上每一条链都可以拆成两条深度单调的链，所以我们可以设表示现在在点已经选择了个链当前点的状态是（没有链经过/有一条单链待匹配...

动态规划凸优化

2020-02-28

0 776

SAM 学习笔记

作为菜鸡 OIer，本文尽量用通俗的语言去讲解后缀自动机。当然学习后缀自动机前是有一点点前置知识的，我一块给说了。有限状态自动机（DFA）定义确定优先状态自动机是由：一个非空有限的状态集合一个输入字母表（非空有限的字符集合）一个转移函数（例如：）一个开始状态一个接受状态的...

后缀自动机

2020-02-28

0 783

「NOI2005」瑰丽华尔兹

题目链接题目大意现在有一个的矩阵，给定的起始点上有个钢琴，矩阵上有些方格是障碍物，用连续的区间和一个参数表示在时间时会向方向滑动（上下左右），当然每个时间点可以选择让钢琴不动，不允许钢琴超出边界或者碰到障碍，询问钢琴可能走的最远距离是多少。其中 ,区间个数，区间最大的右端点...

动态规划

2019-07-19

0 710

DDP 学习笔记

DDP（动态 dp），是通过将状态改写成矩阵，然后定义具有结合律的与转移等价的运算，用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。NOIP2018 Day2T3 - 保卫王国考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡，现在回来学一学。我们来找一道简...

动态DP

2019-07-19

0 683

数论公式

记录各种我这种数论菜鸡不会的式子。。。可能有很 zz 的式子大佬不要嘲笑整除与不定方程证明：存在整数解。证明：从右往左推：令 ,则有从左往右推：考虑构造，这样就可以构造出所有的解了。令,证明现在我们尝试解显然 ,考虑设。如果有解即可。递归出口是 ,显然有解。现...

数论

2019-07-19

0 695

后缀数组

定义维基百科 - 后缀数组让我们来看一下 wiki 上的定义：在计算机科学里, 后缀数组（英语：suffix array）是一个通过对字符串的所有后缀经过排序后得到的数组。此数据结构被运用于全文索引、数据压缩算法、以及生物信息学。令字符串，表示的子字符串，下标从到。的后缀数组 ...

后缀数组

2019-07-19

0 791