讨论 / 请求重测!!!
飞雪天涯 2008-11-07 06:49:00
点我顶贴 收藏 删除
[color=red]怎么可能无输出!我明明有输出的说……Xeost[]们尊重点劳动成果吧!我编了2h!!![/color]

/*

比赛(Test):查看题目 Show Problem

赛题题目:自然的雪糕

所属比赛:回归自然模拟赛

问题编号:385 [提交该赛题]

描述: 题目背景

话说某天小岛从超市里买了许许多多的..雪糕....本来他打算存在冰箱里慢慢享用的...

结果这件事情被寝室里的adx发现了...于是不幸的事情发生了...

题目叙述

小岛回忆起了当时de场景...

那时...寝室里包括自己一共聚集了 n 个人...我从超市里共买了 m 袋不同种类的雪糕.....

醒来之后身边一支雪糕也没有了.....我还可以隐约知道...每个人都不会一支雪糕也不拿...

小岛想知道自己的雪糕现在会在哪...那么当时的情况下...一共有多少种不同的可能呢..?

数据规模

对于30% 的数据,n <= 10,m <= 20。

对于100%的数据, n <= 100,m<= 100。

样例解释

雪糕以 1-3 编号。共六种情况,其中三种为:

1. {1} {2, 3}

2. {2} {1, 3}

3. {3} {1, 2}

另三种与之对称。

输入格式: 一行两个数 n,m...

输出格式: 一个数表示当时可能的情况数目...

输入文件: 直接输入即可

输出文件: 直接输出即可 注意,不要在最后输出空行或空格!

样例输入: 3 3

样例输出: 6

*/

#include<iostream>

#define MAXN 100

#define MAXM 100

using namespace std;

struct mynode{

int len;

string data;

};

mynode dp[MAXM+1][MAXN+1];

//F(n,m)=F(n-1,m-1)+m*F(n-1,m)

mynode zero={1,"0"},one={1,"1"},fuyi={1,"fyi"};

mynode jia (mynode a,mynode b){

int jinwei=0,temp;

mynode c;

string aa,bb,cc="";

aa=a.data;

bb=b.data;

while (aa.size()<bb.size()) aa="0"+aa;

while (aa.size()>bb.size()) bb="0"+bb;

for (int i=aa.size()-1;i>=0;i--){

temp=jinwei+(int)(aa[i]-’0’)+(int)(bb[i]-’0’);

jinwei=temp/10;

temp%=10;

cc+=(char)(temp+’0’);

}

if (jinwei!=0)

cc=(char)(jinwei+’0’)+cc;

c.len=cc.size();

c.data=cc;

//cout<<"jia "<<a.data<<" "<<b.data<<"="<<c.data<<endl;

return c;

}

mynode cheng(mynode a,mynode b){

mynode temp=zero,ppp=b;

for (int i=a.data.size()-1;i>=0;i--){

for (int j=0;j<a.data[i]-’0’;j++)

temp=jia(temp,ppp);

ppp.len++;ppp.data=ppp.data+"0";

}

//cout<<"cheng "<<a.data<<" "<<b.data<<"="<<temp.data<<endl;

return temp;

}

mynode tonode(int n){

string temp="";

while (n){

temp=(char)(n%10+’0’)+temp;

n/=10;

}

mynode temp2;

temp2.len=temp.size();

temp2.data=temp;

return temp2;

}

mynode fac(int n){

if (n==1) return one;

return cheng(fac(n-1),tonode(n));

}

mynode output(mynode x){

cout<<x.data;

}

bool eq(mynode a){

if (a.data=="fyi")

return true;

return false;

}

mynode work (int m,int n){

if (!eq(dp[m][n])) return dp[m][n];

//mynode ans;

if (m<n) return zero;

if (m==n) return one;

if (n==0) return zero;

if (n==1) return one;

dp[m][n]=jia(work(m-1,n-1),cheng(tonode(n),work(m-1,n)));

return dp[m][n];

}

int main (void){

for (int i=0;i<=MAXN;i++)

for (int j=0;j<=MAXN;j++)

dp[i][j]=fuyi;

int n,m;cin>>n>>m;

--n;

//output(zero);cout<<’ ’;output(one);

output(cheng(work(m,n),fac(n)));

//while(1);

return 0;

}

#1 飞雪天涯@2008-11-07 06:30:00
回复 删除
renqing赶快处理下!!!
#2 飞雪天涯@2008-11-07 06:30:00
回复 删除
[color=blue]55555555555555555[/color]
#3 飞雪天涯@2008-11-07 06:32:00
回复 删除
快啊!
#4 飞雪天涯@2008-11-07 06:33:00
回复 删除
评完了我就死定了!!!

TX们要把我骂死了!!!

#5 linshutan@2008-11-07 06:34:00
回复 删除
我第一题全超..KMP也能..我无奈了.

RQ帮我看看啊.

#6 飞雪天涯@2008-11-07 06:40:00
回复 删除
快!!!
#7 飞雪天涯@2008-11-07 06:42:00
回复 删除
我求rq啦!!
#8 linshutan@2008-11-07 06:44:00
回复 删除
第一题..一定要用readln(s1);

我用char读如数组全超..这什么情况!!!

#9 飞雪天涯@2008-11-07 06:46:00
回复 删除
我用string的!
#10 renqing@2008-11-07 06:49:00
回复 删除
已经重测,结果相同
查看更多回复
提交回复