| 逝者如斯 |
|
|
| 网志分类 |
|
| 最新评论 |
|
|
|
| 搜索本站 |
|
| 友情链接 |
|
0017461
|
|
|
没有艰难的跋涉 如何成就辉煌
我一直都期望着美好的未来
纵使是现在 我也依然看到 未来那美好的梦
终有一天 会是我 所可以 预见的
因为那不仅是梦~
|
|
Density Map
代号：map
问题描述
在ByteLand上有一块地区，蕴藏了ByteLand上最珍贵的Bit矿物质。科学家们将这块地区划分成了N×N个相同大小的单元格，并对每个单元格进行了考察研究：有的单元格中有丰富的Bit矿物质——科学家用1来标识；有的单元格蕴藏的矿物质很少——科学家用0来标识。
假设用W(i,j)和F(i’,j’)来分别表示两个单元格。那么它们之间的距离被定义为：max(|i - i'|, |j - j'|)，例如W(1,3)和F(4,2)的距离为3。
鉴于可持续发展的思想和开采能力的限制，ByteLand当局计划以一块单元格为中心，开采与中心距离不超过R的所有单元格内的矿藏。为了选定一个合适的单元格作中心，当局希望能够预先了解：以任意一个单元格为中心时，开采量的情况。
于是，当局将一张矿藏地图交给你，上面的N×N个单元格中包含数字0或1。你被要求根据这张矿藏地图，绘制出相应的“矿藏密度图”，分别以每块单元格为中心，计算与中心距离不超过R的所有标识为1的单元格个数。
输入文件
输入文件名：MAP.IN
第一行有两个数字N和R（0<=R<N<=250）。
以下N行，每行N个数字。第i+1行第j个数字为单元格(i,j)的标识——0或1。
输出文件
输出文件名：MAP.OUT
输出文件有N行，每行N个数字。第i行第j个数字表示：与(i,j)距离不超过R的所有标识为1的单元格个数。
样例输入
5 1
1 0 0 0 1
1 1 1 0 0
1 0 0 0 0
0 0 0 1 1
0 1 0 0 0
样例输出
3 4 2 2 1
4 5 2 2 1
3 4 3 3 2
2 2 2 2 2
1 1 2 2 2
不要看小了简单的题目，预处理是很重要di~
经典公式： sum[x2,y2]+sum[x1-1,y1-1]-sum[x1-1,y2]-sum[x2,y1-1]
简化： sum[x2,y2]+sum[x1,y1]-sum[x1,y2]-sum[x2,y1]
|
远野美凤，女配角，有事无事就坐在凳子上吹泡泡。然而，这次她竟然不吹泡泡，玩起骨牌来。如果你没见过骨牌的话，往下看，否则跳过。
每块骨牌有上下两个数（[1..6]），现在共有N（[1..1000]）个骨牌排成一排，我们可以同过旋转某个骨牌180度来改变上下两层数字和的差值。
现在要求的是，至少经过几步操作，我们可以使得上下两层数字和达到最少。
输入的第一行为N。
以下N行，每行两个数Pi Qi 表示最初骨牌的上下两个数。
输出使得上下两行差值最少的最少旋转次数。
输入：
4
6 1
1 5
1 3
1 2
输出：
1
BFS，信不信由你~~
生成达到某值的最小次数，再延展其他状态~
|
代号：PLE
一个蛙人现在拥有一些潜水用的特殊器材。这些器材均为一些圆筒，每一个圆筒中都包含两个部分，一部分装氧气，另一部分装氮气。现在我们给出每个圆筒的氮气和氧气的含量，还有它们的重量，试根据蛙人所需的两种气体的数量计算出蛙人所需携带的最少的重量。
示例：
假设这个蛙人拥有如下5个圆筒，每一个圆筒中氧气、氮气的含量（升）和它的重量都用一行三个整数来表示如下：
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
如果该蛙人需要5升的氧气和60升的氮气，那么它至少需要带2个总重249的圆筒（例如它取第一个和第二个圆筒或第四个和第五个圆筒）。
任务：
请写一个程序：
l 从文本文件PLE.IN中读入圆筒的数目和每个圆筒中氧气、氮气的含量及它的重量；
l 计算为了满足蛙人的需要他所需携带的最少重量；
l 把结果输出到文本文件PLE.OUT中。
注释：我们给出的数据总是保证可以满足蛙人的需要的。
输入格式：
再文本文件PLE.IN的第一行包括用空格分开的两个整数t和a，1 ≤ t ≤ 21且1 ≤ a ≤ 79，表示蛙人所需的氧气和氮气的体积。第二行包括一个整数n，1 ≤ n ≤ 1000，为不同圆筒的数目。以下的n行每行包括一个对圆筒的描述，第i+2行包括三个用空格分开的整数ti、ai、wi，分别表示第i个圆筒中氧气、氮气的含量和该圆筒的重量。
输出格式：
你的程序应该在文本文件PLE.OUT中输出唯一的一个整数，表示为了满足蛙人的要求，它所需携带的最少重量。
样例：
输入（PLE.IN）：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出（PLE.OUT）：
249
f[i,j,k]=min{f[i,j,k-1],f[i-x[k],j-y[k],k-1]}(两个数必须存在)
|
代号：PRZ
现给定n个闭区间[ai, bi]，1 £ i £ n。这些区间的并可以表示为一些不相交的闭区间的并。你的任务就是在这些表示方式中找出包含最少区间的方案。你的输出应该按照区间的升序排列。这里如果说两个区间[a, b]和[c, d]是按照升序排列的的，那么我们有a £ b < c £ d。
任务：
请写一个程序：
l 在文本文件PRZ.IN中读入这些区间；
l 计算满足给定条件的不相交闭区间；
l 把这些区间按照升序输出到文件PRZ.OUT中。
输入格式：
在文本文件PRZ.IN的第一行包含一个整数n，3 £ n £ 50000，为区间的数目。以下n行为对区间的描述，第i行为对第i个区间的描述，为两个整数1 £ ai £ bi £ 1000000，表示一个区间[ai, bi]。
输出格式：
你应该在文本文件PRZ.OUT中输出计算出来的不相交的区间。每一行都是对一个区间的描述，包括两个用空格分开的整数，为区间的上下界。你应该把区间按照升序排序。
样例：
输入（PRZ.IN）:
5
5 6
1 4
10 10
6 9
8 10
输出（PRZ.OUT）：
1 4
5 10
用qsort排序后，把可以并的区域并起来~
|
Symbol辛辛苦苦排好那些树，突然发现他老婆快放工回来了，于是他必须搬回去，他知道自己一个人肯定来不及了，所以就拖来一帮无辜的学生去帮他。Symbol排列树的时候是把他放进一个通道的2边的房间里面（Symbol总共有400个房间）
+----+----+----
+ 1 | 3 | 5
+----+----+----
| 过道 ……
+----+----+----
+ 2 | 4 | 6
+----+----+----
很多树要移动到房间。这些树的大得足以占据整个过道，
所以，当把树从A房间移动到B房间，两个房间之间的过道都会被占用。例如桌子从房间1移到6，则1,2,3,4,5,6房间前面的过道都会被占用，不能作其他用途。
输入：
有多组输入数据，文件第一行为一个表示输入数据总数的整数N，然后是N组输入数据。每组数据的第一行M表示有M组移动树的任务。以下M行每行两个整数I，J，表示把树从房间I移到房间J。(1<=M<=200，1<=i,j<=400大家很惊讶Symbol的家突然变得这么小吧……)
输出：
每组输入都有一行的输出数据，为一整数T，表示完成任务所花费的最小时间。（假设有无限个学生并且可以同时移动树，只要路线不重叠，假设每轮移动都需要10s）
Sample Input
3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50
Sample Output
10
20
30
（对于30%测试文件，n<=50,m<=100
对于50%测试文件，n<=100,m<=150
对于100%测试文件，n<=200,m<=200）
到最后Symbol无聊的一天就过去了……
用贪心做di,若能过的则过~~
|
总算靠别人完成了这个约瑟夫问题，Symbol觉得有点口渴，于是就下楼买可乐，他发现很多人买可乐，而且身高不等。虽然天气不热，但是等这么久也会让人很烦厌的。于是他为了考电脑组那帮学生，想出了一道题目，假设每个人都有不快乐指数，这个指数的数值就是在这个人前面身高比他高的人的个数。正当他准备出这道题目的时候，有很多不同的队列会有同一个不快乐指数总和，现在Symbol郁闷了，他叫你求出有N个人里面不高兴指数总和为K的情况有多少种（假设每个人的身高都是递增的，n个人的身高分别是1..n且各不相同）
输入：
每行2个数n,k，直到0,0结束（0<n<=20,0<=k<=n*(n-1)/2）
输出：
在n个人下不快乐指数为k的一共有多少种情况
Sample Input
2 0
5 3
0 0
Sample Output
1
15
（2个人总不快乐指数为0的情况只有1 2这个情况，而5个人不快乐指数总和为3的情况有，41235，32145……15种）
（对于30%的测试文件，测试数据个数<=100
对于50%的测试文件，测试数据个数<=500
对于100%的测试文件，测试数据个数<=1000）
又是递推time~~
f[n,m]=f[n-1,m]+f[n-1,m-1]+f[n-1,m-2]...+f[n-1,m-n+1]
初始条件:f[0,0]=0 f[1,0]=1
|
问题描述：
GDOI组委会准备举办一次抽奖活动，这次抽奖规则如下：组委会将发行刮奖卡，每张卡片有n个种类的图案，其出现的概率相同，只要筹齐这n种图案就算中奖，某人买了m张卡片，问其能中奖的概率p有多高？
输入格式：
输入文件只有一行，包含两个整数n,m(1<=n,m<=20),分别表示图案的种类与某人买卡片的张数。
输出格式：
输出文件也只有一行，一个实数p,为中奖的概率，答案保留4位小数。
输入样例1：
2 3
输出样例1：
0.7500
输入样例2：
1 2
输出样例2：
1.0000
中奖的方案数f[n,m]=1、f[n-1,m]*n+f[n-1,m-1]*n(n<m)
2、n! (n=m)
3、0 (n>m)
|
给出一列数，从这列数中找出M段不相交的子段，使得这些子段的数的总和最大。特别地，若一子段的数全为负，则这个子段的和为0.
（若两子段x[i..j]与y[i’..j’]不相交，则他们的关系是I<=j<I’<=j’或I’<=j’<I<=j）
输入:
第一行：n, m(1<=n<=100 1<=m<=10,m<=n) n表示数列中有多少数 。
第二行：n个数 每个数的绝对值<=1000
Sample Input
5 2
-5 9 -5 11 20
Sample Output
40
不用说了~~
dp方程：
f [ i , j ]=max{ f [ k , j - 1 ] + sum [ k + 1 ~ i ]}
(j-1<=k<i,且当sum[k+1~i]<0时，sum[k+1~i]=0) |
|
|
|
|
|
|