Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:求助！ 2680 Computer Transformation 超时呀！

Posted by Silgon at 2009-02-08 13:14:01 on Problem 2680
In Reply To:求助！ 2680 Computer Transformation 超时呀！ Posted by:Silgon at 2009-02-07 23:51:26
```> #include <stdio.h>
> #include <string.h>
>
> char f[3][2][400] = {{"0", "1"}, {"0", "1"}, 0};
> char temp[400] = {0}, tmp[400] = {0};
> int n;
> int max(int a, int b)
> {
>     if (a > b) return a;
>     else  return b;
> }
> void fix(char *s)
> {
>      int i, len = strlen(s);
>      char t;
>      for (i = 0; i < len/2; i++)
>      {
>          t = s[i];
>          s[i] = s[len-1-i];
>          s[len-1-i] = t;
>      }
> }
> char *add(char *s1, char *s2)
> {
>      int i, c, len, len1 = strlen(s1), len2 = strlen(s2);
>      fix(s1);
>      fix(s2);
>      len = max(len1, len2);
>      for (i = len1; i < len; i++)      s1[i] = '0';
>      for (i = len2; i < len; i++)      s2[i] = '0';
>      memset(temp, 0, sizeof(temp));
>      for (c = i = 0; i < len; i++)
>      {
>          c += ((s1[i]-'0')+(s2[i]-'0'));
>          temp[i] = (char)(c%10+'0');
>          c /= 10;
>      }
>      if (c > 0)  temp[len++] = (char)(c+'0');
>      fix(temp);
>      fix(s1);
>      fix(s2);
>      return temp;
> }
>
> int main()
> {
>     int i;
>     while (scanf("%d", &n) != EOF)
>     {
>           memset(f, 0, sizeof(f));
>           f[0][0][0] = f[1][0][0] = f[2][0][0] = '0';
>           f[0][1][0] = f[1][1][0] = f[2][1][0] = '1';
>           for (i = 2; i <= n; i++)
>           {
>               strcpy(f[0][0], f[1][0]);
>               strcpy(f[0][1], f[1][1]);
>               strcpy(f[1][0], f[2][0]);
>               strcpy(f[1][1], f[2][1]);
>           }
>           printf("%s\n", f[2][0]);
>     }
>     //system("pause");
>     return 0;
> }
>
> 试了N次，老是超时！我的递推公式是：  f[n]双0的对数 = (f[n-2]双0的对数） ＋ （f[n-2]中1的个数）

AC了！！！！！
#include <stdio.h>

int result[1001][401], n;

void compute(int a[], int c[], int n)
{
int i, temp;
memset(c, 0, sizeof(result[0]));
if (n % 2 == 0)    c[1]++;
else    c[1]--;
for (i=1; i<=400; i++) {
temp = a[i] + a[i] + c[i];
if(temp < 0) {
temp += 10;
c[i] = temp % 10;
c[i+1]--;
continue;
}
c[i] = temp % 10;
c[i+1] = temp / 10;
}
}

int main()
{
int i, j;
memset(result, 0, sizeof(result));
for(i = 2; i<=1000; i++)         compute(result[i-1], result[i], i);
while (scanf("%d", &n) != EOF) {
if(n == 0) {
printf("0\n");
continue;
}
if(n == 1) {
printf("0\n");
continue;
}
for(i=400; i>0; i--)
if(result[n][i] != 0)   {
j = i;
break;
}
for (; j > 0; j--)
printf("%d", result[n][j]);
printf("\n");
}
//system("pause");
return 0;
}
```

Followed by: