- 博客(111)
- 收藏
- 关注
RSS订阅原创 Luogu P2333 [SCOI2006]一孔之见 计算几何
#include <cstdio>#include <cmath>#include <algorithm>#define eps 1e-5#define INF 1e20using namespace std;const double pi=acos(-1.0);inline double sq(double x) { return x*x; }struct Point {
2017-07-13 19:21:30
755
原创 BZOJ 2330 [SCOI2011]糖果 差分约束系统
#include <cstdio>#include <cstring>#include <queue>#define N 100005using namespace std;struct Edge { int from,to,nxt,val; Edge() {} Edge(int _from,int _to,int _nxt,int _val): f
2017-07-10 14:45:37
469
1
原创 BZOJ 3295 动态逆序对 CDQ分治
#include <cstdio>#include <algorithm>#define N 100005#define INF (1<<30)using namespace std;typedef long long LL;inline int lowbit(int x) { return x & -x; }struct Data { int x,y,t; bool
2017-07-04 19:22:18
441
原创 BZOJ 2725 [Violet 6]故乡的梦 最短路
include include include include define N 200005define INF (1llusing namespace std; typedef long long LL; namespace Segment_Tree { struct Node { Node* ch[2];
2017-07-03 07:29:58
591
原创 BZOJ 3218 a + b Problem 网络流 可持久化线段树优化建图
#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#define N 200005#define INF 1000000000using namespace std;int n;namespace NetworkFlow { struct Edge { int to,n
2017-06-30 17:22:28
673
原创 BZOJ 3037 创世纪 树形DP
#include <cstdio>#include <cstring>#include <algorithm>#define N 1000005#define INF 1000000000using namespace std;struct Edge { int from,to,nxt; Edge() {} Edge(int _from,int _to,int _
2017-06-30 11:39:00
487
原创 BZOJ 4585 [Apio2016]烟火表演 可并堆
#include #include #include #define N 300005using namespace std;typedef long long LL;struct Node { Node *ch[2]; int dpt; LL val; Node() {} Node(LL); void* operator new(siz
2017-06-29 11:18:17
513
原创 BZOJ 3699 GAL的数组
题目大意：给出3*N的非负整数，分配到3个长度为N的数组A,B,C中。定义三个数组的GAL值，GAL(A,B,C)=Σ(A[i]-B[i])*C[i],1 ≤ i ≤ N。求出GAL(A,B,C)的最大值。
2017-06-29 11:16:15
337
原创 BZOJ 3685 普通van Emde Boas树 zkw线段树
#include <cstdio>#define N 4000005#define ls(x) (x<<1)#define rs(x) (x<<1|1)#define pa(x) (x>>1)using namespace std;namespace IStream { char get_char() { const int L=1<<15; st
2017-06-28 17:12:49
453
原创 BZOJ 4519 [Cqoi2016]不同的最小割 最小割树(分治最小割)
#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#define N 10005#define INF 1000000000using namespace std;int n,m,seq[N],w[N];namespace NetworkFlow { struct Edge {
2017-06-28 07:38:31
290
原创 BZOJ 1016 [JSOI2008]最小生成树计数 Kruskal Matrix-Tree定理
#include <cstdio>#include <algorithm>#define N 105#define MOD 31011using namespace std;struct Edge { int u,v,c; Edge() {} void scan() { scanf("%d%d%d",&u,&v,&c); } bool operator <
2017-06-25 15:54:05
369
原创 BZOJ 2095 [Poi2010]Bridges 二分 最大流(混合图欧拉回路)
题目大意：给出一张n个点m条边的联通图，无重边，每条边有正反两个权值。现要从点1出发经过每条边每个点一次，问最大边权最小是多少。
2017-06-22 15:41:06
354
原创 BZOJ 4720 [Noip2016]换教室 期望DP
题目大意：现有v个点和e条边。在n个时刻中，某个时刻i应该前往c[i]，可以申请前往d[i]，有p[i]的几率成功，每个时刻只能申请一次，最多申请m次。问如何分配申请使得期望经过的边权最小。 v<=300,n,m<=2000
2017-06-22 15:10:10
385
原创 BZOJ 4766 文艺计算姬 Prufer序列
题目大意：给定一个一边点数为n，另一边点数为m，共有n*m条边的带标号完全二分图K_{n,m}，计算其生成树个数。1 <= n,m,p <= 1e18
2017-06-22 12:48:10
541
原创 BZOJ 2428 [HAOI2006]均分数据 模拟退火
题目大意：已知N个正整数：A1、A2、……、An 。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。
2017-06-21 21:50:01
325
原创 BZOJ 3569 DZY Loves Chinese(BZOJ 3563) II 线性基
题目大意：给出一张n个点m条边的无向图。进行q次询问，问删掉某k条边后图是否联通。强制在线N≤100000 M≤500000 Q≤50000 1≤K≤15
2017-06-21 10:52:48
512
原创 BZOJ 3265 志愿者招募(BZOJ 1061)加强版 && BZOJ 3112 [Zjoi2013]防守战线 单纯形
题目大意：现要进行n天活动，第i天需要ai个志愿者。有m种志愿者，每种志愿者工作时间为若干个区间[li,ri]（BZOJ 1061：一个区间），招募一个费用为ci，求最小花费
2017-06-21 08:56:49
390
原创 BZOJ 2097 [Usaco2010 Dec]Exercise 奶牛健美操 二分
题目大意：给出一张n个点的无根树，边权均为1。现可以选择断m条边，获得 m+1棵树，问断边后所有树的直径的最大值最小是多少。
2017-06-19 14:19:07
424
原创 BZOJ 3073 [Pa2011]Journeys 最短路 线段树优化建图
题目大意：给出n个点，1~n编号，给出m个建边操作，以如下方式建边：(a,b),(c,d)表示，对于任意两个点x,y，如果a<=x<=b,c<=y<=d，那么在xy之间连边。给定源点求单源最短路n<=500000,m<=100000
2017-06-19 14:15:49
1127
原创 BZOJ 4276 [ONTAK2015]Bajtman i Okrągły Robin 费用流 线段树优化建图
题目大意：n(≤5000)个区间(l,r≤5000)，每个区间只能选其中的一个点得到vi的价值，每个点最多选1次，求最大价值
2017-06-19 08:11:35
446
原创 BZOJ 4080 [Wf2014]Sensor Network 随机化
题目大意：给定平面内的n(<=100)个点，选出一个点集S，使得S里的所有点两两之间欧几里得距离不超过d，问|S|的最大值以及S里的点都有哪些。若答案有多种，输出任意一个。
2017-06-17 14:58:11
576
原创 BZOJ 3064 Tyvj 1518 CPU监控 线段树维护历史最大值
题目大意：给出一个数列要求支持：查询区间最大值，查询区间历史最大值，区间加，区间修改
2017-06-16 09:31:30
697
原创 BZOJ 1877 [SDOI2009]晨跑 费用流
题目大意：给出一张n个点m条单向边的图，经过一条边可以获得一个边权c，每个点只能走一次(1、n除外)，每条边也只能走一次。现多次从1出发到达n，问最大化经过点数最小化权值和。
2017-06-05 20:30:40
378
2
原创 BZOJ 3669 [Noi2014]魔法森林 LCT
题目大意：给出一个n个点m条边的无向图，每条边上有两个权值ai,bi，要求选择一些边使1,n连通，问这些边中两个权值分别取最大后求和最小是多少
2017-05-30 11:20:59
419
原创 BZOJ 1085 [SCOI2005]骑士精神 A*搜索
题目大意：在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。（最多15步） 实在是太懒了不写简化题意了… 当时做的时候都没考虑到
2017-05-23 17:34:02
301
原创 BZOJ 1692 [Usaco2007 Dec]队列变换 后缀数组
题目大意：给出一个包含大写字母的长度为n的字符串，每次可以从字符串的首或尾取出一个字符放在新串的末尾，输出字典序最小的新串当首尾相同时，找第一个不同的位置谁小取谁，然而复杂度是O(n)的。可以将正反串中间用符号隔开连在一起，求出后缀数组，这样取rank较小的就可以了#include <cstdio>#define max(a,b) ((a)>(b)?(a):(b))#define N 60005
2017-04-17 18:45:13
348
原创 BZOJ 4399 魔法少女LJJ 线段树合并
题目大意：第一行有一个正整数m，表示操作个数。 接下来m行，每行先给出1个正整数c。 若c=1，之后一个正整数x，表示新建一个权值为x的节点，并且节点编号为n+1（当前有n个节点）。 若c=2，之后两个正整数a，b，表示在a，b之间连接一条边。 若c=3，之后两个正整数a，x，表示a联通块内原本权值小于x的节点全部变成x。 若c=4，之后两个正整数a，x，表示a联通块内原本权值大于x的节点
2017-04-14 14:43:25
444
原创 BZOJ 2989 数列 变换坐标系 主席树
题目大意：给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。 2种操作（k都是正整数）： 1.Modify x k：将第x个数的值修改为k。 2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任
2017-04-14 00:04:37
505
原创 BZOJ 2555 SubString LCT 后缀自动机
题目大意：给出一个初始字符串，要求支持，在末尾添加一段字符串，查询一个串出现了几次，强制在线。构造后缀自动机，一个串出现次数等于代表这个串的状态的right集合大小。然而强制在线，right集合在添加之后会发生改变。 考虑添加一个字母时，只有产生的新状态的所有parent的right集合大小会加1，于是用LCT维护一下就好了。#include <cstdio>#include <cstring>
2017-04-12 21:45:29
330
原创 BZOJ 4756 [Usaco2017 Jan]Promotion Counting 线段树合并
题目大意：给出一棵有根树，每个点有一个权值，问对于每一个点的子树中比这个点大的点的个数。首先权值很大需要离散化。 对于每一个点建一个权值线段树。遍历每一棵子树，然后将子树的线段树合并到自己的线段树上，在查询之后将自己插入。时间复杂度O(nlog2n)#include <cstdio>#include <cstring>#include <algorithm>#define N 100005
2017-04-12 16:13:35
850
原创 BZOJ 3622 已经没有什么好害怕的了 DP 容斥原理
题目大意：给出长度为n的a,b两个序列，元素互不相同。求有多少种匹配满足ai>bi比ai< bi多m对。将问题转化一下，即求有多少种匹配其中ai>bi恰好为(n+m)/2，其余均为ai< bi。 若设状态为f(i,j)表示a序列中前i个元素匹配完恰好有j对为ai>bi，发现根本没法转移。看到计数问题可以考虑容斥。需要将状态设置得便于转移，将状态改为f(i,j)表示a序列中前i个元素至少匹配了j对满
2017-04-11 19:52:03
392
原创 BZOJ 3238 [Ahoi2013]差异 后缀自动机
题目大意： len(Ti)+len(Tj)枚举一下就好，主要是如何算sigma{lcp(Ti,Tj)}将原串反过来建后缀自动机，两个节点的lca即最长子串就是这两个节点代表的串的lcp于是枚举、DP一下即可#include <cstdio>#include <algorithm>#include <cstring>#define N 500005using namespace std;t
2017-04-10 15:13:46
380
原创 BZOJ 1858 [Scoi2010]序列操作 线段树
题目大意：给出长度为n的0/1序列，要求支持：区间赋值(0/1)，区间取反，查询区间和、区间最长连续1个数。线段树练手题，今天闲来无事打算水一水，然后发现这个真的够屎..维护赋值标记、翻转标记，注意在赋值时清空翻转标记，判断好翻转与赋值的关系，细节见代码。 在赋值时记得把相反的清空（以为指针比数组快很多于是写到一半把数组改成指针，然而Rank前100都没挤进去…可能是因为我的线段树太屎了吧0.0#
2017-04-09 23:09:30
318
原创 BZOJ 3992 [SDOI2015]序列统计 NTT
题目大意： 给出一个集合S，元素都是小于m的整数。现给定整数x，求所有长度为n且每个元素都属于集合S的数列中满足数列中所有数的乘积mod m的值等于x的不同的数列的有多少乘积为定值不怎么会算，而和为定值就是一个卷积的形式，于是将数列转成其对数做加法。 数列中有n个数，快速幂即可。#include <cstdio>#include <cstring>#include <algorithm>
2017-04-07 23:14:22
455
原创 BZOJ 3779 重组病毒 LCT维护子树信息
题目大意：给定一棵树，要求支持：将某个点到根的路径染色；换根后将原来的根到现在的根的路径染色；求某个点的子树到根的平均颜色段数比较麻烦的LCT维护子树信息变量名是照neither_nor神犇抄的..意义相同，链接 因为要计算子树到根的平均颜色段数，所以要维护子树到(子树的)根的颜色段数和(Col)，Splay在原树中代表的链的颜色段数(cols)，子树size(rsiz)。 其实就是把子树到当前
2017-04-07 09:52:11
393
原创 BZOJ 4530 [Bjoi2014]大融合 LCT维护子树信息
题目大意：给出n个点，定义一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量，要求支持两个操作：加边，询问边的负载。保证加边不会出现环。暴力用LCT维护子树信息。LCT维护子树信息（子树信息LCT） LCT维护边权（边权LCT） 知识点讲解#include <cstdio>#include <algorithm>#define N 100005using namespace st
2017-04-06 17:17:59
863
1
原创 BZOJ 1457 棋盘游戏 SG函数
题目大意：有一个100 * 100的棋盘，从0开始编号。棋盘上有N个Queen。两个玩家轮流选择其中一个Queen，将它跳到(Xi – k, Yi)或(Xi, Yi - k)或(Xi – k, Yi - k), 其中k > 0。一个格子里面可能出现多个Queen。先将任意一个Queen移动到(0, 0)的人获胜。问先手必胜还是后手必胜?对于每个queen可以看成是两堆石子，SG函数搞一搞就好 需要
2017-04-05 09:41:34
463
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人