博文
位图(2007-08-13 17:18:00)
摘要：
位图
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 50, Accepted users: 43
Problem 10109 : No special judgement
Problem description
现在我们给出一个n×m的单色位图，且该为图中至少含有一个白色的像素。我们用(i, j)来代表第i行第j列的像素，并且定义两点p1=(i1, j1)和p2=(i2, j2)之间的距离为： d(p1, p2)=|i1 - i2| + |j1 - j2|
请写一个程序：
读入该位图；对于每个像素，计算出离该像素最近的白色像素与它的距离。
Input
第一行包括两个用空格分开的整数n和m，1<=n<=182，1<=m<=182。以下的n行每行包括一个长度为m的用0和1组成的字符串，在第i+1行的第j个字符如果为”1”，那么表示像素(i, j)为白的，否则为黑的。
Output
输出一个n×m的数表，其中的第i行的第j个数字为f(i, j)表示像素(i, j)到最近的白色像素的距离。
Sample Input
3 4
0001
0011
0110
Sample Output
3 2 1 0
2 1 0 0
1 0 0 1#include <iostream>
#include <list>
using namespace std;
#define MAX_BIT 200
int gm[MAX_BIT][MAX_BIT];
char gs[MAX_BIT];
class node{
public:
int i,j;
node(int a=0, int b=0):i(a),......
Rare Order(拓扑排序)(2007-08-13 16:54:00)
摘要：/*
Rare Order
Problem description
A rare book collector recently discovered a book written in an unfamiliar language
that used the same characters as the English language. The book contained a short
index, but the ordering of the items in the index was different from what one would
expect if the characters were ordered the same way as in the English alphabet. The
collector tried to use the index to determine the ordering of characters (i.e., the
collating sequence) of the strange alphabet, then gave up with frustration at the
tedium of the task.
You are to write a program to complete the collector's work. In particular, your
program will take a set of strings that has been sorted according to a particular
collating sequence and determine what that sequence is.
Input
The input consists of several blocks. Each block is an ordered list of strings of
uppercase letters, one string per line. Each string contains at most 20 charact......
道路(广搜)(2007-08-12 20:50:00)
摘要：
道路
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 23, Accepted users: 13
Problem 10183 : No special judgement
Problem description
编号为1…N 的N个城市之间以单向路连接，每一条道路有两个参数： 路的长度和通过这条路需付的费用。 Bob和Alice生活在城市1，但是当Bob发现了Alice玩扑克时欺骗他之后，他决定与她翻脸，离开城市1前往城市N. Bob想尽快到达城市N，他是他的钱不多。我们希望你帮助Bob找到一条从城市1到城市N的总费用不超过Bob的承受能力的最短路径。
Input
输入的第1行包含一个整数K, 0 <= K <= 10000, 表示Bob能承受的最大费用；第2行包含一个整数N, 2 <= N <= 100,表示城市的总数；第3行包含整数R, 1 <= R <= 10000,表示道路的条数；接下来的R行，每行用S D L T（以空格隔开）表示一条道路： S：表示道路的出发城市，1 <= S <= N D：表示道路的目标城市，1 <= D <= N L：表示道路的长度，1 <= L <= 100 T：表示通过这条道路需付的费用，0 <= T <=100
Output
仅有的一行中输出总费用小余或等于最大费用K的最短路径的长度。如果这样的路径不存在，则仅仅输出 -1 。
Sample Input
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
Sample Output
11
Problem Source
CSU 1st Contest
//// 狂WA了几次, 原来两城市间可能不止两条道路, 好晕, 第一次用 C++ 写#include <iost......
拼图(2007-08-08 20:19:00)
摘要：
背景 Background
潘帕斯草原最近流行起了一种拼图游戏，@潘帕斯雄鹰为了显示自己是最强的鹰，想尽办法要在这个游戏上赢过其他鹰……
描述 Description
这个拼图游戏要求将一些图形拼成一个正方形，图形的个数从1到5。如下图所示，图形个数是4。
图形不能旋转，拼的时候不能重叠，拼完后的正方形里面不能有空隙。所有给定的图形都要使用。
左面的图表示这样拼不行，右面是一个成功的拼法。
现在，@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰；如果可以，请输出一种完成这个游戏的方案。
输入格式 Input Format
文件的第一行是一个整数n，表示图形的个数，范围从1到5。
接下来有n个部分，每个部分的第一行是2个整数i和j，表示下面的i行j列用来描述一个图形。图形用0和1表示，1表示图形占有这个位置，0表示不占有，中间没有空格。例如上图中图形A的描述是
2 3
111
101
所有图形的长与宽都不超过5。
根据图形给出的顺序给每个图形编号，从1开始，至多到5。
保证数据无多解情况。
输出格式 Output Format
如果不能拼成一个正方形，就输出"No solution possible"；否则，输出一种拼的方案：一个正方形的数阵，每个位置上的数字是占有这个位置的图形的编号，中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4，那么就可以输出
1112
1412
3422
3442
///// 没什么好方法,穷举过了
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 10
int gm[10][10][10]={0},gmfig[1......
Fibnacci string(题库)(2007-08-04 17:56:00)
摘要：Fibnacci string
Problem description
The Fibnacci string is as follows:
S1=b
S2=a
Sk=Sk-1Sk-2 k>2
We are given a string, is there a Fibnacci string?
Input
The input will consist of a series of string, one string per line, followed by a line containing only the char ‘0’ that signals the end of the input file and need not to be processed.
You may assume that the length of each string is no more than 1,000,000.
Output
For each string you should output the ‘true’ if the string is a Fibnacci string, or ‘false’ if the string is not a Fibnacci string and with one line of output for each line in input.
Sample Input
abaab
abaababa
abaababaababa
0
Sample Output
true
true
false
//友情提示，请注意 a, b my code as followed :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char gstr[1000010],str[1000010];
int gm[34];
void Init(){
int t,i,j;
for(i......
合唱队形(2007-07-30 17:35:00)
摘要：合唱队形
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
Input
输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
Output
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
Sample Input
8
186 186 150 200 160 130 197 220
Sample Output
4
/////////////////////////////////////////////////////////////////////////////////////////
解题方法：Dp 设三个数组，其中一个用于保存身高，另外两个保存子状态。 up[n]表示身高一直按升序排列时，从第一个人到 第 n 个人合法排列的最大人数。down[n]表示混合的即可以从中间某个位置降序。
假如输入数据为：
4
3 4 1 2
up[] = {1,2,1,2}, down[] = {1,1,3,3}
至少需要 n - max(up[],down[]), 即 4 - 3 = 1
测试数据：
8
186 186 150 200 160 130 197 220
5
1 2 3 4 5
6
1 3 2 4 2 1
结果：
4
0
1
///////////////////////////////////////////////////////////////////////////////////////......
青蛙过河(DP加状态压缩)(2007-07-30 10:20:00)
摘要：
以前写代码都不写解题报告，从现在开始对于比较难的题都提供解题报告
一方面自己以后好查阅，一方面供网友理解学习交流。
---- 江南孤峰 ----
2007--7--30
下面这题调试了很久，主要是状态压缩出错，最后到网上找到了测试数据，终于
AC了，而且还是最优的代码，冲这点，我觉得发点时间写份详细的报告，值得。
代码真的是调试出来的！！！
/////////////////////////////////////////////////////////////////////
青蛙过河
Problem description
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子
青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以
把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定
青蛙要想过河，最少需要踩到的石子数。
Input
输入的第一行是一个整数T,测试数据的组数。对于每一组测试数据，第一行是一个正整数
L（1 <= L <= 10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
Output
对于每一组测试数据，输出一行只包括一个整数，表示青蛙过河最少需要踩到的石子数。
Sample Input
1
10
2 3 5......
典型DP(2007-07-28 20:38:00)
摘要：ct5_2: 跳棋★★
题目描述：
水平方向上有n个格子，格子上写着1到n的数字中的一个，
游戏规则是：走到某一格，上面的数字假如是s，
则可以选择跳到第s个格子或者前进一格，
问你最少要走多少步才能到达最后一格并且返回起点。
如：3 5 3 2 6 5 ，你去的时候可以一步一步到终点(5步)，
也可以一开始就跳到第三格，再一步一步到终点(4步)，
或者先前进一步再跳到第5格再一步一步地走(3步)，
最少是3步到达。然后要再返回的时候，最少步数的走法是，
左移两步再跳到第二格再左移一步(4步)，共7步。
输入：
多组测试数据，第一行是一个整数n(1<=n<=1e5)，
第二行是n个整数，表示对应的格子上写着的数。
当n输入为0的时候结束。
输出：
输出最少所需要的到达终点再返回原点的总步数
样例输入：
6
3 5 3 2 6 5
0
样例输出：
7
//////// 写了下面的东西，干脆就帖出来了
ct5_2 解题DP方法
例如数据：
6
3 5 3 2 6 5
设两个数组： data[] = 3 5 3 2 6 5
另设一个用于DP Dp[],Dp[n]表示从n位置到达终点需要走的最少的步数
首先，从终点 n=6 开始，终点到终点需要 0 步,所以设Dp[6]=0
然后n--,即 n=5，n=5到达终点需要 1 步，设Dp[5]=1
到此Dp[]数组初始化完毕 n--,此时 n=4
因为 data[4] <= 4 因此这里不能往终点方向跳
只能向前一步,Dp[4] = Dp[5]+1 = 2
同里Dp[3] = Dp[4]+1 = 3
Dp[2]，因为data[2] = 5 > 2 所以可以跳到第五个位置，这里需要决策，从
两种方法里选一种，如果往前一步，则到达终点最少需要 Dp[3]+1 = 4 步
而跳到第五个位置，则需要 Dp[5]+1= 2,显然选择 Dp[2] = Dp[5]+1 = 2
同理Dp[1]=Dp[2]+1 = 3;
因此从起始点到终点最少需要 Dp[1] = 3 步
从终点回到起点是一样的方法。
data[] = 3 5 3 2......
组合(2007-07-21 00:26:00)
摘要：题目描述：
列出C(a,b)的所有组合
输入：
多组测试数据，每组一行有两个数字a和b(1<=b<a<=30)
输入的a=b=0的时候结束。
输出：
输出从1到a的数中选出b个数的所有组合，一行输出一个组合，
每个组合里的数从小到大排列，各组之间按字典顺序从小到大
排列。
样例输入：
5 2
0 0
样例输出：
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
#include <stdio.h>
void putout(int s[],int b){
int i;
for(i=1; i < b; i++)
printf("%d ",s[i]);
printf("%d\n",s[i]);
}
int main(){
int a,b,s[32],i;
while(scanf("%d %d",&a,&b)!=EOF){
if(a==0 && b==0)
break;
for(s[0]=i=1; i<=b; i++)
s[i]=i;
for(i--; i>0; ){
if(i==b)
putout(s,b);
if(s[i]+1+b-i > a){
if(i==1)
break;
for(;i>1 && s[i-1]+2+b-i>a;i--)
;......
滑雪（DP）(2007-07-10 18:18:00)
摘要：滑雪★★★★
Description
Michael喜欢滑雪但这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input
多组测试数据。输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output
25
解题报告：
对于 4*4 矩阵:
a1 a2 a3 a4
b1 b2 b3 b4
c1 c2 c3 c4
d1 d2 d3 d4
假如我们从某个点开始滑，可以向它周围的四个点中的某个高度小于该点的
点滑过去，对于某个点，如果从它周围的四个点开始滑的最优值已经求出，
则该点的最优值就是在四个点中所有高度比它小的点最优值最大的那个加一
我们可以设两个数组，一个用于保存原来的高度，另外一个用于记录从该点
开始滑的最优值
比如，假设高度值矩阵如下：
1 2 5 3
14 2 5 6
14 2 56 3
1 7 8 9
最优值矩阵初始化如下：
0 0 0 0......