博文
最长公共子序列(DP)(2007-07-10 18:17:00)
摘要:题目:
有两个字符串,求这两个字符串的最长公共子序列,所谓公共子序列是指
下标依次递增的字符串,如 abcdefsg kbcdssssfsg 的最长公共子序列为
bcdgsg,字符串的长度范围为 [1,100]
输入:
多个实例,每个实例两行,每行一个字符串
输出:
形式为 Case x:zzz ,x表示实例序号,从1开始,zzz 表示最长公共子序列
每个实例的输出占一行。
如:
输入:
ab
ab
agbcdf
kkbdckd
abcdefsg
kbcdssssfsg
输出:
Case 1:ab
Case 2:bcf
Case 3:bcdfsg
// my code
#include <stdio.h>
#include <string.h>
char a[100],b[100],m[101][101]={0};
void putOut(int i, int j){
if(i==0 || j==0)
return;
else if(m[i][j] == m[i-1][j-1]+1){
putOut(i-1,j-1);
putchar(a[i-1]);
}
else if(m[i][j] > m[i-1][j])
putOut(i,j-1);
else
putOut(i-1,j);
}
int main(void){
unsigned int i,j,n=1;
while(gets(a)!=NULL){
gets(b);
for(i=1; i<=strlen(a); i++)
for(j=1; j<=strlen(b); j++){
if(a[i-1......
2007 软考的风风雨雨及所感(2007-07-02 21:09:00)
摘要:今年我参加了软件设计师资格考试,其间的心态是:满怀信心,放弃,加把劲,成功
最后到失望。我上午考了60,下午考了71,虽然分数线还没出来,但估计软考办不敢
把分数提高到60,不然不被砖头砸死也会被唾沫淹死。因此,我应该过了,不过过了
却有点失望。
简单说下,我四月分报名,有两个月的时间备考,因此满怀信心;因为基础不好,软
件设计师的考试考得又很广,因此,学了段时间有点想放弃,其实我应该算放弃了;
最后剩下两个星期因为心疼那点钱,决定背水一战,于是加了把劲;最后看到成绩
应该算成功了;失望的是今年的软件设计师考试含金量太低了。
要很好的讲述我的软考经历,我觉得有必要介绍一下我自己,以及我的大学生活。
我是一所普通本科院校的学生,从小到大我一直是一个遵纪守法的良好学生,大学里
因为涉猎了一些很“前卫”的思想,当然这些“前卫”只是在我这个来自于偏远山区
的良好市民的眼里仍“新潮”,网络上早就洪水泛滥般充斥着各种以前我没听过的观
点,比如有人对中国的教育感到怀疑,认为它扼杀了学生的创造力想象力动手能力,
培养出来的只是应试高手,做题机器;还有的人认为凭什么我们要那么重视英文,将
四六级和学位证挂钩,批评那些发大把时间学英语背单词,而不重视中国人自己的文
化中国人自己的语言的人 等等。于是我开始思考过去,现在,将来。得到的结论是我
必须学一点实用的东西而不是一直捧着那些教科书,为期末考试,为奖学金而奔波。其
间的得失只有自己心里明白。
正如前面所说的,我不再是期末考试成绩和奖学金的追求者,于是在大一拿了两次三
等奖后,一直没有拿过了。大二开始我有了台二手电脑,CPU 1G,内存 256M ,显卡 32M
完反恐的时候可以看见子弹的发射路径,暴力摩托可能是因为显卡驱动的原因一完就蓝
屏,唯一的一个游戏是微软的“帝国时代”我们是完“帝国二--征服者”,现在寝室里
完帝国暂时我是老大,呵呵我们寝室就五个人,有时也连机两两对战交流感情。虽然我
这里电脑一出台接着就是一大堆游戏,但我不是游戏迷,相反我很少完游戏,因为我知
道游戏完多了就是浪费青春。我喜欢编程,从学C语言开始我就一直爱好编程,看着那些
简单的代码控制这个曾经对我很神秘的机器,心理就说不出的......
猴子吃桃(DP)(2007-07-01 11:53:00)
摘要:问题描述:
有一班科学家正在设计一个测试猴子IQ的试验。他们 把一只“banana”吊在天花板,而且同时给猴子一些箱子。如果猴子聪明的话,它们会把箱子一个个叠起来做成一个塔子来取得食物。科学家有n种箱子,而且每一种箱子都有好多个。第 i 种箱子有三维(xi,yi,zi)。箱子可以用它的任意一面作底面来摆放,也就是它的三维之中可以任选两条来做它的底面长和宽。科学家想确定箱子叠到最高的时候是可以到达天花板的。现在问题是,要叠起一个塔子,上下摆放的两个箱子,在上的箱子的底面长宽必须严格小于在下的箱子的底面长宽,留下些地方让猴子落脚来爬上去。也就是说,底面面积相等的箱子不能叠放。现在你的任务是利用所给定的箱子,决定塔子最高能达到的高度
输入:
输入数据有多组测试数据。
每一组测试数据的第一行是一个整数n,表示不同三维的箱子的总数。n最大为30。
以下的n行每一行有三个正整数,表示该箱子的三维xi,yi和zi。
当n=0的时候输入结束。
输出:
对应每组测试数据,输出一行包括数据组号case(从1开始)和塔子最高高度height,
并按照一下格式: "Case case: maximum height = height"
样例输入
1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
样例输出
Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342
// DP
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 32
#define SWAP(a,t,b) { t=a; a=b; b=t......
电话号码统计(2007-07-01 11:50:00)
摘要:问题描述:
Felicia发现电话机上的数字下方有对应的三个英文字母:
A, B, C 对应 2
D, E, F 对应 3
G, H, I 对应 4
J, K, L 对应 5
M, N, O 对应 6
P, R, S 对应 7
T, U, V 对应 8
W, X, Y 对应 9
Q和Z没有对应的数字。
于是,她在记录电话号码的时候为了好记,有的就换成数字所对应的大写字母来记了,如TUT-GLOP,就是888-4567。现在,她所在的公司里的客户联系电话有一大堆,她希望整理出有哪些重复的号码,请你写一个程序帮助她实现。
输入:
每次执行只有一组测试数据,第一行是n(1<=n<=1000,000),其后n行是电话号码列表,号码中可能存在多个"-",
输出:
输出有重复的电话号码,要按照样例那样的标准格式(不出现英文字母),其后跟随一个数字表示重复次数。没有重复的号码不要输出。多个电话号码之间按字典顺序由小到大排好。如果没有重复的号码,请输出一行No duplicates.
样例输入:
12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279
样例输出:
310-1010 2
487-3279 4
888-4567 3
// 动态内存老是RUNTIME ERROR
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
typedef struct node{
char str[8];
}NODE;
NODE p[1000002];
int myCmp(const NODE *a, const NODE *b){
return strcmp(a->str,b->s......
求幂(2007-06-30 22:26:00)
摘要:输入:
有多组测试数据,每行输入非负浮点数a和非负整数n,其中a固定长度为6个字符,且n小于100
输出:
计算a的n次方的结果,特别注意,如果结果小于1大于0,请不要输出前导0
样例输入:
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
000002 32
样例输出:
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
4294967296
// code 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 800
char result[MAX]={0};
int pr = 1;
int change(char *str){
char temp[10];
unsigned int k=0,i=0,j=0;
if(str[0] == '0'){
for(i=1; str[i]=='0'; i++)
;
if(str[i] != '.'){
for(k=......
剔除相关数(2007-06-22 19:08:00)
摘要:剔除相关数
时间限制:1000MS 内存限制:65536K
Total Submit:1 Accepted:1
问题描述
一个数与另一个数如果含有相同数字和个数的字符,则称两数相关。现有一堆乱七八糟的整数,里面可能充满了彼此相关的数,请你用一下手段,自动地将其剔除。
输入
每组数据前有一个N(<1000),表示跟随的整数P(0<P<2^32)个数,若N为0,表示结束。
输出
按从小到大的顺序输出非相关数,若没有非相关数,则输出None。
输入样例
8
213 667 3 213 43 34 677 2
3
322 232 232
0
输出样例
2 3 667 677
None
// my code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node{
int s;
int c;
}a[1002];
void deal(struct Node *a){
char meter[10] = {0},str[12];
int i,k;
if(a->s==0){
a->c=0;
return;
}
for(i=a->s; i!=0; i/=10)
meter[i%10]++;
if(meter[0]){
for(i=1; i<10; i++){
if(meter[i])
break;
}
str[0]=i+'0';
for(k=1; meter[0]; meter[0]--,k++)
&nb......
乘法代码(汇编)(2007-06-22 19:04:00)
摘要:;计算 a * b,其中a b的位数可以在 1 - 2^8 之间,默认位数为 50
;注意 a,b 必须为正数否则结果不正确
;******************************************************************
.model small
.const
MAX equ 50 ;乘数的最大位数
.data
a db MAX,MAX dup(0)
b db MAX,MAX dup(0)
r db MAX+MAX+1 dup(0)
txta db 'Enter a:$'
txtb db 'Enter b:$'
result db 'a * b = $'
enter db 13,10,'$'
.code
;------------------------------------------------------------------
;子程序,在屏幕上打印回车
;------------------------------------------------------------------
PtEnter proc near
mov dx,offset enter
mov ah,09h
int 21h
ret
PtEnter endp
;------------------------------------------------------------------
;在提示下输入数据,提示信息为 si ,数据输入到 di
;------------------------------------------------------------------
GetData proc near
mov dx,si
&n......
导弹计算(2007-06-19 20:18:00)
摘要:Problem description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
Input
输入数据为导弹依次飞来的高度,所有高度值均为不大于30000的正整数。
Output
输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。
两个数据之间用一个空格隔开.
Sample Input
389 207 155 300 299 170 158 65
Sample Output
6 2
Problem Source
NOI 99
// my code
#include <stdio.h>
int a[10000],b[10000];
int main(){
int i,j,k,m,n,maxr,maxt;
for(i = 0; scanf("%d",&a[i]) != EOF; i++)
;
for(maxr = 1,j = i-1; j >= 0; j--){
for(maxt = 0,b[j] = 1,k = j+1; k < i; k++){
if(a[k] <= a[j] && b[k] > maxt)
maxt = b[k];
}
b[j] += maxt;
maxr = (maxr > b[j] ? maxr : b[j]);
}
for(k=0,n=j=1,b[0]=a[0]; j < i; j++){......
火星数排序(2007-06-17 17:24:00)
摘要:火星数排序
时间限制:1000MS 内存限制:65536K
Total Submit:27 Accepted:7
问题描述
哈哈,大家对地球上的排序规则都比较清楚了吧!可是火星上的规则跟地球上的不一样。地球上的十个数字的顺序是{0,1,2,3,4,5,6,7,8,9},火星上的却是{0,8,1,5,2,3,9,4,7,6}。好在火星上基本数字也是十个,也是十进制,因此,很容易推得9<80<88<81<… 请根据火星上的规则对火星数进行从小到大的排序。
输入
第一行为N,表明接下来有N个火星数,每个火星数用空格隔开(不超过5位)。
输出
输出占一行,为N个经过火星由小到大排序的数。
输入样例
4
756 12 3 87
输出样例
3 87 12 756
// my code
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int meter[]={0,8,1,5,2,3,9,4,7,6};
int myChange(int d,int flag){
int k;
if(flag){
for(k=0; k < 10; k++)
if(d == meter[k]){
d = k;
return d;
}
}
return meter[d];
}
void Change(int *a,int flag){
int i,j,d,dest;
for(dest=0,i=1,j=(*a); j; ){
d = j%10;
j /= 10;
d = myChange(d,flag);
dest += (d......
三进制小数(2007-06-17 17:23:00)
摘要:三进制小数
时间限制:1000MS 内存限制:65536K
Total Submit:14 Accepted:2
问题描述
你的任务呢,是将一个有理数转换成三进制小数。“什么是三进制小数呢?”你一定会问,这很明白,就是以三为基(二进制数以2为基,而十进制数则以10为基)的小数。
输入
有理数的值都是在0与1之间的,每个有理数都由一个分子和一个分母表示,分子与分母之间隔着一个斜杠。有理数的个数不会超过1000个。
输出
输出格式见样本输出,它是以小数点开头的具有10位精度的3进制数。
输入样例
1 / 3
1 / 4
1 / 6
7 / 8
输出样例
.1000000000
.0202020202
.0111111111
.2121212122
// my code
#include <stdio.h>
void test(int a[]){
int i;
if(a[10] >= 2)
a[9]++;
else
return;
for(i=9; i>=0; i--){
if(a[i]>=3){
a[i]=0;
a[i-1]++;
}
else
break;
}
}
int main(){
int i,a,b,save[12];
char c;
while(scanf("%d %c %d",&a,&c,&b)!=EOF){
printf(".");
for(i=0; i<11;i++){
save[i] = a*3/b;
&nb......