博文
最长公共子序列（DP）(2007-07-10 18:17:00)
摘要：题目：有两个字符串，求这两个字符串的最长公共子序列，所谓公共子序列是指下标依次递增的字符串，如 abcdefsg kbcdssssfsg 的最长公共子序列为bcdgsg,字符串的长度范围为 [1，100]
输入：多个实例，每个实例两行，每行一个字符串输出：形式为 Case x:zzz ,x表示实例序号，从1开始，zzz 表示最长公共子序列每个实例的输出占一行。
如：输入：ababagbcdfkkbdckdabcdefsgkbcdssssfsg
输出：Case 1:abCase 2:bcfCase 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] == b[j-1]) m[i][j] = m[i-1][j-1]+1; else if(m[i-1][j] > m[i][j-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"
样例输入110 20 3026 8 105 5 571 1 12 2 23 3 34 4 45 5 56 6 67 7 7531 41 5926 53 5897 93 2384 62 6433 83 270
样例输出Case 1: maximum height = 40Case 2: maximum height = 21Case 3: maximum height = 28Case 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; }
typedef struct node{ int length; int width; int height; int value;}NODE;
void deal(int *a,int *b,int *c){ ......
电话号码统计(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 对应 9Q和Z没有对应的数字。于是，她在记录电话号码的时候为了好记，有的就换成数字所对应的大写字母来记了，如TUT-GLOP，就是888-4567。现在，她所在的公司里的客户联系电话有一大堆，她希望整理出有哪些重复的号码，请你写一个程序帮助她实现。
输入：每次执行只有一组测试数据，第一行是n(1<=n<=1000,000)，其后n行是电话号码列表，号码中可能存在多个"-"，
输出：输出有重复的电话号码，要按照样例那样的标准格式（不出现英文字母），其后跟随一个数字表示重复次数。没有重复的号码不要输出。多个电话号码之间按字典顺序由小到大排好。如果没有重复的号码，请输出一行No duplicates.
样例输入：124873279ITS-EASY888-45673-10-10-10888-GLOPTUT-GLOP967-11-11310-GINOF101010888-1200-4-8-7-3-2-7-9-487-3279
样例输出：310-1010 2487-3279 4888-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->str);}
void putOut(char *str,int n){ int i; for(i=0; i < 7; i++){ if(i==3) putchar('-'); ......
求幂(2007-06-30 22:26:00)
摘要：输入：有多组测试数据，每行输入非负浮点数a和非负整数n，其中a固定长度为6个字符，且n小于100输出：计算a的n次方的结果，特别注意，如果结果小于1大于0，请不要输出前导0样例输入：95.123 120.4321 205.1234 156.7592 998.999 101.0100 12000002 32样例输出：548815620517731830194541.899025343415715973535967221869852721.0000000514855464107695612199451127676715483848176020072635120383542976301346240143992025569.92857370126648804114665499331870370751166629547672049395302429448126.76412102161816443020690903717327667290429072743629540498.1075960194566517745610440100011.1268250301319697206612014294967296
// 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=0; str[i] != '.'; i++,k++) temp[k] = str[i]; } else{ for(; str[i]=='0'; i+......
剔除相关数(2007-06-22 19:08:00)
摘要：剔除相关数
时间限制:1000MS 内存限制:65536KTotal Submit:1 Accepted:1
问题描述
一个数与另一个数如果含有相同数字和个数的字符，则称两数相关。现有一堆乱七八糟的整数，里面可能充满了彼此相关的数，请你用一下手段，自动地将其剔除。
输入
每组数据前有一个N(<1000)，表示跟随的整数P(0<P<2^32)个数，若N为0，表示结束。
输出
按从小到大的顺序输出非相关数，若没有非相关数，则输出None。
输入样例
8213 667 3 213 43 34 677 23322 232 2320
输出样例
2 3 667 677None
// 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++) str[k] = '0'; for(meter[i]--; meter[i]; meter[i]--,k++) str[k] = i+'0'; i++; }&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 retPtEnter endp
;------------------------------------------------------------------;在提示下输入数据,提示信息为 si ,数据输入到 di;------------------------------------------------------------------GetData proc near mov dx,si mov ah,09h int 21h mov dx,di mov ah,0ah &nb......
导弹计算(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++){ for(m=0; m<=k; m++){ if(a[j] < b[m]) break;......
火星数排序(2007-06-17 17:24:00)
摘要：火星数排序
时间限制:1000MS 内存限制:65536KTotal 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个经过火星由小到大排序的数。
输入样例
4756 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*i); i *= 10; } *a = dest;}
int myCmp(const int *a,const int *b){&......
三进制小数(2007-06-17 17:23:00)
摘要：三进制小数
时间限制:1000MS 内存限制:65536KTotal Submit:14 Accepted:2
问题描述
你的任务呢，是将一个有理数转换成三进制小数。“什么是三进制小数呢？”你一定会问，这很明白，就是以三为基（二进制数以2为基，而十进制数则以10为基）的小数。
输入
有理数的值都是在0与1之间的，每个有理数都由一个分子和一个分母表示，分子与分母之间隔着一个斜杠。有理数的个数不会超过1000个。
输出
输出格式见样本输出，它是以小数点开头的具有10位精度的3进制数。
输入样例
1 / 31 / 41 / 67 / 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; a = a*3%b; } test(save); for(i=0; i<10; i++) printf("%d",save[i]); ......