USACO section1.2

Complete Search(穷竭搜索)

穷竭搜索时将所有的可能性罗列出来,在其中寻找答案的方法。穷竭搜索的思路非常简单直接,也是在编程竞赛中,第一个被想到的方法。而如果没有时间和空间的限制,那就采用这种方法吧,反正竞赛是为了找到一个解决问题的方法,而不是找到一个最快的方法。

题目见:http://www.nocow.cn/index.php/USACO_Training#Section_1.2

  1. Milking Cow

    很简单,按照牛奶价格从低到高选择即可。 需要注意的一点是,厂家在选择一个农民后,不需要购买这个农民所有的牛奶,即买一部分也是可以的。

  2. Transaction

    题意:判断是否可以通过一系列操作(90度旋转,180度旋转和翻转等等)从原始图像变换到目标图像。

    这个也很简单,只要计算出旋转前后的变换公式即可。其中有几个trick:1. 180度旋转=90度旋转+90度旋转;2.由于原始图像比较小,可以直接在栈里面申请空间。相比使用共同的临时空间,这样代码更整洁,逻辑也更清晰。

  3. namenum

    题意:根据一串数字找到对应的字符串,并判断该字符串是否已经存储在一个文件中

    利用深度搜索获得所有的字符串,再判断该字符串是否符合条件。

    Trick:1. 利用stl中的set存储文件中的字符串;

  4. Palindromic Squares

    题目是在规定的进制下,如果1~300的数的平方是回文数,则输出此数和次数的平方(均在该给定进制下)。

    该问题主要想考回文数和不同进制转换,这两点也是编程教学中常用的两个题目。 回文数自然没什么好说的,比较第i个和第len-1-i个字符是否相等就可以了。
    而进制转换却让我遇到了些麻烦。windows下有个api,itoa,可以将数字按照不同的进制转换成字符串,而linux下却没有,这就浪费了两三次提交。后来自己找到了个itoa的程序,又发现字符串数组开的太小,只开了10个,导致在处理二进制的时候,字符串不够长,判断出错。

    总结,windows的itoa不仅可以用于将数字转成字符串,还可以进行进制转换。 在自己实现进制转换时,先给出一个索引表,即char index[] = "0123456789ABCDEFG....",有助于实现。

  5. PROB Dual Palindromes

    题目是给定两个数S, N,分别表示需要查找到数目的个数,和查找的范围。如,在大于N的整数内,查找符合条件的S个数,条件为,以2~10为进制的表示中,至少有两个进制的表示为回文数。

    考察内容跟上题一样,只需要对2~10的进制表示判断一下即可。



Previous     Next