题目链接 题意 有n个房间，每个房间里面有若干把钥匙，每把钥匙可以打开对应的一扇门。如果手中没有钥匙，就要随机轰炸一个房间来打开这个房间。如果有钥匙，就要去打开这些房间。问期望轰炸次数是多少。 思路 根据期望的线性性质，总期望轰炸次数就是每个房间被轰炸的概率\(\times\) 1。 所以就考虑每个房间被轰炸的概率。 先理解一下题意，也就是说只要打开了一扇门就可以打开若干扇门。所以可以从每个房间向他房间中钥匙所对应的房间连边。 每个房间被轰炸当且仅当所有可以到达他的房间都没有被轰炸。 所以把上面所说的边放过了。跑一边传递闭包。第i个点被轰炸的概率就是\(1/anc(i)\)，\(anc(x)\...

题目链接 思路 floyd求一下传递闭包，然后统计每个点可以到达的点数。 会tle，用bitset优化一下。将floyd的最后一层枚举变成bitset。 代码 /* * @Author: wxyww * @Date: 2019-01-23 15:08:40 * @Last Modified time: 2019-01-23 15:22:52 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include&...

题目链接 思路 floyd求一下传递闭包，然后统计每个点可以到达的点数。 会tle，用bitset优化一下。将floyd的最后一层枚举变成bitset。 代码 /* * @Author: wxyww * @Date: 2019-01-23 15:08:40 * @Last Modified time: 2019-01-23 15:22:52 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include&...

听attack学长讲完课，整理一波   基本运算   按位或   \(1|1 = 1，1 | 0 = 1，0|0 = 0\)   按位与   \(1\&1=1 ,1 \& 0 = 0,0 \& 0 = 0\)   异或   \(1 \bigoplus 1 = 0,1\bigoplus 0 = 1,0 \bigoplus 0 = 0\) 异或性质 1.\(a \bigoplus a = 0\) 2.\(a \bigoplus 0 = a\) 3.\(a \bigoplus b = b \bigoplus a\) 4.\(a \bigoplus b \bigoplus c ...

题目链接 圆方树 圆方树就是对于联通无向图中的每一个点双新建一个方点，与点双中的每个点连一条边，然后将原来的边删去。将原来的点看作圆点，新建的点看作方点。所以叫做圆方树。 性质 1.圆方树肯定是棵树(废话)。证明显然。 2.圆方树中与圆点相连的点肯定是方点。与方点相连的点肯定是圆点。 算法 根据圆方树的定义就可以知道。构建圆方树的过程实际上就是找点双的过程。本质上就是找割点。所以用tarjan来做就好了。将找出的点双中的点与新建的点连边即可。 思路 这个题就是圆方树的经典应用，先对于原图构建出圆方树。那么对于每个从S到T的路径。在圆方树上两点之间的简单路径上的圆点就是在原图中必须经过的点。然后...

题目链接 圆方树 圆方树就是对于联通无向图中的每一个点双新建一个方点，与点双中的每个点连一条边，然后将原来的边删去。将原来的点看作圆点，新建的点看作方点。所以叫做圆方树。 性质 1.圆方树肯定是棵树(废话)。证明显然。 2.圆方树中与圆点相连的点肯定是方点。与方点相连的点肯定是圆点。 算法 根据圆方树的定义就可以知道。构建圆方树的过程实际上就是找点双的过程。本质上就是找割点。所以用tarjan来做就好了。将找出的点双中的点与新建的点连边即可。 思路 这个题就是圆方树的经典应用，先对于原图构建出圆方树。那么对于每个从S到T的路径。在圆方树上两点之间的简单路径上的圆点就是在原图中必须经过的点。然后...

题目链接 Boruvka生成树算法 \(Boruvka\)算法就是先把每个点看作一个联通块，然后不断在联通块之间找最优的边进行合并。因为每次联通块的数量最少缩小一半。所以合并次数是\(log\)的 先把所有的点权挂到\(trie\)树上。然后对于每个联通块进行合并的时候。对于联通块中的每个点都去\(trie\)上搜索他能找到的最优秀的边。也就是说如果当前位置是\(1\)那么就搜索1子树，否则的话既要搜0子树，也要搜1子树。这样1子树是一定要搜的。所以把0子树变为1子树和0子树合并起来的结果。然后就可以搜索了。 还有一个问题就是。如果当前子树中的所有点都已经在这个联通块里了怎么办。所以统计出每棵...

受限于博主水平，本博客可能会有一些错误。请勿轻信。欢迎指正。 博主是一个正在OI路上摸爬滚打的现役OIER， 我的个人博客 申请友链请联系我 QQ 博客园消息 自二月十五日之后的博客题目链接会尽量改为镶嵌页面(权限题和加载过慢的网站除外)，题解提交一条龙服务哦\(qwq\)

定义——来自百度百科 子串 一个字符串中连续的一段成为这个字符串的子串。 后缀 后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 r 的从 第 i 个字符开始的后缀表示为 Suffix(i) ，也就是Suffix(i)=r[i,len(r)] 。 子串的大小 大小比较：关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i 从1 开始顺次比较u[i]和v[i]，如果u[i]=v[i]则令 i 加1，否则若u[i]<v[i]则认为u<v，u[i]>v[i]则认为u>v（也就是v<u），比较结束。如果i>len(...

题目链接 思路 先求出后缀数组，并且求出LCP。二分一下长度len。check的时候就是看有没有连续的k个后缀的LCP大于len。也就是判断是不是有连续的k-1个height大于len。 代码 #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int N = 20000+10; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c ==...

题目链接 思路 先求出后缀数组，并且求出LCP。二分一下长度len。check的时候就是看有没有连续的k个后缀的LCP大于len。也就是判断是不是有连续的k-1个height大于len。 代码 #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int N = 20000+10; ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c ==...

题目链接 思路 首先肯定想到贪心，从队尾和队首取更小的那个。 但是如果遇到队尾和队首一样大的情况呢，总不能再挨个往前比较。所以就把整个字符串倒过来再挂到现在字符串的后面，也就是把当前字符串对称过去。然后求出后缀数组，给每个后缀都求个排名。然后每次取得时候取排名更小的就行了。 注意这个题的输出格式，每80个字符输出为一行。 代码 #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset&...

题目链接 思路 首先肯定想到贪心，从队尾和队首取更小的那个。 但是如果遇到队尾和队首一样大的情况呢，总不能再挨个往前比较。所以就把整个字符串倒过来再挂到现在字符串的后面，也就是把当前字符串对称过去。然后求出后缀数组，给每个后缀都求个排名。然后每次取得时候取排名更小的就行了。 注意这个题的输出格式，每80个字符输出为一行。 代码 #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset&...

基础 暴力！！ 啥叫莫队 莫队是前国家队队长莫涛想出的算法。用于处理一些可离线的区间问题。可以将本来是\(n^2\)的复杂度优化成n*根号级别。是基于分块的。 普通莫队 这类莫队用来处理一类可离线，无修改的区间问题，也是最基础的莫队。 先来看这样一道题:  给出一个长度为n的序列，然后有m次询问，每次询问从l到r这个区间内不同的数字的个数。\(1 \leq n ,m \leq 10^5\) 先考虑普通的暴力怎么打，那就是每次询问都扫一遍呗。 然后考虑有一些点，在很多次询问的时候都被扫到过。是不是可以把这里给优化一下。 是的。莫队的做法是给每个位置的点分块。然后把询问离线下来，排个序。排序的标准...