跳至正文

USACO 1.5.2 Prime Palindromes

  • OI路程

  这一题我用的依然是以前的解法,现只求回文数,而且偶数回文数不需要求(如:312213)必定是11的倍数但是11要特殊处理,反正这一次我错了不少地方。
  1,把变量名写错了,上面分明是给a赋值,下面却写成了对b进行操作。

  2,对于回文数的制造的下标弄错了(不好细说,看代码里的注释和上下文把。)
  3,循环的范围错误,也是制造回文的错误!
  4,字符串的结尾忘记’\0’了。
  5,搜索的范围错误!!
  一次AC,代码如下:
/
LANG: C
ID: yylogoo2
PROG: pprime
/
#include&nbsp[……]

继续阅读

USACO 1.5.1 Number Triangles

  • OI路程

  明显是一个动态规划,有两种思路,一种是至上而下的,一种是至下而上的,让我联想到了几个大国家的革命和改革,我支持改革,革命总是要留下一些历史痕迹,漏洞,所以我选择的是至下而上的改革。至下而上的DP有什么好处呢?好处多了,因为没有任何特殊情况要考虑,如果是至上而下的DP的话,首先有特殊情况,对于每一个内层循环的值等于外层的值的话,但是这个处理得好的话还是可以做到不要多余的if来判断i是否等于j,在输出答案时不需要遍历底层,在这里的代码我犯了一个小错误导致我的代码丢了最后一个点。
  犯的错误:数组的下标使用错误了,在[……]

继续阅读

USACO 1.4.4 Mother's Milk

  • OI路程

  这一题经过反复的深思熟虑,使用三元数组作为牛奶桶中的牛奶,可以解决很多不必要的纠纷!这个题目充分体现了数据结构对算法影响力的巨大!如果不使用数组而使用三个变量作为参数传递的话,真的会很麻烦的,虽然程序大致的时间复杂度不会改变,但是其常数项会大大增加!所以这题的数据结构选择十分重要。
  我的思路就是暴力枚举所有牛奶可能的情况,反复搜索,用used[a][c]防止重复搜索。

  这里我还有一个空间的优化,不需要单独为答案开辟一个数组,直接使用防止重复的used二维数组来输出就是,也省去了枚举中很多不必要的判断时间,所[……]

继续阅读

USACO 1.4.3 Arithmetic Progressions

  • OI路程

  算法应该是比较单纯的,先把所有的双平方数找出来,并排序;然后再比如双平方数num[i], num[i + 1],那么a = num[i], b = num[i + 1] – num[i] (num已经排序了),然后便利他们就是,唯一要注意的就是一个大的剪支,当a + (n – 1) b > 最大的双平方数时,那么就结束循环,把所有的答案a, b排序一次输出即可。

  Mistacks:
  1、求双平方数的时候,应该是i

i + j j,我却写成i j。

  2、双平方数应该是两个同时从0开始遍历的数的[……]

继续阅读

USACO 1.4.2 The Clocks

  • OI路程

  这一个题目我还算是自豪吧,代码比以前写的好看一点,仅仅是因为几行代码的原因,但是这几行代码我觉得挺好的!具体是哪几行,看代码的注释,代码中唯一的一个错误就是判断一个数据是否为答案时竟然忘记判断了!!

  代码如下:
/
LANG: C
ID: yylogoo2
PROG: clocks
/
#include <stdio.h>
#include <string.h>
int clocks[9];
char ways[9][6] = {"ABDE",[……]

继续阅读

[未完成]USACO 1.4.1 Prime Cryptarithm

  • OI路程

  这是这一次做USACO目前唯一一个没做完的题目!第六种情况实在是不知道怎么写,我觉得最好还是不写最好,所以就没去写了。我也尝试了一下自己试着写写,结果写了最后一种情况竟然还不如不写的分数高!但是自己实在是不知道为什么,以前的代码这三行(最后一种情况)也是抄的,不是理解的,所以现在也就忘了……
  我的思路就是暴搜,用srch0将所用的矩形换位置,srch1将所有的矩阵的长宽交换,然后用count进行判断,代码十分易读(以前别人写的,不过因为确实有特色,所以已经变成了自己的东西了。)
  总结一下错误:

  1、把re[……]

继续阅读

USACO 1.3.4 Prime Cryptarithm

  • OI路程

  我没找到什么很巧的方法,纯暴力搜索:
  枚举100~999,10~99然后再分别进行判断,是各个数值否是在范围内,然后是否是输入输入的集合,如果都是ans递增,代码就是这样,犯了两个错误!
  1、在比较是否属于全集时,我是判断如果都不属于才算不属于,即用的“与”进行连接,应用“或”连接,在有一个不属于全集时就算不属于了。
  2、在判断是否是千位数时我用的是i >= 999,应该用i>999。
  不过都是打代码就发现的问题,所以一次性AC!

/
ID: yylogoo2
PROG: crypt1
LANG:[……]

继续阅读

算法: 求最长的回文

  • 技术

  最近USACO写到了(第三次)1.3.3,这一题(http://zqynux.blog.163.com/blog/static/16749959720109291375436/)我用的是我自己原创的一个算法(可能也有别人想到了,但是对于我来说,确实是我自己独立思考出来的),在此发表一下。
  程序:输入:一行字符串,输出:最长的回文字符的长度以及把它们给输出来。
  如:

    输入:1596156432111234
    输出:6
       432111234
回文的性质
  首先先把题目撇开,单说回文数的性质,如[……]

继续阅读

USACO 1.3.3 Calf Flac

  • OI路程

  这一题是USACO所有题目中我最自豪的一个题目,首先因为大部分人的代码都是在小数后一位上,而我这个算法是O(n)的,所以非常的快。又因为这是我自己想出来的,而且思维角度比较独特,所以我甚为自豪!
  但是我这个思路很难表达清晰。
  想把它单独提出来作为一篇文章(http://zqynux.blog.163.com/blog/static/1674995972010929683892/)写,包裹题解也在左边的链接里面,写好了把链接贴上来。
  这里我犯的几个错误分别如下:

  1、在比较不同字母时没注意大小写的区分。
 [……]

继续阅读

USACO 1.3.2 Barn Repair

  • OI路程

  这一题想了好久才想起来以前是怎么做的,直接使用的贪心,首先假设只有一块木板,自然而然是从最小的到最大的全部盖上,此时假设值为ans,那么如果是两块木板,那两块木板之间隔的距离必定是整个牛棚中距离最远的两个牛之间的距离,也就是说答案等于:只有一块木板的长度减去一个最长间隔:ans-max(dis),那三块木板的话很自然就是只有一块木板的长度减去最长的前两个间隔的值,以此类推,代码就很简单了。
  但是又由于需要快排的实现,我嫌它麻烦了,就直接使用数组进行排序(这个排序方法准确叫什么名字我也忘了,不记得是基数还是桶还[……]

继续阅读