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))，还是太粗心啦）