A simple Blog for wyx I've been down the bottle hoping.
BZOJ2780 后缀自动机 树状数组
发表于: | 分类:Oi | 评论:0 | 阅读:149
最开始的时候写的指针……写了半个小时最后发现记标号实在是蛋疼 大概是这样,我们建立一个广义后缀自动机 然后可以发现树上的一条链必然对应着一个后缀 我们在插入的时候再插入的结尾记录下他是第几个串 然后把询问的串放在上面匹配 就像是这样 显然根到红点以及根到子树内的路...

阅读全文>>

HDU5354 分治并查集 动态二分图 cdq分治
发表于: | 分类:Oi | 评论:0 | 阅读:156
给定一个无向图,问假如删除了一个点剩下的图是否是二分图 上面的那个询问是对于每个点的 首先如果每次都暴力的重新染色,你一定是$GG$的,于是你需要一些技♂巧 这个是典型的动态二分图,这类问题的处理方法有两种 1.对边进行询问,我们可以按时间分治,然后$Lct$维护...

阅读全文>>

BZOJ 4016 最小路径树问题 点分治
发表于: | 分类:Oi | 评论:0 | 阅读:157
求在他的字典序最小的最短路树上,包含K个点的链最长多长,有多少个 我觉得第一问比第二问有意思的多TAT,为什么讲题的时候跳过了@$Infinity37$ 第二问我们还是一棵子树一棵子树的合并就行的 主要是第一问,我们在平时gdb调试的时候体会到了一个奇妙的事情,那...

阅读全文>>

hdu5730 cdq+FFT
发表于: | 分类:Oi | 评论:0 | 阅读:137
题目大意 给出长度分别为$1~n$的珠子,长度为$i$的珠子有$a_i$种,每种珠子有无限个,问用这些珠子串成长度为$n$的链有多少种方案 大概这个东西就是强行套了一波两个模板233333 首先容易得到$$f(i)=\sum\limits_{j=0}^{i-1}{...

阅读全文>>

BZOJ4237 cdq分治 单调栈
发表于: | 分类:Oi | 评论:0 | 阅读:166
给定平面内一坨点,求有多少个矩形,满足矩形内部没有给定的其他的点 讲道理如果不是$cdq$习题我肯定就往什么奇怪的容斥上去想了 但是既然已经说是$cdq$的题了这题就比较好做了 我们可以先按照x排序,然后分成左右两个部分,然后分治这两个部分,分治的含义就是处理一下...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP