2014 网选上海赛区 hdu 5047 Sawtooth-白红宇

题意：求n个'M'型的折线将一个平面分成的最多的面数！

思路：我们都知道n条直线将一个平面分成的最多平面数是 An = An-1 + n+1

也就是f(n) = (n*n + n +2)/2

对于一个'M'型的折线呢？它有四条线，但是由于三个顶点的关系导致划分的平面

的数目减少了9个！所以有递推公式 f(n) = (m*m + m + 2)/2 - 9*n; m = 4*n

最后 f(n) = (8*n+1)*(n-1)+2)

由于 n<=1e12 , 所以回报 long long！那么对于大于1e9的数我做了大数乘法的处理！

1 #include
         2 #include
          3 #include
           4 using namespace std; 5   6 void fun(int a[], long long b, int &l){
     //将一个数进行拆分放到数组中！  7     while(b){ 8         a[l++] = b%10; 9         b/=10;10     }11 }12 13 14 int a[30], b[30], c[30];15 int la, lb;16 17 void cal(){18     memset(c, 0, sizeof(c));19     for(int i=0; i
           0) c[len++] = k;30     k = 2;31     for(int i=0; i
            0) c[len++] = k;37     38     for(int i = len-1; i>=0; --i)39         printf("%d", c[i]);40     printf("\n");41 }42 43 int main(){44     long long n;45     int t, cnt=0;46     scanf("%d", &t); 47     while(t--){48         scanf("%I64d", &n); 49         printf("Case #%d: ", ++cnt);50         if(n <= 1e9)51             printf("%I64d\n", (8*n+1)*(n-1)+2);52         else{53             long long x = 8*n+1;54             long long y = n-1;55             la=lb=0;56             fun(a, x, la);57             fun(b, y, lb);58             cal();59         }60      } 61     return 0;62 }

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3997036.html，如需转载请自行联系原作者