xuxuxuxuxu

分类

未归档(20) 题解(24)

/ 注册

TA的专栏 39篇文章 0人订阅

39篇文章 2130人学习

全部文章（共43篇）

SOS-DP(子集DP) 来自专栏

简单的求子集和的4种做法: for(int i=0;i<(1<<n);i++) for(int j=0;j<i;j++) if(j&i==j)F[i]+=A[j]; for(int i=0;i<(1<<n);i++) { ...

SOS-DP

2019-08-29

0 2130

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

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

概率生成函数

2019-07-25

0 939

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

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

决策单调性

2019-07-19

1 1054

2-sat学习笔记来自专栏

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

2-sat

2019-07-19

1 741

三元环学习笔记来自专栏

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

三元环

2019-07-19

1 922

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

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

同余最短路

2019-07-19

1 1174

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

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

李超线段树

2019-07-19

1 819

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

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

模拟退火

2019-07-19

0 634

洪水来自专栏

题目：给你一棵树，节点从到编号，每个节点有一个权值，有若干次操作，操作有以下两种：  ：将编号为的点的权值改为 :询问将号节点为根的子树中的所有叶子结点与子树外的其他所有叶子节点分离的最小代价，分离可以通过删除节点实现，删除一个节点的对应代价为该点的权值 ...

动态DP

2019-07-19

0 734

[SDOI2018]旧试题来自专栏

题目：其中表示的约数个数。题解：首先有具体证明我不会，见他人博客设发现了什么，这个式子是不是就是 #2476. 「2018 集训队互测 Day 3」蒜头的奖杯中的然后，我们来推一下这个式子，感觉这个式子还是蛮重要的。首先: 常规莫比乌斯反演, 令这一步我不是很看得懂...

莫比乌斯反演

2019-07-19

0 758