USACO Raucous Rockers

这道题的正解是三维的动态规划，和背包问题很相似。本人起初也想到了背包，不过只写了个二维的，因此一直没有通过。但是，由于N的最大值只有20，并且要计算某个情况下可以收入的歌曲数非常容易的（贪心算法）。因此本人使用了枚举，用一个long型表示几个歌曲的选择情况，再用test函数计算可以收入的歌曲数量。

为什么要使用三维动态规划呢？如果仅仅用max[i][j]表示第i个光盘占用前j分钟可以装下的歌曲数量，就无法体现题目的一个约束条件“The songs on the set of disks must appear in the order of the dates that they were written.”，因此不具有最优子结构性质，因此还要增加第三维k，用来表示最后一个专辑的编号。

实测表明动态规划算法在时间上明显优于枚举算法。

使用枚举算法的代码：

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MXN 23
05
06 long base[MXN];
07 int N,T,M;
08 int len[MXN];
09
10 int test(long state)
11 {
12     int i,c;
13     int t,d;
14     for(i = c = t = d = 0;i < N && d < M;i ++)
15     {
16         if(state & base[i])        //add this song
17         {
18             if(len[i] + t <= T)
19             {
20                 t += len[i];
21                 c ++;
22             }
23             else if(d < M - 1)
24             {
25                 t = len[i];
26                 d ++;
27                 c ++;
28             }
29             else break;
30         }
31     }
32     //printf("%d\n",c);
33     return c;
34 }
35
36 void calc_base()
37 {
38     int i;
39     base[0] = 1;
40     for(i = 1;i < MXN;i ++)
41         base[i] = base[i - 1] << 1;
42 }
43
44 int get_max(int a,int b)
45 {
46     if(a > b)    return a;
47     return b;
48 }
49
50 int main()
51 {
52     freopen("rockers.in","r",stdin);
53     freopen("rockers.out","w",stdout);
54     scanf("%d%d%d",&N,&T,&M);
55     long i;
56     int ans;
57     for(i = 0;i < N;)
58     {
59         scanf("%d",&len[i]);
60         if(len[i] <= T)    i ++;
61         else N --;
62     }
63     calc_base();
64     for(i = ans = 0;i < base[N];i ++)
65     {
66         ans = get_max(test(i),ans);
67     }
68     printf("%d\n",ans);
69     fclose(stdin);
70     fclose(stdout);
71     return 0;
72 }

使用动态规划的代码

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MXN 22
05
06 int len[MXN];
07 int N,T,M;
08 int max[MXN][MXN][MXN];
09
10 void solve()
11 {
12     int i,j,k,v;
13     for(i = 0;i < MXN;i ++)
14     for(j = 0;j < MXN;j ++)
15     for(k = 0;k < MXN;k ++)
16         max[i][j][k] = -1;
17     max[1][0][0] = 0;
18     for(i = 1;i <= M;i ++)
19         for(j = 0;j <= T;j ++)
20             for(k = 0;k <= N;k ++)
21             {
22                 //printf("disc:%d time:%d last:%d max:%d\n",i,j,k,max[i][j][k]);
23                 if(max[i][j][k] != -1)
24                     for(v = k + 1;v <= N;v ++)
25                     {
26                         if(j + len[v] <= T)
27                         {
28                             if(max[i][j][k] + 1 > max[i][j + len[v]][v])    max[i][j + len[v]][v] = max[i][j][k] + 1;
29                         }
30                         else
31                         {
32                             if(max[i][j][k] + 1 > max[i + 1][len[v]][v])    max[i + 1][len[v]][v] = max[i][j][k] + 1;
33                         }
34                     }
35             }
36 }
37
38 void output()
39 {
40     int ans = 0;
41     int i,j,k;
42     for(i = 1;i <= M;i ++)
43         for(j = 1;j <= T;j ++)
44             for(k = 1;k <= N;k ++)
45                 if(max[i][j][k] > ans)    ans = max[i][j][k];
46     printf("%d\n",ans);
47 }
48
49 int main()
50 {
51     freopen("rockers.in","r",stdin);
52     freopen("rockers.out","w",stdout);
53     scanf("%d%d%d",&N,&T,&M);
54     int i;
55     for(i = 1;i <= N;)
56     {
57         scanf("%d",&len[i]);
58         if(len[i] <= T)    i ++;
59         else N --;
60     }
61     if(N == 0)
62     {
63         printf("0\n");
64         return 0;
65     }
66     solve();
67     output();
68     fclose(stdin);
69     fclose(stdout);
70     return 0;
71 }

USACO American Heritage

这题在很多书籍上都出现过，可以说是基础了，不知为何USACO把它放在这里，由于数据规模很小，使用递归解决很方便。

代码如下：

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAXLENGTH 30
05
06 int n;
07 char in_order[MAXLENGTH],pre_order[MAXLENGTH];
08 int in_location[255];
09
10 //一边计算一边输出结果，省去额外构建树的空间
11 void create_tree(int ib,int pb,int len)
12 {
13     if(len == 1)
14     {
15         printf("%c",pre_order[pb]);
16         return;
17     }
18     if(in_location[pre_order[pb]] > ib)    //have left sub-tree
19     {
20         create_tree(ib,pb + 1,in_location[pre_order[pb]] - ib);
21     }
22     if(in_location[pre_order[pb]] < ib + len - 1)    //have right sub-tree
23     {
24         create_tree(in_location[pre_order[pb]] + 1,pb + in_location[pre_order[pb]] - ib + 1,len - (in_location[pre_order[pb]] - ib) - 1);
25     }
26     printf("%c",pre_order[pb]);
27 }
28
29 void locate(int *arr,char *str)     //预处理字符的位置
30 {
31     int i;
32     for(i = 0;i < n;i ++)
33         arr[(int)str[i]] = i;
34 }
35
36 int main()
37 {
38     freopen("heritage.in","r",stdin);
39     freopen("heritage.out","w",stdout);
40     scanf("%s\n",in_order);
41     scanf("%s",pre_order);
42     n = strlen(in_order);
43     locate(in_location,in_order);
44     create_tree(0,0,n);
45     putchar('\n');
46     return 0;
47 }

USACO A Game

本人是看题解才过的，直到现在还弄不清什么叫作"best possible" opponent，本人认为这题是背包，而且还是比较奇怪的背包。

只贴代码了，如果有朋友理解题意的麻烦留个言，谢了！

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #define MAXN 110
04
05 long num[MAXN],sum[MAXN] = {},best[MAXN][MAXN] = {};
06 int N;
07
08 void init()
09 {
10     scanf("%d",&N);
11     int i;
12     for(i = 1;i <= N;i ++)
13         scanf("%ld",&num[i]);
14 }
15
16 long max(long a,long b)
17 {
18     if(a > b)    return a;
19     return b;
20 }
21
22 void solve()
23 {
24     int i,len;
25     for(i = 1;i <= N;i ++)
26     {
27         sum[i] = sum[i - 1] + num[i];
28         best[i][i] = num[i];
29     }
30     for(len = 1;len < N;len ++)
31         for(i = 1;i <= N - len;i ++)
32             best[i][i + len] = max(num[i] + sum[len + i] - sum[i] - best[i + 1][len + i],num[i + len] + sum[len + i - 1] - sum[i - 1] - best[i][len + i - 1]);    //这里sum的处理方法和NOIP2011质检员那题相同
33     printf("%ld %ld\n",best[1][N],sum[N] - best[1][N]);
34 }
35
36 int main()
37 {   
38     freopen("game1.in","r",stdin);
39     freopen("game1.out","w",stdout);
40     init();
41     solve();
42     return 0;
43 }

Gnome3之Shell Extension

在同学推荐下，本人下载安装了openSUSE 12.1版（本人一直使用Linux Mint，不过不太适应Linux Mint 12，因此一直停留在11版）。由于不太喜欢KDE的风格，俺选择了Gnome 3.2。

用了几天发现Gnome 3提供了一个叫Gnome shell extension的东西，就研究了一下。下面推荐几个认为不错的扩展。

貌似用Chrome打开下面的链接是不能安装扩展的，只有开启GNOME Shell Integration扩展的Firefox可以。

Remove Accessibility
点此安装

Media player indicator
点此安装

Touchpad Indicator
点此安装

Net Monitor
点此安装

Input-Method Status Indicator
比ibus自带的那个好多了
点此安装

Dock
提供一个额外的dock
点此安装

USACO Riding the Fences

本题考察的是无向图上的欧拉路问题，这题也是前面那个text中的例题，因此，思路并不复杂。
不过需要注意一些细节问题：
首先，是起点的选择。可以找到欧拉路的图有两种，其一是每个顶点度数都是偶数，另一个是仅有两个度数为奇数的顶点。要针对这两种情况分别考虑。
其次，是无向图转换有向图，要保证删边时两条都要删掉。
还有，重边的问题，本人使用一个cnt变量记录每条边的数量。
最后，数组可以开大一点，本人开到510在第八个数据会出错，扩大到600就不会了。不知是什么原因。

代码如下，本人没有写检查是否是欧拉图的代码。

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

001 #include <stdio.h>
002 #include <stdlib.h>
003 #define MXN 600
004
005 typedef struct node
006 {
007     int v;
008     struct node *next;
009     int cnt;    //whether the route exists and its count
010 }node;
011
012 node *first[MXN];
013 int deg[MXN] = {};
014 int route[MXN] = {};
015 int cnt;
016 int max = 0;
017 int min = MXN;
018
019 void add_edge(int b,int e,long cnt)
020 {
021     node *p;
022     p = malloc(sizeof(node));
023     p->cnt = cnt;
024     p->v = e;
025     p->next = first[b];
026     first[b] = p;
027 }
028
029
030 long adj[MXN][MXN] = {};
031 void init()
032 {
033     int F;
034     int b,e;
035     scanf("%d\n",&F);
036     while(F --)
037     {
038         scanf("%d%d",&b,&e);
039         adj[b][e] ++;
040         adj[e][b] ++;
041         deg[b] ++;
042         deg[e] ++;
043         if(b > e)
044         {
045             if(b > max)    max = b;
046             if(e < min)    min = e;
047         }
048         else
049         {
050             if(b < min)    min = b;
051             if(e > max)    max = e;
052         }
053     }
054     //convert adjcency matrix to adjcency list thus node->v is in increasing order
055     int i,j;
056     for(i = min;i <= max;i ++)
057         for(j = max;j >= min;j --)
058             if(adj[i][j] > 0)
059                 add_edge(i,j,adj[i][j]);
060 }
061
062 int findstart()
063 {
064     int i;
065     int odd_cnt = 0;
066     for(i = 1;i <= max;i ++)
067         if(deg[i] % 2)
068             odd_cnt ++;
069     if(odd_cnt == 2)
070         for(i = min;i <= max;i ++)
071             if(deg[i] % 2)    return i;   //use the min odd node as start node
072
073     return min;     //no odd nodes, use the minimum node as start node
074 }
075
076 void disable(int b,int e)    //delete one edge from b to e
077 {
078     node *p;
079     for(p = first[b];p != NULL;p = p->next)
080         if(p->v == e)
081         {
082             p->cnt --;
083             return;
084         }
085 }
086
087 void solve(int s)
088 {
089     node * p;
090     for(p = first[s];p != NULL;p = p->next)
091     {
092         if(p->cnt > 0)
093         {
094             p->cnt --;
095             disable(p->v,s);
096             solve(p->v);
097         }
098     }
099     route[cnt ++] = s;
100 }
101
102 void pt()
103 {
104     int i;
105     for(i = cnt - 1;i >= 0;i --)    //output in reverse order
106         printf("%d\n",route[i]);
107 }
108
109 void debug()
110 {
111     int i;
112     node * p;
113     for(i = min;i <= max;i ++)
114     {
115         printf("%d ->",i);
116         for(p = first[i]; p != NULL;p = p->next)
117             printf(" %d",p->v);
118         printf("\n");
119     }
120 }
121
122 int main()
123 {
124     freopen("fence.in","r",stdin);
125     freopen("fence.out","w",stdout);
126     init();
127     //debug();
128     cnt = 0;
129     solve(findstart());
130     pt();
131     fclose(stdin);
132     fclose(stdout);
133     return 0;
134 }