文章列表
题意分析：
该题是需要深度优化的八皇后问题，首先看一下，经典八皇后问题的一般解法：
public class Queens {
private final static int MAX = 8;
// site[i] = j => col:i row:j
private static int[] site = new int[MAX];
private static boolean check(int col){
for(int i = 0; i < col; i++){
if(site[i] == site[col] || //不在一行上
...
题意分析：
7331是素数，733是素数，73是素数，7也是素数。这样7331就是我们要的。给定位数N，就所有这样的数
解题思路：
这题也是用递归。初始的数只可能为{2,3,5,7}，递归时检查不是素数就退出，是的话for i = 0: 9 dfs(10*num+i)继续递归，如果位数到了N且是素数，则输出。
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/sprime.java
题意分析：
找出a和b间既对称既是素数的数。
解题思路：
用递归去解这题。初始数据为单个的0-9和双数的00-99，扔进递归里每次在两边加0-9再递归，直到过长（大于b的长度）。这样每次递归的参数都可能是要的数值，所以递归方法首先要检查是否满足条件，除了要检查是否是素数、是否在[a,b]之间，还要注意有前导零的是不符合条件的。
素数检查代码，一般不需要写到究极，如下的就可用了。
if(tmp % 2 ==0 || tmp %3 == 0) return;
for(int i = 5; i*i <=tmp; i+=2){
if(tmp %i == 0)
ret ...
题意分析：
数字三角形，找到从顶到底的最大和的通路。
解题思路：
DP题。newRow[j]+= max(oldRow[j-1], oldRow[j])。从上至下。边读边计算，状态只需保存当前行和上一行。每一行首尾补零，为了方便计算。
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/numtri.java
题意分析：
有容量为A,B,C的三个牛奶桶，容量范围为1-20。开始时，A,B为空C为满。三个桶之间一个桶倒入另一个桶来回倒（要么倒满，要么倒光）。给定A,B,C。求A桶为空时C的可能值。
解题思路：
用DFS解。用searched[x][y]数组记录搜索过的状态，不使用三维数组是因为前2维决定了第三维。用amount[z]的布尔值记录当x=0时z的值。
private static void dfs(int x, int y, int z){
if(searched[x][y]) return;
searched[x][y] = true;
if(x == 0) ...
题意分析：
定义算术级数：一种序列a, a+b, a+2b, …,a+nb，a是非负整数，b是正整数
定义双平方：能表示成p方+q方的数，p和q为非负整数
给定N (3 <= N <= 25)，要找的算术级数序列的长度；以及M (1 <= M <= 250)，p和q的上限。
找出给定长度N的，所有序列元素都是双平方数的算术级数，输出a和b
解题思路：
这题的时间限制是5秒。首先决定在算术级数中找双平方还是在双平方中找算术级数。直觉是在双平方数中找算术级数，首先生成所有的双平方数，保存在一个boolean数组中，这个数组大小为250×250×2=125000。然后外层循环 ...
题意分析：
有编号为A-I的9个时钟，时钟只有指向3、6、9、12四种状态，一次转动只能顺时针转90度，已知9种转动方式，每种转动方式指定不同的几个钟顺时针转90度，要使所有钟都回到12点，根据不同的输入，要如何组合这9种转动方式呢？找出最短序列，同样长度的情况下以序列编号小为先。
解题思路1：
某一种转动方式若使用4次即没使用。因此1-9每一种转动方式至多使用4次，因此9种转动方式最多产生4(enum 0...3)^9=262144个序列，使用dfs完全遍历也不会超时。保存每次产生的有效序列结果，全部遍历完成后，按序列长度和数字大小排序，输出第一个结果。
代码实现1：
https://git ...
题意分析：
给出4个长方形的高和长，以及给出6种基本布局，求合成无重叠的最小面积时的长和宽。
解题思路：
这一题比较容易成为被卡住的第一题。
【首先】使用贪心的念头不要有，必须老老实实地将所有情况列出，那到底有多少情况呢？
1.六种基本布局中，第四种与第五种实则为一种，布局为5种。
2.在每种布局中，由于长方形摆放的位置不同，有4的阶乘种。
3.不同布局，不同摆放位置的每个长方形都有横竖两种摆法，有2的4次方种。
综上：共有 5 × 4! × 2^4 = 1920种。
【其次】要回忆一下回溯法。
在S1×S2×S3×…×Sn中，求解向量X=（x1,x2,x3…xn）。
算法描述：
1.令解 ...
题意分析：
已知数字1-9组成集合的一个子集，求满足题意乘法步骤的情况有多少，注意乘数、被乘数、结果都不能超出位数，且每个数字都在题目给出的子集中。
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/crypt1.java
题意分析：
一眼看上去，又是找对称的，不过有一些明显的干扰因素，比如是从一堆很长的字符中（最长为20000个）找出对称的最长字符串（最长为2000个）；找出的对称字符串中允许有其它干扰的字符whitespace以及其他符号；最长的长度是指不包含非字母的，而输出的对称字符串是包含非字母的等。
解题思路：
输入的读取方式和之前的不一样，因为要读取所有字符，while(in.ready()) …= (char)in.read();这种形式。第二个难点是容易去想难了，因为一眼看上去数量级肯定要TLE，但是仔细想想，对称的话，只有AABAA，AABBAA这样两种形式，就算是枚举以每一个字符为中心的所有字 ...
题意分析：
C头奶牛在畜栏里（一个畜栏里最多只能有一头奶牛），畜栏共有S个，并告诉你哪些编号的畜栏里有奶牛。一共有M块板要将所有有奶牛的畜栏栏起来。因为奶牛分布的分散和板的数量的限制，势必有空着的畜栏也被栏起来。求所有被栏起来的畜栏的最小个数。
解题思路：
比上一题稍难的贪心法。题目分析清楚后，S个畜栏这个条件实际上在计算中是没用的。为了使被栏起来畜栏数目最小，即空着被栏起来的畜栏最少，那么就要尽量减少横跨两个有牛畜栏间连续无牛畜栏的个数。这题贪心的思路就是将两个有牛畜栏间连续无牛畜栏个数进行排序，也就是碰到最大的M-1个连续无牛畜栏时，多用一块板以避免覆盖到这些无牛畜栏。剩余较小的连续无牛畜 ...
题意分析：
牛奶收购站每天需要收购总量为N加仑牛奶，告诉你每天每个奶农生产的牛奶量和每加仑价格，求收购站至少要付多少钱才能满足每天的收购量。
解题思路：
典型的贪心法。按每加仑价格排序，然后循环直到满足需求量
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/milk.java
题意分析：
这题和上一题基本是一样的，输出N个大于S的Dual Palindromes。其中N (1<=N<=15)，S (0<S<10000)。Dual Palindromes是能以二进制到十进制中两种进制表示成palindromic（左右对称）的数字。
解题思路：
十进制数与X进制数的转换。
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/dualpal.java
题意分析：
N固定为10进制的1-300，N的平方表示成B进制时若左右对称则为Palindromic Squares。输入为B（B为2-20），输出B进制的PalSquare及其对应的N。
解题思路：
十进制数与B进制数的转换。
代码实现：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/palsquare.java