【BZOJ】1601: [Usaco2008 Oct]灌水（kruskal）
http://www.lydsy.com/JudgeOnline/problem.php?id=1601很水的题，但是一开始我看成最短路了T_T果断错。我们想，要求连通，对，连通！连通的价值最小！当然是生成树！最小生成树！边的还好做，但是这题有点，怎么办呢？因为点在图中也起到连通作用，我们加个附加源...
[BZOJ2456] mode（一道很有意思的题）
传送门看到这个题的第一反应是离散化+线段树乱搞。。eeeeeeeeeeee感觉数据结构学傻了，其实直接存下来，sort一遍，n/2的位置的就是答案当然前提是空间够的话1m的空间连数组都开不下于是有了一个很巧妙的思路，吼吧，直接给链接http://blog.csdn.net/suncongbo/art...
bzoj 2038 [2009国家集训队]小Z的袜子(hose)（莫队算法）
【题目链接】http://www.lydsy.com/JudgeOnline/problem.php?id=2038【题意】给定一个有颜色的序列，回答若干个询问:区间内任选两个颜色相同的概率。【思路】设一个颜色在区间内的出现次数为cnt，则抽到这种颜色的概率为：(cnt-1)*cnt/2=1+2+…...
BZOJ 3689 异或 Trie木+堆
标题效果：特定n的数量，这种需求n数22XOR的值前者k少首先，我们建立了一个二进制的所有数字Trie木，您可以使用Trie木size域检查出一些其他的数字XOR值首先k少然后，我们要保持一个堆。其他XOR的整数值首先2增加堆(第一小是自己异或自己。不在题目要求范围内)。当取出一个数异或值的第k小后...
【BZOJ 2440】[中山市选2011]完全平方数
Description小X自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。 这天是小X的生日，小W想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后...
BZOJ.2437.[NOI2011]兔兔与蛋蛋游戏(二分图博弈 匈牙利)
题目链接首先空格的移动等价于棋子在黑白格交替移动（设起点移向白格就是黑色），且不会走到到起点距离为奇数的黑格、到起点距离为偶数的白格（删掉就行了），且不会重复走一个格子。（然后策略就同上题了，只不过第一步是走棋子）还是考虑二分图最大匹配。如果起点不一定在最大匹配上，先手走到最大匹配点，后手沿最大匹配...
【BZOJ 3196】二逼平衡树 线段树套splay 模板题
我写的是线段树套splay，网上很多人写的都是套treap，然而本蒟蒻并不会treap奉上sth神犇的模板：//bzoj3196二逼平衡树，支持修改某个点的值，查询区间第k小值，查询区间某个值排名，查询区间某个值值前驱、后继。查询第k小值是log^3(n)的，其他都是log^2(n)的#includ...
bzoj 1912 : [Apio2010]patrol 巡逻 树的直径
题目链接如果k==1，显然就是直径。k==2的时候，把直径的边权变为-1，然后在求一次直径。变为-1是因为如果在走一次这条边，答案会增加1.学到了新的求直径的方法...#include<bits/stdc++.h>usingnamespacestd;#definepb(x)push_ba...
BZOJ 2286 消耗战 (虚树+树形DP)
给出一个n节点的无向树，每条边都有一个边权，给出m个询问，每个询问询问ki个点，问切掉一些边后使得这些顶点无法与顶点1连接。最少的边权和是多少。(n<=250000,sigma(ki)<=500000)考虑树形DP，我们令mn[i]表示i节点无法与1节点相连切除的最小权值。显然有mn[i...
BZOJ 3546 Life of the Party （二分图匹配-最大流）
题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3546题意：给定一个二分图。（AB两个集合的点为n，m），边有K个。问去掉哪些点后最大匹配会减少。思路：首先建图跑最大流。然后从s开始dfs一次，若能跑到B集合中的点x，那么说明x可以...
bzoj2938
显然AC自动机，但什么叫无限生成呢？显然就是在AC自动机上匹配，出现了一个环（不能走结尾节点）直接搜索即可vartrie:array[..,''..'']oflongint;q,f:array[..]oflongint;can,v,r:array[..]ofboolean;l,n,i,t,j,k:l...
【权值线段树】bzoj3224 Tyvj 1728 普通平衡树
一个板子。#include<cstdio>#include<algorithm>usingnamespacestd;#defineN100001structData{intv,p;}t[N];boolcmp(constData&a,constData&b){r...
BZOJ3224 Tyvj 1728 普通平衡树（Treap）
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！题目链接：BZOJ3224正解：$Treap$解题报告：$Tr...
【bzoj3224】 Tyvj1728—普通平衡树
http://www.lydsy.com/JudgeOnline/problem.php?id=3224 (题目链接)题意1.插入x数；2.删除x数(若有多个相同的数，因只删除一个)；3.查询x数的排名(若有多个相同的数，因输出最小的排名)；4.查询排名为x的数；5.求x的前驱(前驱定义为小于x，且...
[BZOJ3224]普通平衡树(旋转treap,STL-vector)
3224:Tyvj1728普通平衡树TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 20328 Solved: 8979[Submit][Status][Discuss]Description您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供...
BZOJ 3676 【APIO2014】 回文串
题目链接：回文串我终于也会回文自动机辣！其实吗……我觉得回文自动机(听说这玩意儿叫\(PAM\))还是比较\(simple\)的……至少比\(SAM\)友善多了……所谓回文自动机，每个节点就代表一个回文串。回文自动机的每个节点有两个东西，一个是\(next\)，，一个是\(fail\)。\(next...
bzoj 5286: [Hnoi2018]转盘
DescriptionSolution首先注意到一个点不会走两次,只会有停下来等待的情况,把序列倍长那么如果枚举一个起点\(i\),答案就是\(min(max(T[j]+n-(j-i)-1)),j∈[i,2*n]\)相当于从\(i\)出发,先走到\(j\)停下来,然后再走完剩下的,如果不合法则不会更...
[BZOJ3224]Tyvj 1728 普通平衡树
[BZOJ3224]Tyvj1728普通平衡树试题描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1.插入x数2.删除x数(若有多个相同的数，因只删除一个)3.查询x数的排名(若有多个相同的数，因输出最小的排名)4.查询排名为x的数5.求x的前驱(前驱定义为小于x，且...
BZOJ 1060 时态同步
贪心。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxv500500#definemaxe1000500usingnamespacestd;...
【BZOJ-1055】玩具取名 区间DP
1055:[HAOI2008]玩具取名TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 1560 Solved: 907[Submit][Status][Discuss]Description某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意...