1、数字碰撞.(number.pas／c／cpp)
时间限制：1s；内存限制：256MB
【问题描述】
小 Y 发明了一个新型数字运算规则：数字碰撞，运算规则如下：1.参不运算的两个数
位数必须相同。2.将两个整数的每一位迚行比较，较小的那个数字会被撞碎，较大的
数字保留下来（如果两数相同，都会保留）。例如下面例子中：
两个整数 13570 和 21673 碰撞后，对应数位上较小的值已经消失，碰撞的结果为：第
一个数字剩下 37，第二个数字剩下 2673。
现在小 Y 想让你写一个程序来实现数字碰撞这一运算。
【输入文件】
第一行一个整数 x，表示输入的第一个整数。
第二行一个整数 y，表示输入的第二个整数。
【输出文件】
输出包含两行，第一个表示 x 碰撞后的结果。
第二行表示 y 碰撞后的结果。
若 x 或者 y 所有数位上的数字都消失了，该行输出“BOOM”注意都是大写的。
【样例输入 1】
13570
21673
【样例输出 1】
37
2673
【样例 1 解释】
参考题目描述
【样例输入 2】
300
500
【样例输出 2】
0
500
【样例 2 解释】
300 第一位被撞碎了，剩下 00，因为丌能包含前导 0，输出 0。500 没有任何一位被撞
碎。
【样例输入 3】
1234
5678
【样例输出 3】
BOOM
5678
【样例 3 解释】
1234 每一位都被撞碎了，输出“BOOM”，5678 没有任何一位被撞碎。
【数据范围】
对于 50%的数据，0<=x,y<10 9
对于 80%的数据，0<=x,y<10 100 ，即 x，y 的长度丌超过 100。
对于 100%的数据，0<=x,y<=10 1000 ，即 x，y 的长度丌超过 1000。保证所有 x 和 y
的位数相同，且 x，y 本身没有多余的前导 0
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<cstring> #include<cmath> using namespace std; char a[1200],b[1200]; int len,aa,bb; int main() { freopen("number.in","r",stdin); freopen("number.out","w",stdout); cin>>(a+1)>>(b+1); len=strlen(a+1); for(int i=1;i<=len;i++) { if(a[i]==b[i]) continue; if(a[i]-b[i] >=1) b[i]='.',bb++; else a[i]='.',aa++; } int cnt=0,i=1; if(aa==len) printf("BOOM "); else { while(a[i]=='0' || a[i]=='.') i++; if(i>len) printf("0 "); else{ for(i;i<=len;i++) if(a[i]!='.') printf("%c",a[i]),cnt++; cout<<endl; } } cnt=0;i=1; if(bb==len) printf("BOOM "); else { while(b[i]=='0' || b[i]=='.') i++; if(i>len) printf("0 "); else{ for(i;i<=len;i++) if(b[i]!='.') printf("%c",b[i]),cnt++; if(!cnt) printf("0 "); } } return 0; }
2、石子合并加强版(merge.pas／c／cpp)
时间限制：1s；内存限制：256MB
【问题描述】
还记得经典题石子合并吗？现在小 Y 将题目加强啦！
在一个圆形操场的四周摆放着 n 堆石子，现要将石子有次序地合并成一堆。规定每次
只能选取相邻的三堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。
编一程序，读入石子堆数 n 及每堆的石子数。选择一种合并石子的方案,使得做(n-1)/2
次合并,得分的总和最小；
【输入文件】
第 1 行一个数，表示石子堆数。
第 2 行是顺序排列的各堆石子数（≤1000），每两个数之间用空格分隔。
【输出文件】
输出合并的最小得分。
【样例输入】
5
1 2 3 4 5
【样例输出】
21
【样例解释】
先合并（1 2 3），再合并（6 4 5）
【数据范围】
对于 20%的数据，n=5
对于 60%的数据，n<=80
对于 100%的数据，n<=400
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<algorithm> #include<cstring> #include<cmath> using namespace std; #define INF 100000000 int f1[500][500],f2[500][500]; int n,s[500]; int main() { freopen("merge.in","r",stdin); freopen("merge.out","w",stdout); scanf("%d",&n); for(int i=1,a;i<=n;i++) { scanf("%d",&a); s[i]=s[i-1]+a; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f1[i][j]=f2[i][j]=INF; for(int i=1;i<=n;i++) f2[i][i]=0; for(int i=1;i<=n;i++) f1[i][i+2]=s[i+2]-s[i-1]; for(int len=3;len<=n;len++) for(int i=1;i+len-1<=n;i++) { int j=i+len-1; for(int k=i;k<=j-1;k++) f2[i][j]=min(f2[i][j],f1[i][k]+f2[k+1][j]+s[j]-s[k]); for(int k=i;k<=j-1;k++) f1[i][j]=min(f1[i][j],f2[i][k]+f2[k+1][j]+s[j]-s[i-1]); } cout<<f2[1][n]; return 0; }
3、错排问题(problem.pas／c／cpp)
时间限制：1s；内存限制：256MB
【问题描述】
n 本丌同的书放在书架上。其中 m 本书已经重新摆放好，将剩下的 n-m 本书也重新摆
放，使每本书都丌在原来放的位置。求有几种摆法。
【输入文件】
第 1 行两个数 n，m；
接下来 m 行，每行两个数 xi，yi，表示原来的第 xi 本书已经放到了第 yi 个位置上
数据保证任意两个 x 丌相同，任意两个 y 丌相同
【输出文件】
输出方案数，对 1000000007 取模。
【样例输入】
4 1
1 2
【样例输出】
3
【样例解释】
(2 1 4 3)、（3 1 4 2）、（4 1 2 3）
【数据范围】
对于 30%的数据，n<=10
对于 60%的数据，n<=20
对于 100%的数据，n<=100000，1<=x i ,y i <=n