#
以前一直對樹狀數組這種結構并不感冒，因為覺得它能做到的事兒線段樹也可以很好的完成。而且線段樹應用更加靈活，可以說比樹狀數組的應用范圍大很多。不過最近碰到兩道題，都可以用樹狀數組這種結構很好的解決，代碼非常精簡單，特別是在二維應用的時候，用線段樹非常麻煩，如果不是必要的話，不應當菜用線段樹這種結構，而應用樹狀數組。稍微研究了下樹狀數組這種結構，寫個總結吧。
樹狀數組它的每個元素并不像普通數組那樣只保存自己的值，而是保存了從它開始前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;
}
最近在學?？铩墩小飞习l表了一遍關于小人的文章，由于比較匆忙，投稿時沒有經過仔細地史料考證，原文中提到趙高是服毒而死，這是不符合歷史史實的，實際上，趙高死于秦王子嬰之手。
趙高(前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.生理需要是人類維持自身生存的最基本要求，它具有自我保存和種族延續的意義，在人類各種基本需要中占有最強的優勢，也是人類社會發展的動力。
?。?）生理上的需要包括：
◆ 呼吸
◆ 水
◆ 食物
◆ 睡眠
◆ 生理平衡
◆ 分泌
◆ 性
如果這些需要（除性以外）任何一項得不到滿足，人類個人的生理機能就無法正常運轉。換而言之，人類的生命就會因此受到威脅。在這個意義上說，生理需要是推動人們行動最首要的動力。馬斯洛認為，只有這些最基本的需要滿足到維持生存所必需的程度后，其他的需要才能成為新的激勵因素，而到了此時，這些已相對滿足的需要也就不再成為激勵因素了。
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次。