#
以前一直对树状数组这种结构并不感冒，因为觉得它能做到的事儿线段树也可以很好的完成。而且线段树应用更加灵活，可以说比树状数组的应用范围大很多。不过最近碰到两道题，都可以用树状数组这种结构很好的解决，代码非常精简单，特别是在二维应用的时候，用线段树非常麻烦，如果不是必要的话，不应当菜用线段树这种结构，而应用树状数组。稍微研究了下树状数组这种结构，写个总结吧。
树状数组它的每个元素并不像普通数组那样只保存自己的值，而是保存了从它开始前2^k个值的和(k为位置后面的二进制的0的个数）你可以看下图：
粉线色结点都只保持它自己的值，因为它们的二进制未尾0个数为0。绿色结点都保持了自己与它前一个值的和，蓝色结点保存了四个结点的值的和。棕色结点保存了8个结点的值的和。说了这么多，这种结构有什么用？它有什么优势呢？
它的主要优势就是可以快速求一段的和，即将求一段和的复杂度降到logN级别的，但是它增了修改一个元素的复杂度，使修改一个元素的复杂度也是logN级别的，不难知道，如果一个应用对于查询很多，每次查询都是一个区间的和，那么树状数组它的优势就很明显了。
问题一：怎么求一段元素的和？如果要求A[i –> j]，显然如果能快速求A[1->i-1]和A[1->j]那么问题就解决了。怎么快速转化呢？
因为每个位置它都包含了一段的值，如果这一段值被加进来后，可以快速跳到下一个值，再求。如求A[1->6]，那么知道6包括两个元素的和，下一次再求4，发现4包括四个元素的和，那么这两个和加进来就是结果。怎么快速求6的下一个元素呢？这就需要求出它二制后的0的个数的2的次幂，再与6作差即可。如6=(0000 0110)2，所以2^1=2 ,6-2=4, 4=(0000 0100), 所以2^2=4，4-4=0，结束。
int sum(int n) {
int ret = 0;
while(n > 0) {
ret += ss[n];
n -= lowbit(n);
}
return ret;
}
问题二：怎么快速求一个数二进制后面0的个数的2次幂？位运算。两种方法：x&(-x)或x&(x^(x-1))，它们都利用了位运算的特点，因为我们要求的就是从低位到到高位把遇到的第一个1保持不变，其余各位清0的一个操作！
inline int lowbit(int x) {
return x & (x ^ (x - 1));
}
问题三：怎么快速修改一个元素的值？从上面的图可以看到，修改一个元素的值，所有包含它的值的元素都会被修改。同样，它的变化只与求和有一些不同，求和是往下走，而修改值是往上走！
void change(int i, int value) {
while(i <= N) {
ss[i] += value;
i += lowbit(i);
}
}
变形应用：上面应用都是修改一个元素的值，求一段元素的和。那么它还可以进行什么样的操作呢？修改一段元素都增加或减少一个定值，查询一个元素的值！同样是logN级别的。问题是这样转化的：如果把a-b区间内的元素都要增加v，那么实际就可以把a元素增加v, b+1减少v，那么查询a元素的值呢？就是求sum(1->a)所有元素的和就行了！这样操作是否是正确的？正确性很容易证明，自己在纸上画画就会明白了。
二维树状数组与一维的情况类似。它也可以进行一段的操作，变形应用也可以。要注意的问题就是修改的值会变成四个角。
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/MasterLuo/archive/2009/12/25/5073784.aspx
| You are now registered to take the GRE Split exam in |
Nanjing. |
| Test Date: |
2010-04-08 |
|
Test Time: |
08:30 |
| |
|
|
|
|
| Confirmation No.: |
8850000000460565 |
|
Test Center: |
8513 |
You must arrive at least 30 minutes prior to the testing time to allow for the check-in process and orientation. You will need to bring your confirmation number and two forms of photo-bearing identification with you on the day of the exam; at least one form of primary ID is required. Acceptable forms of primary identification in China are passport, citizenship ID (provisional citizenship ID is not acceptable) or military ID. The test administrator may also ask you to present a secondary form of identification; Secondary forms of Identification are driver license, student ID or employee ID. Identification must meet ETS -GRE requirements or you will not be permitted to test. Additional information on identification requirements can be found on Page 10 of the GRE information Bulletin.
| |
|
| The test center in Nanjing is located at: |
| |
| |
Address: |
Nanjing Testing Center,National Education Examinations Authority,1/F North Door of Library, Nanjing University, #22 Hankou Road,Nanjing, Jiang Su Province,P. R. China南京市汉口路22号 南京大学图书馆北侧门一楼 教育部考试中心南京考点 (210093) |
| |
|
|
|
| |
Tel: |
025-83594869 |
Fax: |
025-83594869 |
好题啊，才发现用网络流也能解这么有实际意义的问题，说不定以后再工程中真的能遇到呢。
网络上的方法是用KM,不过个人比较喜欢用最小费用，就是跑得慢了点。
一点教训吧：这个题里面总点数应该是2500+50+2
最小的边数应该是 (2500*50+50+2500)*2,刚开始没有乘以2，结果猛RE.后来想到网络流里是要建正反边的，汗啊。
建图的代码如下：
int main()
{
int t ;
int i,j,k;
scanf("%d",&t);
while(t--)
{
len=0;
int tem;
scanf("%d%d",&m,&n);
for(i=0;i<n*m+m+2;i++)
adj[i]=NULL;
for (i = 0; i < m; i++)
for (j = 0; j < n; j++)
{
scanf("%d", &tem);
for (k = 0; k < m; k++)
insert(i,m+j*m+k,1,(k + 1) * tem);
}
int s=n*m+m;
int t=n*m+m+1;
for(i=0;i<m;i++)
insert(s,i,1,0);
for(i=m;i<n*m+m;i++)
insert(i,t,1,0);
printf("%.6lf\n",(double)mincostflow(t+1,s,t)/(double)m);
}
return 0;
}
最近在学校刊物《正行》上发表了一遍关于小人的文章，由于比较匆忙，投稿时没有经过仔细地史料考证，原文中提到赵高是服毒而死，这是不符合历史史实的，实际上，赵高死于秦王子婴之手。
赵高(前259─前207)
赵高,本为赵国贵族，后入秦为宦官(一说赵高为“宦官”乃后世曲解），任中车府令，兼行符玺令事，「管事二十余年」。秦始皇死后，他与李斯合谋伪造诏书，逼秦始皇长子扶苏自杀，另立胡亥为帝，并自任郎中令。他在任期间独揽大权，结党营私，征役更加繁重，行政更加苛暴。公元前207年又设计害死李斯，成为秦国丞相。第二年他迫二世自杀，另立子婴。不久被子婴杀掉，诛夷三族。
蛮麻烦的一个题 但是说白了 也就是一个类似最长上升子序列的东西（可能跳转的跨度大了些） 从底部往上逐层DP,每一层有两个状态 分别求之。小结一下吧 做了这么多动态规划题 我发现 动态规划的实质 居然是穷举 ，囧啊，或者更确切的来说是 带记忆化的穷举！存储加递归应该还是欠妥的，因为毕竟有了最优子结构以后 后效状态便消除了，而且也并没有揭示出DP解法的全局性（如果用更宏观的视角来看待它），即它在求得答案的同时，也获得了其他更多的信息，这些信息不是冗余（redundant 恩GRE高频词），形象的说 应该是在DP之路上，为答案作出贡献的朋友，如果我们换一个问题，也许它们也就成了答案。
对了，补充一下，我觉得这个题最重要的地方在于，当你找到了一块板刚好能接住从左侧下降的你时，你便不用再考虑更下层的板了，因为你不可能穿墙（板）！
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define INF 999999999
struct node
{
int x1;
int x2;
int h;
bool operator <(node other)
{
return h>other.h;
}
}a[1005];
int dp[1001][2];
int n,x,y,mh;
int main()
{
int t;
int i,j,k;
scanf("%d",&t);
for(k=1;k<=t;k++)
{
scanf("%d%d%d%d",&n,&x,&y,&mh);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x1,&a[i].x2,&a[i].h);
dp[i][0]=dp[i][1]=INF;
}
dp[n+1][0]=dp[n+1][1]=0;
a[n+1].x1=-INF;
a[n+1].x2=INF;
sort(a+1,a+1+n);
for(i=n;i>=1;i--)
{
bool l=false;
bool r=false;
for(j=i+1;j<=n+1;j++)
{
if(a[i].h-a[j].h>mh)
break;
if(!l&&a[i].x1>=a[j].x1&&a[i].x1<=a[j].x2)
{
if(j==n+1) dp[i][0]=0;
else
{
dp[i][0]=min(dp[i][0],dp[j][0]+a[i].x1-a[j].x1);
dp[i][0]=min(dp[i][0],dp[j][1]+a[j].x2-a[i].x1);
l=true;
}
}
if(!r&&a[i].x2>=a[j].x1&&a[i].x2<=a[j].x2)
{
if(j==n+1) dp[i][1]=0;
else
{
dp[i][1]=min(dp[i][1],dp[j][0]+a[i].x2-a[j].x1);
dp[i][1]=min(dp[i][1],dp[j][1]+a[j].x2-a[i].x2);
r=true;
}
}
}
}
int res=0;
for(i=1;i<=n+1;i++)
{
if(a[i].x1<=x&&x<=a[i].x2&&y>=a[i].h)
{
res=min(x-a[i].x1+dp[i][0],a[i].x2-x+dp[i][1]);
break;
}
}
res+=y;
printf("%d\n",res);
}
return 0;
}
自我实现的需求
↑
尊重的需求（社会承认的需求）
↑
社交的需求（社会关系的需求）
↑
安全的需求
↑
生理的需求（身体基本需求）
生理需要和安全需要得到满足后，归属需要、自尊需要和自我实现的需要才能充分展现
1.生理需要是人类维持自身生存的最基本要求，它具有自我保存和种族延续的意义，在人类各种基本需要中占有最强的优势，也是人类社会发展的动力。
（1）生理上的需要包括：
◆ 呼吸
◆ 水
◆ 食物
◆ 睡眠
◆ 生理平衡
◆ 分泌
◆ 性
如果这些需要（除性以外）任何一项得不到满足，人类个人的生理机能就无法正常运转。换而言之，人类的生命就会因此受到威胁。在这个意义上说，生理需要是推动人们行动最首要的动力。马斯洛认为，只有这些最基本的需要满足到维持生存所必需的程度后，其他的需要才能成为新的激励因素，而到了此时，这些已相对满足的需要也就不再成为激励因素了。
2.安全需求是人们对于周围环境的依赖和信赖。在现实中，安全需要常常是一个幻觉。即人们认为有安全需要或没有安全需要。
安全需求包括：
◆ 人身安全
◆ 健康保障
◆ 资源所有性
◆ 财产所有性
◆ 道德保障
◆ 工作职位保障
◆ 家庭安全
马斯洛认为，整个有机体是一个追求安全的机制，人的感受器官、效应器官、智能和其他能量主要是寻求安全的工具，甚至可以把科学和人生观都看成是满足安全需要的一部分。当然，当这种需要一旦相对满足后，也就不再成为激励因素了。
3.归属需要就是参加和依附于一定组织的需要，爱的需要包括给予爱和接受爱，归属和爱的需要如果得不到满足，个人就会感到孤独和空虚。
包括
◆ 友情
◆ 爱情
◆ 性亲密
人人都希望得到相互的关系和照顾。感情上的需要比生理上的需要来的细致，它和一个人的生理特性、经历、教育、宗教信仰都有关系。
4.尊重的需要包括两个方面：自尊和他人对自己的尊重。这种需要的满足会使人建立自信，使人觉得自己在这个世界上是有价值的、有能力的、有力量的。如果得不到满足，就会导致自卑感、无助感和失落感。
◆ 自我尊重
◆ 信心
◆ 成就
◆ 对他人尊重
◆ 被他人尊重
人人都希望自己有稳定的社会地位，要求个人的能力和成就得到社会的承认。尊重的需要又可分为内部尊重和外部尊重。内部尊重就是人的自尊。外部尊重是指一个人希望有地位、有威信，受到别人的尊重、信赖和高度评价。马斯洛认为，尊重需要得到满足，能使人对自己充满信心，对社会满腔热情，体验到自己活着的用处和价值。
5.这种需要是一种创造、发挥个人潜能、实现自我理想、实现个人价值的需要。
◆ 道德
◆ 创造力
◆ 自觉性
◆ 问题解决能力
◆ 公正度
◆ 接受现实能力
在马斯洛看来，人类价值体系存在两类不同的需要，一类是沿生物谱系上升方向逐渐变弱的本能或冲动，称为低级需要和生理需要。一类是随生物进化而逐渐显现的潜能或需要，称为高级需要。
人都潜藏着这五种不同层次的需要，但在不同的时期表现出来的各种需要的迫切程度是不同的。人的最迫切的需要才是激励人行动的主要原因和动力。人的需要是从外部得来的满足逐渐向内在得到的满足转化。
低层次的需要基本得到满足以后，它的激励作用就会降低，其优势地位将不再保持下去，高层次的需要会取代它成为推动行为的主要原因。有的需要一经满足，便不能成为激发人们行为的起因，于是被其他需要取而代之。
高层次的需要比低层次的需要具有更大的价值。热情是由高层次的需要激发。人的最高需要即自我实现就是以最有效和最完整的方式表现他自己的潜力，惟此才能使人得到高峰体验。
摘要: 自己太水了。。。呵呵A题 打表。。。
#include<iostream>using namespace std;/**//*int dp[10000001];int rex[10000];int rey[10000];int main(){ freopen("out.txt",...
阅读全文
Cayley公式是说，一个完全图K_n有n^(n-2)棵生成树，换句话说n个节点的带标号的无根树有n^(n-2)个。今天我学到了Cayley公式的一个非常简单的证明，证明依赖于Prüfer编码，它是对带标号无根树的一种编码方式。
给定一棵带标号的无根树，找出编号最小的叶子节点，写下与它相邻的节点的编号，然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。由于节点数n>2的树总存在叶子节点，因此一棵n个节点的无根树唯一地对应了一个长度为n-2的数列，数列中的每个数都在1到n的范围内。下面我们只需要说明，任何一个长为n-2、取值范围在1到n之间的数列都唯一地对应了一棵n个节点的无根树，这样我们的带标号无根树就和Prüfer编码之间形成一一对应的关系，Cayley公式便不证自明了。
注意到，如果一个节点A不是叶子节点，那么它至少有两条边；但在上述过程结束后，整个图只剩下一条边，因此节点A的至少一个相邻节点被去掉过，节点A的编号将会在这棵树对应的Prüfer编码中出现。反过来，在Prüfer编码中出现过的数字显然不可能是这棵树（初始时）的叶子。于是我们看到，没有在Prüfer编码中出现过的数字恰好就是这棵树（初始时）的叶子节点。找出没有出现过的数字中最小的那一个（比如④），它就是与Prüfer编码中第一个数所标识的节点（比如③）相邻的叶子。接下来，我们递归地考虑后面n-3位编码（别忘了编码总长是n-2）：找出除④以外不在后n-3位编码中的最小的数（左图的例子中是⑦），将它连接到整个编码的第2个数所对应的节点上（例子中还是③）。再接下来，找出除④和⑦以外后n-4位编码中最小的不被包含的数，做同样的处理……依次把③⑧②⑤⑥与编码中第3、4、5、6、7位所表示的节点相连。最后，我们还有①和⑨没处理过，直接把它们俩连接起来就行了。由于没处理过的节点数总比剩下的编码长度大2，因此我们总能找到一个最小的没在剩余编码中出现的数，算法总能进行下去。这样，任何一个Prüfer编码都唯一地对应了一棵无根树，有多少个n-2位的Prüfer编码就有多少个带标号的无根树。
一个有趣的推广是，n个节点的度依次为D1, D2, ..., Dn的无根树共有(n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ]个，因为此时Prüfer编码中的数字i恰好出现Di-1次。