1、POJ 2249 Binomial Showdown组合数学。
高精度，也可把分子分母的数组进行两两约分#include<iostream>using namespace std;double c(int c,int k){double a=1;int i,j=2;for(i=c;i>c-k;i--)a=a*i/(c-i+1);return a;}int main(){int n,k;while(scanf("%d%d",&n,&k)!=EOF && (n!=0 || k!=0)){if(k>n/2 )k=n-k;printf("%.0lf\n",c(n,k));}return 0;}2、poj 1023 the fun number system （经典进位制）题意：一种由2进制衍生出来的进制方法（我们暂且称为“类2进制”）；标明'n'的位置上原2进制该位的权重要乘上-1，才是现在进制方法该位的权重；譬如说；pnp对于的能表示的数2来说就是110；即1*2^2+(-1)*1*2^1+1*2^0=2;算法：这是数论中的进位制问题，我们可以仿照原来的求一个数二进制表示方法；但首先，我们应该考虑几个问题；①k位这种类2进制的表示范围；显然，当给出的'p','n'序列中，我们将所有p的位置都置为1其余位是0，此时最大；当我们将所有n的位置置为1，其余为0，此时最小；不过当我们求最大限max和最小限min时会有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断；②是否是最大限和最小限之间的数都能表示呢？都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）；#include<iostream>using namespace std;__int64 N,M;char s[100],res[100]={'\0'};int main(){int T;scanf("%d",&T);int i,j;__int64 _max,_min;char ch;while(T--){scanf("%I64d",&N);scanf("%s",s);_max=0;_min=0;for(i=0;i<N;i++) //找出能表示的范围；{if(s[i]=='p') _max=2*_max+1,_min*=2;else _min=2*_min-1,_max*=2;}scanf("%I64d",&M);if((M<_min&&_min<=0)||(M>_max&&_max>=0)) puts("Impossible"); //注意防止64位数的溢出；else{memset(res,'\0',sizeof(res));for(i=N-1;i>=0;i--){int flag=0;if(M&1) //这里不能是平常的%2；{res[i]='1';if(s[i]=='n') flag=1;}else res[i]='0';M>>=1;if(flag) M++; //如果是n就需其高位加1；}printf("%s\n",res);}}system("pause");return 0;}3、POJ2506 Tiling 递推+高精给看似复杂的题找到了合适的规律就会变得简单。
这个题就是这样。
对于n列来说，可以在n-1列的基础上加上一块，或者是在n-2列的基础上加上2块而2块独立的，不依赖于1块的情况有两种，所以得到递推公式f(n)=f(n-1)+2f(n-2)看样例，要用到高精。
#include<iostream>//f(n)=f(n-1)+2f(n-2)using namespace std;int f[251][300];void HPprint(int *a){for (int i=a[0];i>=1;i--) cout<<a[i];cout<<endl;}void HPplus(int *a,int *b,int *c){int i,j;j=0;for(i=1;i<=min(a[0],b[0]);i++){c[i]=a[i]+b[i]+j;j=c[i]/10;c[i]%=10;}if(j!=0) c[i]=j;c[0]=a[0]>b[0]?a[0]+2:b[0]+2;while(c[c[0]]==0 && c[0]>1) c[0]--;}void HPmultyNUM(int *a,int b,int *c) {int i,j,k;for (i=1;i<=a[0];i++)c[i]+=a[i]*b;k=0;for (j=1;j<=a[0];j++){c[j]+=k;k=c[j]/10;c[j]%=10;}//进位if(k!=0) c[j]=k;c[0]=a[0]+3;while (c[c[0]]==0 && c[0]>1) c[0]--; }int main(){int i,j,t[300],test;f[0][0]=1;f[0][1]=1;f[1][0]=1;f[1][1]=1;f[2][0]=1;f[2][1]=3; for(i=3;i<=250;i++){memset(t,0,sizeof(t));HPmultyNUM(f[i-2],2,t);HPplus(t,f[i-1],f[i]);}while(cin>>test)HPprint(f[test]);return 0;}4、POJ 1079 Ratio 分数操作题目大意：给出一个分数，比如1498/902。
求出当分母分别为1, 2, ....的时候，最接近1498/902的分数。
比如：当分母为1的时候，最接近1498/902的分数为1/1。
当分母为2的时候，最接近1498/902的分数为3/2。
当分母为3的时候，最接近1498/902的分数为5/3。
思路：不要用高精度哦，直接模拟分数的操作最好了。
#include <stdio.h>#include <math.h>struct frac {__int64 up, down;};__inline __int64 gcd(__int64 a, __int64 b){__int64 r;if (a < b) {r = a;a = b;b = r;}while (1) {r = a % b;if (!r)return b;a = b;b = r;}}__inline struct frac frac_init(__int64 up, __int64 down){__int64 r, s;struct frac f;r = up ? gcd(up, down) : 1;if (r < 0)r = -r;f.up = up / r;f.down = down / r;return f;}__inline struct frac frac_sub(struct frac fa, struct frac fb){return frac_init(fa.up*fb.down-fa.down*fb.up, fa.down*fb.down); }__inline __int64 frac_cmp(struct frac fa, struct frac fb){return frac_sub(fa, fb).up;}__inline struct frac frac_abs(struct frac f){if (f.up < 0)f.up = -f.up;return f;}int main(){__int64 up, down;struct frac target, min_dis, f, dis;while (scanf("%I64d%I64d", &up, &down) != EOF) {target = frac_init(up, down);min_dis.down = 1;min_dis.up = (__int64)1e15;for (down = 1; down <= target.down; down++) {up = (down*target.up)/target.down;if (((down*target.up)%target.down)*2 >= target.down)up++;f = frac_init(up, down);dis = frac_abs(frac_sub(f, target));if (frac_cmp(dis, min_dis) < 0) {printf("%I64d/%I64d\n", f.up, f.down);min_dis = dis;}}printf("\n");}return 0;}5、poj 1019 Number Sequence (找规律)找规律的题目：先计算出从1到n这个小区间有多长，保存到digit[]数组中，然后计算从112123到n一共有多少位数字，然后根据输入数据查找，其中我在找那一位时比较暴力，把从1开始一直存放，直到存放的比那一位还多，然后取出那一位。
#include <iostream>#include <sstream>#include <string>#include <cmath>using namespace std ;const int MaxSize=100000+10 ;__int64 digit[MaxSize], len[MaxSize] ;stringstream ss ;void init(){int i ;digit[1] = len[1] = 1 ;for( i=2; i<MaxSize; ++i ){digit[i] = digit[i-1] + (int)log10((double)i)+1 ;len[i] = len[i-1] + digit[i] ;}/*for( i=1; i<10; ++i ){cout << i << " 位数" << digit[i] << " 长度" << len[i] << endl ;}*/}char getDigit( int num ){int i ;for( i=1; len[i]<num; ++i );int pos = num-len[i-1] ;// 清空ssss.str("");for( i=1; i<=pos; ++i ){ss << i ;//cout << ss.str() << endl ;}return (ss.str())[pos-1] ;}int main(){int i, sets, num ;init() ;cin >> sets ;while( sets-- ){cin >> num ;cout << getDigit( num ) << endl ;}return 0 ;}6、POJ 1095 Trees Made to Order思路：首先，设拥有N个结点的不同形态的有序二叉树有L[N]棵。