分类 Oi 下的文章:

4896: [Thu Summer Camp2016]补退选 可持久化trie
发表于: | 分类:Oi | 评论:0 | 阅读:131
我一定是数据结构学傻了…… 我写了一个可持久化trie来维护历史最大值,然后每次询问二分答案上可持久化trie上跑一下验证 然后被大爷一顿神D,我也非常绝望 其实我们考虑在每个节点维护一个vector表示第一次超过$times$是什么时候就行了…… 跪大爷 #i...

阅读全文>>

3456: 城市规划 CDQ分治+NTT 计数问题
发表于: | 分类:Oi | 评论:0 | 阅读:175
求$n$个点无向连通图的方案数 首先我们非常容易得到一个$n^2$的递推式,设$f(i)$表示$i$个点无向连通图的方案数,那么我们用所有情况的方案数减去不合法的方案数,不合法的话我们可以枚举$1$所在的联通块的大小进行计算,用$t(x)$表示$x$个点形成的完全...

阅读全文>>

4916: 神犇和蒟蒻 杜教筛 狄利克雷卷积
发表于: | 分类:Oi | 评论:0 | 阅读:158
第一问不会的出门左转百度$\mu$是啥去 第二问的话显然答案是等于$\sum_{i=1}^n{i\varphi(i)}$的,不知道的出门左转百度$\varphi$计算公式去…… 然后考虑那个东西我们用杜教筛搞一下 考虑$f(x)=x$和$g(x)=x\varphi...

阅读全文>>

BZOJ 3510: 首都 LCT 求重心
发表于: | 分类:Oi | 评论:0 | 阅读:224
首先到达所有点的距离和最小的一个点必然是重心……做过幻想乡那道动态点分治的都知道吧…… 然后看到这种题显然就是启发式合并暴力拆开小的一个扔到另外一个里面 然后这题就变成动态维护size了,维护一下所有的轻儿子就行了= = 老子AAA树都会求个$size$算个P啊 ...

阅读全文>>

BZOJ3346 : Ural1811 Dual Sim Phone
发表于: | 分类:Oi | 评论:0 | 阅读:141
这题的思路很棒棒啊…… 考虑先把所有边去重,多个$a,b$间的边只保留权值最小的,那么新图最坏情况下就是$n^2$条边 然后传统套路二分答案,问题变成两个点使得他们的出边边集是全集 考虑这样一个问题,两个点的出度之和必然$>= n$,那么对于一个度数较大的点...

阅读全文>>

Title - Artist
0:00

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

TOP