博文
烦人的电梯(2007-05-25 22:37:00)
摘要：Dissatisfying Lift
Problem description
There's a building with M floors. The amounts of tenants of every floor are K1, K2, K3, ..., Km. One day all the tenants went home together and they took the same lift (suppose the lift was large enough). Because of some reason the lift could only stop on one floor and the tenants must go upstairs or downstairs to their houses. Every tenant went up N floors would make the dissatisfied degree rise N * a + 0.5 * N * (N - 1) degrees, and every tenant went down N floors would make the dissatisfied degree rise N * b + 0.5 * N * (N - 1) degrees. Your task is to tell which floor the lift should stop, in order to make the dissatisfied degree as low as possible.
Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then T cases follow. The first line of each test contains M (1 <= M <= 10000), a and b (0 <= a, b <= 100). The second line contains K1, K2, K3, ...,......
合并果子acm(2007-05-19 10:19:00)
摘要：合并果子
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一
堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果
子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆
，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
Input
输入包括两行，第一行是一个整数n（1 <= n <= 10000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <=
20000）是第i种果子的数目。
Output
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2的31次方。
Sample Input
3
1 2 9
Sample Output
15
Problem Source
NOI
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
struct node{
int value;
struct node *next;
struct node *prep;
}a[10004];
int myCompare(const int *a,const int *b){
if(*a &g......
前缀表达式(2007-05-07 07:07:00)
摘要：Postfix expression evaluation
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 121, Accepted users: 113
Problem 10142 : No special judgement
Problem description
Postfix expressions are arithmetical expressions where the operators come after anything they operate on. Postfix is important because it maintains precedence without the use of (), and they're "easy" to evaluate. In this problem, you get to see how "easy" postfix expressions are to evaluate.
Input
Each line of the input will be no more than 80 characters and will contain one expression to be evaluated. All expressions will be correct postfix expressions. There will be one space between each number/operator. The only operators we're interested in is + (addition), - (subtraction), and * (multiplication). There is no division. All numbers are non-negative integers.
Output
Your program is to output the result of evalu......
acm拼凑春联(2007-04-30 21:35:00)
摘要：拼凑春联
Problem description
春节到了，春联是必不可少的东西^_^。众所周知，一幅对联的“上联”和“下联”是对偶（也叫对仗）的。例如：上联：九州雨顺千山绿下联：六合风调万户丰 BluePoint不喜欢已有的春联组合，所以此人想从已知的佳句中找出两句对偶的，组合出一些新的春联^_*。图书馆有一个“名句文库”，BluePoint想知道其中的名句一共可以拼凑出多少组不同的春联，请您帮帮忙，好吗？为了简化问题，BluePoint只选择七个字的佳句，并把它们的形式化成了字母（按意群将句子分组、断开）。例如“鲲鹏展翅乾坤大”可化为“AABBCCD”，也可以化为“YYQQZZH”，即字母只起显示结构的作用，与句子内容无关。两个句子按照字母的连续性分段后，如果各成分的字数依次相同，则这两个句子对偶。例如：例如“QBLLLDE”和“DEZZZBF”，将第一句按照字母的连续性分为5段：Q、B、LLL、D、E，每段长度分别为1、1、3、1、1，而第二句经过断句后，各段的长度也分别为1、1、3、1、1，因此这两个句子对偶。注：“AABCCCD”和“EEFBBBE”这类句子也算作对偶：第二个句子中两次出现“E”，但“E”是断开的，所以断句情况仍为：2、1、3、1。由于字母只用来突出结构，所以如果出现两次同样的字母串，则它们表示的春联内容不相同，当然，它们是对偶的。
Input
第一行，一个整数N，2≤N≤100000 以下N行，每行都有一个由七个大写字母组成的字符串，代表一个佳句。
Output
一个整数：这些佳句可以拼凑成的对联的种类数。这个整数占一行。
Sample Input
5
ABCCCDA
LLLMNNO
DEZZZBF
AAABCCD
KKKXPPQ
Sample Output
4
Judge Tips
“ABCCCDA”和“DEZZZBF”两句形式相同，可以组成1种春联。 “LLLMNNO”、“AAABCCD”和“KKKXPPQ”形式都相同，任取两个共可组成3种春联。综上所述，答案为4。
Problem Sou......
ACM题，英文的(2007-04-24 21:27:00)
摘要：Square Ice
Time Limit:1000MS Memory Limit:10000K
Total Submit:615 Accepted:228
Description
Square Ice is a two-dimensional arrangement of water molecules H2O, with oxygen at the vertices of a square lattice and one hydrogen atom between each pair of adjacent oxygen atoms. The hydrogen atoms must stick out on the left and right sides but are not allowed to stick out the top or bottom. One 5 x 5 example is shown below.
H-O H-O-H O-H O-H
| | |
H H H H
|
H-O-H O H-O H-O-H
| |
H H H H
| |
H-O H-O H-O-H O-H
| ......
单词接龙(2007-04-16 12:19:00)
摘要：单词接龙
Problem description
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“
龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为
beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。
Input
输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。
你可以假定以此字母开头的“龙”一定存在。
Output
只需输出以此字母开头的最长的“龙”的长度。
Sample Input
5
at
touch
cheat
choose
tact
a
Sample Output
23
Problem Source
NOIP2000
// 开始题意理解错了，提交几次都不成功，后来仔细想了想，呵终于AC了
// 下面是代码
// 主要用到了栈，其次就是字符串的灵活处理。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_WORD_LENGTH 20
#define MAX_WORD 20
#define WORD_USE_MAX 2
#define TRUE 1
#define FALSE 0
#define FAILED 1
#define SUCCESS !FAILED
typedef struct stackk{
int findIndex;
int wordIndex;
int addLength;
}STACK;
STACK ......
让我郁闷一个下午的题(2007-04-14 17:50:00)
摘要：Fractal
Problem description
A fractal is an object or quantity that displays self-similarity, in a somewhat technical sense, on all scales. The object need not exhibit exactly the same structure at all scales, but the same "type" of structures must appear on all scales.
A box fractal is defined as below :
A box fractal of degree 1 is simply
X
A box fractal of degree 2 is
X X
X
X X
If using B(n - 1) to represent the box fractal of degree n - 1, then a box fractal of degree n is defined recursively as following
B(n - 1) B(n - 1)
B(n - 1)
B(n - 1) B(n - 1)
Your task is to draw a box fractal of degree n.
Input
The input consists of several test cases. Each line of the input contains a positive integer n which is no greater than 7. The last lin......
最长合法序列(2007-04-14 12:42:00)
摘要：最长合法序列
Problem description
有k个整数A[1],A[2]...A[k],你需要从前往后选出若干个数,使得每一个后面的数都要大于或等于前面的
数.例如,对于系列1,4,2,5,2,3,选出1,2,2,3是合法的,但是选出4,2,3是不合法的.
请你编写程序对于一个已知系列,求出最长的合法系列的数的个数.
Input
第一行为n，表示n个测试序列; 第二行到第n+1行，每行开始第一个数为k, k后面紧跟k个数A[1],A[2]
….A[k]。
Output
输出n行，每行输出一个整数，表示相应测试序列中最长的合法序列的数的个数。
Sample Input
2
12 13 45 23 53 23 88 123 3 125 10 87 89
6 1 4 2 5 2 3
Sample Output
6
4
Judge Tips
其中0
Problem Source
CSU 1st Contest
//我的代码
#include <stdio.h>
#include <stdlib.h>
struct Node{
int i;
int n;
};
int main(){
int nTest,i,j,k,n,m,max;
struct Node *p;
scanf("%d",&nTest);
for(i = 0; i < nTest; i++){
scanf("%d",&n);
p = (struct Node*)malloc(sizeof(struct Node)*n);
for(j = 0; j < n; j++){
scanf("%d",&......
FBI(2007-04-11 14:03:00)
摘要：Problem description
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树 ，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1) T的根结点为R，其类型与串S的类型相同；
2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
Input
输入第一行是一个整数N(0 <= N <= 10)，第二行是一个长度为2N的“01”串。
Output
输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
Sample Input
3
10001011
Sample Output
IBFBBBFIBFIIIFF
Judge Tips
1.二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
2.后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。
Problem Source
NOIP2004
/* 编译环境 VC ++ */
#include <stdio.h>
#include <string.h>
#include <malloc.h>
typedef struct Tree /* 以二叉树结构存储结果 */
{ char data;
int flag;
struct Tree *lchild;
struct......
IP address(2007-04-11 14:02:00)
摘要：Problem description
Suppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of '1s' and '0s' (bits) to a dotted decimal format. A dotted decimal format for an IP address is form by grouping 8 bits at a time and converting the binary representation to decimal representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decimal numbers remember that both are positional numerical systems, where the first 8 positions of the binary systems are:
27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1
Input
The input will have a number N (1<=N<=9) in its first line representing the number of streams to convert. N lines will follow.
Output
The output must have N lines with a doted decimal IP address. A dotted decimal IP address is formed by grouping 8 bit at the time and converting the binary representation to decimal representation.
Sample Inpu......