passzh的博客
passzh · 共 16 篇文章
0-1背包问题
在动态规划中,有一类经常出现的问题,即0-1背包问题。所谓0-1背包问题,即有n个物品,其每个背包的价值为vi(1<=i<=n),每个物品的重量为wi(1<=i<=n),背包能够放的总重量为c,求放哪几个物品使得物品的总价值最大。 很明显,物品要么放进背包,要么不放进。故称为0-1背包。 我们假设放进了m个物品{x1,x2,...,xm},那么它是满足最优子结构的,即如果这是问题的最优解,那么{x2,...,xm}一定是问题c-wx1的最优解。所以,这道问题可以用动态规划进行求解。 我们可以定义一个数组m*,用它表示背包容量为j,可选物品为i,i+1,...,n时背包问题的最优值。那么我们可…
2012-08-08T09:32:41Z · 编程语言 · 评论(0)
Digital Roots
题目的链接为: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1028 题目为: Digital Roots 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:329 测试通过:112 描述 The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit the…
2012-05-11T17:33:36Z · 编程语言 · 评论(0)
拙作几首
《偶得》 风吹杨柳飘轻絮,雨打春江满目愁。 两处相思催人老,转眼青丝尽白头。 《落花》 庭院深深伴孤身,清酒月下忘世纷。 醉卧芍药不觉晓,一夜红泪尽沾身。 《桃源》 幽涧曲径何处访,清月千年笼寒沙。 东晋仙翁应不在,辜负流水待落花。 《浮生如梦》 坐听风吹竹,笑看暮合昏。 醉眼观世事,杯酒祭乾坤。 《夜雨》 寒雨打窗楞,凉意入薄衾。 孤枕梦难成,一夜到天明。 《红梅》 点点猩红染虬枝,冷香徐放报春知。 傲雪凌寒铮铁骨,何惧风雪夹击时。 《景》 萧风凄清湘水寒,雾霭迷蒙月色残。 冷涛幽咽轻推岸,多情谁人独凭栏。
2012-05-10T14:00:56Z · 非技术 · 评论(0)
哈夫曼编码与译码
题目的链接为: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1022 题目的描述为: 哈夫曼编码与译码 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:343 测试通过:123 描述 已知电文包括的字符集为{A,C,I,M,N,P,T,U},输入对应权值,对字符集合进行哈夫曼编码,完成电文的哈夫曼编码与译码工作。 输入 共三行: 第一行为对应字符集{A,C,I,M,N,P,T,U}的权值 第二行为一段字符串表示的电文(长度不超过1000); 第…
2012-05-09T19:45:54Z · 编程语言 · 评论(0)
二叉树复制和左右子树互换
题目的地址: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1021 题目的描述: 二叉树复制和左右子树互换 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:272 测试通过:174 描述 二叉树是非常重要的树形数据结构。复制一棵二叉树是在另一个存储区存放相同的结构和内容,而一棵二叉树上所有左右子树互换是在原存储区上的运算。 请分别根据先序遍历序列建立两棵的二叉树(用#代表空树或空子树),再将这两棵二叉树复制为左右子树建立第三棵二叉树,输出先序和…
2012-05-07T17:45:58Z · 编程语言 · 评论(0)
乘积最大
题目的链接为: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1017 题目的描述为: 乘积最大 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:228 测试通过:100 描述 今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友XZ也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目: 设有一个长度为N的数…
2012-05-07T15:03:00Z · 编程语言 · 评论(0)
Sleep less leads to gain more fat
Today I have read a unbelievable news that less sleep may leads to gain more fat. In traditional opinon,a man who usually feel fatigue and do many works may looks very thin. The news points out that the sleep habit may affects a man's look including his weight. So I must persist sleep more than 7 h…
2012-05-03T23:13:24Z · 非技术 · 评论(0)
数的计算
题目的链接: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1010 题目的描述: 数的计算 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:531 测试通过:162 描述 要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理: 不作任何处理; 在它的左边加上一个自然数,但该自然数不能超过原数的一半; 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 输入 一个自然…
2012-05-03T15:40:59Z · 编程语言 · 评论(0)
2的N次方
题目的链接为: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1009 题目为: 2的N次方 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:999 测试通过:500 描述 编程精确计算2的N次方。(N是介于100和1000之间的整数)。 输入 正整数N (100≤N≤1000) 输出 2的N次方 样例输入 200 样例输出 1606938044258990275541962092341162602522202993782792835301376…
2012-05-02T17:17:08Z · 编程语言 · 评论(0)
第几天
题目的链接为: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1008 题目为: 第几天 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:899 测试通过:237 描述 在我们现在使用的日历中, 闰年被定义为能被4整除的年份,但是能被100整除而不能被400整除的年是例外,它们不是闰年。例如:1700, 1800, 1900 和 2100 不是闰年,而 1600, 2000 和 2400是闰年。 给定公元2000年1月1日后的某年某月某日(包括2…
2012-05-02T16:32:09Z · 编程语言 · 评论(0)
多项式乘法
题目的链接为: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1006 题目为: 多项式乘法 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:171 测试通过:77 描述 线性表是一种最简单、最基本,也是最常用的数据结构,其用途十分广泛,例如,用带表头结点的单链表求解一元整系数多项式加法和乘法运算。 现给两个一元整系数多项式,请求解两者的乘积。 输入 两组数据,每一组代表一个一元整系数多项式,有多行组成,其中每一行给出多项式每一项的系数和指数,这…
2012-05-02T14:25:19Z · 编程语言 · 评论(0)
多项式加法
题目的链接为 http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1005 题目如下: 多项式加法 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:964 测试通过:100 描述 线性表是一种最简单、最基本,也是最常用的数据结构,其用途十分广泛,例如,用带表头结点的单链表求解一元整系数多项式加法和乘法运算。 现给两个一元整系数多项式,请求解两者之和。 输入 两组数据,每一组代表一个一元整系数多项式,有多行组成,其中每一行给出多项式每一项的系数和指数,这…
2012-05-02T13:44:56Z · 编程语言 · 评论(0)
线性表的操作
题目的链接地址为: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1004 题目为: 线性表操作 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:1610 测试通过:340 描述 线性表是n个元素的有序集合(n³0),n是线性表中元素的个数,称为线性表的长度。可以用一组地址连续的存储单元依次存储线性表中元素,采用这种存储方式的线性表称为顺序表。 请在顺序表上实现运算,实现顺序表的逆置,删除表中所有元素值等于x的元素。 输入 三组数据,顺序表元素类…
2012-05-02T10:47:00Z · 编程语言 · 评论(0)
POJ1611解题报告
The Suspects Time Limit: 1000MS Memory Limit: 20000K Total Submissions: 14274 Accepted: 6780 Description Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy i…
2012-04-27T22:46:46Z · 编程语言 · 评论(0)
并查集
并查集是一种比较有用的数据结构,主要是用于解决将一些元素合并和查找元素在某个集合的操作,即union操作和findSet操作。 其中,利用有根树实现并查集的方法是普遍使用的方法,也是效率最优的方法。 在并查集一开始时,每个元素做为一个单独的集合,即每个都是只含有一个根的子树。 在合并的时候,主要是采用按秩合并。在开始时,每个元素的秩为0,随着合并秩发生变化。 其中包括makeSet方法,即初始化集合的方法。我们用p 表示元素i所属的集合的祖先(即此集合的标识),用rank 表示元素i的秩。 //初始化并查集 void makeset(int i) { p[i]=i; } 接着就是合并操作: …
2012-04-27T20:45:20Z · 编程语言 · 评论(0)