数学题(分割平面问题)-UVA 10079-Pizza Cutting

浅浅的花香味﹌ 2022-05-16 08:05 220阅读 0赞

*  # 数学题(分割平面问题)-UVA 10079-Pizza Cutting #

--------------------

*  ## 题目链接：[10079 - Pizza Cutting][] ##
 *  ## 思路： ##

就切蛋糕，问切n次最多能把蛋糕分成几份

直线分割问题，假设现在已经切n-1次，那么**第n次的直线与前面直线有n-1个交点，多出平面为：（n-1）+1**

**可得递推式：![F(n)=F(n-1)+n][F_n_F_n-1_n]**

**用高中数学数列知识，可得通项公式为：![F(n)=(n-1)(n+2)/2+2][F_n_n-1_n_2_2_2]**

*  ## 代码： ##

#include<iostream>
    using namespace std;
    int main()
    {
        long long N;
        long long Res;
        while(cin>>N,N>=0)
        {
            /*if(N%2)   //防止溢出，实际上不会溢出。。
                Res=2+((N-1)/2)*(N+2);
            else
                Res=2+((N+2)/2)*(N-1);*/
            Res=2+((N+2)*(N-1))/2;
            cout<<Res<<endl;
        }
        return 0;
    }

*  ## Tip： ##

**看到数据：N (0 ≤ N ≤ 210000000)，我觉得不妙可能long long也受不了，所以考虑(n-1)(n+2)相乘可能会溢出，分成奇数偶数进行计算，其实不会溢出。。。**

[10079 - Pizza Cutting]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1020
[F_n_F_n-1_n]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20F%28n%29%3DF%28n-1%29&plus;n
[F_n_n-1_n_2_2_2]: https://private.codecogs.com/gif.latex?%5Cdpi%7B120%7D%20F%28n%29%3D%28n-1%29%28n&plus;2%29/2&plus;2

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关基础算法题——折线分割平面（规律）

题目 [测试平台][Link 1] 我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成

约定不等于承诺〃/ 2023年02月27日 05:41/ 0 赞/ 15 阅读

相关 uva 10003——Cutting Sticks

题意：给定一长为L的木棍和n个切割点，每次切割的费用为切割的长度，求最小的费用。思路：dp,子问题是区间（i，j）的最小费用，临界是（i,j)只有一个切割点。dp

曾经终败给现在/ 2022年08月17日 14:24/ 0 赞/ 22 阅读

相关 UVA 10079 - Pizza Cutting

Time Limited: 8.333 Seconds When someone calls Ivan lazy, he claimsthat it is his intel

￡神魔★判官ぃ/ 2022年08月09日 13:47/ 0 赞/ 18 阅读

相关折线分割平面

Problem Description 我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成

不念不忘少年蓝@/ 2022年07月13日 03:40/ 0 赞/ 200 阅读

相关平面分割

平面分割描述 Description 【问题描述】　　同一平面内有n（n≤500）条直线，已知其中p（p≥2）条直线相交于同一点，则这n条直线最多能将平面分割成

╰半夏微凉°/ 2022年07月11日 08:51/ 0 赞/ 212 阅读

相关 Pizza Separation——————数学

题意翻译学生Vasya和Petya在比特州立大学就读。在某一个课间他们打算订一个披萨。在这道题目中披萨是有着某个半径长度的标准圆。披萨已经被切成了 n 块，第 i 块的

ゞ浴缸里的玫瑰/ 2022年05月16日 08:24/ 0 赞/ 134 阅读

相关数学题(平面分割问题)HDU 2050-折线分割平面

数学题(平面分割问题)HDU 2050-折线分割平面 -------------------- 题目链接：[折线分割平面][Link 1] 基础

「爱情、让人受尽委屈。」/ 2022年05月16日 08:05/ 0 赞/ 208 阅读

相关数学题(分割平面问题)-UVA 10079-Pizza Cutting

数学题(分割平面问题)-UVA 10079-Pizza Cutting -------------------- 题目链接：[10079 - Pizza

浅浅的花香味﹌/ 2022年05月16日 08:05/ 0 赞/ 221 阅读

相关数学题(直线分割)UVA 10167-Birthday Cake

数学题(直线分割)UVA 10167-Birthday Cake -------------------- 题目链接：[10167 - Birthday

超、凢脫俗/ 2022年05月15日 22:54/ 0 赞/ 167 阅读

相关 uva 10079 - Pizza Cutting

[题目链接：uva 10079 - Pizza Cutting][uva 10079 - Pizza Cutting] 题目大意：有一个披萨，切n刀，问最多可以切几

客官°小女子只卖身不卖艺/ 2022年05月14日 13:52/ 0 赞/ 139 阅读