進(jìn)程在運(yùn)行時(shí)，會(huì)占用計(jì)算機(jī)的各種資源，比如CPU時(shí)間、內(nèi)存、文件等等。但是，進(jìn)程是不可以占用無(wú)限多的資源的，操作系統(tǒng)會(huì)給進(jìn)程設(shè)定所使用資源的上限。想獲取這些資源的上限值，是需要調(diào)用getrlimit()即可。

int getrlimit(int resource, struct rlimit *rlptr);

第一個(gè)參數(shù)是資源，有哪些資源呢？

第二個(gè)參數(shù)是rlimit，rlimit結(jié)構(gòu)是這樣的：

struct rlimit
{
    rlim_t rlim_cur; /* soft limit: current limit */
    rlim_t rlim_max; /* hard limit: maximum value for rlim_cur */
};

其中含有軟限制和硬限制。超級(jí)用戶可以增加硬限制；一般用戶可以降低硬限制，但不能增加硬限制，一般用戶還可修改軟限制，但修改的軟限制不能超過硬限制。

實(shí)際運(yùn)行的效果如何呢？實(shí)踐一下吧！

#include <stdio.h>
#include <sys/resource.h>

#define doit(name) pr_limit(#name, name)

void pr_limit(char* name, int resource);

int main ()
{
	printf("resource name  soft\thard \n");
#ifdef  RLIMIT_AS
	doit(RLIMIT_AS);
#endif
	doit(RLIMIT_CORE);
	doit(RLIMIT_CPU);
	doit(RLIMIT_DATA);
	doit(RLIMIT_FSIZE);
#ifdef  RLIMIT_LOCKS
	doit(RLIMIT_LOCKS);
#endif
#ifdef  RLIMIT_MEMLOCK
	doit(RLIMIT_MEMLOCK);
#endif
	doit(RLIMIT_NOFILE);
#ifdef  RLIMIT_NPROC
	doit(RLIMIT_NPROC);
#endif
#ifdef  RLIMIT_RSS
	doit(RLIMIT_RSS);
#endif
#ifdef  RLIMIT_SBSIZE
	doit(RLIMIT_SBSIZE);
#endif
	doit(RLIMIT_STACK);
#ifdef  RLIMIT_VMEM
	doit(RLIMIT_VMEM);
#endif

	return 0;
}


void pr_limit(char* name, int resource)
{
	struct rlimit limit;
	if ( getrlimit(resource, &limit) < 0 )
	{
		printf("getrlimit error!\n");
		return;
	}
	printf("%-14s ", name);
	if ( limit.rlim_cur == RLIM_INFINITY )
		printf("infinite ");
	else
		printf("%8ld ", limit.rlim_cur);

	if ( limit.rlim_max == RLIM_INFINITY )
		printf("infinite ");
	else
		printf("%8ld ", limit.rlim_max);
	putchar('\n');
} 

運(yùn)行的結(jié)果：

resource name  soft	hard 
RLIMIT_AS      infinite infinite 
RLIMIT_CORE           0 infinite 
RLIMIT_CPU     infinite infinite 
RLIMIT_DATA    infinite infinite 
RLIMIT_FSIZE   infinite infinite 
RLIMIT_LOCKS   infinite infinite 
RLIMIT_MEMLOCK    65536    65536 
RLIMIT_NOFILE      1024     1024 
RLIMIT_NPROC   infinite infinite 
RLIMIT_RSS     infinite infinite 
RLIMIT_STACK    8388608 infinite 

在shell中對(duì)程序進(jìn)行重定向很簡(jiǎn)單，用<和>符號(hào)就可以了，但在自己的程序中怎么實(shí)現(xiàn)輸入輸出重定向呢？

先來看看Linux內(nèi)核中，文件（還是設(shè)備）是通過哪些數(shù)據(jù)結(jié)構(gòu)保存的：

每個(gè)進(jìn)程都保存一份文件描述符的表格，每一行又指向file table，然后file table再指向v-node table。v-node table我們可以暫不考慮，暫且把它當(dāng)作文件的內(nèi)容。而從process table entry中的file pointer可以指向不同或者相同的file table。原本標(biāo)準(zhǔn)輸入輸出是指向“鍵盤”和“屏幕”這兩個(gè)設(shè)備的，如果可以將它們指向我們指定的文件，就可以實(shí)現(xiàn)重定向了。

先用open()打開需要重定向到的文件，獲取去文件描述符fd，在用dup2()把進(jìn)程中原先的輸入輸出文件描述符STDIN_FILENO和STDOUT_FILENO重定向至fd，這樣就可以實(shí)現(xiàn)輸入輸出重定向了。我想，shell實(shí)現(xiàn)重定向也應(yīng)該是類似的思想，關(guān)鍵代碼如下：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <unistd.h>
#include <sys/wait.h>
#include <sys/resource.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <errno.h>
#include <fcntl.h>
#include <signal.h>

int main (int argc, char** argv)
{
	if ( argc != 3 )
	{
		printf("usage: inputFile outputFile\n");
		return 1;
	}
	int inFd, outFd;
	//open file descriptor
	inFd = open(argv[1], O_RDONLY);
	if ( inFd < 0 )
	{
		printf("inFd open error!\n%s\n",strerror(errno));
		return 1;
	}
	outFd = open(argv[2], O_CREAT | O_TRUNC | O_RDWR, S_IRWXU | S_IRGRP | S_IROTH);
	if ( outFd < 0 )
	{
		printf("outFd open error!\n%s\n", strerror(errno));
		return 1;
	}

	//change standard input and output
	if ( dup2(inFd, STDIN_FILENO) < 0 )
	{
		printf("inFd dup2 error!\n");
		return 1;
	}
	if ( dup2(outFd, STDOUT_FILENO) < 0 )
	{
		printf("outFd dup2 error!\n");
		return 1;
	}		

	char line[128];
	while ( scanf("%s", &line) != EOF )
	{
		printf("%s\n", line);
	}

	return 0;
}

有這樣一種集合，集合元素為長(zhǎng)度N（1～31）的二進(jìn)制串，并且每個(gè)二進(jìn)制串中1的個(gè)數(shù)小于等于L，求這個(gè)集合中第I大的元素是多少？

最開始很天真的想枚舉每個(gè)數(shù)，計(jì)算其中1的個(gè)數(shù)，結(jié)果第8組測(cè)試數(shù)據(jù)開始就超時(shí)的不行了。

枚舉不行，來試試構(gòu)造可不可以，假設(shè)我們有一個(gè)長(zhǎng)度為n，1個(gè)數(shù)<=l的二進(jìn)制串的集合，那么怎么把它們從大到小區(qū)分呢？我們一位一位來，根據(jù)第n位，可以將集合劃為2部分：第n位是0的，第n為是1的。好了，遞推式突然就變得很明顯了。如何設(shè)num[N][L]為長(zhǎng)度為N，1個(gè)數(shù)小于等于L的二進(jìn)制串的個(gè)數(shù)，那么：

num[N][L] = num[N-1][L]   +   num[N-1][L-1]
                     （第n位是0）         （第n位是1）

個(gè)數(shù)有了，那么第I個(gè)數(shù)是多少怎么求呢？說來也簡(jiǎn)單，就是用遞歸的思想，看I落在num[N-1][L]和num[N-1][L-1]的哪一部分，看下面的代碼應(yīng)該就明白了：

void Print (int len, int num1, long long idx)
{
     if ( len == 0 )
          return;
     if ( num[len-1][num1] >= idx )
     {
          putchar('0');
          Print(len-1, num1, idx);
     }
     else
     {
          putchar('1');
          Print(len-1, num1-1, idx-num[len-1][num1]);
     }
}

問你N階乘的最低非零位上是什么數(shù)字。(0 <= N <= 4220)

從1一直乘到N，如果能整除10，就除以10，可以嗎？不行，因?yàn)榧词谷サ舻臀坏?，高位的非0位仍然很大，無(wú)法保存下來。

可以將N!這樣表示：
N! = 2^K * 5^L * V(N)
= 2^(K-L) * V(N) * 10^L ( K >= L 如何證明呢？)

10^L不影響N!最低非零位，這個(gè)數(shù)由(K-L)以及V(N)的個(gè)位數(shù)所決定。K和L容易得到，V(N)的個(gè)位數(shù)也好得到，只要枚舉i（從1到N），去除因子2和5（因子個(gè)數(shù)加到K和L），將其個(gè)位數(shù)乘以中間結(jié)果就可以了。

關(guān)鍵代碼如下：

const int f2 [] = {6, 2, 4, 8};

int i, tmp, n2, n5;
int ans = 1;
n2 = n5 = 0;
for ( i = 1; i <= n; i ++)
{
	tmp = i;
	while ( tmp % 2 == 0 )
	{
		n2 ++;
		tmp /= 2;
	}
	while ( tmp % 5 == 0 )
	{
		n5 ++;
		tmp /= 5;
	}
	ans = (( tmp % 10) * ans) % 10;
}
ans = ( ans * f2[( n2- n5)%4] ) % 10;
printf( "%d\n", ans);

有N(1<=N<=50)種不同面值郵票，由這些郵票組成面值1～M，1、2、……、M每種面值均由不超過K(1<=K<=200)數(shù)目的郵票組成，求最大的M為多少？郵票最大面值為10000

一開始想到DP，數(shù)組canComprise[10000*200][200]，canComprise[i][j]表示用j張郵票是否可以組成面值i，但數(shù)組太大，放棄。

后來改用深搜，優(yōu)化了許久，最后幾組數(shù)組仍然超時(shí)，放棄。

又回頭想DP，如果canComprise[i][j1]和canComprise[i][j2]均為true，j1 < j2，那么canComprise[i][j1]肯定是更優(yōu)的解，因?yàn)閖1可以擴(kuò)展更多i+stamps[x]。所以，只要用一維數(shù)組保存答案就可以了，比如minStamp[i] = j就表示組成i所用到的最少郵票數(shù)為j，遞推式很容易想到：

minStamp[i] = Min{ minStamp[i-stamp[x]] + 1 } ( i – stamp[x] >= 0 )

同一種情況，表達(dá)解的方式可能有多種，盡量使用最精簡(jiǎn)的方式，已達(dá)到降維的效果。

一道幾何題，解決方法很容易想到，不過要細(xì)心。

隨著輸入的順序，將矩形一個(gè)個(gè)放入集合，如果新的矩形與集合中的舊矩形相交，就將舊矩形分解，刪除舊矩形，放入新矩形和分解的矩形。

設(shè)矩形R1、R2，寬和高分別為(W1, H1)和(W2, H2)，兩矩形中心坐標(biāo)分別為(X1, Y1)以及(X2, Y2)。判斷兩矩形是否相交（也就是是否有面積相重合），就看兩矩形中心坐標(biāo)的豎直和水平距離是否小于兩矩形高的和的一半以及兩矩形寬的和的一半。即：

( |X1 - X2| < (W1 + W2) / 2 ) && ( |Y1 - Y2| < (H1 + H2) / 2 )

如果條件滿足，R1和R2即相交。

那相交會(huì)有幾種情況呢？我想到了16種：

根據(jù)不同的情況，可以將原來的矩形分解為0～4個(gè)小矩形，這樣就可以解出來了。

（做幾何題可真費(fèi)草稿紙啊，看來以后得學(xué)學(xué)matlab了，低碳、環(huán)保！）

另外，USACO還有一種解法，就是將矩形的四條邊進(jìn)行離散化處理，將線段排序，然后再依次掃描，大體思路是這樣的，具體細(xì)節(jié)沒怎么看。

最直接的想法是枚舉每個(gè)數(shù)，看是否能用S中的元素將其分解，但1<=N<=100000，第N個(gè)數(shù)肯定會(huì)很大，這樣做肯定超時(shí)，放棄。

后來想利用STL中的set來解決，枚舉某一個(gè)數(shù)，如果屬于set，將其與S中各元素相乘的數(shù)放入set，如此循環(huán)，直至找到第N個(gè)數(shù)，提交后還是超時(shí)。看來即便是set，畢竟存取的效率不是O(1)，性能還是有影響。

突然想到，這題不是跟poj的Ugly Number挺像的嘛，是Ugly Number的加強(qiáng)版。具體思想是：對(duì)于S中的每個(gè)元素p[i]，設(shè)置一個(gè)下標(biāo)pIdx[i]，pIdx[i]指向humble number數(shù)組。進(jìn)行N次循環(huán)，每次找出最小的p[i] * humble[pIdx[i]]，將該數(shù)加入humble數(shù)組，然后pIdx[minIdx]++。這樣就能由小到大找出第N個(gè)humble number了。

PS：其實(shí)這種方法生成的humble number只能保證非降序，比如2×3和3×2就會(huì)生成相同的humble number，這種情況要排除。

一個(gè)圖，有至少2個(gè)連通分量，用分別屬于不同連通分量的點(diǎn)對(duì)將這兩個(gè)連通分量連接，使其“直徑”最小，問最小直徑為多少。（直徑的定義為連通分量中點(diǎn)對(duì)的最短路徑中最長(zhǎng)的路徑）

我的思路是：

1、Floyd算出點(diǎn)對(duì)最短路徑

2、深搜找出不同連通分量

3、枚舉同一連通分量中的點(diǎn)對(duì)最短路徑，最大的作為該連通分量的直徑，順便算出一點(diǎn)到連通分量中最遠(yuǎn)點(diǎn)的距離

4、枚舉不同連通分量的任意點(diǎn)對(duì)a和b，找出以下的最大值

      a所在連通分量的直徑
      b所在連通分量的直徑
      ab的距離 + a到本連通分量最遠(yuǎn)距離 + b到本連通分量最遠(yuǎn)距離

5、找出這些最大值中的最小值

明明是一道難度不大的題，我卻做了N天才做出來，慚愧慚愧！看到題的第一想法就是如果A控制了B，就把B所占有的股份傳給A以及A的母公司，并且這樣遞歸下去。可自己編程會(huì)發(fā)生股份重復(fù)計(jì)算的情況，解決方法是當(dāng)將B的股份更新到A上時(shí)（通過母公司的關(guān)系找到A），如果之前A已經(jīng)直接或間接控制了B，那么如果再加就算是重復(fù)計(jì)算了。但在判斷A是否直接或間接控制B時(shí)，又要判斷是否有環(huán)。

后來在網(wǎng)上找到了一種解法：當(dāng)發(fā)現(xiàn)A控制B時(shí)，將B的股份傳給A，如果發(fā)現(xiàn)增加股份之后，A中的股份[A][i] > 50 并且A還沒有控制i，則將(A, i)加入隊(duì)列。一直循環(huán)操作，直至隊(duì)列為空為止。

官方的解題報(bào)告中，其實(shí)就是我一開始想的遞歸的方法，他在更新（A, B）時(shí)：

1. 如果A已經(jīng)控制B，退出
2. 若沒有，control[A][B] = 1
3. 將B的股份傳給A
4. 枚舉已控制了A的i，遞歸更新（i, B）
5. 枚舉A的股份[A][k]，如果大于50，遞歸更新（A, k）

一棵樹，每個(gè)節(jié)點(diǎn)有0或2個(gè)孩子，共N個(gè)節(jié)點(diǎn)，高度為K，問可以組成多少種不同的結(jié)構(gòu)？

假設(shè)，當(dāng)前樹的節(jié)點(diǎn)問n，高度為k，那么子樹可分為3種情況：

1. 左子樹高度為k-1，右子樹高度為1～k-2
2. 右子樹高度為k-1，左子樹高度為1～k-2
3. 左右子樹均為k-1

并且，滿足題目要求的樹的節(jié)點(diǎn)與高度有這樣的關(guān)系：2*k-1 <= n <= 2^k-1，可是根據(jù)這個(gè)關(guān)系枚舉左右子樹的節(jié)點(diǎn)數(shù)

于是就可以用遞歸+DP的方法解出這道題了。

（在對(duì)n <= 2^k-1進(jìn)行轉(zhuǎn)化時(shí)，自己居然寫成了k >= log(n+1.0)/log(2.0)，其實(shí)應(yīng)該是k >= floor (log(n+1.0)/log(2.0))，還是太粗心啦）