9 发奋屠强

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 7w+

LCA 多次询问 解法总结

N个节点,M次询问,求两点间的最近公共祖先一、

2014-10-28 15:13:27

编程之美-中国象棋将帅问题

首先,我们归纳总结一下展开原理,对于 a*b = i ,我们可以用如下公式展开    loop1=i%b;    loop2=(i/b)%a  其中loop1是内层循环,loop2是外层循环  那么如果 a 本身就是 k*j 组成的呢?由于 k*j = i/b  ,套用公式得到       loop1= (i/b)%j    loop2= ((i

2014-09-19 11:15:54

分布式计算、网格计算和云计算

1、分布式计算所谓分布式计算是一门计算机科学,它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分,然后把这些部分分配给许多计算机进行处理,最后把这些计算结果综合起来得到最终的结果。最近的分布式计算项目已经被用于使用世界各地成千上万位志愿者的计算机的闲置计算能力,通过因特网,您可以分析来自外太空的电讯号,寻找隐蔽的黑洞,并探索可能存在的外星智慧生命;您可以寻找超过1000万

2014-08-22 11:12:15

【HDU3721】枚举+最长路

题意:给你一颗n个节点n-1条边的树,每条边都有一个权值,现在让你任意移动一条边然后把这条边连接到任意两个点上,最后问你怎样移动才能使树上相距最远的两个点距离最小。 思路:先求出树的最长路,然后枚举移动最长路上的所有边,移走这条边后,原树必定分为不连接的两颗子树,分别求这两颗子树的最长路,然后分别找到两颗子树最长路上靠近中点的点,那么最长路有三种情况:假设这条边为 u -> v1.u的

2013-09-20 14:14:55

HDU 4679 Terrorist’s destroy (拆边+树的直径)

给一棵树,每条边上都有一个权值,去掉树上任意一条边之后,分成两个子树,两个子树的最长路与这条边上的权值相乘,的到一个乘积。问去掉那一条边可以使这个乘积最小。首先找到树上的最长路,那么删边的时候有两种情况:1. 这条边不是最长路上的边2. 这条边是最长路上的边对于第一种情况,很容易计算出乘积。对于第二种情况,只需要计算出被分成的两个子树里面的最长路径长度即可,这个可以预处理一下。

2013-09-20 13:58:15

SPOJ 375. Query on a tree【树链剖分】

http://www.spoj.pl/problems/QTREE/给一颗树,每条边有一个权值。有两种操作:1、修改某条边的值;2、询问a、b两点路径上边权的最大值。树链剖分。#include #include #include #include using namespace std;#define maxn 100100#define lson (pos<<

2013-09-17 11:07:54

hdu4714 Tree2cycle 树形DP

题目是问把一棵树通过剪边、加边形成一个环的最小代价。分成两步,先把树剪成一些链,再把链连接成一个环。My Code://dp[u][0]表示u节点是所在链的端点时,以u节点为根节点的子树形成的最少的切边数。//dp[u][1]表示u节点是所在链的中间的点时,以u节点为根节点的子树形成的最少的切边数。#pragma comment(linker,"/STACK:102400000,1

2013-09-10 23:09:33

POJ 1895 Bring Them There 分层构图 求最大流 并输出路径

这个题在输出路径上上纠结了好久,直到我遇到了下面这个代码,,堪称完美!Code: //神一样的思想,神一样的代码,我佩服的五体投地!! //题目给出五个正整数n,m,k,s,t。n表示n星球,m表示m个双向隧道, //k,s,t表示要把k个电脑从s星球运到t星球,双向道只能单行,走一条 //道用时一天,求最短时间,并输出运输方案。 //

2013-09-06 10:12:02

HDU 1733 [Escape] 分层图网络流+枚举时间

题目大意:给定一个矩阵,'.'表示空位,'X'表示人,'#'表示墙,'@'表示门,每个位置至多只能站一个人,人不能穿越墙,人能从门中出去。每个人每分钟只能上下左右移动一步,问最少需要多少时间让所有的人出去。思路:(1):把每个点按照天数拆成d个点。(2):添加源汇点S和T。(3):源点向第0天地图上人所在位置的点连一天容量为1的边。(4):枚举时间Ti(5):每次枚举只

2013-09-05 17:05:27

hdu4628状态压缩DP

这题学到了一个方法吧:如果要枚举集合S的子集:for(int i = S; i > 0; i=(i-1)&S)如果要枚举包含S的集合:for(int i = S; i 很巧的方法,以前从未见过,在这mark下了。下面给出两种方法的代码:记忆化搜索:#include #include #include #include using namespace

2013-07-31 10:36:28

背包专辑(转)

(解题报告本人所写,博客内容转自zeroclock)这短时间看了论文《背包九讲》,看到背包问题解法中的优美之处也看到背包问题在现实中的应用,总结出一句话:背包问题值得一看。    背包问题可以概括为这样的模型:有若干种选择,每种选择有一定的代价和价值,做某些选择会得到特定的状态,问我们在约定的条件下怎么得到特定的状态?这里的状态可以是代价和或者价值和或者由其他这两者组合而来的状态。这类问题

2013-07-29 19:51:32

树形DP总结(转)

树,一种十分优美的数据结构,因为它本身就具有的递归性,所以它和子树见能相互传递很多信息,还因为它作为被限制的图在上面可进行的操作更多,所以各种用于不同地方的树都出现了,二叉树、三叉树、静态搜索树、AVL树,线段树、SPLAY树,后缀树等等..     枚举那么多种数据结构只是想说树方面的内容相当多,本专辑只针对在树上的动态规划,即树形DP.做树形DP一般步骤是先将树转换为有根树,然后在树上进行

2013-07-29 19:48:29

hdu 4614

题意:给你N个花瓶,编号是0  到 N - 1 ,初始状态花瓶是空的,每个花瓶最多插一朵花。然后有2个操作。操作1,a b c ,往在a位置后面(包括a)插b朵花,输出插入的首位置和末位置。操作2,a b ,输出区间[a , b ]范围内的花的数量,然后全部清空。很显然这是一道线段树。区间更新,区间求和,这些基本的操作线段树都可以logN的时间范围内完成。操作2,很显然

2013-07-26 18:50:28

LCA和RMQ模板

一、最近公共祖先(Least Common Ancestors)对于有根树T的两个结点u、v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点。这里给出一个LCA的例子:例一对于T=V={1,2,3,4,5}E={(1,2),(1,3

2013-05-12 22:46:14

tarjan求强连通分量模板

在有向图中,如果两个顶点间至少存在一条路径,称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量。而用tarjan算法可以起求出各个强连通分量,然后再把强连通分量缩成一个点,非强连通图就被转换成一个DAG,去多问题都是在此基础上求解。以下是模板:#include #include #

2013-05-07 21:59:42

割点,桥模板

求割点:割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点若low[v]>=pre[u],则u为割点。这说明v的子孙不能够通过其他边到达u的祖先,这样去掉u之后,图必然分裂为两个子图。这样我们处理点u时,首先递归u的子节点v,然后从v回溯至u后,如果发现上述不等式成立,则找到了一个割点u,并且u和v的子树构成一个块。求割边(桥)割边(桥):删掉它之后,图

2013-05-07 21:51:12

北大ACM试题分类

转载请注明出处:優YoU http://blog.csdn.net/lyy289065406/article/details/6642573  最近AC题:2528   更新时间:2011.09.22  已AC题数:146初级题已在2011.06.30全部完成 部分解题报告添加新内容,除了原有的“大致题意”和“解题思路”外,新增“Source修正”,因为原S

2013-05-07 15:33:03

十个利用矩阵乘法解决的经典题目

这篇文章很经典,我是从这儿http://www.matrix67.com/blog/archives/276/看到的! 好像目前还没有这方面题目的总结。这几天连续看到四个问这类题目的人,今天在这里简单写一下。这里我们不介绍其它有关矩阵的知识,只介绍矩阵乘法和相关性质。    不要以为数学中的矩阵也是黑色屏幕上不断变化的绿色字符。在数学中,一个矩阵说穿了就是一个二维数组。一个n行m列的矩

2013-05-04 14:52:45

01分数规划

【关键字】0/1分数规划、最优比率生成树、最优比率环【背景】 根据楼教主的回忆录,他曾经在某一场比赛中秒掉了一道最优比率生成树问题,导致很多人跟风失败,最终悲剧。可见最优比率生成树是多么凶残的东西,但是这个东西只要好好研究半天就可以掌握,相信你在看了我写的这篇总结之后可以像楼教主一般秒掉这类问题。因为网上对于01分数规划问题的详细资料并不是太多,所以我就结合自己的一些理解总结这种问

2013-05-04 14:47:20

求模的逆元

欧拉函数Φ(n)一些定理:•欧拉定理–a和n都是正整数,且a和n互素,则aΦ(n) ≡ 1 (mod n)•ab (mod n) = a(b % Φ(n) + Φ(n)) (mod n)•ab (mod n) = a(b % Φ(n))(mod n),gcd(a,n)=1•费马小定理(欧拉定理弱化形式)–设a是正整数,p是素数,且a和p互素,则p

2013-05-02 22:06:52

查看更多

勋章 我的勋章
    暂无奖章