bzoj专题
最小生成树计数 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 =
BZOJ 1025 游戏 DP+lcm+素数筛选
排数=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轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩
BZOJ 1601 [Usaco2008 Oct]灌水 题解与分析
1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec Memory Limit: 162 MB Description Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=10
![BZOJ 1821 [JSOI2010]Group 部落划分 Group 题解与分析](http://www.lydsy.com/JudgeOnline/images/1821.jpg)
BZOJ 1821 [JSOI2010]Group 部落划分 Group 题解与分析
1821: [JSOI2010]Group 部落划分 Group Time Limit: 10 Sec Memory Limit:64 MB Submit: 825 Solved: 386 Description 聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则
![BZOJ 1787 [Ahoi2008]Meet紧急集合 题解与分析](https://img-blog.csdn.net/20130819212535625?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY3N5emN5ag==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
BZOJ 1787 [Ahoi2008]Meet紧急集合 题解与分析
[Ahoi2008]Meet 紧急集合 Time Limit: 20 Sec Memory Limit: 162 MB Description Input Output Sample Input 6 4 1 2 2 3 2 4 4 5 5 6 4 5 6 6 3 1 2 4 4 6 6 6 Sa
BZOJ 4712 洪水
Description 小A走到一个山脚下，准备给自己造一个小屋。这时候，小A的朋友（op，又叫管理员）打开了创造模式，然后飞到山顶放了格水。于是小A面前出现了一个瀑布。作为平民的小A只好老实巴交地爬山堵水。那么问题来了：我们把这个瀑布看成是一个n个节点的树，每个节点有权值（爬上去的代价）。小A要选择一些节点，以其权值和作为代价将这些点删除（堵上），使得根节点与所有叶子结点不连通。问最小代价。不
BZOJ 1833 [ZJOI2010]count 数字计数(数位dp)
题目链接：[kuangbin带你飞]专题十五 数位DP D - Bomb 题意 输入n,m，求n～m范围内的所有数字中，分别输出0～9出现的总数是多少。 思路 和 POJ 3286 How many 0’s? (数位dp)的思路基本是一样的，只是略有区别。 0和1～9要分开处理，是因为前缀0的问题。因为当某一位取0时，前面部分的数是不能为0的，而取1～9是可以前面为0的。
BZOJ 3224 Tyvj 1728 普通平衡树(权值线段树)
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3224 题目大意：您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，
BZOJ 1041 [HAOI2008] 圆上的整点（数论）
Description 求一个给定的圆(x2+y2=r^2)，在圆周上有多少个点的坐标是整数。 Input 只有一个正整数n,n<=2000 000 000 Output 整点个数 Sample Input 4 Sample Output 4 Hint 科普视频 Source 太神了，竟然和素数扯上关系。 https://blog.csdn.net/csyzcyj/article/det
BZOJ 4033. [HAOI2015]树上染色（树形DP，边贡献）
Description 有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并 将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。 Input 第一行两个整数N,K。 接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。 输入保
![【BZOJ - 3832】[Poi2014] Rally](https://img-blog.csdnimg.cn/20181031111714395.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1Rpd19BaXJfT3AxNzIx,size_16,color_FFFFFF,t_70)
【BZOJ - 3832】[Poi2014] Rally
[Poi2014] Rally @Description@@Solution - Part 1@@Solution - Part 2@@Some Details@@Code@@End@ @Description@ 给定一个N个点M条边的有向无环图，每条边长度都是1。 请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。 Input 第一行包含两个正整数 N , M (
![bzoj 1031 [JSOI2007]字符加密Cipher(后缀数组)](https://www.lydsy.com/JudgeOnline/images/1031/1.jpg)
bzoj 1031 [JSOI2007]字符加密Cipher(后缀数组)
1031: [JSOI2007]字符加密Cipher Time Limit: 10 Sec Memory Limit: 162 MB Submit: 8411 Solved: 3742 [Submit][Status][Discuss] Description 喜欢钻研问题的JS同学，最近又迷上了对加密方法的思考。一天，他突然想出了一种他认为是终极的加密办法 ：把需要加密的信息排成
bzoj 2038: [2009国家集训队]小Z的袜子(莫队算法)
2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Submit: 15386 Solved: 6996 [Submit][Status][Discuss] Description 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜
求补图的联通块数（bzoj 1098+codefoces920E）
思路：链表加BFS的强优化，具体是这样的：我们先把所有的节点挂链，然后再把链表上的一个节点入队，遍历其在原图上相邻的点并做上标记，那么这时没有打上标记的点在补图上和当前节点一定有边相连因而一定在同一个联通块中，所以再把这些没有打上标记的点入队，并且在链表中除去，继续这个过程，直到队列为空时这个联通块就找出来了，再取链表上还存在的点入队寻找一个新的联通块，直到删掉所有点为止，复杂度降为了O(n +
bzoj 4178: A
传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=4178 比较裸的NTT NTT讲的比较好的博客 http://blog.csdn.net/acdreamers/article/details/39026505 #include<cmath>#include<cstdio>#include<cstring>#inclu
bzoj 1690: [Usaco2007 Dec]奶牛的旅行
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1690 思路：0-1分数规划 其实0-1分数规划重要的是它的思想，就像最小乘积XXX（生成树，匹配等）一样，知道了思想，再套一个对应的的算法即可 一个不错的博客：http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html
BZOJ 1477 青蛙的约会 扩展欧几里得
Description 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的
BZOJ 1260 [CQOI2007]涂色paint 记忆化搜索/dp
Description 假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。 Input 输入