Home > Old Blog Posts > USACO Chapter 2 完整题解

USACO Chapter 2 完整题解


2.1.1 The Castle
用dfs搜索房间大小即可(应该就是所谓的Flood Fill吧)。
注意对题目的理解:“墙壁由它在相邻的小正方形的西部或南方来命名。”即相邻的小正方形的东部或北部有墙。所以在输出时要代换一下。

2.1.2 Ordered Fractions
先生成所有的没有约分的真分数,约分,去重,排序,再输出(巨水题,题解都感觉在说废话)。

2.1.3 Sorting a Three-Valued Sequence
用贪心。输入数据记录到数组a,生成排好序的数组b,然后开始循环。每次寻找a[i]与b[i]不相等的,先查找是否存在一个a[j],使得a[i]与a[j]交换后都能到自己正确的位置上;再查找是否存在a[j]使a[i]与a[j]交换后至少一个能到正确的位置;若两者都没有,则取最前面的一个a[j]和b[j]不相等的进行交换。每次交换次数+1。
最后统计次数输出。

2.1.4 Healthy Holsteins
这道题一开始就想复杂了。其实就是枚举..2^15=32768这都能爆才叫强。

2.1.5 Hamming Codes
这道题就是纯粹的位运算。枚举下一个数,先用异或,如t=a xor b,再取t中1的个数(详情可参考M67的位运算)即为不相同的个数,若此个数大于所要求的则加进数组里,继续枚举。注意海明距离要求两两距离满足此条件,即每两个之间都满足,而不是相邻的满足。输出注意10个一换行。

2.2.1 Preface Numbering
认真研究可发现,罗马数字记法其实也是比较特殊的十进制记法。总结得出:
string ge[10]={””,”I”,”II”,”III”,”IV”,”V”,”VI”,”VII”,”VIII”,”IX”},
shi[10]={””,”X”,”XX”,”XXX”,”XL”,”L”,”LX”,”LXX”,”LXXX”,”XC”},
bai[10]={””,”C”,”CC”,”CCC”,”CD”,”D”,”DC”,”DCC”,”DCCC”,”CM”},
qian[4]={””,”M”,”MM”,”MMM”};
接下来就很简单了..

2.2.2 Runaround Numbers
这道题数据实在太弱了,直接向后枚举判断就能过。
更好的方法是考虑字典序排列,9位数也最多只能有9!=362880种情况。

2.2.3 Subset Sums
DP。设f[i][j]为用前i个自然数组成j的方法数,则f[i][j]=f[i-1][j]+f[i-1][j-i]。边界条件f[1][1]=1。2<=i<=n,1<=j<=n*(n+1)/4。若n*(n+1)/4不是整数则直接输出0。

2.2.4 Party Lamps
注意到每个按钮按2次等同于没有按。所以实际情况只有8种。另外灯的状态有大量的重复,因此可以在空间上进行压缩(这是在别人题解上看到的,不压缩也能过)。最后,排序。

2.3.1 Longest Prefix
DP。设f[i]为前i个字符可以用前缀表示的长度,若i-j+1..i的部分匹配于某个前缀(二分查找)则f[i]=max(f[i-j]+j,f[i])。总方程f[i]=max{f[i-j]+j}。初始条件f[0]=0。

2.3.2 Cow Pedigrees
DP。设f[i][j]为i个节点最多j层高度的二叉树的个数。则f[i][j]=最多j层高度的左子树的个数*最多j层高度的右字树的个数。则最后结果为f[N][K]-f[N][K-1]。

2.3.3 Zero Sum
傻瓜式枚举。没什么可多说的。

2.3.4 Money Systems
很容易得到方程f[i][j]=f[i-1][j]+f[i-1][j-a[i]]+f[i-1][j-2*a[i]]+…+f[i-1][j-k*a[i]],其中f表示前i种面额组合出j面值的方法数,k=(int)j/a[i]。但这样复杂度较高。进一步分析后改进方程为f[i][j]=f[i-1][j]+f[i][j-a[i]],复杂度为O(n^2)。

2.3.5 Controlling Companies
这道题数据极弱,直接一遍遍扫就行了。由于公司不超过100个,关系链长度不超过100,搜100次即可。

2.4.1 The Tamworth Two
很水的——模拟题吧。建个六维数组判重-人坐标2维,牛坐标2维,各自方向2维..其它的没难度了。

2.4.2 Overfencing
和castle方法基本一样,只不过对输入数据的处理会麻烦点。总体还是水题。

2.4.3 Cow Tours
先用floyd过一遍,取任两个牧区中的点i,j,maxx[i]为从i点出发的最远距离,maxl为maxx中的最大值,则直径为max(maxx[i]+maxx[j]+dis(i,j),maxl)。也可先求出最短的maxx[i]+maxx[j]+dis(i,j),再和maxl比较取最大值为答案。

2.4.4 Bessie Come Home
Floyd水题。

2.4.5 Fractions to Decimals
这道恶心题在判重上折腾了好久,不知脑子是哪里进水了,其实用个布尔数组就行了。

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: