- 博客(472)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为()
首先说明一点,我们平时一般所说的哈夫曼树是指最优二叉树,也叫做严格二叉树（注意不是完全二叉树）,但是哈夫曼树完全不局限于二叉树,也存在于多叉树中,即度为m的哈夫曼树,也叫最优m叉树,严格m叉树（注意不是完全m叉树）.这题表示哈夫曼树的节点 的度要么是0要么是m设度不为0（即非叶结点）的个数为X则总的结点数为：X+n除根结点外，其余的每一个结点都有一个分支连向一个结点，对于度
2016-09-02 10:03:26
19297
13
原创 HDU 1512 Monkey King 左偏树
左偏树入门题#include #include #include #include #include #include using namespace std;const int N = 100005;struct node{ int l, r, dis, key;}tree[N];int n, m;int fa[N
2016-07-27 09:09:11
490
原创 URAL1004 Sightseeing Trip Floyd 最小环
const int maxn=110; int dist[maxn][maxn], map[maxn][maxn]; //最短距离，原图int pre[maxn][maxn]; // pre[i,j]记录最短路里，j前面一个点int path[maxn]; // 答案路径int n, m, num, minc; // num记录path里有多少个点，minc是最短环长度
2016-07-27 09:09:11
359
原创 URAL1076.Trash 二分图完美匹配
有n个垃圾桶，每个垃圾桶装有n种的垃圾，每个垃圾桶的每种垃圾都有重量，要求把所有垃圾桶中的同一种垃圾放到同一个垃圾桶的最小花费，其中从第i个桶搬到第j个桶的花费为垃圾的重量，i==j花费为0统计每种垃圾的总和，若将K种垃圾倒入第F个垃圾桶，那么花费就是K-F(k) （自己已经有的垃圾不用倒）。然后就是简单的二分图建图。
2016-07-27 09:09:11
371
原创 HDU 1402 A * B Problem Plus FFT
http://www.cnblogs.com/iwtwiioi/p/4123976.htmlhttp://blog.csdn.net/v_july_v/article/details/6684636http://blog.csdn.net/rappy/article/details/1700829http://www.gatevin.moe/acm/fft%e7%ae%97%e6%b3
2016-07-27 09:09:11
333
原创 HDU 2966 In case of failure KD树
第一道kd树#include #include #include #include #include #include using namespace std;#define N 100005#define lson rt << 1#define rson rt << 1 | 1#define Sqrt2(x) (x) * (x)in
2016-07-27 09:09:10
443
原创 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)
2016-07-22 09:02:37
291
原创 BZOJ 1009 GT考试 DP+矩阵快速幂
dp[i][j]表示长度为i，匹配了j个的方案数，压缩成矩阵，转移即可。#include #include 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){
2016-07-22 09:02:33
361
原创 BZOJ 1006 神奇的国度 弦图最小染色 MCS算法
给定一个弦图，求最小染色参考cdq的弦图与区间图论文http://wenku.baidu.com/view/07f4be196c175f0e7cd13784.htmlhttp://tieba.baidu.com/p/2891159900http://www.cnblogs.com/zhj5chengfeng/p/3279649.html
2016-07-22 09:02:33
429
原创 BZOJ 1056 排名系统 Splay
实现一颗名次树，提供如下操作上传一条新的得分记录、查询某个玩家的当前排名以及返回某个区段内的排名记录。splay的基本的插入删除操作，在加一个hash映射名字和得分，不过可能值会相同。可以给每个节点增加一个表示时间的域，如果值一样，就以时间为第二关键字继续在子树中递归查找。
2016-07-22 09:02:29
452
原创 BZOJ 1211 树的计数 Prufer序列
一个节点在prufer数列中出现的次数是这个节点的度数减一。这样我们就知道这个数列中有哪些数了，因为一个prufer数列唯一对应一颗树。然后问题就变成了求有多少种prufer数列。又因为我们知道了元素种类与出现次数。于是问题就变成了求一个有重复元素的全排列。因为n最大有150.所以分解一下质因数就好了。
2016-07-22 09:02:25
451
原创 BZOJ 1143 祭祀river 最长反链
http://vfleaking.blog.163.com/blog/static/1748076342012918105514527/大前提：在有向无环图中链是一个点的集合，这个集合中任意两个元素v、u，要么v能走到u，要么u能走到v。反链是一个点的集合，这个集合中任意两点谁也不能走到谁。最长反链是反链中最长的那个。那么最长反链怎么求呢？另一个东西叫：最小
2016-07-22 09:02:21
485
原创 BZOJ 1189 紧急疏散evacuate 二分+BFS+最大流
建图的时候需要拆点，按照每一个时间点拆点，主要可以保证每次只有一个人走出门。BFS处理出人到门的距离二分答案，判断是否可以建边，S指向每一块空地，空地到门如果可以建边就建一条容量为x的边每个门按照时间拆点，保证单位时间内走一次，然后跑最大流
2016-07-22 09:02:21
368
原创 2013省赛选拔
Sum of Digitshttp://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4165求一段区间有多少个数每一位加起来的和是s，并且求出最小的一个。数位dp求个数，模拟求最小的数。package net.smgui.common;import java.util.Arrays;impo
2016-07-21 09:00:55
366
原创 2015省赛选拔
Arc and Pointhttp://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=4709几何弱成狗Block Toyhttp://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=47103维版本的铺砖，状态压缩dp。
2016-07-21 09:00:54
482
原创 POJ 2046 Gap BFS+哈希
将4*8的矩阵转成一个64位整数，我是用乘2的方法转成long long的，判断有没有出现过这个状态就用有没有出现这个数字来表示，然后用哈希链地址发解决冲突，x%mod相同的放在一个链表里面，剩下的就是普通的广搜了。#include #include #include #include using namespace std;typedef __int64 LL;con
2016-07-18 09:03:58
360
原创 POj 2449 Remmarguts' Date K短路 A*+SPFA
第一道A*，网上教程一大把就不说了。#include #include #include #include #include using namespace std;const int INF = 999999999;const int maxn = 1010;struct edge{ int u, v, w; int next;
2016-07-18 09:03:58
412
原创 POJ 3134 Power Calculus 迭代加深搜索
第一发迭代加深搜索，参考网上的。。。#include #include #include using namespace std;int ans, n;int a[15];bool dfs(int dep, int x){ if(a[dep] == n) return true; if(dep == ans)
2016-07-18 09:03:58
325
原创 POJ 1011 Sticks DFS+剪枝
#include #include #include using namespace std;bool cmp(int a,int b){ return a > b;}int map[70];int a[70];int n,sum,m,flag;bool dfs(int s, int len, int x, int sum, int num){
2016-07-18 09:03:54
217
原创 POJ 3537 Crosses and Crosses SG函数
在1*n的格子里轮流划×，先划3个连续的×获胜，当在i这个位置划×之后，分成2部分：开始到i-3和i+2到结束。package fd;import java.lang.reflect.Array;import java.util.Arrays;import java.util.HashSet;import java.util.Scanner;import java.ut
2016-07-18 09:03:53
306
原创 POJ 2345 Central heating 高斯消元
n个人n个开关，每个人可以开或者关一些开关，选出一部分人，使得所有的开关都是开的。package fd;import java.util.Scanner;public class Main { static void rank(int[][] A, int m, int n) { int i = 0, j = 0, k, r, u; while(i <
2016-07-18 09:03:53
562
原创 POJ 2082 Terrible Sets 单调栈
首先最暴力的方法就是2个循环，枚举每一个矩形，往左边找第一个高度小于当前的矩形，然后求面积，即(wi-wj)*hi，在i和j矩形之间的矩形的高度都是大于i和j的，因此可以用一个单调递增的栈维护，对于矩形i，弹出栈尾小于等于i高度的矩形，并且计算面积，最后栈中都是高度单调递增的矩形。import java.util.ArrayList;import java.util.Scanner;
2016-07-18 09:03:52
265
原创 POJ 2311 Cutting Game SG函数
宽w高h的纸张轮流切割，首先切出1*1纸张的获胜，必败态为宽和高有一个长度为2的状态，剩下的就是SG函数了，就是切成2个纸张的SG值异或和。package fd;import java.lang.reflect.Array;import java.util.Arrays;import java.util.HashSet;import java.util.Scanner;
2016-07-18 09:03:52
459
原创 POJ 3169 Layout 差分约束
#include #include #include using namespace std;const int maxn = 1010;const int maxm = 100010;int al[maxn], bl[maxn], dl[maxn];int ad[maxn], bd[maxn], dd[maxn];int d[maxn];int main()
2016-07-18 09:03:51
245
原创 POJ 1284 Primitive Roots 原根
//原根+完全剩余系：//看了别人的解题报告 明白了原根的重要定理：// 设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）//假设一个数g对于P来说是原根，那么g^i mod P的结果两两不同,且有 1<g<P, 0<i<P,那么g可以称为是P的一个原根,/*这一题主要是用到了两个定理：1)所有的奇素数都是有原根的
2016-07-18 09:03:47
294
原创 POJ 1742 Coins 多重背包
dp[i][j]为用了前i种硬币，得到j，最多还剩下i种硬币多少个。dp[n][x] >= 0说明可以达到x。#include #include const int maxn = 110;const int maxm = 100010;int a[maxn], b[maxn];int dp[maxm];int main(){ int n, m; whil
2016-07-18 09:03:47
238
原创 POJ 2976 Dropping tests 01分数规划 二分解法
01分数规划：令a=(a1,a2,a3,...,an)，b=(b1,b2,b3,...,bn)，x=(x1,x2,x3,...,xn)都是n维整数向量，求a*x/b*x的最大值或最小值，其中x[i]只能取0或1，也就是求(a1*x1+a2*x2+a3*x3+...+an*xn)/(b1*x1+b2*x2+b3*x3+...+bn*xn)，且xi={0,1},的最值，x取01的意思就是：如果xi取1
2016-07-16 09:34:57
281
原创 POJ 2566 Bound Found two pointers
求一段连续的子序列，使得子序列和的绝对值和x最接近将所有前缀和排序，然后two pointersimport java.sql.Array;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.Scanner;/** *
2016-07-16 09:34:56
252
原创 POJ 3045 Cow Acrobats 贪心
每头牛的危险系数是所有它上面牛的重量之和sum减去这头牛的力量。设牛i在牛j的上面，它们上面所有牛的重量之和为sum，所以牛i的危险系数为ai=sum-si，aj=sum+wi-sj，它们交换位置后bi=sum+wj-si，bj=sum-sj。现在已知aibj。假设ai>aj，得到bi>ai>aj>bj，满足max(ai, aj) < max(bi, bj)，所以i在j上面更优，si+wi
2016-07-16 09:34:56
321
原创 CodeMirror简单使用
看着官网的文档，搞了半天，一个半成品。。。有自动提示，代码高亮，括号匹配等功能。。。在线编程$(function(){ var textarea = document.getElementById('editorBo
2016-07-16 09:34:53
6339
原创 Codeforces Round #276
A. Bits给你一段区间，求区间里面二进制表示1个数最多的数，有多个输出最小值。从l开始，从末尾开始，如果二进制表示下是0，就变成1，知道大于r为止。#include #include typedef __int64 LL;int main(){ int T; scanf("%d", &T); while(T--) {
2016-07-16 09:34:52
224
原创 Codeforces Round #244
A. Police Recruits签到题就不说了#include #include int main(){ int n; while(scanf("%d", &n) != EOF) { int ans = 0; int sum = 0; while(n--) {
2016-07-16 09:34:52
212
原创 Codeforces Round #300
http://codeforces.com/contest/538A. Cutting Banners=raw_input()flag = 0for i in range(len(s)): for j in range(i, len(s)): if(s[:i]+s[j+1:] == 'CODEFORCES'): flag = 1
2016-07-16 09:34:48
264
原创 Codeforces Round #301
http://codeforces.com/contest/540A. Combination Lockn = input()s1 = raw_input()s2 = raw_input()ans=0for i in range(n): tmp1 = abs((int)(s1[i])-(int)(s2[i])) ans += min(tmp1, 10-t
2016-07-16 09:34:48
304
原创 Codeforces Round #313
A. Gerald's Hexagon告诉你一个6边型的边长，求这个6边型是有多少个小三角形组成的。模拟一下。#include #include int main(){ int a[10]; for(int i = 1; i <= 6; i++) scanf("%d", &a[i]); int ans = 0; if
2016-07-16 09:34:48
244
原创 POJ 3614 Sunscreen 优先队列
有n头牛，每头牛有一个区间代表它能忍受阳光强度的范围，m种防晒霜，每种有SPF和cover２个属性，SPF代表使用后可以使阳光强度变为SPF，cover代表使用次数，求最多可以满足多少头牛。首先按照SPF将防晒霜按照从小到大排序，每头牛的区间按照起始点从小到大排序，起始点一样按照结束点从小到大排序，从第一种防晒霜开始，找到所有起始点小于等于SPF的，然后把结束点放进优先队列，优先队列队首是最小
2016-07-16 09:34:43
253
原创 POJ 2010 Moo University - Financial Aid 优先队列
有c个同学，每个同学有成绩和助学金２个属性，现在要你选出n个人，满足他们的助学金之和小于等于f并且中位数尽量大。我用了２个优先队列，首先按照助学金从小到大排序，把前面的n个人放进优先队列中，然后弹出前n/2个人，并且把n/2个人放进另外一个优先队列中，这个优先队列队是最大堆，队首是最大的助学金，然后从剩下的人开始枚举，判断是否成绩大于第一个优先队列队首那个人的成绩，如果是在判断钱是否够，如
2016-07-16 09:34:43
361
原创 POJ 3040 Allowance 贪心
有n种硬币，现在需要付c元，超过也可以，问最多可以付多少次。贪心，先从小到大排序，能用面值大的付就用大的，从后到前扫一次，如果没有达到c，在从前往后用面值小的。
2016-07-16 09:34:43
242
原创 POJ Roadblocks 次短路
求次短路，相比最短路多维护一个值就可以了，次短路要么是S->u的最短路+u->v，要么是 S->u次短路+ u->v 第二小的是次短路。#include #include #include #include #include using namespace std;const int INF = 999999999;const int maxn = 5010;
2016-07-15 09:40:48
412
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人