博文
判断线段与矩形是否相交(2007-09-05 18:05:00)
摘要：
Intersection
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
You are to write a program that has to decide whether a given line segment intersects a given rectangle.
An example:
line: start point: (4,9)
end point: (11,2)
rectangle: left-top: (1,5)
right-bottom: (7,1)
Figure 1: Line segment does not intersect rectangle
The line is said to intersect the rectangle if the line and the rectangle have at least one point in common. The rectangle consists of four straight lines and the area in between. Although all input values are integer numbers, valid intersection points do not have to lay on the integer grid.
Input
The input consists of n test cases. The first line of the input file contains the number n. Each following line contains one test case of the format:
xstart ystart xend yend xleft ytop xright ybottom
where (xstart, ystart) is the start and (xend, yend) ......
上台阶(2007-09-04 22:38:00)
摘要：上阶梯★★★
上阶梯，你可以一个一个阶梯上，也可以两个两个地来，也可以一个和二个间隔着上，甚至可以一次k个
阶梯
问题是，上一个阶梯数为n，每步能上1至k个阶的话，你有多少种方法走完它？
如 n = 5 , k = 2，可以
1,1,1,1,1
2,1,1,1
1,2,1,1
1,1,2,1
1,1,1,2
2,2,1
2,1,2
1,2,2
共8种
输入阶梯数n(1 <= n <= 30)和每步最大阶数k(1<=k<=n)：
5 2
5 3
输出：
8
13
解题报告：不记得什么时候写的程序了，当时写了个简单思路“斐波那弃序列变种” ，现在自己看了十几分钟才弄明白。因此写个详细的报告，以备不时之需：我们先看下 k=2 的情况，设 f(n) 表示走完台阶数为 n 的方法如果n = 1， 显然 f(1) = 1如果n = 2，台阶: 1 1 我们的走法是 f(1) 1, 2, 即若最后一步走一步则走法是 f(1) , 还有两个台阶 一步走完又是一种方法，所以 f(2) = f(1)+1 = 2;如果n = 3，同 2 我们有 f(3)=f(2)+f(1),即最后一步走一个台阶就是 f(2), 另外最后一步走两个台阶 则为 f(1), 因为k=2,最后一步不能超过 2，因此 3 2 的走法就是 f(3) = f(2)+f(1)。一般的 n = m 我们有 f(m) = f(m-1)+f(m-2) (m>=3) 即 k=2 时为正中的斐波那弃序列。
通常的 n k ,我们防上面的方法: 有 f(m) = f(m-1)+f(m-2)+ ... + f(m-k)
证明：显然 f(1) = 1 如果 k>=2 则 f(2) = 2, 如果 k>=3 , 则 f(3) = f(2)+f(1)+1 表示最后一步分别走 1，2，3个台阶。 我们按最后一步的走法即可得上面的公式：
f(m) = f(m-1)+f(m-2)+ ... + f(m-k) (m>k)
// 下面是实现代码 f(n) 的值记录在 数组 a 中了
#include <stdi......
编写易于理解的代码(2007-09-04 20:35:00)
摘要：
》》》》》》》转自： CSDN， 编程风格是值得一再强调的，因此特转载此篇文章。对于一名开发人员，时间是最宝贵的资源。本文所要介绍的这六种编写可维护代码的方法可以保证让您节省时间和少受挫折：在编写注释上多花一分钟，会让您少受一小时研读代码的痛苦折磨。
》》》》》》》一般衡量代码的顺序为： 正确性，可读性，可维护性，高效性，无论哪个领域正确性都是必不可少的，可能有的领域更强调高效性，可读是可维护的前提，可维护的代码，容易扩充，容易升级。这方面比较好的书是，《代码大全》。
我学习编写、改善和维护代码的过程是很艰苦的。在过去的 12 年里，我一直在编写计算机游戏并通过曾红极一时的共享软件技术进行网络销售，并以此为生。这就是说，我常常要从空白的屏幕开始从头编码，当代码达到数万行之后才能拿去销售。
这也就是说，如果我出了错，我必须要自己去解决问题。当我在凌晨三点还在竭力寻找 bug 的时候，看着这些不知所云的晦涩代码，我不禁自问：“我的天啊，这些垃圾代码究竟是哪个笨家伙写的啊？”，很不幸，问题的答案是 “我”。
在学习了良好、正规的编码技巧之后，我大受其益。本文就包括了其中的一些实践。具有丰富经验的资深程序员大都对这些内容烂熟于心。他们可以通过本文优美的散文式的介绍再重温一遍，并可回顾一下在采取清晰编码的理念之前，编码是多么地令人头痛。
但更多的人会如同我一样，是无意间跌跌绊绊地闯入编程领域的，而且没有人为其灌输这些编程技巧和理念。本文所要介绍的这些内容对很多人来说也许很基础，但对于其他人来说却是极为宝贵的资源，因为之前没有人告诉过他。所以，如果您不想走弯路，那么本文将非常适合您。
示例
为了便于解释，本文全篇都将使用一个示例太空游戏程序，称为 Kill Bad Aliens。在这个游戏中，您将通过键盘来控制一个宇宙飞船，它可以在屏幕底端水平向前或向后移动，还可以向上发射子弹。
图 1. 我们的假想游戏
游戏发生在称为 Wave 的各个时间段。在每个 wave，外星人都会一个接一个地出现在屏幕顶端。它们到处飞，还会投掷炸弹。外星人将按固定时间间隔出现。在杀死一定数量的外星人之后，一个 Wave 就告结束。
杀死一个外星人会给您加分。当结束一个 wave 时，根据您完成游戏所需时间的长短还会有额外的分数奖励。 ......
浮点数精度问题(2007-09-04 19:52:00)
摘要：
Exact Change Only
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem 10838 : No special judgement
Problem description
Boudreaux reached over and shook awake Thibodeaux, who had dozed off somewhere in New Mexico. "Where we at?" Thibodeaux groggily yawned.
"Not in Vegas, I gua-ran-tee, but could you get my knapsack?" Boudreaux asked, gesturing to the worn, leather backpack in the back seat of their cherry red Ford Miata.
"Why, is there a problem?"
"Just hand me my knapsack, problem or not."
Thibodeaux complied, glancing up as Boudreaux slowed the car to a stop in a line of vehicles approaching a toll booth. "$1.65 -- Exact change only," Thibodeaux read the yellow sign on the front of a small wooden building occupied by a lone toll booth operator. "I have to get $1.65 in exact change?" Thibodeaux asked, digging through the knapsack, "all I have are ten quarters, four dimes, and three pennies. I don't have any nickels . . ......
Wooden Sticks (STL use)(2007-09-03 19:13:00)
摘要：
Wooden Sticks
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l<=l' and w<=w'. Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are......
Marbles in Three Baskets（广搜）(2007-09-03 01:26:00)
摘要：
Marbles in Three Baskets
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 15, Accepted users: 13
Problem description
Each of three baskets contains a certain number of marbles. You may move from one basket into another basket as many marbles as are already there, thus doubling the quantity in the basket that received the marbles. You must find a sequence of moves that will yield the same number of marbles in the three baskets. Moreover, you must achieve the goal in the smallest possible number of moves. Your program must also recognize the case in which there is no such sequence of moves.
Input
Each line of the input file will contain data for one instance of the problem: three positive integers, with one blank space separating adjacent integers. The three integers represent the initial numbers of marbles in the three baskets. The sum of the three integers will be at most 60.
Output......
Permutation Recovery(2007-09-02 21:04:00)
摘要：
Permutation Recovery
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Problem description
Professor Permula gave a number of permutations of the n integers 1, 2, ..., n to her students. For each integer i (1 <= i <= n), she asks the students to write down the number of integers greater than i that appears before i in the given permutation. This number is denoted ai. For example, if n = 8 and the permutation is 2,7,3,5,4,1,8,6, then a1 = 5 because there are 5 numbers (2, 7, 3, 5, 4) greater than 1 appearing before it. Similarly, a4 = 2 because there are 2 numbers (7, 5) greater than 4 appearing before it.
John, one of the students in the class, is studying for the final exams now. He found out that he has lost the assignment questions. He only has the answers (the ai's) but not the original permutation. Can you help him determine the original permutation, so he can review how to obtain the answers?
Input
The input......
Campaign Stops （拉票）(2007-08-28 16:24:00)
摘要：
Campaign Stops
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 18, Accepted users: 15
Problem 10924 : No special judgement
Problem description
One of the important parts of running an election year campaign is to go lots of places, give your carefully crafted stump speech, and convince a lot of potential voters to vote for you. Unfortunately, there are only so many hours in the day, so you cannot go everywhere. So you need to plan your campaign trips carefully, trading off between travel time, time spent at the stops, and the number of voters you are going to sway. Better have a computer do the planning for you.
We assume that for each potential campaign stop, you are given the number of voters you expect to sway by appearing there, and the number of hours you would have to spend at the location. In addition, for each pair of stops, you are given the travel time ......
角色扮演（湖南省第二界程序设计赛题）(2007-08-28 16:07:00)
摘要：
角色扮演
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 26, Accepted users: 8
Problem 10845 : No special judgement
Problem description
某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你,“你研究研究剧本，看最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求：
1 男演员只能演男角色，女演员只能演女角色。
2 角色的扮演者确定下来后，在演出的过程中就不能中途更改。
3 如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。
导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。
Input
输入文件的第一行包含用空格分隔的3个正整数，M, F和S。
其中M代表剧中的男角色数目，取值在[1, 10]之间；
F代表剧中的女角色数目，取值在[1, 10]之间；
S代表剧中的场景数目，取值在[1, 100]之间。
第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间有空格分隔。
下面的S行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。
Output
本剧需要的男女演员的最少数目，具体格式如下：
“You need x actors and y actresses” 其中x和y分别代表男、女演员的最少数目
Sample Input
4 3 6
Tarzan Jim John Tom
Lucy Cynthia Jane
3 Jim John Tom
2 Tarzan Lucy
2 Jane Cynthia
2 Jim Jane
2 Tarzan......
求二叉树的先序序列(2007-08-24 21:17:00)
摘要：
描述 Description
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。
输入格式 Input Format
第一行为二叉树的中序序列
第二行为二叉树的后序序列
输出格式 Output Format
一行，为二叉树的先序序列
/////////////
#include <iostream>
using namespace std;
void print(char *midOrder, char *backOrder){
if(strlen(backOrder)==0)
return ;
char c = backOrder[strlen(backOrder)-1];
cout<<c;
unsigned i;
for(i=0; i<strlen(midOrder)-1; i++){
if(midOrder[i]==c)
break;
}
char *rmid = new char[strlen(midOrder)-i];
char *rback = new char[strlen(midOrder)-i];
strcpy(rmid,&midOrder[i+1]);
backOrder[strlen(backOrder)-1] = '\0';
strcpy(rback,&backOrder[i]);
midOrder[i] = '\0';
backOrder[i] = '\0';
print(midOrder,backOr......