2 ylsoi

尚未进行身份认证

暂无相关描述

等级
博文 261
排名 2w+

NOI2013 树的计数

NOI2013树的计数给定一个dfs序和bfs序,求解符合这两个条件的所有树的平均树高。思路如果我们能够给bfs序中每一段区间分层,然后再去对应dfs序,不难发现可以唯一确定一棵树,即在dfs的过程中,前后两个节点的关系可以按照层数来判断,分为儿子或者是某一层祖先的另外一个儿子。而给bfs序分层的时候我们需要满足一些限制:bfs序中同一层在dfs中访问顺序必须严格按照bfs的访问顺序...

2019-06-18 19:00:10

拆系数FFT学习笔记

拆系数FFT学习笔记拆系数FFT当题目中取模的数不是NTT模数的时候,我们无法利用原根来进行快速数论变换,这个时候就要用到毛啸论文里提到的拆系数FFT。大致思路拆系数FFT实际上是将多项式卷积之后的值具体算出来,普通的FFT由于精度误差较大,当然无法胜任。于是可以考虑将一个较大的数拆成两个较小的数,即将xxx拆成a×t+ba\timest+ba×t+b,这样相当于将xxx给ttt...

2019-04-05 09:20:03

HAOI2017 八纵八横——线段树分治+线性基

题目大意给定一个图,每次加一些边,或者删掉一些后来加上去的边,定义一个环的价值为环上所有的边的异或和,重复走的边重复算。每次询问这个时刻图中的所有经过1号点的环的最大价值。思路首先考虑对于一个静态的图如何求解图中所有经过1号点的环的最大价值,发现这个经过1号点就是唬人的,图中任意一个环都可以经过1号点再走回来。于是题目变成了求解图中环的最大价值,可以将图中所有的简单环给拎出来放到线性基里面...

2019-04-03 11:52:25

BJOI2018链上二次求和——线段树

BJOI2018链上二次求和思路[l,r]的限制可以拆成[1,l-1],[1,r],然后考虑推式子。设sis_isi​为aia_iai​的前缀和。ans=∑i=1x∑j=insj−sj−i{\rmans}=\sum_{i=1}^{x}\sum_{j=i}^{n}s_{j}-s_{j-i}ans=∑i=1x​∑j=in​sj​−sj−i​设tit_iti​为sis_isi​的前缀和。...

2019-03-31 22:18:10

[bzoj3514]Codechef MARCH14 GERALD07加强版——lct+主席树

题目大意给定一个图,求编号在[l,r]之间的边形成的图的连通块个数。思路考虑一条边什么时候会造成贡献,即这条边相连的两个部分在之前从未连通过,或者是把所有编号小于l的边去掉之后这两个部分未连通。对于第一种情况可以轻松地用并查集来实现。对于第二种情况,对于每一个l,我们需要判断出u,v这两个点的所有路径中是否存在一条路径使得min(id)>=l,如果不存在则(u,v)这条边可以造成一...

2019-03-31 17:02:15

KD-Tree 学习笔记

KD-Tree学习笔记SDOI2010捉迷藏对于i=1…n,求曼哈顿距离距离i最近和最远的点的距离分别是多少。思路KD-Tree的模板题目。KD-Tree,实际上就是对一个多维空间进行不断的划分,在一维上类似于二叉搜索树。如果是多维的,我们可以每一次只划分一维,然后这样不断轮流划分不同的维度。具体的,对于当前维度的划分,我们最优秀的策略就是取所有点按照当前维度排序之后从中点划分...

2019-03-27 22:03:41

SDOI2010 捉迷藏 —— KD-Tree

SDOI2010捉迷藏对于i=1…n,求曼哈顿距离距离i最近和最远的点的距离分别是多少。思路KD-Tree的模板题目。KD-Tree,实际上就是对一个多维空间进行不断的划分,在一维上类似于二叉搜索树。如果是多维的,我们可以每一次只划分一维,然后这样不断轮流划分不同的维度。具体的,对于当前维度的划分,我们最优秀的策略就是取所有点按照当前维度排序之后从中点划分开来,这样可以保证整颗树尽...

2019-03-25 22:38:26

HAOI2018染色——容斥

HAOI2018染色思路设fif_ifi​表示至少出现了i种颜色的方案数fi=(mi)×(s×i)!(s!)i×(ns×i)×(m−i)n−s×ifi=(mi)×n!(s!)i×(n−s×i)!×(m−i)n−s×i\begin{aligned}f_i&={m\choosei}\times\frac{(s\timesi)!}{(s!)^{i}}\times{n...

2019-03-23 15:31:33

[BJWC2018]Border 的四种求法——SAM+线段树合并+DSU+链分治

Border的四种求法给定一个串,q次询问[l,r]的border长度。思路首先先对整个串建sam,然后我们对包含r的每一个状态去计算。设当前状态的最大长度为len,如果一个结束位置i是合法的,当且仅当l≤i<rl\leqi<rl≤i<r,且i<l+leni<l+leni<l+len,然后我们需要找到一个最大的...

2019-03-13 16:21:15

[uoj218]火车管理——主席树

题目大意维护一个栈,每次区间压栈,单点弹栈,区间询问栈顶的元素和。思路如果没有弹栈的操作的话,我们每一次只需要在一颗线段树上面区间赋值即可。加上弹栈操作,我们每次就需要知道当前栈顶元素的上一个元素是什么,考虑用主席树来维护每一个时刻每一个位置的最近一次的修改位置。假设当前的时间为x且我们需要弹栈,那么我们需要先查询得到最近的一次时间y,然后查询y-1的修改时间z,那么我们就得到了栈顶下面...

2019-03-11 21:45:57

[bzoj2125]最短路——仙人掌,圆方树

题目大意求仙人掌上最短路.思路将仙人掌上的所有环给建立方点,所有环上的点作为圆点连在方点上面.考虑一个以1为根的树型结构,我们将所有环上的点和方点的距离设为该点离环上深度最小的点的最小距离.这样利用树上倍增来求解两点之间距离后,我们发现跨过的环(方点)上的路程就是环上的点离环上深度最小的点的最小距离,于是我们只需要判断一下lca是否是方点即可。/*===================...

2019-03-03 20:16:16

[loj2731]「JOISC 2016 Day 1」棋盘游戏

题目大意有一个3×n的棋盘,你在上面玩游戏。开始时,棋盘有一些格子上已经摆上了棋子,剩下的格子都是空的。每次你可以选择一个空的格子摆上棋子,这个格子必须满足以下两个条件之一:这个格子上下两格都有棋子;这个格子左右两格都有棋子。你想知道有多少种不同的摆满棋盘的摆放顺序。思路首先判断无解,如果四个角没有棋子或者一三行出现了连续两个空格子,那么就无解.然后发现整个图变成了这个样子:...

2019-02-27 15:28:12

[WC2018]州区划分——FMT优化DP

题目大意:这是链接思路:考虑动态规划,设fSf_{S}fS​表示$S集合中的点的划分的满意度之和,设集合中的点的划分的满意度之和,设集合中的点的划分的满意度之和,设t_{S}表示表示表示S集合中的点是否合法,集合中的点是否合法,集合中的点是否合法,w_S表示表示表示S$集合中的点的权值之和,那么可以得到方程:fS=∑T⊆SfS−T×tT×(wTwS)pf_{S}=\sum_{T\sub...

2019-02-21 16:35:04

「NOI2018」你的名字——后缀自动机

题目大意:给定一个母串和若干个询问串,求每个询问串有多少个本质不同的子串没有在母串中出现过。思路:ION2017的串我们称为S串,ION2018的串我们称为T串。先考虑68pts怎么去做。考虑T串有多少个子串未在S串中出现过,于是将S建立SAM,然后将T丢进S的SAM里跑子串匹配,这样我们可以得到T的每一个结束位置的最大匹配长度,所有长度大于这个长度的子串都是符合要求的子串。上述方法对...

2019-02-20 21:00:09

4566: [Haoi2016]找相同字符——后缀自动机

题目大意:给定两个串,求有多少种方式从两个串中各提取出一个子串并且两个子串相等。思路:涉及两个串的子串问题考虑对第一个串建立SAM。然后用第个二串在SAM上匹配,每到一个点,贡献是(目前的长度-这个状态的父亲的长度)x这个状态RIGHT集合的大小,同时对这个状态的每个祖先也像这样计算贡献即可。/*=======================================*Aut...

2019-02-14 18:11:27

[uoj276][清华集训2016]汽水——分数规划+点分治

题目大意:给定一颗带边权的树,求一条路径使得这条路径上的边权的平均值最接近一个给定的值。思路:既然是求平均值,那么自然而然就想到了分数规划了,即最小化∣∑i=1lenwilen−k∣|\frac{\sum_{i=1}^{{len}}w_i}{len}-k|∣len∑i=1len​wi​​−k∣。然后二分答案xxx,考虑是否存在比xxx更优的答案:∣∑i=1lenwilen−k∣≤x|\f...

2019-02-13 14:22:19

[bzoj3451]Tyvj1953 Normal——点分治+fft

题目大意:求随机点分治的期望复杂度,每次对一颗大小为nnn的子树需要O(n)O(n)O(n)的复杂度。思路:考虑计算每个点期望下被算的次数,根据期望的线性性,最后将每个点的答案加起来就可以了。计算点u的计算次数可以考虑v对点u的贡献,即在v作为分治重心的时候u在v所在的子树里面。不难发现如果v对u产生了贡献,那么从u到v的路径上,v必定是第一个选的,路径外的点怎么选没有影响,于是期望贡献...

2019-02-13 09:58:48

[bzoj3143][Hnoi2013]游走——动态规划+高斯消元

题目大意:一个无向连通图,顶点从1编号到N,边从1编号到M。小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z到达N号顶点时游走结束,总分为所有获得的分数之和。现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。思路:由于我们需要确定每条边的权值,所以不妨将每条边期望意...

2019-02-11 13:41:14

[loj2542]「PKUWC2018」随机游走——min-max容斥+树上高消

题目大意:给定一棵n个结点的树,你从点x出发,每次等概率随机选择一条与所在点相邻的边走过去。有Q次询问,每次询问给定一个集合S,求如果从x出发一直随机游走,直到点集S中所有点都至少经过一次的话,期望游走几步。特别地,点x(即起点)视为一开始就被经过了一次。答案对998244353取模。思路:看到所有点都经过一次直接上min-max反演。然后我们要求每个集合...

2019-02-10 20:29:14

[bzoj4589]Hard Nim——SG函数+FWT

题目大意:Claris和NanoApe在玩石子游戏,他们有n堆石子,规则如下:Claris和NanoApe两个人轮流拿石子,Claris先拿。每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜。不同的初始局面,决定了最终的获胜者,有些局面下先拿的Claris会赢,其余的局面Claris会负。Claris很好奇,如果这n堆石子满足每堆石子的初始数量是不超过m的...

2019-02-10 17:07:48
奖章
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。