博文
分牌(2007-08-24 17:07:00)
摘要：描述 Description
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N=4，4 堆纸牌数分别为：
① 9 ② 8 ③ 17 ④ 6
移动3次可达到目的：
从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。
输入格式 Input Format
N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
//// 真没想到这么简单 。。。。
#include <iostream>
using namespace std;
int main(){
int a[100],n,move,b,i,sum;
cin>>n;
for(sum=i=0; i<n; i++){
cin>>a[i];
sum+=a[i];
}
for(sum/=n,i=b=move=0; i<n; i++){
if((a[i]+b) != sum){
b+=(a[i]-sum);
move++;
}
&nbs......
旅行(2007-08-24 16:12:00)
摘要：：：：：：旅 行：：：：：
描述 Description
某趟列车的最大载客容量为V人，沿途共有n个停靠站，其中始发站为第1站，终点站为第n站。
在第1站至第n-1站之间，共有m个团队申请购票搭乘，若规定：
（1）对于某个团队的购票申请，要么全部满足，要么全部拒绝，即不允许只满足部分。（2）每个乘客的搭乘费用为其所乘站数。问：应如何选择这些购票申请，能使该趟列车获得最大的搭乘费用？
其中，每个团队的购票申请格式是以空格分隔的三个整数：a b t，即表示有t个人需要从第a站点乘至第b站点（注：每个团队的所有人员都必须同时在a站上车，且必须同时在后面的b站下车）。
输入格式 Input Format
输入有若干行。其中：
第1行只有三个整数n，m，v，分别表示站点数、申请数、列车的最大载客容量。这三个整数之间都以一个空格分隔。
第2行至第m+1行，每行有三个整数，中间都以一个空格分隔。其中第k+1行的三个整数a，b，t表示第k个申请，含义为：有t个人需要从第a站乘至第b站。
其中：1≤n≤10；1≤m≤18
输出格式 Output Format
输出只有一行，该行只有一个整数，为该列车能获得的最大搭乘费用。
////// 江南孤峰
按站点上车的先后排序团体，递归搜索最优解，在 a 团体上
车时车上能够容下的人数记得减掉到站的团体人数。。。。
#include <iostream>
using namespace std;
typedef struct node{
int a,b,t;
bool s;
}NODE;
NODE gGroup[20];
int myCmp(const void *a, const void *b){ // 用于排序
if(((NODE*)a)->a > ((NODE*)b)->......
交换比率(2007-08-21 21:49:00)
摘要：
交换比率
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 9, Accepted users: 9
Problem description
用纸币来支付商品和服务的费用可以使生活方便，可是人们有时希望能够直接交换物品而不使用钱币来作媒介。为了确保一致的“价格”，商人们制订了一个关于商品的交换比率。我们用正整数M和N来表示商品A和B的交换比率，并说M个商品A等价于N个商品B。举例来说，2个火炉应该等价于3个冰箱(从数学的角度来说，1个火炉等价于1.5个冰箱,但是要拿出半个冰箱不是件容易的事,交换比率总是那些有实际意义的整数)。请写一个程序，对于给出的交换比率表，计算出任意两件商品的交换比率。
Input
输入有一个或多个命令,结尾用一个“.”号来表示。
每个命令独占一行，命令可以是一个断言或一个疑问。如果是断言，则以感叹号开头，并按如下格式： ! m itema = n itemb
itema和itemb应是具体的商品名称，m和n都是不大于100的正整数。这个命令断言了m个itema等价于n个itemb。如果命令是一个疑问，则以问号开头，并按如下格式：
? itema = itemb
表示询问itema和itemb之间的交换比率，itema和itemb是在上文的断言中曾出现过的具体的商品名称（itema和itemb不一定要在同一断言中出现）。
注意：
商品名字只能用不多于20个小写字母来表示。
商品的名字用单数表示（不要用复数形式）。
最多有60种不同的商品。
对于每一对不同的商品，最多只能有一个断言。
没有永假的断言，比如, "2 pig = 1 cow", "2 cow = 1 horse", and "2 horse = 3 pig" 是永假。
断言中的比率不一定要是最小的，但是输出的比率一定要是最小的形式。
虽然断言中不能有大于100的数字，但疑问中可以出现比100大的数字。疑问的答案化成最小后输出。
Output
对于每个疑问，根据所有的有关的断言，输出ite......
岛上的植物(湖南省第二届大学生程序设计大赛)(2007-08-19 10:40:00)
摘要：
岛上的植物
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 31, Accepted users: 26
Problem 10844 : No special judgement
Problem description
测绘人员将卫星拍摄的地面遥感图像转换成了数值方阵。方阵中的每个元素都是正整数，代表某单位面积土地上的植物类型。元素为质数时对应土地上的植物为稀有类型，元素为合数时对应土地上的植物为常见类型。为保护稀有植物，林业局雇佣你编写程序分析上述数值方阵，从中检测出稀有植物区和非稀有植物区。划分区域的原则是：如果数值方阵中的两个元素同为质数或同为合数，而且它们共行相邻或共列相邻，则这两个元素同属一个区域。
Input
输入文件中包含若干待分析的数值方阵。方阵的每一行占据文件的每一行，同一行的方阵元素之间用空格分隔。每个数值方阵的前一行包含且仅包含一个正整数，代表该方阵的行数。文件的结尾行包含且仅包含一个负整数。数值方阵的行数不会超过100，元素的值不会大于100000000。
Output
针对输入文件中的每一个数值方阵分别输出如下信息： 1 该数值方阵的序号（按照其在输入文件中的位置从1计起）。格式是：“Area n:” (n代表方阵序号) 2 稀有植物区域的数目和每个稀有植物区域的面积（按升序排列）。格式是： “M unique vegetation regions: a1 a2 ...” (M为区域数目，a1, a2,...等代表每个区域的面积) 3 非稀有植物区域的数目。格式是：“K non-unique vegetation regions” (K为区域数目) 具体的输出格式请参考示例。
Sample Input
3
2 4 9
17 6 37
29 8 11
4
2 3 12 15
5 7 21 33
4 6 11 17
8 9 13 29
-1
Sample Output
Area 1:
2 unique vegetation regions: 2 ......
何时“苏醒”? (湖南省第二届程序设计大赛)(2007-08-19 10:00:00)
摘要：
何时“苏醒”?
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 61, Accepted users: 41
Problem 10843 : No special judgement
Problem description
人类的大脑是按功能分区的。正常人的大脑分区都是活跃的，分区之间有着广泛的神经连接；而脑病患者的某些大脑分区则是不活跃的，处于“睡眠”状态。最近的研究发现：如果某个“睡眠”分区X与其它至少3个活跃分区保持连接1年时间，则分区X会“苏醒”过来，恢复成活跃状态。 “苏醒”后的分区不会再转入“睡眠”状态。
有位病人的大脑分区都处于“睡眠状态”。经用一种新方法治疗后，其中3个分区同时“苏醒”过来。根据上文的结论，若不再进行治疗则其它分区经过多少年也能全部“苏醒”过来？
Input
输入文件的第1行仅包含1个整数M，取值范围是[3, 26]，它表示病人大脑的分区数。
第2行也只包含1个非负整数N，它表示分区之间的连接数（如果分区A与分区B相连，则分区B也与分区A相连。由于这样的连接是等价的，所以只计数1次）。
第3行包含3个相邻的大写英文字母，分别代表刚刚同时“苏醒”的3个分区。
第4行中包含N个用空格分割的字符串，每个字符串包含2个大写英文字母，分别代表2个相连接的分区。
Output
如果该病人的大脑分区经过若干年后能够全部“苏醒”，请在输出文件中按格式输出一行：
“WAKE UP IN n YEARS” （其中n指分区全部“苏醒”需要的年数）
如果该病人的大脑分区无法全部“苏醒”，请在输出文件中按格式输出一行：
“THIS BRAIN NEVER WAKES UP”
Sample Input
6
11
HAB
AB AC AH BD BC BF CD CF CH DF FH
Sample Output
WAKE UP IN 3 YEARS
Problem Source
湖南省第二届程序设计大赛......
完全二叉树(湖南省第二界程序设计大赛)(2007-08-19 09:52:00)
摘要：
完全二叉树
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 22, Accepted users: 18
Problem 10846 : No special judgement
Problem description
“树”在计算机科学中是一种非常重要的数据结构。它的应用极为广泛，从计算机图形学中的空间层次剖分到人工智能中的状态搜索都离不开它。二叉树是一种特殊的树，它的每个节点最多只有左、右两个子树，如下图所示。
我们用二元组(n,s)来表示二叉树中的任意节点。其中n代表该节点的值，s代表从根节点到该节点的路径字符串，字符串中只包含’L’和’R’两种字符，分别指“左子树”和“右子树”。上图中值为13的节点用(13,RL)表示，值为2的节点用(2, LLR)表示；根节点用(5,)表示，空路径字符串表示它是根节点。如果每个节点到根节点的路径上都没有缺少节点，而且每个节点只被赋值一次，则称这样的二叉树是“完备描述”的。本题目要求你判断给定二叉树是否是“完备描述”的，如果是，输出其节点值的按层次遍历序列（即先上层后下层、从左至右地遍历）。图1中的二叉树，其节点值的按层次遍历序列为：5, 4, 8, 11, 13, 4, 7, 2, 1。
Input
输入文件中包含多个二叉树的节点序列，每个节点用上述(n,s)形式描述，节点值都是正整数。节点之间以空格分隔，节点内部没有空格。每个二叉树至少包含一个节点，树的结尾处以两个英文括号字符“()”标记，括号之内没有空格。
Output
针对输入文件中的每个二叉树，分别输出其对应的信息。对于完备描述的二叉树，输出其节点值的按层次遍历序列。每个二叉树的遍历序列值占据一行，且值与值之间用空格分隔。对于不完备描述的二叉树，则在新的一行中输出字符串“not complete”。
Sample Input
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) ......
Channel Allocation (2007-08-13 17:31:00)
摘要：
Channel Allocation
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 6, Accepted users: 6
Problem 10821 : No special judgement
Problem description
When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels.
Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.
Input
The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters......
Pathfinding (搜索题)(2007-08-13 17:27:00)
摘要：
Pathfinding
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 6, Accepted users: 5
Problem 10820 : No special judgement
Problem description
Recently you have been working on the pathfinding module for your AI system. Your objective is to find the shortest path for an agent that wants to travel between two points on a plane. The agent will start at the point (0,0), and travel to the point (x,y). You decided that the agent will move either on horizontal of vertical lines such that, at every moment, at least one coordinate of the agent is an integer.
There is yet another restriction however. Each line will only allow movement in one direction. All horizontal lines with odd y-coordinates will be directed toward decreasing values of x, and all other horizontal lines toward increasing values of x. Similarly, all vertical lines with odd x-coordinates will be directed toward decreasing values of y, and all other vertical lin......
Max Sequence(双向DP)(2007-08-13 17:22:00)
摘要：
Max Sequence
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB
Total submit users: 88, Accepted users: 73
Problem 10478 : No special judgement
Problem description
Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N).
You should output S.
Input
The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.
Output
For each test of the input, print a line containing S.
Sample Input
5
-5 9 -5 11 20
0
#include <stdio.h>
#include <limits.h>
int a[100002],b[100002],c[100002];
int main(){
int i,n,t,sum;
while(scanf("%d",&n) && n){
for(i=0; i<n......
Children of the Candy Corn (阅读理解)(2007-08-13 17:20:00)
摘要：
Children of the Candy Corn
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 29, Accepted users: 23
Problem 10833 : No special judgement
Problem description
The cornfield maze is a popular Halloween treat. Visitors are shown the entrance and must wander through the maze facing zombies, chainsaw-wielding psychopaths, hippies, and other terrors on their quest to find the exit.
One popular maze-walking strategy guarantees that the visitor will eventually find the exit. Simply choose either the right or left wall, and follow it. Of course, there's no guarantee which strategy (left or right) will be better, and the path taken is seldom the most efficient. (It also doesn't work on mazes with exits that are not on the edge; those types of mazes are not represented in this problem.)
As the proprieter of a cornfield that is about to be converted into a maze, you'd like to have a computer program that can dete......