何事秋。

分类

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 图论基本算法(31) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章（共461篇）

P2664 树上游戏（点分治）

题目链接题面：题解：点分治。考虑当前点分治子树的根节点为p。那么我们需要处理两部分贡献。 ①、所有节点对点p的贡献（包括p节点自己） ②、经过点p的路径（x，y）对x点的贡献。第一类贡献：如果一个节点 x 的颜色 color [ x ] 在它到根节点 p 的路径上是第一次出现，...

2020-09-04

0 562

P3157 [CQOI2011]动态逆序对（树状数组，线段树）

题目链接题面：代码： #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<...

2020-09-04

0 631

P3168 [CQOI2015]任务查询系统（主席树）

题目链接题面：题解：将 ( s , e , p) 拆分为（s，p）和（e+1，-p）按照第一键值升序排序，对于每一个（t，p）的二元组，在第 t 棵主席树上的abs（p）位置加上p。查询时，在第 xi 棵主席树上查询前 ki 个数的和。代码： #include<iostr...

2020-09-04

0 440

P3258 [JLOI2014]松鼠的新家（LCA，树上差分）

题目链接题面：题解：明显是个树上差分的题目，不知道为什么当时会用树链剖分+线段树写。 a [ 1 ] – a [ 2 ] a [ 2 ] – a [ 3 ] 其中 a [ 2 ] 最终要-1。 #include<iostream> #include<cstdio>...

2020-09-04

0 821

P3194 [HNOI2008]水平可见直线（直线交）

题目链接题面：题解：我们先按照直线的斜率从小到大排序，斜率相同按照b从大到小排序。现在考虑按照斜率排好序的三条直线 i - 1 ，i ，i +1 若 i 与 i + 1 的交点在 i 与 i - 1 交点的左侧，那么 i 不可见。代码： #include<iostream&...

2020-09-04

0 578

P3302 [SDOI2013]森林（树上主席树+启发式合并）

题目链接题面：题解：路径上第 k 大用树上主席树完成。合并的时候直接小树往大树上合并（启发式合并）。时间复杂度大概O（n logn logn），也不太会算。 #include<iostream> #include<cstdio> #include<al...

2020-09-04

0 534

P3313 [SDOI2014]旅行（树链剖分）

题目链接题面：题解：树链剖分+动态开点线段树。对于每一个宗教值 ci 建立一棵线段树，查询x–y时，在c [ x ] 这棵线段树上查询。 #include<iostream> #include<cstdio> #include<algorithm>...

2020-09-04

0 530

P3676 小清新数据结构题（树链剖分）

题目链接题面：题解：见注释代码： #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #incl...

2020-09-04

0 453

P2148 [SDOI2009]E&D （Ferguson游戏的sg函数）

题目链接题面：题解：每一组可以看作一个Ferguson游戏。重点在怎么求Ferguson游戏的sg值上。代码： #include<iostream> #include<cstdio> #include<cstring> #include<...

2020-09-04

0 530

P1772 [ZJOI2006]物流运输（最短路、dp）

题目链接题面：题解：最短路+dp 代码： //dp[i]=min(dp[j]+f[j+1][i]*(i-j)+k,dp[i]) //f[i][j] 第i天到第j天都走同一条最短路的花费 #include<iostream> #include<cstdlib> ...

2020-09-04

0 480