UVa 10519 !! Really Strange !! (递推)

10519 - !! Really Strange !!

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1460

思路：注意到题目所说“Every two area have exactly two points to intersect and no three circles intersect in a common point”，所以第n个圆与其它n-1个圆共有2*(n-1)个交点，新生成2*(n-1)个区域，所以f(n)=f(n-1)+2*(n-1)，进而可得f(n)=n^2-n+2，边界f(0)=1。

完整代码：

/*0.012s*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;

char numstr[maxn];

struct bign
{
    int len, s[maxn];

    bign()
    {
        memset(s, 0, sizeof(s));
        len = 1;
    }

    bign(int num)
    {
        *this = num;
    }

    bign(const char* num)
    {
        *this = num;
    }

    bign operator = (const int num)
    {
        char s[maxn];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }

    bign operator = (const char* num)
    {
        len = strlen(num);
        for (int i = 0; i < len; i++) s[i] = num[len - i - 1] & 15;
        return *this;
    }

    ///输出
    const char* str() const
    {
        if (len)
        {
            for (int i = 0; i < len; i++)
                numstr[i] = '0' + s[len - i - 1];
            numstr[len] = '\0';
        }
        else strcpy(numstr, "0");
        return numstr;
    }

    ///去前导零
    void clean()
    {
        while (len > 1 && !s[len - 1]) len--;
    }

    ///加
    bign operator + (const bign& b) const
    {
        bign c;
        c.len = 0;
        for (int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if (i < len) x += s[i];
            if (i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }

    ///减
    bign operator - (const bign& b) const
    {
        bign c;
        c.len = 0;
        for (int i = 0, g = 0; i < len; i++)
        {
            int x = s[i] - g;
            if (i < b.len) x -= b.s[i];
            if (x >= 0) g = 0;
            else
            {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }

    ///乘
    bign operator * (const bign& b) const
    {
        bign c;
        c.len = len + b.len;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < b.len; j++)
                c.s[i + j] += s[i] * b.s[j];
        for (int i = 0; i < c.len - 1; i++)
        {
            c.s[i + 1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }

    ///除
    bign operator / (const bign &b) const
    {
        bign ret, cur = 0;
        ret.len = len;
        for (int i = len - 1; i >= 0; i--)
        {
            cur = cur * 10;
            cur.s[0] = s[i];
            while (cur >= b)
            {
                cur -= b;
                ret.s[i]++;
            }
        }
        ret.clean();
        return ret;
    }

    ///模、余
    bign operator % (const bign &b) const
    {
        bign c = *this / b;
        return *this - c * b;
    }

    bool operator < (const bign& b) const
    {
        if (len != b.len) return len < b.len;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }

    bool operator > (const bign& b) const
    {
        return b < *this;
    }

    bool operator <= (const bign& b) const
    {
        return !(b < *this);
    }

    bool operator >= (const bign &b) const
    {
        return !(*this < b);
    }

    bool operator == (const bign& b) const
    {
        return !(b < *this) && !(*this < b);
    }

    bool operator != (const bign &a) const
    {
        return *this > a || *this < a;
    }

    bign operator += (const bign &a)
    {
        *this = *this + a;
        return *this;
    }

    bign operator -= (const bign &a)
    {
        *this = *this - a;
        return *this;
    }

    bign operator *= (const bign &a)
    {
        *this = *this * a;
        return *this;
    }

    bign operator /= (const bign &a)
    {
        *this = *this / a;
        return *this;
    }

    bign operator %= (const bign &a)
    {
        *this = *this % a;
        return *this;
    }
};

int main()
{
    bign n;
    while (gets(numstr))
    {
        n = numstr;
        puts(n == 0 ? "1" : (n * n - n + 2).str());
    }
    return 0;
}

作者：csdn博客 synapse7

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， return
， this
， const
， operator
len
win10 10519、递推公式、递推宝、递推公式求通项公式、递推数列，以便于您获取更多的相关知识。