bzoj专题

【BZOJ】1324 Exca王者之剑最大权独立集

传送门：【BZOJ】1324 Exca王者之剑题目分析：赤裸裸的最大权独立集。。。最小割解决代码如下： #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP( i , a , b ) for ( int

【BZOJ】1026: [SCOI2009]windy数数位DP

传送门：【BZOJ】1026: [SCOI2009]windy数题目分析：数位DP水题。代码如下： #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,

【BZOJ】2152: 聪聪可可点分治

传送门：【BZOJ】2152: 聪聪可可题目分析：记录权值和%3的路径的个数。。。然后去重。。没了。。代码如下： #include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std ;typedef lo

BZOJ 2440 2301 莫比乌斯应用

http://www.lydsy.com/JudgeOnline/problem.php?id=2440 Description 小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌

BZOJ 3732: Network（最小生成树+倍增）

题目链接题意：给出一个图，每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少很明显最终查询的边一定是在最小生成树里面的，先跑出最小生成树，然后，可以树链剖分，也可以使用倍增来计算 #include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define

BZOJ 2038 小Z的袜子(hose) （莫队离线）

题目地址：BZOJ 2038 裸的莫队算法。代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>#in

BZOJ 2152 聪聪可可 (树上点分治)

题目地址：BZOJ 2152 找有多少对权值和为3的倍数的点。最简单的点分治。代码如下： #include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#incl

BZOJ 3530 数数【AC自动机+数位dp】

[Sdoi2014]数数简单数位dp+简单AC自动机反正数位DP是队友写的 AC自动机要记录两个值，一个是是否为一个串的结束，即不合法状态，一个是前缀零的情况。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostr

BZOJ 3531 旅行【树链剖分】

[Sdoi2014] 简单的树链剖分以每个信仰应该建一个线段树，空间复杂度为 O(5×1010) O(5\times 10^{10}) 因此会爆空间，所以需要动态申请空间。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <

BZOJ 3262（树套树）

【bzoj3262】陌上花开 Description 有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。 Input 第一行为N,K (1

BZOJ 1208 （可持久化Treap,合并与分裂操作）

1208: [HNOI2004]宠物收养所 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 4965 Solved: 1902 [ Submit][ Status][ Discuss] Description 最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领

BZOJ 2152 (树形DP)

2152: 聪聪可可 Time Limit: 3 Sec Memory Limit: 259 MB Submit: 798 Solved: 419 [ Submit][ Status][ Discuss] Description 聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到

BZOJ 2049 动态树-模板题

BZOJ 2049:[Sdoi2008]Cave 洞穴勘测辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 。如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 。经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变

BZOJ 2435（BFS+输入输出外挂）

2435: [Noi2011]道路修建 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 2299 Solved: 682 [ Submit][ Status][ Discuss] Description 在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家

bzoj 1199 二分暴力

这道题的数据范围是25W... 直接暴力。。。将所有点按照x排序之后。遍历所有的矩形和圆，用upper_bound和lower_bound寻找出符合图形x坐标的所有点，（位于区间[s,t]）,然后暴力枚举刚才寻找的点判断是否在当前形状内。。好黄好暴力。upper_bound和lower_bound的新用法~~ #include <algorithm>#include <algor

bzoj 2502 有上下限的最小流

觉得有可能是网络流~~但是题目一直说是最小次数~~~一直卡在最大流这个思维，都快忘记有最小流这个东西了~~~~ 建图方式：每条边设下限为1，上限为无穷大 s连接到每一个点，下限为0，上限无穷大 t连接到每一个点，下限为0，上限无穷大这样跑一个有上下限的最小流，就可以得出答案了~~~所有边都被遍历了~~~ #

最小生成树计数 bzoj 1016 hdu 4408

最小生成树计数比生成树计数多了边的权值 bzoj 1016 http://www.lydsy.com/JudgeOnline/problem.php?id=1016 #include <map>#include <stack>#include <queue>#include <math.h>#include <vector>#include <string>#inclu

BZOJ 1208 宠物收养所 Splay树

Splay的简单应用，找和一个数最接近的数，例如找和x最接近的数，把x旋转到根，要么是左子树的最大值，要么是右子树的最小值。 #include <cstdio>#include <cstring>#include <algorithm>#include <cstdlib>using namespace std;typedef long long LL;const int mod =

排数=lcm{Ai,Ai表示循环节长度},sum(Ai)=n根据lcm的定义，分解质因数拆掉Ai=p1^x1*p2^x2*...*pk^xklcm=∏(pi^max{xi})所以我们只看max{xi}即可，即忽略掉≤max{xi}的其它因子。所以问题等价于：sum(pi^xi)≤n的方案数。然后随便dp即可设d(i,j) 表示前i个质数和为j的方案，有d(i,j)=d(i−1,j)+sum(d(i

BZOJ 1009 GT考试 DP+矩阵快速幂

dp[i][j]表示长度为i，匹配了j个的方案数，压缩成矩阵，转移即可。 #include <cstdio>#include <cstring>using namespace std;struct Mat{int a[22][22];};Mat I, A;int n, m, mod;char s[22], ss[22];Mat mul(Mat& x, Mat& y){Ma

BZOJ 1006 神奇的国度弦图最小染色 MCS算法

给定一个弦图，求最小染色参考cdq的弦图与区间图论文 http://wenku.baidu.com/view/07f4be196c175f0e7cd13784.html http://tieba.baidu.com/p/2891159900 http://www.cnblogs.com/zhj5chengfeng/p/3279649.html

BZOJ 1056 排名系统 Splay

实现一颗名次树，提供如下操作上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。 splay的基本的插入删除操作，在加一个hash映射名字和得分，不过可能值会相同。可以给每个节点增加一个表示时间的域，如果值一样，就以时间为第二关键字继续在子树中递归查找。

BZOJ 1211 树的计数 Prufer序列

一个节点在prufer数列中出现的次数是这个节点的度数减一。这样我们就知道这个数列中有哪些数了，因为一个prufer数列唯一对应一颗树。然后问题就变成了求有多少种prufer数列。又因为我们知道了元素种类与出现次数。于是问题就变成了求一个有重复元素的全排列。因为n最大有150.所以分解一下质因数就好了。

BZOJ 1189 紧急疏散evacuate 二分+BFS+最大流

建图的时候需要拆点，按照每一个时间点拆点，主要可以保证每次只有一个人走出门。BFS处理出人到门的距离二分答案，判断是否可以建边，S指向每一块空地，空地到门如果可以建边就建一条容量为x的边每个门按照时间拆点，保证单位时间内走一次，然后跑最大流

BZOJ 2818: Gcd 欧拉函数

继续复制QSC https://www.cnblogs.com/qscqesze/p/5403692.html BZOJ 2818: Gcd 筛法 2818: Gcd 题目连接： http://www.lydsy.com/JudgeOnline/problem.php?id=2818 Description 给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有

BZOJ 1293 [SCOI2009] 生日礼物题解与分析

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec Memory Limit:162 MB Submit: 630 Solved: 326 Description 小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩