博文
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-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......
旅行(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......
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......
位图(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......