Coin163

首页 > woj1034 hdu1290 Cut the Apple 数学题

woj1034 hdu1290 Cut the Apple 数学题

相关标签: apple woj 水题 acm 数学

2020腾讯云双十一活动,全年最低!!!(领取3500元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1074

【阿里云】双十一活动,全年抄底价,限时3天!(老用户也有),
入口地址https://www.aliyun.com/1111/home

题意: 题意跟hdu1290是一样的 切n刀最多可以把蛋糕分成多少份,注意直接2^n是错的 仔细想想,问题转化成N个平面最多可以把空间划分成多少份,公式是fn=(n^3+5n)/6+1 数据比较大,记得用64位整数long long 代码: /* * Author: NICK WONG * Created Time:

2/14/2016 18:29:09 * File Name:

*/#include<iostream>#include<sstream>#include<fstream>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<cstdio>#include<cstdlib>#include<cstring>#include<cctype>#include<cmath>#include<ctime>#include<iomanip>using namespace std;#define out(x) cout<<#x<<": "<<x<<endlconst double eps(1e-8);const int maxn=10100;const long long maxint=-1u>>1;const long long maxlong=maxint*maxint;typedef long long lint;lint n;void init(){}void work(){

lint ans=(n*n*n+5*n+6)/6;

cout<<ans<<endl;}int main(){

while(cin>>n)

{

init();

work();

}

return 0;} 推导过程 由二维的分割问题可知,平面分割与线之间的交点有关,即交点决定射线和线段的条数,从而决定新增的区域数。试想在三维中则是否与平面的交线有关呢?当有n-1个平面时,分割的空间数为f(n-1)。要有最多的空间数,则第n个平面需与前n-1个平面相交,且不能有共同的交线。即最多有n-1 条交线。而这n-1条交线把第n个平面最多分割成g(n-1)个区域。(g(n)为(1)中的直线分平面的个数 )此平面将原有的空间一分为二,则最多增加g(n-1)个空间。

故:f=f(n-1)+g(n-1)

ps:g(n)=n(n+1)/2+1

=f(n-2)+g(n-2)+g(n-1)

……

=f(1)+g(1)+g(2)+……+g(n-1)

=2+(1*2+2*3+3*4+……+(n-1)n)/2+(n-1)

=(1+2^2+3^2+4^2+……+n^2-1-2-3-……-n )/2+n+1

=(n^3+5n)/6+1 参考: 分割平面与空间公式 Cut the Apple Time Limit: 1000MS

Memory Limit: 65536KB

Difficulty: 3 Total Submit: 8

Accepted: 2

Special Judge: No Description On the way home, DragonFly has got an extraordinarily large apple. He would like to share it with his friends. Now he wants to get as many pieces as possible with n cuts. But he cannot decide how to cut it, because the apple is rather delicious. Now he needs your help. Input

Each line contains an integer n (0<= n <= 100000).

Input will be terminated by EOF. Output

You should print the largest number of pieces by n cuts of each case . Sample Input 1 2 3 Sample Output 2 4 8 Hint Source WHUCPC04 Final Round  

原文

题意: 题意跟hdu1290是一样的 切n刀最多可以把蛋糕分成多少份,注意直接2^n是错的 仔细想想,问题转化成N个平面最多可以把空间划分成多少份,公式是fn=(n^3+5n)/6+1 数据比较大,记得用64位整

------分隔线----------------------------
相关推荐