存档

文章标签 ‘USACO题解’

USACO Arithmetic Progressions

2010年12月3日 4 条评论

Arithmetic Progressions题目大概意思:一个等差数列是一个能表示成a, a+b, a+2b,…, a+nb (n=0,1,2,3,…)的数列。在这个问题中a是一个非负的整数,b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p^2+q^2的数的集合)S中长度为n的等差数列。
这个题目拿到手感觉只能暴力搜索,事实便是如此。而且题目给了5秒钟的时限,于是我就开始写搜索了。提交之后在中间某一组数据果断超时了。实在想不到该怎么优化。后来看了[......]

继续阅读

分类: USACO题解 标签: , , ,

USACO Mother’s Milk|DFS

2010年12月2日 2 条评论

USACO Mother's Milk以前在POJ上面看到过类似的题目,就是搜索所有可能的状态。对于每一个状态都可能存在6中转换:A->B, A->C; B->A, B->C; C->A, C->B,当然只能选择其中的一种。搜索其中的每一种状态即可。属于简单型的DFS。可以用一个20×20×20的数组来判重。

/*
ID:stackex1
LANG:C++
PROG:milk3
*/
#include <iostr[......]

继续阅读

分类: USACO题解 标签: ,

USACO The Clocks|BFS

2010年12月1日 3 条评论

The Clocks一题看完之后第一个想到的就是BFS(其实很有多方法可以解决,有兴趣可以去参考参考NOCOW的解题代码)。对于这样的BFS,我都是定义结构体来作为节点,像本题中使用一个state字符串来记录当前的状态,然后最开始用了一个vector来记录已经出现过的状态,结果在提交的时候悲剧的TLE了。
于是各种加优化,想了想,中间产生大量状态,然后每次都从头到尾的搜索vector效率是低了点(对于vector来说,全局的find函数是O(N)的复杂度),于是改用map,map排序了,复杂度O[......]

继续阅读

分类: USACO题解 标签: , , , , ,

USACO Barn Repair

2010年11月30日 5 条评论

贪心问题。首先可以按照stall的编号从小到大排序,然后计算每个stall编号之见的距离,再按照距离从大到小排序(也可以从小到大,反正排序就行了),然后找出M-1个最大的距离,这些都是分隔段,其他的stall都是应该被覆盖的。
比如,1 3 9,给一个board的话,肯定是全部覆盖;如果能给两个board,则是一个覆盖1,2,3;另一个覆盖9。题目大概就是这个意思:

/*
ID:stackex1
LANG:C
PROG:barn1
*/
#include <stdio.h>
[......]

继续阅读

分类: USACO题解 标签: ,

USACO Prime Cryptarithm

2010年11月30日 没有评论

先产生所有能的三位数和两位数,然后两层循环枚举所有可能的情况,判断是否符合条件即可。
/*
ID:stackex1
LANG:C
PROG:crypt1
*/
#include <stdio.h>

int checkok(int num, int digit[], int n)
{
int i;
if(!(num >= 100 && num <= 999))
return 0;
while(num)
{
[......]

继续阅读

分类: USACO题解 标签: ,

USACO Calf Flac

2010年11月28日 2 条评论

USACO Calf Flac又是一个回文数问题。因为数据量不是非常大,所以这里采用暴力枚举。即枚举所有可能的中心节点,往后依次求得以此节点为中心节点的最大回文传长度。
这样做需要注意一个对称问题存在两种情况,如长度为奇数的AABBXBBAA;长度为偶数的AABBBBAA;两种情况都要考虑到。这样之后,只要简单处理一下字符串问题即可。
/*
ID:stackex1
LANG:C
PROG:calfflac
*/
#include <stdio.h>
#include[......]

继续阅读

USACO Mixing Milk

2010年11月28日 没有评论

USACO Mixing Milk简单的贪心问题,按照单价从小到大排序,然后对Farmers的牛奶一个一个的进行收购,知道已经买到了所有Milk。代码如下:
/*
ID:stackex1
LANG:C
PROG:milk
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM 5010

typedef struct TagNode
{
int price;
int amou[......]

继续阅读

USACO Dual Palindromes

2010年11月28日 没有评论

USACO Dual Palindromes又是一个进制转换和回文数判断相关的题目,跟上一个题目“USACO Palindromic Squares”类似,可以重用一下上一个题目的代码:
/*
ID:stackex1
LANG:C
PROG:dualpal
*/
#include <stdio.h>
#include <string.h>

void num2str(int num, char *s, int base)
{[......]

继续阅读

USACO Palindromic Squares

2010年11月28日 没有评论

USACO Palindromic Squares属于回文数判断与进制转换问题。在Windows下有一个itoa函数,可以方便的将10进制数转换成2到36进制字符串,但是很遗憾GCC里面没有这个函数。于是就自己来写一个通用的转换函数吧。同样是通过一个map数组,可以方便的实现进制的转换,具体请参考下面代码中的num2str函数。
/*
ID:stackex1
LANG:C
PROG:palsquare
*/
#include <stdio.h>
#include &[......]

继续阅读

USACO Name That Number

2010年11月28日 没有评论

USACO Name That Number要求将数字通过手机键盘转换成字母,然后去字典中查找字符串是否存在,存在则输出。如果老老实实的照着这种做法,显得有点繁琐。因为数字串最长有12个,可能转换成的字符串有3^12次方,计算量很大,效率低。我们可以逆向思维,将字典中的字符串转换成对应的数字,如果和给定的数字相等,则说明字符串可以输出。
另外需要注意,题目给定的输入数据是数字串,得到的输出字符串里面不可能有Q和Z,所以这些字符串都可以忽略掉。我是直接打表的……题目给定[......]

继续阅读

分类: USACO题解 标签: , , ,