QuXiao

進程在運行時，會占用計算機的各種資源，比如CPU時間、內存、文件等等。但是，進程是不可以占用無限多的資源的，操作系統會給進程設定所使用資源的上限。想獲取這些資源的上限值，是需要調用getrlimit()即可。

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

第一個參數是資源，有哪些資源呢？

第二個參數是rlimit，rlimit結構是這樣的：

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

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

實際運行的效果如何呢？實踐一下吧！

#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');
} 

運行的結果：

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中對程序進行重定向很簡單，用<和>符號就可以了，但在自己的程序中怎么實現輸入輸出重定向呢？

先來看看Linux內核中，文件（還是設備）是通過哪些數據結構保存的：

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

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

#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;
}

有這樣一種集合，集合元素為長度N（1～31）的二進制串，并且每個二進制串中1的個數小于等于L，求這個集合中第I大的元素是多少？

最開始很天真的想枚舉每個數，計算其中1的個數，結果第8組測試數據開始就超時的不行了。

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

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

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

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階乘的最低非零位上是什么數字。(0 <= N <= 4220)

從1一直乘到N，如果能整除10，就除以10，可以嗎？不行，因為即使去掉低位的0，高位的非0位仍然很大，無法保存下來。

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

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

關鍵代碼如下：

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)數目的郵票組成，求最大的M為多少？郵票最大面值為10000

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

后來改用深搜，優化了許久，最后幾組數組仍然超時，放棄。

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

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

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

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

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

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

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

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

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

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

（做幾何題可真費草稿紙啊，看來以后得學學matlab了，低碳、環保！）

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

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

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

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

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

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

我的思路是：

1、Floyd算出點對最短路徑

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

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

4、枚舉不同連通分量的任意點對a和b，找出以下的最大值

      a所在連通分量的直徑
      b所在連通分量的直徑
      ab的距離 + a到本連通分量最遠距離 + b到本連通分量最遠距離

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

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

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

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

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

一棵樹，每個節點有0或2個孩子，共N個節點，高度為K，問可以組成多少種不同的結構？

假設，當前樹的節點問n，高度為k，那么子樹可分為3種情況：

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

并且，滿足題目要求的樹的節點與高度有這樣的關系：2*k-1 <= n <= 2^k-1，可是根據這個關系枚舉左右子樹的節點數

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

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