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

USACO Chapter 1 完整题解


1.1.1 Your Ride Is Here
水模拟。

1.1.2 Greedy Gift Givers
水模拟。

1.1.3 Friday The Thirteenth
简单模拟题。题目数据量保证不会超时。按天数递增。

1.1.4 Broken Necklace
简单模拟题。

1.2.1 Milking Cows
简单模拟题,注意按区间存储。

1.2.2 Transformations
解题报告:
一开始误入歧途,用复数法解决旋转,代价是编了很巨的代码,但还是过了。其实可以按行读入按列存储来完成90度转换。复数z*i即逆时针旋转90度。

1.2.3 Name That Number
枚举所有单词,看是否满足所输入的数字,若满足则输出。

1.2.4 Palindromic Squares
很简单,没有什么难点。注意输出10进制以上时使用字母便是。

1.2.5 Dual Palindromes
直接利用上一题进制转换和判断的函数即可。

1.3.1 Mixing Milk
贪心,每次取价格最便宜的直到没有,先快排。

1.3.2 Barn Repair
很简单的贪心。每次取当前相距最近的两个有牛的牛棚并相连,直到满足木板数目的限制条件为止。
1.3.3 Calf Flac
从第一个循环到最后一个字符,枚举回文中心向两边扩展,复杂度为O(n^2)。输入时注意用C的输入输出(切记),fscanf和fprintf单个字符读入来解决空格和换行问题。

1.3.4 Prime Cryptarithm
没有什么难点。穷举即可。

1.4.1 Packing Rectangles
模拟+枚举,十分繁琐。最后还出了点问题:在自己的机子上数据点全过,但是在测评机上却不能。后来经检查是数组越界..倒是加了些经验。

1.4.2 The Clocks
一开始用广搜/深搜,都不能过。分析题目特点,每个操作重复4次即复原,且各操作先后顺序改变,结果不变。先预存一张表,a[i][j]表示只把第i个钟转90度而其它钟不变所需第j种方法的次数,这个表由搜索预处理制得,如下:
int a[9][9]=
{ {3,3,3,3,3,2,3,2,0},
{2,3,2,3,2,3,1,0,1},
{3,3,3,2,3,3,0,2,3},
{2,3,1,3,2,0,2,3,1},
{2,3,2,3,1,3,2,3,2},
{1,3,2,0,2,3,1,3,2},
{3,2,0,3,3,2,3,3,3},
{1,0,1,3,2,3,2,3,2},
{0,2,3,2,3,3,3,3,3} };
1.4.3 Arithmetic Progressions
这道题最重要的是剪枝,主要是这三行:
int tmp2=(M*M)<<1,tmp=(int)(tmp2/(N-1));
for(a=0;a<=tmp2;a++)
for(b=1;b<=tmp&&a<=tmp2-b*(N-1);b++)

外a循环内b循环非常重要,比外b内a快2秒(极限数据)。
1.4.4 Mother’s Milk
广搜水题,存储用list[i].a[1..3]代表A,B,C桶
倒的时候用dao(now,i,j)表示状态now的第i个桶倒到第j个桶。
1.5.1 Number Triangles
最基础的DP。f[i][j]=max(f[i][j-1],f[i-1][j-1])。

1.5.2 Prime Palindromes
枚举+优化。比如对于最高的8位数(无视100000000),则枚举前4位直接构成回文,再加以判断,这样最高循环次数减少到10000次左右。所以先直接处理完5~100000000,再根据数据按区间输出。

1.5.3 Superprime Rib
深搜。从高位到低位判断,朴素判定质数+sqrt(n)优化。

1.5.4 Checker Challenge
这道题直接用了M67牛的位运算的方法,稍加改动即可记录状态,注意p是被取出的最右边的1,若这个1位于右起第4位,则p=8………
由此,递归函数增加两个参数,一个数组记录状态,一个变量n记录深度。

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: