手机短号
大家都知道，手机号是一个11位长的数字串，同时，作为学生，还可以申请加入校园网，如果加入成功，你将另外拥有一个短号。假设所有的短号都是是 6+手机号的后5位，比如号码为13512345678的手机，对应的短号就是645678。 现在，如果给你一个11位长的手机号码，你能找出对应的短号吗？ Input 输入数据的第一行是一个N(N <= 200)，表示有N个数据，接下来的N行每一行为一个11位的手机号码。 Output 输出应包括N行，每行包括一个对应的短号，输出应与输入的顺序一致。 Sample Input 2 13512345678 13787654321 Sample Output 645678 654321
解题思路： 输入完后直接按要求输出就可以，不需要多余的处理。 注意用getchar读入换行符。
#include<stdio.h> int main() { int t; char num[15]; scanf("%d",&t); getchar(); while(t--) { gets(num); printf("6"); for(int i=6;i<11;i++) { printf("%c",num[i]); } printf("\n"); } return 0; }小兔的棋盘
小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧! Input 每次输入一个数n(1<=n<=35)，当n等于－1时结束输入。 Output 对于每个输入数据输出路径数，具体格式看Sample。 Sample Input 1 3 12 -1 Sample Output 1 1 2 2 3 10 3 12 416024
解题思路: 第一行上的点只有一种路线，这是基础。 dp[i][i]=dp[i-1][i];只能往上走 dp[i][j]=dp[i-1][j]+dp[i][j-1];向右走或者向上走。 半个三角形部分用dp递推。 先打表再输出。 最后的结果应该是对角线两侧三角形的和。 2*dp[n-1][n]。
#include<stdio.h> __int64 dp[40][40]; void init() { int i,j; for(i=1;i<=35;i++) { dp[0][i]=1; } for(i=1;i<=35;i++) { dp[i][i]=dp[i-1][i]; for(j=i+1;j<=35;j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } } int main() { init(); int t=0,n; while(1) { scanf("%d",&n); if(n==-1) return 0; printf("%d %d %I64d\n",++t,n,2*dp[n-1][n]); } }数塔问题
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的： 有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 已经告诉你了，这是个DP的题目，你能AC吗? Input 输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。 Output 对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。 Sample Input 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output 30
解题思路： 用dp[i][j]保存到第i行第j个位置中所有可能的最大值。
#include<stdio.h> #include<memory.h> int dp[101][101]; int main() { int n,t,c; scanf("%d",&c); while(c--) { scanf("%d",&n); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { scanf("%d",&t); dp[i-1][j]>dp[i-1][j-1]?dp[i][j]=t+dp[i-1][j]:dp[i][j]=t+dp[i-1][j-1]; } } int max=0; for(int i=1;i<=n;i++) { dp[n][i]>max?max=dp[n][i]:max=max; } printf("%d\n",max); } }核反应堆
某核反应堆有两类事件发生： 高能质点碰击核子时，质点被吸收，放出3个高能质点和1个低能质点； 低能质点碰击核子时，质点被吸收，放出2个高能质点和1个低能质点。 假定开始的时候（0微秒）只有一个高能质点射入核反应堆，每一微秒引起一个事件发生(对于一个事件，当前存在的所有质点都会撞击核子)，试确定n微秒时高能质点和低能质点的数目。 Input 输入含有一些整数n(0≤n≤33)，以微秒为单位，若n为-1表示处理结束。 Output 分别输出n微秒时刻高能质点和低能质点的数量，高能质点与低能质点数量之间以逗号空格分隔。每个输出占一行。 Sample Input 5 2 -1 Sample Output 571, 209 11, 4
解题思路： 简单的递推问题，找到公式，先打表再输出。
#include<stdio.h> __int64 h[35],s[35]; void init() { h[0]=1; s[0]=0; h[1]=3; s[1]=1; for(int i=2;i<=33;i++) { h[i]=h[i-1]*3+s[i-1]*2; s[i]=h[i-1]+s[i-1]; } } int main() { init(); int n; while(1) { scanf("%d",&n); if(n==-1) return 0; printf("%I64d, %I64d\n",h[n],s[n]); } }简易版之最短距离
寒假的时候，ACBOY要去拜访很多朋友，恰巧他所有朋友的家都处在坐标平面的X轴上。ACBOY可以任意选择一个朋友的家开始访问，但是每次访问后他都必须回到出发点，然后才能去访问下一个朋友。 比如有4个朋友，对应的X轴坐标分别为1， 2， 3， 4。当ACBOY选择坐标为2的点做为出发点时，则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| = 4。 现在给出Ｎ个朋友的坐标，那么ACBOY应该怎么走才会花费时间最少呢？ Input 输入首先是一个正整数M，表示M个测试实例。每个实例的输入有2行，首先是一个正整数N（N <= 500)，表示有N个朋友，下一行是N个正整数，表示具体的坐标(所有数据均<=10000). Output 对于每一个测试实例，请输出访问完所有朋友所花的最少时间，每个实例的输出占一行。 Sample Input 2 2 2 4 3 2 4 6 Sample Output 2 4
解题思路： 先把所有数按大小排序，再取中间的数，求时间就可以了。 如果有偶数个数，把中间的两个数的时间都求出来，取最小值。
#include<stdio.h> #include<algorithm> #include<math.h> using namespace std; int main() { int i,t,n,ans,sum,sum1,sum2,num[505]; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&num[i]); } sort(num+1,num+n+1); sum=0; sum1=0; sum2=0; if(n%2==1) { ans=n/2+1; for(i=1;i<=n;i++) { sum+=abs(num[i]-num[ans]); } } if(n%2==0) { ans=n/2; for(i=1;i<=n;i++) { sum1+=abs(num[i]-num[ans]); } ans=n/2+1; for(i=1;i<=n;i++) { sum2+=abs(num[i]-num[ans]); } sum1>sum2?sum=sum1:sum=sum2; } printf("%d\n",sum); } }