NOIP 2000 解题报告

进制转换
其实负数进制和正数的解决方法是类似的，需要注意的是计算机计算余数符号取决于被除数，因此如果为负数则要再加上除数使其变为正数。还需要注意的是，整除不能再使用num /= base了，因为这种方法不适用于负数，取而代之的是num = (num - 余数（正的）) / base.

贴一小段函数

C语言: 高亮代码由发芽网提供

01 void process(int n,int b)
02 {
03     int i;
04     top = 0;
05     printf("%d = ",n);
06     while(n != 0)
07     {
08         stack[top] = n % b;
09         if(stack[top] < 0)  stack[top] -= b;
10         n = (n - stack[top]) / b;
11         //it is different from 'n /= b' which only works for positive integer;
12         top ++;
13     }
14     for(i = top - 1;i >= 0;i --)    printf("%c",map[stack[i]]);
15     //map stores the corresponding alphabet of number i;
16     printf(" (base %d)\n",b);
17 }

最大乘积

本题是矩阵连乘的改编，可以参考算法导论。
状态表示：f[n][i][j]在第i个字符和第j个字符中放置n个乘号可以获得的最大乘积。
转移方程：f[n][i][j] = max{f[n - k][i][t] * f[n - k - 1][t + 1][j]}
                    0 <= k <= n - 1 i <= t <= j - 1
f[K][0][N - 1]即为最终结果。

单词接龙
由于单词数量不多，考虑搜索。先计算每个单词直接是否可以连接和重合部分的长度，然后DFS找最长串即可。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04
05 char str[21][50];
06 int len[21];
07 int adj[21][21];
08 int used[21];
09 int n;
10 int ans = 0;
11 char begin;
12
13 int calc_dist(int a,int b)
14 {
15     int i,l;
16     if(len[a] > len[b]) l = len[b];
17     else l = len[a];
18     for(i = 1;i < l;i ++)
19     {
20         if(strncmp(str[a] + len[a] - i,str[b],i) == 0)  return i;
21     }
22     return 0;
23 }
24
25 void dfs(int now,int tot)
26 {
27     int i;
28     if(tot > ans)
29         ans = tot;
30     for(i = 0;i < n;i ++)
31     {
32         if(used[i] < 2 && adj[now][i] > 0)
33         {
34             used[i] ++;
35             dfs(i,tot + len[i] - adj[now][i]);
36             used[i] --;
37         }
38     }
39 }
40
41 int main()
42 {
43     int i,j;
44     scanf("%d",&n);
45     for(i = 0;i < n;i ++)
46     {
47         scanf("%s\n",str[i]);
48         len[i] = strlen(str[i]);
49     }
50     scanf("%c",&begin);
51
52     for(i = 0;i < n;i ++)
53         for(j = 0;j < n;j ++)
54             adj[i][j] = calc_dist(i,j);
55
56     for(i = 0;i < n;i ++)
57     {
58         if(str[i][0] == begin)
59         {
60             used[i] = 1;
61             dfs(i,len[i]);
62             used[i] = 0;
63         }
64     }
65     printf("%d\n",ans);
66     return 0;
67 }