DYM Blog

Thinking will not overcome fear but action will.

USACO/Runaround Numbers

USACO/Runaround Numbers

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacorunaround-numbers/ 寻找比给定数字大的第一个循环数。定义循环数:从最左边的数字开始向右数最左边这个数(如果数到了最右边就回到最左边),你会停止在另一个新的数字(如果停在一个相同的数字上,这个数就不是循环数),重复这样做,如果你经过每一个数字一次以后没有回到起点,你的数字不...

USACO/Subset Sums

USACO/Subset Sums

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacosubset-sums/ 把从1到N (1 <= N <= 39) 的连续整数集合划分成两个子集合,且保证每个集合的数字和是相等的。 解法:两个集合的和相同,即将1~N的和的一半进行整数划分(即将和的一半拆成若干不同数的和);若1~N的和为奇数,则无解。 动态规划的状态方程为:...

USACO/Preface Numbering

USACO/Preface Numbering

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacopreface-numbering/ 传统罗马数字用单个字母表示特定的数值,给定罗马数字的组成规则,统计从1~n的数字转化为罗马数字以后,各个字母出现的总次数 解法:先预处理整数的各个位用罗马数字的表示方式,并存入数组,然后将整数转换成罗马数字并进行统计。 #include<ios...

USACO/Checker Challenge

USACO/Checker Challenge

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacochecker-challenge/ 求解n皇后问题的解。 解法:回溯法求前三种解的情况;位操作法求总的步数,参考了matrix67的位操作方法。 #include<stdio.h> #include<iostream> #include<stdlib.h&...

USACO/Superprime Rib

USACO/Superprime Rib

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacosuperprime-rib/ 写一个程序对给定的 N (1<=N<=8),求出所有的特殊质数。 数字1不被看作一个质数。举例来说: 7331是质数,733是质数,73 是质数,7 也是质数。 7331 被叫做长度 4 的特殊质数。 解法:注意最高位必为2 3 5 7,其他位必...

USACO/Prime Palindromes

USACO/Prime Palindromes

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacoprime-palindromes/ 写一个程序来找出范围a,b间的所有回文质数。 解法:1.采用的位操作存储的第一种方法想要暴力解决,但是超时了。应该先构造回文再判断素性,没写,还需要再尝试! 2.用打表的方式过了,代码不贴了。

USACO/Number Triangles

USACO/Number Triangles

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usaconumber-triangles/ 数字金字塔,写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。 解法:最直接的动态规划 #include <iostream> #include <fstream> #include <string&...

USACO/Mother's Milk

USACO/Mother's Milk

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacomothers-milk/ 三个容量分别是A,B,C升的桶,A,B,C分别是三个从1到20的整数。最初,A和B桶都是空的,而C桶是装满牛奶的。农民执行把牛奶从一个桶倒到另一个桶中的操作,直到被灌桶装满或原桶空了。找出当A桶是空的时候,C桶中牛奶所剩量的所有可能性。 解法:宽度优先搜索 #...

USACO/Arithmetic Progressions

USACO/Arithmetic Progressions

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacoarithmetic-progressions/ 写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p的平方+q的平方的数的集合,其中p和q为非负整数)S中长度为n的等差数列。 解法:先打表,然后暴力枚举,加一个关键性的剪枝,见如下标记。 #include <iostre...

USACO/The Clocks

USACO/The Clocks

本文迁移自老博客,原始链接为 https://seven.blog.ustc.edu.cn/usacothe-clocks/ 求找一个最小的移动顺序将所有的指针指向12点。给出了9种不同的旋转指针的方法。选择1到9号移动方法,将会使在对应的受影响的时钟的指针顺时针旋转90度。 解法:枚举,一共4的9次方种情况,感觉题目的数据有点弱,没有判断最小的,循环结束输出结果就过了。 #inclu...