首页 / 软件开发 / 数据结构与算法 / UVa 10519 ！！ Really Strange ！！ （递推）

UVa 10519 ！！ Really Strange ！！ （递推）2014-07-2510519 - ！！ 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] = "";}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