- 博客(128)
- 收藏
- 关注
RSS订阅
原创 网络流题目合集
属实狠活HDU 2883 kebab还是区间k重覆盖的变形，然而每想到就这？HDU 3315 My BruteHDU 3947 River Problem 区间k重覆盖的变形拉了
2019-10-29 13:31:52
640
原创 线段树合并，分裂和分治
先说线段树合并如果你会写主席树或者平时使用结构题那种线段树，那么理解起来就毫无压力。首先从字面上理解，如果要合并两个线段树，用最暴力的方法，就是dfs一次，然后将信息合并到一颗线段树上，那么时间复杂度就取决于不同的节点数（因为如果是只有一棵线段树有的信息，直接不管即可）。如果要合并很多个线段树，每个线段树只存了一点信息，那么自然不可能开满点，需要动态开点。这个就和主席树一样开即可。解决了开...
2019-09-18 14:35:17
665
原创 有趣题目和认知合集（持续更新）
好久没写博客了，写个树上启发式合并水水吧E. Blood Cousins森林中求某个点深度为x的孩子个数D. Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths和这个题好像，不过一个是统计点，一个统计子树。导致一个是点分治一个启发式合并...
2019-07-01 19:33:46
386
原创 Codeforces Daily (Round 370-410)
—————————————————————————-时间:8.1 &am
2019-04-11 19:52:11
327
原创 李超树学习笔记
        牛客多校出了这样一道题，一颗有边权的树，对于一条路径
2018-07-24 15:31:40
4804
2
原创 从零开始的几何学习
概念篇点/向量:同样使用两个值表示,A向量表示为A→\overrightarrow{A}A线:两个点实现点积:x1x2+y1y2x_1x_2+y_1y_2x1x2+y1y2，A→\overrightarrow{A}A⋅B→=∣A∣⋅∣B∣⋅cosΘ\cdot\overrightarrow{B}=|A|\cdot|B|\cdot cos\Theta⋅B=∣A∣⋅∣B∣⋅cosΘ叉积...
2019-09-17 15:39:25
706
原创 b2324/luogu4542 [ZJOI2011]营救皮卡丘
题意： 中文题思路：首先，如果要探寻新的点，假设i->j，一定是走的路径上比他们小的点过去的，并且在这个条件下，一定是走的最短路。这个过程可以使用floyd完成。对于i<j，假如能够到达，那么就建立一条长度为跑完floyd的dist[i][j]。那么现在问题就变成了最多使用k条路径覆盖整个dag，并且要求花...
2019-07-16 15:30:50
254
原创 网络流24题
飞行员配对方案问题二分图最大匹配+输出路径，简单题负载平衡问题费用流，让每个数都减去平均数，然后正数连源点，负数连汇点，相邻的连边，然后跑一次就行了，这里能够发现，无向图跑费用流要建两次边，而最大流不需要...
2019-04-18 10:38:06
250
原创 CodeChef QCHEF Chef and Problems （分块）
题意： 一个数列，m次查询，每次查询[L,R]中，一样的数字的最远距离思路： 分块，对于每一个块，维护fi[i][j] (第j个块，i出现最前的位置),la[i][j] （第j个块，i的出现最后的位置），再维护ans[i][j]（第i个块到第j个...
2018-09-28 21:39:51
239
原创 HDU 4776 （字典树）
题意：&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; 一棵树，有边权，路径价值为所有边权异或的值，m次查询，每次查询第k大的路径的价值###思路：&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; 从1dfs出其他点到1的路径的值，我们发现任意一条路径可以
2018-09-27 13:21:03
253
原创 CodeChef VLB Vasya and Little Bear (树上莫队)
#include&amp;lt;bits/stdc++.h&amp;gt;using namespace std;const int N = 100100;stack&amp;lt;int&amp;gt; s; //分块时需要int blocks,nowblo;//块大小,当前处于哪个块int n,m;//节点数，问题数int to[N][20],depth[N];//LCAint block[N];long ...
2018-09-16 00:24:23
246
原创 牛客多校训练（第一场）H-Longest Path(点分治+李超树)
题意： 一颗有边权的树，对于一条路径(u,v)，假设经过的边权为e1,e2,e3,...efe1,e2,e3,...efe_1,e_2,e_3,...e_f，则该路径权值cal(u,v)为(e2−e1)2+(e3−e2)2+...+（ef−ef−1)2(e2−e1)2+(e3−e2)2+...+（ef−ef−1)2(e_...
2018-07-25 10:45:51
560
原创 洛谷P4097 bzoj3615 [HEOI2013]Segment(李超树)
题意：&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; 两种操作，插入一个线段，或询问x=x0x=x0x=x_0时最大y对应的线段编号思路：&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;刚刚学了李超树就来A一下板子题，比起之前的题多了很多细节， 错误
2018-07-24 22:32:06
357
原创 spoj GSS4 Can you answer these queries IV （线段树）
题意：思路： 套路题，因为在根号几次以后，继续根号就没有意义了，利用这一点就能AC了错误及反思：代码：#include<bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r...
2018-07-24 15:30:17
405
原创 bzoj 1018 堵塞的交通traffic (线段树)
题意：思路：参考博客：https://www.cnblogs.com/MashiroSky/p/5973686.html 非常非常难写的线段树，不仅难想还难写。 首先，这个线段树维护的是什么，是该区域四个顶点的连通性 ...
2018-07-24 15:26:51
720
原创 Codeforces 85D. Sum of Medians (线段树)
题意： 三种操作,1.加入一个数,2,删除一个数,3,询问经过排序以后，所有下标mod5mod5mod5余3的数的和思路： 注意到，当我们加入一个数以后，会让所有后面的数后移一位，删除会使得后面全部前移一位，每次移动都使得下标变化1，所以我...
2018-07-20 16:45:41
485
原创 bzoj 1103 大都市meg (dfs序+线段树)
题意： 一颗树，每条边权是1，两种操作，一种查询x到根的距离，一种把某边改为0思路： 对于一个边变了，那么影响的就是子树，所以dfs序+线段树就行了，这题对于时间要求很低，vector存边，每次暴力找答案也能A错误及反思：代码：...
2018-07-20 14:13:51
313
原创 Codeforces Round #104 (Div. 1) E. Lucky Queries (线段树)
题意： 长度为n的47串，两种操作，一种是区间变换，即4变7，7变4，一种是询问，问最长的非严格递增子序列长度思路： 线段树维护即可,47可以抽象成01串,变换就是异或，存储全0串最长长度，全1串最长长度，000..111串长度，111…0...
2018-07-20 13:41:01
423
原创 treap入门题目集合（附模板）
POJ 3481 HDU 5877 BZOJ 1208 BZOJ 3224 Tyvj 1728 BZOJ 1588 这些题目都很裸，套套模板就能A，所以就放一起了，treap=tree+heap，让数值维持二叉树性质，用随机值维护堆性质（用这个维护树的平衡）const int N = 100010;str...
2018-07-14 17:48:37
767
原创 NEERC 17 G The Great Wall (treap)
题意：&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp; 给你一个数列，每个点有abc三个值，现在让你画两个区间x，y，区间大小为r，区间不可以完全重合，当一个点没有被区间覆盖时值为a,被一个区间覆盖时值为b，两个区间为c，问第k小的数列数值总和为多少思路：&nbsp;&nbsp;&nbsp;&nbsp; &
2018-07-13 11:19:27
546
原创 NEERC 17 I Interactive Sort (交互题)
题意： 给出1到n这n个数的任意一个排列，然后奇数按顺序分到o数组，偶数按顺序分到e数组，你每次可以询问e数组中第i个和o数组中第j个的大小情况，查询结束后输出结果，查询次数最多30 000次，n≥1000n≥1000n\ge1000思路： 我...
2018-07-12 14:04:30
545
原创 NEERC 17 L Laminar Family (树链剖分)
题意： 给你一颗树，每次选取一个路径，把路径上的所有点加入到一个集合里面，问最后的集合是否两两之间满足 A∈BA∈B A\in B 或者B∈AB∈AB\in A或者A∪B=∅A∪B=∅A\cup B = \emptyset思路： 我们发现，如果最后是符合条件的，那么必定是一个集合被另一个集合...
2018-07-12 08:19:11
393
原创 SPOJ FTOUR2 Free tour II (点分治+启发式合并)
题意：树上n个点，点有黑有白，一条路径上黑点个数不超过k个的最大权值是多少思路： 从点分治上想，我们每次统计通过某个点的，符合条件的路径最大权值，然后不停更新答案。当我们遍历完某个子树，就把这个子树的信息和之前子树合并，然后不停更新即可。很明显，我们要维护当经过黑点为x个时的最大权值。 假...
2018-06-17 13:49:20
496
原创 Codecraft-18 and Codeforces Round #458 E. Palindromes in a Tree（点分治）
题意：&nbsp;&nbsp;&nbsp;&nbsp; 一棵树，每个点都有一个字母，如果一条路径的字符的某个排列是回文串，就称这个路径是回文的，问经过每个点的回文路径有多少条思路：&nbsp;&nbsp;&nbsp;&nbsp; 很明显的点分治。首先因为字母是a到t，所以可以状压一下，利用异或来改变路径的状态，如果二进制中1的个数小于等于1，那么就是回文的（利用__bu
2018-06-14 13:02:30
210
原创 spoj PT07J Query on a tree III (主席树+dfs序)
题意：一棵树，每次查询某个子树的第k大思路： 询问子树的问题，因为子树的dfs序是连续的一个区间，所以我们将这棵树dfs地建立主席树，查询子树就是查询子树对应的区间，这样就把树变成数列了错误及反思： 其实很简单，但是spoj卡常啊，在优化了常数，vector变成链式前向星，用了快读，...
2018-06-12 20:40:05
189
原创 hdu 4866/bzoj 3932 Shooting/任务查询系统(主席树)
题意：&nbsp;&nbsp;&nbsp;&nbsp; 有n条平行于x轴的线段，m次射击，每次射击射中前k个线段，得到的分数为∑ki=1di∑i=1kdi\sum_{i=1}^k{d_i}其中didid_i为线段到x轴距离，k为(a∗pre+b)modc(a∗pre+b)modc(a*pre+b)\mod c，pre为上次得分，并且如果pre大于p，那么本次得分翻倍思路：&nbsp;&...
2018-06-12 17:03:06
147
原创 CodeChef CLONEME Cloning (主席树+HASH)
题意： 一个数列，q次查询，每次给你l1,r1,l2,r2l1,r1,l2,r2l_1,r_1,l_2,r_2，问你将l1到r1,l2到r2l1到r1,l2到r2l_1到r_1,l_2到r_2这两个区间的数排序后，如果一个位置不同或者全部相同则称为相似，对于每次询问，回到是否相似思路： 排序后比...
2018-06-12 14:12:10
273
原创 hdu 5111 Alexandra and Two Trees (主席树+树剖)
题意：给你两颗树，q次查询，每次查询，问你第一颗树u1到v1，第二棵树u2到v2上，出现的数字交集大小，每颗树上不会有重复数字思路： 我们首先先想这样一个问题，给你两个数列a1,a2,a3...ana1,a2,a3...ana_1,a_2,a_3...a_n和b1,b2,b3,...bmb1,b2,b3,...bmb_1,b_2,b_...
2018-06-11 16:13:48
236
原创 hdu 5919 Sequence II (主席树)
题意：思路： 乍一看以为是神题，想了半天都没想到怎么写，一看题解发现读错了。。。 和D-query这题一样，只不过因为要求最前面的数，所以需要从后向前添加。首先维护的不是权值线段树，1-n维护a[1]-a[n]出现过几次，如果之前某个数出现过，那么我们直接在前一棵树的基础上减去之前的位置...
2018-06-06 14:57:16
212
原创 hdu 3727 Jewel （主席树）
题意：思路： 主席树模板题，其实权值线段树也行，练练板子熟练度了 每次Insert就是新开一颗树，区间第k大和总体第k大就是正常的静态主席树操作，查询排名要注意，是包含那个数的错误及反思：代码：#include<cstdio>#include<algori...
2018-06-05 16:11:47
251
原创 zoj 2112 Dynamic Rankings (主席树+树状数组)
题意：思路： 动态区间第k大，我用的是主席树+树状数组，这个不是最优解，因为空间很吃紧，正解应该是整体二分，CDQ分治什么的，然而现在不会，会了补上写法 那么我们来说一下怎么用主席树过，首先我们发现，假如我们改变了x，那么对应就影响了x,x+1,x+2,…..n这几颗树，暴力地每个开一个时间...
2018-06-05 14:29:27
180
原创 hdu 4348 To the moon （带标记主席树）
题意：思路： 每次修改，就新开一个树，如果大小是l到r包含叶子节点的一颗树自然是不可以的，那么我们只能保存包含他们的上面的节点，并且lazy也要同步更新（这一步和线段树很类似），但是，我们并不能pushdown，因为pushdown会直接导致空间炸掉。 那么我们为了能够用到lazy，那么我们...
2018-06-03 21:00:13
173
原创 spoj cot Count on a tree (主席树)
题意：思路： 我们根据dfs顺序建立主席树。求树上第k大，对于u到v的一条路径，我们用u的树+v的树，很明显lca(u,v)多算了一次，fa[lca(u,v)]多算了两次，所以用u的树+v的树-lca(u,v)的树-fa[lca(u,v)]的树即可错误及反思：代码：#include<bits/stdc++.h>...
2018-06-03 13:25:19
184
原创 spoj Qtree6/bzoj 3637 Query on a tree VI(树链剖分+线段树/LCT)
题意：思路：首先，我们要开两颗线段树，一颗表示，当前节点为白时，和子树所组成的最大联通块大小是多少，另一颗表示，当前节点为黑时，和子树所组成的最大联通块大小是多少。 那么我们查询点u的答案的时候，就向上找到最远的相同颜色的点v，点v所保存的答案就是u的答案（我们v为最远同色祖先）。 更新某个点u的颜色的时候，就是把u的父亲和最远同色祖先的父亲，这一条路径上的都更新（注意，黑白各更新...
2018-06-03 00:29:26
255
原创 bzoj 3052/洛谷 P4074/uoj 58 [WC2013]糖果公园（树上带修莫队）
题意：UOJ地址 &nbsp;&nbsp;&nbsp;&nbsp; 洛谷地址 BZOJ因为版权挂了。。。思路：&nbsp;&nbsp;&nbsp;&nbsp; 比较裸的一道树上带修莫队，我们只要维护一下某个糖出现了几次，然后更新答案即可错误及反思：&nbsp;&nbsp;&nbsp;&n
2018-05-29 14:10:32
310
原创 bzoj 4129 Haruna’s Breakfast（树上带修莫队）
题意：思路：树上带修莫队+块状数组，基本上还是很裸的 但是写起来很麻烦，看到好多人硬是压到90多行，真是跪了 总体思路就是，树上询问和修改还是莫队，但是在查询的时候，肯定不能O(n)地去询问，而线段树因为莫队每次移动区间都需要修改，会让总体复杂度多出一个logn，所以在查答案的时候用块状数组维护，这样由块状数组产生的复杂度是O(nn−−√)O(nn)O(n\sqrt{n}),不会使...
2018-05-29 08:38:29
207
原创 SPOJ COT2 Count on a tree II (树上莫队)
题意：思路： 树上分块方法<-由这个题，我们可以得出一种分块方法，他能保证每个块中内部移动次数，同时也能保证块的大小 这个是讲述怎么转移的因为转移的时候，lca非常麻烦，要各种分类讨论，这个博客告诉我们，只要不管lca进行转移，最后计算结果的时候临时加上lca即可错误及反思：...
2018-05-26 11:58:20
252
原创 bzoj 1086 王室联邦 (dfs，构造)
题意：思路：&nbsp;&nbsp;&nbsp;&nbsp; 首先我们dfs，如果一个节点v的儿子u所在的子树大于等于B，那么就把这个子树当作一个省份，对于这种情况，省会是u,v其实都可以。如果一个儿子u所在的子树小于B，可以先暂存起来，继续遍历其他儿子，当暂存的数量大于等于B的时候，将暂存的都归为一个省，省会为v，因为会暂存的子树大小为B-1,所以这样产生的子树大小最大为2B-2，在...
2018-05-26 10:12:19
226
原创 Codeforces Round #466 (Div. 2) F. Machine Learning (带修莫队)
题意： 一个数组，问某个区间里面，第一个没出现的所有数出现次数的出现次数正整数思路： 题意有点毒，第二次才读对。一读题就觉得，带修莫队就可以处理了，然后我们发现需要离散化，那么我们干脆在之前就把数字离散了，因为有修改，所以最多为2e5个数，这样就很好处理了。因为是出现次数的出现次数，所以最多...
2018-05-24 20:13:09
159
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人