暑期个人赛--第一场--E
E. 数的关系?2014新生暑假个人排位赛01
时间限制?5000 ms?
内存限制?65536 KB
题目描述用关系“＜”和“=”将3个数A、B和C依序排列时有13种不同的序关系：
现在输入数字的个数，要求你给出上述关系的数目。 数的个数不大于100 输入格式多组数据，EOF结束 每行一个输入 输出格式对于每个输入，输出一行，即对应答案 输入样例3 输出样例13 赛中提交情况：NULL 赛后AC：Y 题目大意： 题目给出一个整数n， 要求输出，用< > =这三个符号联接起来的这n个数的式子的数量 其实这么说也不准确，应该说这n个数的大小排序关系，因此在等号两边调换位置不产生新的关系 思路： 赛后听了别人转述了的丁犇的思路，这是一道用大数运算来卡人的DP 必须注意，因为等号联接的两个数可以任意调换位置，所以用一个或者多个等号联接起来的几个数可以看做一个堆 递推思路有如下： 如果当前有n个数，想要向n+1个数递推，也就是要向其中插入一个数 （1）这个数可以插在堆里面，那么就任选一个堆插即可，Ck1，在已有的k个堆中任选一，dp[i][j]*(j+1) （2）如果不插在堆里面，那么就是选择一个空隙往里插，一共有n个数，有n+1个空隙，所以C（n+1）1，dp[i][j+1]*j; 递推式： dp[i][j]表示有i个数分为j堆时的关系个数 dp[i+1][j+1]=dp[i+1][j+1]+dp[i][j]*(j+1)+dp[i][j+1]*j; 但是注意写成上式还是不行的，因为dp的地推总是有上界下界的， 而上述加黑的两个表达式，由于与等式左边待求式的下标差值不同 第二个式子取不到第二下标为1的情况（i，j皆从1开始） dp[i+1][j+1]=dp[i+1][j+1]+dp[i][j]*(j+1); dp[i+1][j]=dp[i+1][j]+dp[i][j]*j; 另外就是大数运算了，这次算是熟悉了一下大数运算，觉得还是要学java才行 主要思想是用int数组来存储大数，一个元素只存储一个整数位 至于为什么不用char来存储，是因为在运算中，是模拟竖式算式来计算的， 加乘都会产生两位数，这个时候用int可以直接在一个元素内暂存， 而用char就不行（但是大概想想可以用一个整型tempt来解决这个问题就可以用char了） #include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
struct bignum{
int bit;
int num[205];
bignum(){
bit=0;
memset(num,sizeof(num));
}
void getval(int y){
int i;
for(i=0;y!=0;i+=1){
num[i]=y%10;
y/=10;
}
bit=i;
}
bignum operator * (bignum y){
int mul[205],tempt;
memset(mul,sizeof(mul));
for(int i=0;i<bit;i+=1){
for(int j=0;j<y.bit;j+=1){
mul[i+j]+=(num[i]*y.num[j]);
mul[i+j+1]+=mul[i+j]/10;
mul[i+j]%=10;
}
}
/*for(int j=0;mul[j];j+=1){
printf("nn%d %dn",j,mul[j]);
}
*/
int counta;
for(int i=bit+y.bit-1;;i+=1){
counta=i;
if(!mul[i]){
break;
}
if(mul[i]>=0){
mul[i+1]+=mul[i]/10;
mul[i]%=10;
}
}
/*for(int j=0;mul[j];j+=1){
printf("nn%d %dn",mul[j]);
}*/
//printf("eatshitn %d %d %d",bit,y.bit,counta);
bignum z;
z.bit=counta;
for(int i=0;i<counta;i+=1){
z.num[i]=mul[i];
}
return z;
}
bignum operator * (int y){
int mul[205],tempt,hold[205],holdbit;
memset(mul,sizeof(mul));
memset(hold,sizeof(hold));
for(int i=0;y!=0;i+=1){
hold[i]=y%10;
y/=10;
holdbit=i;
}
holdbit+=1;
for(int i=0;i<bit;i+=1){
for(int j=0;j<holdbit;j+=1){
mul[i+j]+=num[i]*hold[j];
mul[i+j+1]+=mul[i+j]/10;
mul[i+j]%=10;
}
}
int counta;
for(int i=bit+holdbit-1;;i+=1){
counta=i;
if(!mul[i]){
break;
}
if(mul[i]>=0){
mul[i+1]+=mul[i]/10;
mul[i]%=10;
}
}
bignum z;
z.bit=counta;
for(int i=0;i<counta;i+=1){
z.num[i]=mul[i];
}
return z;
}
bignum operator + (bignum y){
int sum[205],i,counta;
bignum z;
memset(sum,sizeof(sum));
for(i=0;i<bit&&i<y.bit;i+=1){
sum[i]+=num[i]+y.num[i];
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
if(bit<y.bit){
for(;i<y.bit;i+=1){
sum[i]+=y.num[i];
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
if(sum[i]>0){
z.bit=y.bit+1;
}
else{
z.bit=y.bit;
}
}
else{
for(;i<bit;i+=1){
sum[i]+=num[i];
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
if(sum[i]>0){
z.bit=bit+1;
}
else{
z.bit=bit;
}
}
for(i=0;i<z.bit;i+=1){
z.num[i]=sum[i];
}
return z;
}
bignum print(){
for(int i=bit-1;i>=0;i-=1){
printf("%d",num[i]);
}
}
};
bignum dp[106][106];
int main()
{
int n,ans=0;
/*dp[0][0].getval(9874651);
//dp[0][0].print();
dp[0][1].getval(8746);
//dp[0][1].print();
dp[0][0]=dp[0][1]*dp[0][0];
dp[0][0].print();
printf("n");
dp[0][0].getval(987465156);
dp[0][0]=dp[0][0]*5;
dp[0][0].print();
printf("n");
dp[0][0].getval(987465156);
dp[0][1].getval(8745156);
//printf("nfdsfas%d",dp[0][0].bit);
printf("aaaa%dn",987465156+8745156);
dp[0][0]=dp[0][0]+dp[0][1];
//printf("nfdsfas%d",dp[0][0].bit);
dp[0][0].print();
system("pause");*/
dp[1][1].getval(1);
for(int i=1;i<=100;i+=1){
for(int j=1;j<=i;j+=1){
dp[i+1][j+1]=dp[i+1][j+1]+dp[i][j]*(j+1);
dp[i+1][j]=dp[i+1][j]+dp[i][j]*j;
/*dp[i+1][j+1].print();
system("pause");*/
}
}
for(int i=1;i<=105;i+=1){
for(int j=1;j<=i;j+=1){
dp[i][0]=dp[i][0]+dp[i][j];
}
}
while(scanf("%d",&n)!=EOF){
dp[n][0].print();
puts("");
}
return 0;
}
. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |