HDU5047 - Sawtooth[找规律]

Problem ： Sawtooth
Description :

一个无限大的矩形区域，现在$N$个“M”型的折线，可以看下题中的图，两边两条线是平行的(其实不平行也是没关系的，答案都是一样)，问最多能把这个矩形分成多少个区域。

Solution：

就是找规律，首先，我们会想到另一种最简单的情况，就是$N$条直线能把这个区域分成多少个区域，我们会看这条线与前面$N-1$条线有多少个交点；那么这个题我们也是一样的，把当前这个“M”拆成4条射线，然后每条射线来与前面的$4(N-1)$条射线求交点，这里要贪心最大化，就是说，每条射线在题目要求的范围内要穿过所有射线并出头一点，这样可以发现，前3条射线中每条射线使得区域数在前$4(N-1)$条射线所形成的最大区域数上增加$4 (N - 1)$个，而最后一条射线会比之前的每一条射线多出1个区域也就是$4(N-1) +1$，这是因为最后一条射线会比之前3条射线多交一条射线.

$$\begin{split} ans_n&=ans_{n-1}+4*4(n-1)+1\\ &=ans_{n-1}+16n-15\\ &=ans_{n-2}+16(n+n-1)-15*2\\ &\vdots \\ &=ans_1+16(2+3+\cdots+n)-15(n-1)\\ &=2+(8n+1)(n-1) \end{split}$$

这里$n$可达$10^{12}$，所以还需要用大整数搞一下.

Code ：

#include 
#include typedef long long LL;#define MAX_LINE 64int toString(LL n, int a[])
{int top = 0;for (; n ; n /= 10)a[top++] = n % 10;if (!top)a[top++] = 0;return top;
}// ans = (8 * n + 1) * (n - 1) + 2int main()
{int T, K = 1;for (scanf("%d", &T); T-- ; K++) {LL n;scanf("%I64d", &n);LL tmp1 = 8LL * n + 1, tmp2 = n - 1;int digit1[MAX_LINE], digit2[MAX_LINE];int len1 = 0, len2 = 0;memset(digit1, 0, sizeof(digit1));memset(digit2, 0, sizeof(digit2));len1 = toString(tmp1, digit1);len2 = toString(tmp2, digit2);int ans[MAX_LINE];memset(ans, 0, sizeof(ans));for (int i = 0; i < len1; i++)for (int j = 0; j < len2; j++)ans[i + j] += digit1[i] * digit2[j];ans[0] += 2;int up = 0;for (int i = 0; i < len1 + len2 + 2; i++) {int tmp = up + ans[i];ans[i] = tmp % 10;up = tmp / 10;}int top = MAX_LINE;for (; top > 0 && ans[top - 1] == 0; top--);printf("Case #%d: ", K);for (int i = top - 1; i >=0 ; i--)printf("%d", ans[i]);puts("");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！