博文
拼图(2007-08-08 20:19:00)
摘要：
背景 Background
潘帕斯草原最近流行起了一种拼图游戏，@潘帕斯雄鹰为了显示自己是最强的鹰，想尽办法要在这个游戏上赢过其他鹰……
描述 Description
这个拼图游戏要求将一些图形拼成一个正方形，图形的个数从1到5。如下图所示，图形个数是4。图形不能旋转，拼的时候不能重叠，拼完后的正方形里面不能有空隙。所有给定的图形都要使用。左面的图表示这样拼不行，右面是一个成功的拼法。现在，@潘帕斯雄鹰想知道他能否完成这个游戏以表示自己是最强的鹰；如果可以，请输出一种完成这个游戏的方案。
输入格式 Input Format
文件的第一行是一个整数n，表示图形的个数，范围从1到5。接下来有n个部分，每个部分的第一行是2个整数i和j，表示下面的i行j列用来描述一个图形。图形用0和1表示，1表示图形占有这个位置，0表示不占有，中间没有空格。例如上图中图形A的描述是2 3111101所有图形的长与宽都不超过5。根据图形给出的顺序给每个图形编号，从1开始，至多到5。保证数据无多解情况。
输出格式 Output Format
如果不能拼成一个正方形，就输出"No solution possible"；否则，输出一种拼的方案：一个正方形的数阵，每个位置上的数字是占有这个位置的图形的编号，中间没有空格。例如上面A、B、C、D的编号依次是1、2、3、4，那么就可以输出1112141234223442
///// 没什么好方法,穷举过了
#include <stdio.h>#include <string.h>#include <math.h>#include <stdlib.h>#define MAX 10int gm[10][10][10]={0},gmfig[10][2],gn;int gfig[MAX][MAX]={0};
int move(int k,int *x, int *y){ int xt,yt,xg,yg,i,j; for......
合唱队形(2007-07-30 17:35:00)
摘要：合唱队形
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
Input 输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
Output 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
Sample Input 8186 186 150 200 160 130 197 220 Sample Output 4
/////////////////////////////////////////////////////////////////////////////////////////
解题方法：Dp 设三个数组，其中一个用于保存身高，另外两个保存子状态。 up[n]表示身高一直按升序排列时，从第一个人到 第 n 个人合法排列的最大人数。down[n]表示混合的即可以从中间某个位置降序。假如输入数据为：43 4 1 2up[] = {1,2,1,2}, down[] = {1,1,3,3}
至少需要 n - max(up[],down[]), 即 4 - 3 = 1
测试数据：8186 186 150 200 160 130 197 22051 2 3 4 561 3 2 4 2 1结果：401///////////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>#define MAX 110
int a[MAX],up[MAX],down[MAX];int getUp(int i)......
组合(2007-07-21 00:26:00)
摘要：题目描述：列出C(a,b)的所有组合
输入：多组测试数据，每组一行有两个数字a和b(1<=b<a<=30)输入的a=b=0的时候结束。
输出：输出从1到a的数中选出b个数的所有组合，一行输出一个组合，每个组合里的数从小到大排列，各组之间按字典顺序从小到大排列。
样例输入：5 20 0
样例输出：1 21 31 41 52 32 42 53 43 54 5
#include <stdio.h>
void putout(int s[],int b){ int i; for(i=1; i < b; i++) printf("%d ",s[i]); printf("%d\n",s[i]);}
int main(){ int a,b,s[32],i; while(scanf("%d %d",&a,&b)!=EOF){ if(a==0 && b==0) break; for(s[0]=i=1; i<=b; i++) s[i]=i; for(i--; i>0; ){ if(i==b) putout(s,b); if(s[i]+1+b-i > a){ if(i==1) break; for(;i>1 && s[i-1]+2+b-i>a;i--) ; if(i==1) continue; for(s[i-1]++; i<=b; i++) &n......
最长公共子序列（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]) ......
猴子吃桃（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-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){&......