bzoj 1058: [ZJOI2007]报表统计【set】
我想写FHQtreap的！是set自己跑进代码的！因为太好写了是有点慢……洛谷上不吸氧会T一个点就是，用一个set p维护所有点值，ans维护MIN_SORT_GAP的答案，每次insert一个点的时候都查一下它在p里的前驱后继，更新一下ans即可；用一个multiset c维护差分后的序列，a[i...
[BZOJ 1058] [ZJOI2007] 报表统计 【平衡树】
题目链接：BZOJ - 1058题目分析这道题看似是需要在序列中插入一些数字，但其实询问的内容只与相邻的元素有关。那么我们只要对每个位置维护两个数 Ai, Bi， Ai 就是初始序列中 i 这个位置的数， Bi 是在 i 这个位置insert的最后一个数。那么在 i insert一个数 Num 的时...
bzoj 1058: [ZJOI2007]报表统计 (Treap）
链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1058题面;1058: [ZJOI2007]报表统计Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 4740 Solved: 1568[Subm...
bzoj 1058 [ZJOI2007]报表统计（set）
【题目链接】http://www.lydsy.com/JudgeOnline/problem.php?id=1058【题意】一个序列，提供插入，查询相邻最小差值，查询任意最小差值的操作。【思路】Set用两个set，listed装所有的相邻差值，sorted装所有的数。然后用front[x],last...
【bzoj3110】[Zjoi2013]K大数查询
Description有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。Input第一行N，M接下来M行，每行形如1 a b c或2 a b cOutpu...
树链剖分+线段树 BZOJ 1036 [ZJOI2008]树的统计Count
题目链接题意： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值III. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意：从点u到点v的路径上的节点包括u和v本身分析：树链剖分第一题，把树拆成一条条链，有重链...
[BZOJ]1093 最大半连通子图(ZJOI2007)
挺有意思的一道图论。Description一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：∀u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'⊆V，E'是E中所有跟V'有关的边，则称...
洛谷P5211 [ZJOI2017]字符串（线段树+乱搞）
题面传送门题解为什么大佬们全都是乱搞的……莫非这就是传说中的暴力能进队，乱搞能AC……似乎有位大佬能有纯暴力+玄学优化\(AC\)（不算上\(uoj\)的\(Hack\)数据的话……这要是放到考场上就是切题的啊……）整体思路呢，就是我们开一个线段树，线段树上的每一个区间维护“以这个区间右端点为结尾有...
ZJOI2018 D1T2 历史（毕竟我菜，所以题解十分易懂。。）
我定睛一看，上一篇博客居然是去年省选写的。。。emmm我果然很懒。。又是一年省选季，临死前订正一下去年的题吧。。作为第一天30pts的滚粗选手，我去年并没有怎么思考这题。。题意概括好麻烦，来来来我们放题目链接。。为了方便叙述，我们用Ti表示 ∑(i在lca的子树中)ai 。从无修改的情况的入手。我们...
BZOJ1057：[ZJOI2007]棋盘制作——题解
http://www.lydsy.com/JudgeOnline/problem.php?id=1057https://www.luogu.org/problemnew/show/P1169国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，...
1003. [ZJOI2006]物流运输【区间DP+最短路】
Description物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够...
Luogu3350 ZJOI2016 旅行者 最短路、分治
传送门题意：给出一个$N \times M$的网格图，边有边权，$Q$组询问，每组询问$(x_1,y_1)$到$(x_2,y_2)$的最短路。$N \times M \leq 2 \times 10^4 , Q \leq 10^5$BZOJ原题竟然没有数据范围矩形的多组询问问题考虑分治。考虑计算矩形...
洛谷 P2272 [ZJOI2007]最大半连通子图 解题报告
P2272 [ZJOI2007]最大半连通子图题目描述一个有向图\(G=(V,E)\)称为半连通的\((Semi-Connected)\)，如果满足：\(\forall u,v \in V\)，满足\(u \to v\)或\(v \to u\)，即对于图中任意两点\(u\)，\(v,\)存在一条\(...
BZOJ1433或洛谷2055 [ZJOI2009]假期的宿舍
BZOJ原题链接洛谷原题链接对于每个需要床位的人向他能睡的床连边，然后就是二分图最大匹配模板了。这里用匈牙利算法。#include<cstdio>#include<cstring>using namespace std;const int N = 55;const int M...
wikioi 1514 and ZJOI2006 书架
1514 书架0人推荐 收藏 发题解提交代码报错题目描述输入描述输出描述样例输入样例输出提示题目描述 Description小 T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用 1 到 n 的正整数给每本书都编了号。 小 T 在看书的时候，每次取出一本书，看...
[ZJOI 2006]超级麻将
DescriptionInput第一行一个整数N（N<=100），表示玩了N次超级麻将。 接下来N行，每行100个数a1..a100，描述每次玩牌手中各种牌的数量。ai表示数字为i的牌有ai张。（0<=ai<=100）Output输出N行，若胡了则输出Yes，否则输出No，注意区分...
BZOJ 3111: [Zjoi2013]蚂蚁寻路
SolDP.首先观察转折,画画图,看看移动路线,可以非常轻易的发现如果走到起点的下方是回不去的..然后它就相当于一个底部是平的,顶部凹凹凸凸的形状,每右转两次或左转两次就会形成小矩阵,这样就可以来DP了.首先一个非常简单的思路,就是f[k][i][j]表示取到第j列高度为h最大权值,枚举上一个转折点...
题解 P2598 【[ZJOI2009]狼和羊的故事】
P2598 [ZJOI2009]狼和羊的故事题目描述“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆...
luogu P2596 [ZJOI2006]书架
传送门感觉要死在\(Splay\)里了 orz这题用\(Splay\)维护这个序列,其中的第\(k\)大点代表这个序列的第\(k\)个数第一个操作,先把那个数所在的点旋到根,然后把整个根的左子树接到右子树中最小的点,记得\(splay\)维护整棵树第二个操作类似,把第一个操作反过来就行第三个本质是两...
bzoj 3926: [Zjoi2015]诸神眷顾的幻想乡【SAM】
有一个显然的性质就是每个串一定在某个叶子为根的树中是一条直的链 然后因为SAM里是不会有相同状态的，所以以每个叶子为根dfs一遍，并且动态构造SAM（这里的节点u的last指向父亲），最后统计答案就是dis[i]-dis[fa[i]]的和 我看别的题解都说和trie有关……然而并没用用到（也可能是用...