久久久久久久久波多野高潮,狠狠综合久久综合88亚洲,东方aⅴ免费观看久久av

quxiao — Fri, 18 Feb 2011 13:55:00 GMT

�q�程在运行时�Q�会占用计算机的各种资源�Q�比如CPU旉��、内存、文件等�{�。但是，�q�程是不可以占用无限多的资源的，操作�pȝ��会给�q�程讑֮�所使用资源的上限。想获取�q�些资源的上限��|��是需要调用getrlimit()卛_��?/p>

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

�W�一个参数是资源�Q�有哪些资源呢？

资源	�_�略含义
`RLIMIT_AS`	�q�程可��用的内存的最大�?/td>
`RLIMIT_CORE`	核心文�g(core file)的最大�?/td>
`RLIMIT_CPU`	CPU旉��最大�?/td>
`RLIMIT_DATA`	数据�D�（已初始化数据+未初始化数据+堆）的最大�?/td>
`RLIMIT_FSIZE`	新徏文�g的最大字节数
`RLIMIT_LOCKS`	持有的锁的最大数
`RLIMIT_MEMLOCK`	锁定内存的最大字节数
`RLIMIT_NOFILE`	打开文�g的最大数�?/td>
`RLIMIT_NPROC`	每个实际用户(real user)的最大子�q�程数目
`RLIMIT_RSS`	RSS(Resident Set Size)的最大字节数
`RLIMIT_SBSIZE`	socket buffer的最大字节数
`RLIMIT_STACK`	�q�程栈的最大字节数
`RLIMIT_VMEM`	与R`LIMIT_AS含义一�?/tt>`

�W�二个参数是rlimit�Q�rlimit�l�构是这��L��Q?/p>

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

其中含有软限制和��限制。超�U�用户可以增加硬限制�Q�一般用户可以降低硬限制�Q�但不能增加��限�Ӟ��一般用戯��可修改��Y限制�Q�但修改的��Y限制不能��过��限制�?/p>

实际�q�行的效果如何呢�Q�实践一下吧�Q?/p>

#include 
#include 

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

�q�行的结果：

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

quxiao 2011-02-18 21:55 发表评论

Linux API 实践�Q�输入输出重定向

quxiao — Wed, 16 Feb 2011 11:53:00 GMT

在shell中对�E�序�q�行重定向很��单，�?lt;�?gt;�W�号��可以了�Q�但在自��q��E�序中怎么实现输入输出重定向呢�Q?/p>

先来看看Linux内核中，文�g�Q�还是设备）是通过哪些数据�l�构保存的：

每个�q�程都保存一份文件描�q�符的表��|��每一行又指向file table�Q�然后file table再指向v-node table。v-node table我们可以暂不考虑�Q�暂且把它当作文件的内容。而从process table entry中的file pointer可以指向不同或者相同的file table。原本标准输入输出是指向“键盘”和“屏�q�”这两个讑֤�的，如果可以��它们指向我们指定的文�g�Q�就可以实现重定向了�?/p>

先用open()打开需要重定向到的文�g�Q�获取去文�g描述�W�fd�Q�在用dup2()把进�E�中原先的输入输出文件描�q�符STDIN_FILENO和STDOUT_FILENO重定向至fd�Q�这样就可以实现输入输出重定向了。我惻I��shell实现重定向也应该是类似的思想�Q�关键代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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

quxiao 2011-02-16 19:53 发表评论

USACO Section 3.2 Stringsobits

quxiao — Wed, 16 Feb 2011 05:06:00 GMT

有这样一�U�集合，集合元素为长度N�Q?�?1�Q�的二进制串�Q��ƈ且每个二�q�制串中1的个数小于等于L�Q�求�q�个集合中第I大的元素是多��？

最开始很天真的想枚�D每个敎ͼ�计算其中1的个敎ͼ��l�果�W?�l�测试数据开始就��时的不行了�?/p>

枚�D不行�Q�来试试构造可不可以，假设我们有一个长度�ؓn�Q?个数<=l的二�q�制串的集合�Q�那么怎么把它们从大到��区分呢�Q�我们一位一位来�Q�根据第n位，可以��集合划�?部分�Q�第n位是0的，�W�n为是1的。好了，递推式突然就变得很明显了。如何设num[N][L]为长度�ؓN�Q?个数��于�{�于L的二�q�制串的个数�Q�那么：

num[N][L] = num[N-1][L] + num[N-1][L-1]
�Q�第n位是0�Q?nbsp; �Q�第n位是1�Q?/p>

个数有了�Q�那么第I个数是多��怎么求呢�Q�说来也��单，��是用递归的思想�Q�看I落在num[N-1][L]和num[N-1][L-1]的哪一部分�Q�看下面的代码应该就明白了：

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]);
     }
}

quxiao 2011-02-16 13:06 发表评论

USACO Section 3.2 Factorials

quxiao — Mon, 14 Feb 2011 07:30:00 GMT

问你N阶乘的最低非零位上是什么数字�?0 <= N <= 4220)

�?一直乘到N�Q�如果能整除10�Q�就除以10�Q�可以吗�Q�不行，因�ؓ即��L��低位�?�Q�高位的�?位仍然很大，无法保存下来�?/p>

可以��N!�q�样表示�Q?
N! = 2^K * 5^L * V(N)
= 2^(K-L) * V(N) * 10^L ( K >= L 如何证明呢？)

10^L不媄响N!最低非零位�Q�这个数�?K-L)以及V(N)的个位数所军_��。K和L�Ҏ��得到�Q�V(N)的个位数也好得到�Q�只要枚举i�Q�从1到N�Q�，去除因子2�?�Q�因子个数加到K和L�Q�，��其个位��C��以中间结果就可以了�?/p>

关键代码如下�Q?/p>

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);

quxiao 2011-02-14 15:30 发表评论

USACO Section 3.1 Stamps

quxiao — Sat, 12 Feb 2011 03:59:00 GMT

有N(1<=N<=50)�U�不同面值邮��，��p��些邮��组成面�?～M�Q?�?、……、M每种面值均�׃��过K(1<=K<=200)数目的邮��组成，求最大的M为多��？邮票最大面��gؓ10000

一开始想到DP�Q�数�l�canComprise[10000*200][200]�Q�canComprise[i][j]表示用j张邮��是否可以组成面值i�Q�但数组太大�Q�放弃�?/p>

后来改用深搜�Q�优化了�怹��Q�最后几�l�数�l�仍然超�Ӟ��攑ּ��?/p>

又回头想DP�Q�如果canComprise[i][j1]和canComprise[i][j2]均�ؓtrue�Q�j1 < j2�Q�那么canComprise[i][j1]肯定是更优的解，因�ؓj1可以扩展更多i+stamps[x]。所以，只要用一�l�数�l�保存答案就可以了，比如minStamp[i] = j��p��C�组成i所用到的最��邮��数为j�Q�递推式很�Ҏ��惛_��Q?/p>

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

同一�U�情况，表达解的方式可能有多�U�，��量使用最�_��的方式，已达到降�l�的效果�?/strong>

quxiao 2011-02-12 11:59 发表评论

USACO Section 3.1 Shaping Regions

quxiao — Tue, 01 Feb 2011 12:55:00 GMT

一道几何题�Q�解��x��法很�Ҏ��惛_��Q�不�q�要�l�心�?/p>
随着输入的顺序，��矩形一个个攑օ�集合�Q�如果新的矩形与集合中的旧矩形相交，��将旧矩形分解，删除旧矩形，攑օ�新矩形和分解的矩形�?/p>
讄��形R1、R2�Q�宽和高分别�?W1, H1)�?W2, H2)�Q�两矩�Ş中心坐标分别�?X1, Y1)以及(X2, Y2)。判断两矩�Ş是否�怺��Q�也��是是否有面�U�相重合�Q�，��q��两矩形中心坐标的竖直和水�q��L��否小于两矩�Ş高的和的一半以及两矩�Ş宽的和的一半。即�Q?/p>
( |X1 - X2| < (W1 + W2) / 2 ) && ( |Y1 - Y2| < (H1 + H2) / 2 )

如果条�g满��Q�R1和R2即相交�?/p>
那相交会有几�U�情况呢�Q�我惛_��?6�U�：

�Ҏ��不同的情况，可以��原来的矩�Ş分解�?�?个小矩�Ş�Q�这样就可以解出来了�?/p>
�Q�做几何题可真费草稿�U�啊�Q�看来以后得学学matlab了，低碳、环保！�Q?/p>
另外�Q�USACO�q�有一�U�解法，��是��矩形的四条边进行离散化处理�Q�将�U�段排序�Q�然后再依次扫描�Q�大体思�\是这��L��Q�具体细节没怎么看�?/p>

quxiao 2011-02-01 20:55 发表评论

USACO Section 3.1 Humble Numbers

quxiao — Sun, 30 Jan 2011 08:59:00 GMT

最直接的想法是枚�D每个敎ͼ�看是否能用S中的元素��其分解�Q�但1<=N<=100000�Q�第N个数肯定会很大，�q�样做肯定超�Ӟ��攑ּ��?/p>
后来惛_��用STL中的set来解冻I��枚�D某一个数�Q�如果属于set�Q�将其与S中各元素�怹�的数攑օ�set�Q�如此��@环，直至扑ֈ��W�N个数�Q�提交后�q�是��时。看来即便是set�Q�毕竟存取的效率不是O(1)�Q�性能�q�是有媄响�?/p>
�H�然惛_��Q�这题不是跟poj�?a target="_blank">Ugly Number挺像的嘛�Q�是Ugly Number的加强版。具体思想是：对于S中的每个元素p[i]�Q�设�|�一个下标pIdx[i]�Q�pIdx[i]指向humble number数组。进行N�ơ��@环，每次扑և�最��的p[i] * humble[pIdx[i]]�Q�将该数加入humble数组�Q�然后pIdx[minIdx]++。这样就能由��到大找出第N个humble number了�?/p>
PS�Q�其实这�U�方法生成的humble number只能保证非降序，比如2×3�?×2��׃��生成相同的humble number�Q�这�U�情况要排除�?/p>

quxiao 2011-01-30 16:59 发表评论

USACO Section 2.4 Cow Tours

quxiao — Tue, 25 Jan 2011 14:03:00 GMT

一个图�Q�有臛_��2个连通分量，用分别属于不同连通分量的点对��这两个�q�通分量连接，使其“直径”最��，问最��直径�ؓ多少。（直径的定义�ؓ�q�通分量中点对的最短�\径中最长的路径�Q?/p>
我的思�\是：

1、Floyd��出点对最短�\�?/p>
2、深搜找��Z��同连通分�?/p>
3、枚丑֐�一�q�通分量中的点�Ҏ��短�\径，最大的作�ؓ该连通分量的直径�Q�顺便算��Z��点到�q�通分量中最�q�点的距��?/p>
4、枚举不同连通分量的��L��点对a和b�Q�找��Z��下的最大�?/p>
      a所在连通分量的直径
      b所在连通分量的直径
      ab的距��?+ a到本�q�通分量最�q�距��?+ b到本�q�通分量最�q�距��?/p>
5、找��些最大��g��的最��?/p>

quxiao 2011-01-25 22:03 发表评论

USACO Section 2.3 Controlling Companies

quxiao — Sat, 22 Jan 2011 08:23:00 GMT

明明是一道难度不大的题，我却做了N天才做出来，惭愧惭愧�Q�看到题的第一��x��是如果A控制了B�Q�就把B所占有的股份传�l�A以及A的母公司�Q��ƈ且这样递归下去。可自己�~�程会发生股份重复计��的情况�Q�解��x��法是当将B的股份更新到A上时�Q�通过母公司的关系扑ֈ�A�Q�，如果之前A已经直接或间接控制了B�Q�那么如果再加就��是重复计算了。但在判断A是否直接或间接控制B�Ӟ��又要判断是否有环�?/p>
后来在网上找��C��一�U�解法：当发现A控制B�Ӟ��B的股份传�l�A�Q�如果发现增加股份之后，A中的股䆾[A][i] > 50 �q�且A�q�没有控制i�Q�则��?A, i)加入队列。一直��@环操作，直至队列为空为止�?/p>
官方的解题报告中�Q�其实就是我一开始想的递归的方法，他在更新�Q�A, B�Q�时�Q?/p>

如果A已经控制B�Q�退�?
若没有，control[A][B] = 1
��B的股份传�l�A
枚�D已控制了A的i�Q�递归更新�Q�i, B�Q?
枚�DA的股份[A][k]�Q�如果大�?0�Q�递归更新�Q�A, k�Q?/li>

quxiao 2011-01-22 16:23 发表评论

USACO Section 2.3 Cow Pedigrees

quxiao — Mon, 10 Jan 2011 12:02:00 GMT

一��|��Q�每个节�Ҏ��0�?个孩子，共N个节点，高度为K�Q�问可以�l�成多少�U�不同的�l�构�Q?/p>
假设�Q�当前树的节炚w��n�Q�高度�ؓk�Q�那么子树可分�ؓ3�U�情况：

左子树高度�ؓk-1�Q�右子树高度�?～k-2
叛_��树高度�ؓk-1�Q�左子树高度�?～k-2
左右子树均�ؓk-1

�q�且�Q�满��题目要求的树的节点与高度有�q�样的关�p�：2*k-1 <= n <= 2^k-1�Q�可是根据这个关�p�L��丑ַ�叛_��树的节点�?/p>
于是��可以用递归+DP的方法解��道题了�?/p>
�Q�在对n <= 2^k-1�q�行转化�Ӟ��自己居然写成了k >= log(n+1.0)/log(2.0)�Q�其实应该是k >= floor (log(n+1.0)/log(2.0))�Q�还是太�_�心啦）

quxiao 2011-01-10 20:02 发表评论