xuxuxuxuxu

未归档

题解(24)

/ 注册

全部文章 / 未归档（共19篇）

概率生成函数学习笔记来自专栏

本文参考：bztMinamoto和露迭月巨佬的博客前置知识：对生成函数有一定了解，有概率期望的一定基础。定义：一个生成函数F(x)，第i位表示某某为i的概率。例题：[CTSC2006]歌唱王国题意：给定一个长度为的序列。然后每次掷一个平骰子（有m种值）并将其上的数字加入到初始为空的序列的末...

概率生成函数

2019-07-25

0 947

决策单调性学习笔记来自专栏

决策单调性（Flush Hu ）这有什么用？这能优化dp。决策单调性和斜率优化差不多。需要细心发现决策之间的递变规律。比如：决策单调性有两种做法： 1.二分栈(队列)：决策二分栈（一种单调栈）来维护所有有用的决策，其中栈顶是当前最优决策。 2.分治：然而二分栈有一个局限性，那就是...

决策单调性

2019-07-19

1 1059

2-sat学习笔记来自专栏

2-sat 题目：[模板]2-SAT 问题题目描述: 有n个布尔变量，另有m个需要满足的条件，每个条件的形式都是“为true/false或为true/false”。比如“为真或为假”、“为假或为假”。2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。题解： 0表示不选，1表示选...

2-sat

2019-07-19

1 749

三元环学习笔记来自专栏

三元环是什么？三元环是求无向图的三元环有两种方法：做法1： ①统计每个点的度数 ②入度$sqrt(m)$的分为第二类 ③对于第一类，暴力每个点，然后暴力这个点的任意两条边，再判断这两条边的另一个端点是否连接因为m条边最多每条边遍历一次，然后暴力的点的入度，所以复杂度约为 ④对于第二类...

三元环

2019-07-19

1 928

同余最短路学习笔记来自专栏

同余最短路是什么？就是没个点i的意义是在模mn的意义下能被构造出来的最小值这有什么用呢？这可以用最短路的方法求的余数是的最小能构造出来的数这就可一求1-k中有多少数能被构造出来，即若干个a1到an的和 dis[(u+a[i])%mn]=min(dis[(u+a[i])%mn],dis[u]+...

同余最短路

2019-07-19

1 1179

李超线段树学习笔记来自专栏

算法介绍：李超线段树是一种用于维护平面直角坐标系内线段（直线）关系的数据结构。它常被用来处理这样一种形式的问题：给定一个平面直角坐标系，支持动态插入一条线段（直线），询问从某一个位置横坐标x从上向下能看到的最高的一条线段（也就是给一条竖线，问这条竖线与所有线段的最高的交点。）主要思想：对...

李超线段树

2019-07-19

1 826

模拟退火学习笔记来自专栏

模拟退火模拟退火能解决三分这类的问题，当然能解决三分不能的（暂时还不太会）它能求出单峰函数的极值。具体实现：时间t初值为区间大小，每次乘上delta，delta一般设为0.992333 每次改变位置（先大范围跳，在小范围跳），计算答案，如果更优就更新，不优就用一个概率去选择更新 void t...

模拟退火

2019-07-19

0 638

线性基学习笔记来自专栏

前言: 如果你不会线性基，希望能对你有点帮助。作者较菜，请大佬轻表。请大家多多支持，谢谢定义：基：在线性代数中，基（也称为基底）是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集，基的元素称为基向量。向量空间中任意一个元素，都可以唯一地表示成基向量的线性组合。如果基中元素个数有...

线性基

2019-07-19

1 644

后缀数组学习笔记来自专栏

简单介绍：在字符串处理当中，后缀树和后缀数组都是非常有力的工具。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。作用：后缀数组能快速比较两...

后缀数组

2019-07-19

0 753