USACO代码解析Checker Challenge (checker)皇后

usaco2024 金组题解我将为您提供一道USACO 2024金组题目的思路和解法。

题目如下：题目：RLE SortDescription:You are given an array of integers nums of length n. Each element in the array is between 1 and 1000. The array is permuted and sorted in non-decreasing order. You are allowed to perform the following operation any number of times:1. Choose an integer x from the array.2. Reverse the substring consisting of the first x elements.3. Reverse the substring consisting of the last x elements.Your goal is to minimize the number of operations required to sort the array.Constraints:1 <= n <= 100001 <= nums[i] <= 1000The array is initially permuted and sorted in non-decreasing order.Input:n = 5nums = [1, 3, 5, 4, 2]Output:2题解：首先，我们要明确题目要求。

题目要求我们通过逆转子数组的方式，将数组nums变为升序排列，而且要求我们尽可能地减少操作次数。

我们可以采用贪心算法来解决这个问题。

具体思路如下：1. 初始化两个指针left和right，分别指向数组的第一个元素和最后一个元素。

描述农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，最初，A和B桶都是空的，而C桶是装满牛奶的。

有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。

当然每一次灌注都是完全的。

由于节约，牛奶不会有丢失。

写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

[编辑]格式PROGRAM NAME: milk3INPUT FORMAT:(file milk3.in)单独的一行包括三个整数A,B和C。

OUTPUT FORMAT:(file milk3.out)只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。

[编辑]SAMPLE INPUT 18 9 10[编辑]SAMPLE OUTPUT 11 2 8 9 10[编辑]SAMPLE INPUT 22 5 10[编辑]SAMPLE OUTPUT 25 6 7 8 9 10#include <fstream>#include <cstdlib>#include <algorithm>using namespace std;ifstream fin ("milk3.in");ofstream fout ("milk3.out");long ans[50],p=-1;long a,b,c; //各桶上限bool found[50][50][50]; //搜索记录bool isIn(long C) //其实可以用置位下表c的元素来自然排序{bool in=false;for (long i=0;i<=p;i++){if (ans[i]==C){in=true;break;}}return in;}void DFS(long A,long B,long C){if (found[A][B][C]) return;found[A][B][C]=true;if (A==0){if (!isIn(C)){ans[++p]=C;}}if (A<=b-B) DFS(0,B+A,C); //A->Belse DFS(A-(b-B),b,C);if (A<=c-C) DFS(0,B,C+A); //A->Celse DFS(A-(c-C),B,c);if (B<=a-A) DFS(A+B,0,C); //B->Aelse DFS(a,B-(a-A),C);if (B<=c-C) DFS(A,0,C+B); //B->Celse DFS(A,B-(c-C),c);if (C<=a-A) DFS(A+C,B,0); //C->Aelse DFS(a,B,C-(a-A));if (C<=b-B) DFS(A,B+C,0); //C->Belse DFS(A,b,C-(b-B));return;}int main(){memset (ans,0,sizeof(ans));memset (found,0,sizeof(found));fin >>a >>b >>c;DFS(0,0,c);sort(ans,ans+p+1);for (long i=0;i<=p;i++) //输出妙！避免多空格{if (i!=0) fout <<' ';fout <<ans[i];}fout <<endl;return 0;}。

USACO比赛规则USACO（美国计算机奥林匹克竞赛）是美国最重要的计算机竞赛之一，旨在选拔和培养年轻的计算机科学家和编程爱好者。

USACO比赛规则是参赛选手参加比赛时需要遵守的规定和要求。

本文将详细介绍USACO比赛规则的内容和要点。

1. 比赛形式USACO比赛分为四个不同的级别：铜牌（Bronze）、银牌（Silver）、金牌（Gold）和铂金（Platinum）。

每个级别的比赛包括四个不同的比赛，分别是：•识别（Identification）：参赛选手需要在规定的时间内完成一份题目的识别，即理解题目的要求和限制。

•模拟（Simulation）：参赛选手需要在规定的时间内编写一个程序来模拟题目要求的过程，并输出正确的结果。

•优化（Optimization）：参赛选手需要在规定的时间内编写一个程序来优化题目要求的过程，并输出最优解。

•分析（Analysis）：参赛选手需要在规定的时间内分析一份题目的代码，并回答相关问题。

每个级别的比赛都有一定的难度和挑战性，参赛选手需要根据自己的水平和能力选择适合的级别参加比赛。

2. 参赛要求参加USACO比赛需要满足以下要求：•年龄限制：参赛选手必须是在指定年份内的13岁至19岁的学生。

具体年份会根据比赛级别而有所不同。

•报名：参赛选手需要在指定的时间内完成在线报名，并支付相应的报名费用。

•设备：参赛选手需要自备一台计算机，并确保可连接互联网。

•编程语言：参赛选手可以使用C++、Java或Python等编程语言参加比赛。

3. 比赛规则USACO比赛有一系列的规则和限制，以确保比赛的公平性和公正性。

以下是一些重要的比赛规则：•时间限制：参赛选手需要在规定的时间内完成每个比赛阶段的任务。

超时提交的解答将不会被接受。

•空间限制：参赛选手需要确保程序运行时所需的内存不超过规定的限制。

超出限制的程序将被判定为错误。

•输入输出：参赛选手需要按照题目要求从标准输入读取数据，并将结果输出到标准输出。

1213：⼋皇后问题【题⽬描述】在国际象棋棋盘上放置⼋个皇后，要求每两个皇后之间不能直接吃掉对⽅。

【输⼊】(⽆)【输出】按给定顺序和格式输出所有⼋皇后问题的解（见样例）。

【输⼊样例】（⽆）【输出样例】No. 11 0 0 0 0 0 0 00 0 0 0 0 0 1 00 0 0 0 1 0 0 00 0 0 0 0 0 0 10 1 0 0 0 0 0 00 0 0 1 0 0 0 00 0 0 0 0 1 0 00 0 1 0 0 0 0 0No. 21 0 0 0 0 0 0 00 0 0 0 0 0 1 00 0 0 1 0 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 0 10 1 0 0 0 0 0 00 0 0 0 1 0 0 00 0 1 0 0 0 0 0...以下省略解题分析：关键在于斜线还有是否访问过，正斜与反斜⾓的特点#include<bits/stdc++.h>using namespace std;int a[10001],b[10001],w[10001],m[10001],tot=0;int print(){tot++;cout<<"No. "<<tot<<endl;for(int j=1;j<=8;++j){for(int i=1;i<=8;++i)if(j==a[i])cout<<1<<" ";else cout<<0<<" ";cout<<endl;}}int search(int j){for(int i=1 ;i<=8;++i){if(b[i]==0&&w[i-j+7]==0&&m[i+j]==0){a[j]=i;b[i]=1;w[i-j+7]=1;m[i+j]=1;if(j==8) print();else search(j+1);b[i]=0;w[i-j+7]=0;m[i+j]=0;}}}int main(){search(1);return 0;}记住限制条件是该列有没访问过，还有斜⾓两个⽅向。

usaco题目集usaco题目集是一系列来自美国计算机奥林匹克竞赛（USACO）的编程题目。

USACO是一项面向中学生的计算机竞赛，旨在培养学生的计算机科学和算法设计能力。

该竞赛涵盖了广泛的主题，包括数据结构、图论、动态规划和搜索等。

usaco题目集的难度分为四个级别：铜牌、银牌、金牌和白金。

每个级别的题目都有一定的难度和要求。

通过完成这些题目，学生们可以提高他们的编程技巧和解决问题的能力。

usaco题目集的题目非常有趣和有挑战性。

每个题目都描述了一个具体的问题，学生需要设计和实现一个程序来解决这个问题。

这些问题有时与现实生活中的情境相关，有时与抽象的数学和逻辑问题相关。

例如，一个题目可能要求学生计算某个数列的前n项之和，另一个题目可能要求学生确定给定图形的面积。

解决这些问题需要学生们运用他们所学的算法和数据结构知识，并且具备良好的编程技巧。

usaco题目集的特点之一是其严格的评判标准。

每个题目都有一组测试数据，用于验证学生程序的正确性和效率。

程序需要在规定的时间内给出正确的输出结果，否则将被判定为错误。

这种评判标准旨在培养学生们高效率和准确性的编程能力。

通过解决usaco题目集中的问题，学生们可以提高他们的计算机科学能力，并为将来的学习和工作做好准备。

这些问题不仅可以让学生们巩固他们所学的知识，还可以培养他们的创造力和解决问题的能力。

此外，usaco题目集还提供了一个平台，让学生们可以与全美范围内的同龄人交流和竞争。

每年，usaco组织全美性的比赛，邀请来自各州的优秀选手进行角逐。

这些比赛不仅考察学生的编程能力，还促进了学生们之间的交流和合作。

总之，usaco题目集是一个很好的学习和提高编程能力的资源。

通过解决这些问题，学生们可以提高他们的计算机科学和算法设计能力，并为将来的学习和工作做好准备。

这些问题的多样性和挑战性，使得usaco题目集成为中学生们学习编程的重要工具。

import java.util.Stack;public class Test {public static void main(String[] args) {Q a = new Q(); //定义一个新Q对象Stack s = new Stack(); //定义一个栈int i = 0, j = 0;do {a.flag = false;for (j = 0; j < 8; j++) {if (a.q[i][j] == 0) {a.flag = true;a.cannotq(i, j);a.q[i][j] = 1;if (i == 7) {s.push(a.copy());a.backdate(i, j);a.q[i][j] = 2;i--;}}}if (!a.flag) {for (j = 0; j < 8; j++) {if (a.q[i][j] == 2) {a.q[i][j] = 0;}}i--;if (i == -1) {break;}for (j = 0; j < 8; j++) {if (a.q[i][j] == 1) {a.backdate(i, j);a.q[i][j] = 2;}}} else {i++;}} while (i < 8);int k = 1;while (!s.empty()) {System.out.println("第" + k + "种方法：");Q t = (Q) s.pop();t.print();k++;}int x=0;x=k-1;System.out.println("恭喜!所有的方法已成功给出.共计"+ x +"种方法！");}}class Q {public int[][] q = new int[8][8];public boolean flag;Q() {for (int i = 0; i < 8; i++)for (int j = 0; j < 8; j++)q[i][j] = 0;}public void cannotq(int m, int n) { //标志不能放置Queen的位置int i, j;for (j = n + 1; j < 8; j++) {this.q[m][j] = this.q[m][j] - 1;}for (i = m + 1; i < 8; i++) {this.q[i][n] = this.q[i][n] - 1;}for (i = m + 1, j = n + 1; i < 8 && j < 8; i++, j++) {this.q[i][j] = this.q[i][j] - 1;}for (i = m + 1, j = n - 1; i < 8 && j >= 0; i++, j--) {this.q[i][j] = this.q[i][j] - 1;}}public void backdate(int m, int n) { //找不到可以放置Queen的地方，回溯int i, j;for (j = n + 1; j < 8; j++) {this.q[m][j] = this.q[m][j] + 1;}for (i = m + 1; i < 8; i++) {this.q[i][n] = this.q[i][n] + 1;}for (i = m + 1, j = n + 1; i < 8 && j < 8; i++, j++)this.q[i][j] = this.q[i][j] + 1;for (i = m + 1, j = n - 1; i < 8 && j >= 0; i++, j--)this.q[i][j] = this.q[i][j] + 1;}public Q copy() {Q t = new Q();for (int i = 0; i < 8; i++) {for (int j = 0; j < 8; j++) {t.q[i][j] = this.q[i][j];}}return t;}public void print() { //输出for (int i = 0; i < 8; i++) {for (int j = 0; j < 8; j++) {if (q[i][j] == 1) {System.out.print("Q ");} else {System.out.print("* ");}}System.out.println();}}}。

我的usaco 总结Personalized Curriculum for Leo Kan; Last visit: 12 hours agoCongratulations! You have finished all available material.Chapter 1 DONE 2008.03.16 Getting startedChapter 2 DONE 2008.01.30 Bigger ChallengesChapter 3 DONE 2008.02.15 Techniques more subtleChapter 4 DONE 2008.03.09 Advanced algorithms and difficult drillsChapter 5 DONE 2008.04.04 Serious challengesChapter 6 DONE 2008.04.03 Contest Practice花了几个月时间,做完了USACO,感觉收获很大.做USACO之前和做USACO之后我感觉我的能力有很大的提升.USACO这个题库是一个完全适合信息学竞赛初学者的题库,它里面的内容由浅至难,很"经典"的一题Your Ride Is Here是只要会编程就能做的题目.接下来的内容可以使你掌握信息学竞赛中一些基本的也是很必要的算法和数据结构.如果只是想参加noip的话做完4甚至还不用就有拿奖的水平了(noip甚至连网络流,几何都不考)Chapter 1,正如它的标题所言Getting started,如果你只会编程而想踏入竞赛的门槛的话,做完Getting started,你就能对什么是竞赛有一点认识了.涉及基础的贪心,动态规划,搜索,模拟.特别需要提一下的我觉得是Checker Challenge 如果不用位运算那么它的剪枝有很大的技巧,很有启发性.另外Packing Rectangles是一道极度繁琐的题目,不考什么技巧,就考是否细心,如果是初学者很有必要练习一下,不是的话可以直接pass.DONE 2007.10.25 TEXT IntroductionSection 1.1 DONE 2008.03.16 TEXT Submitting SolutionsDONE 2007.10.26 PROB Your Ride Is Here [ANALYSIS] 无聊题DONE 2007.10.26 TEXT Contest Problem TypesDONE 2007.10.26 TEXT Ad Hoc ProblemsDONE 2007.10.26 PROB Greedy Gift Givers [ANALYSIS] 模拟DONE 2007.10.27 PROB Friday the Thirteenth [ANALYSIS] 模拟DONE 2007.10.27 PROB Broken Necklace [ANALYSIS] 枚举or动态规划Section 1.2 DONE 2007.10.27 TEXT Complete SearchDONE 2007.12.30 PROB Milking Cows [ANALYSIS] 贪心DONE 2007.12.30 PROB Transformations [ANALYSIS] 模拟DONE 2007.12.31 PROB Name That Number [ANALYSIS] 模拟DONE 2007.12.31 PROB Palindromic Squares [ANALYSIS] 模拟DONE 2007.12.31 PROB Dual Palindromes [ANALYSIS] 模拟Section 1.3 DONE 2007.12.31 TEXT Greedy AlgorithmDONE 2007.12.31 PROB Mixing Milk [ANALYSIS] 标准解法该是线段覆盖或线段树吧,但是作为chapter1 的题可以试试模拟DONE 2007.12.31 PROB Barn Repair [ANALYSIS] 贪心DONE 2007.12.31 TEXT Winning SolutionsDONE 2008.01.01 PROB Calf Flac [ANALYSIS] 枚举DONE 2008.01.01 PROB Prime Cryptarithm [ANALYSIS] 枚举Section 1.4 DONE 2008.01.01 TEXT More Search TechniquesDONE 2008.01.25 PROB Packing Rectangles [ANALYSIS] 模拟DONE 2008.01.14 PROB The Clocks [ANALYSIS] 搜索or枚举还有一种数学方法的 DONE 2008.01.25 PROB Arithmetic Progressions [ANALYSIS] 枚举DONE 2008.01.04 PROB Mother's Milk [ANALYSIS] 搜索Section 1.5 DONE 2008.01.25 TEXT Introduction to Binary NumbersDONE 2008.01.25 PROB Number Triangles [ANALYSIS] 动态规划DONE 2008.01.26 PROB Prime Palindromes [ANALYSIS] 枚举DONE 2008.01.26 PROB SuperPrime Rib [ANALYSIS] 枚举DONE 2008.01.26 PROB Checker Challenge [ANALYSIS] 搜索Chapter 2,它涉及一些算法了,比较基础的就是最短路径的Bessie Come Home,还有很大一部分是练习编程技巧的,其中一个比较实用的—位运算.Section 2.1 DONE 2008.01.26 TEXT Graph TheoryDONE 2008.01.26 TEXT Flood Fill AlgorithmsDONE 2008.01.27 PROB The Castle [ANALYSIS] Flood FillDONE 2008.01.27 PROB Ordered Fractions [ANALYSIS] 枚举or递归DONE 2008.01.27 PROB Sorting A Three‐Valued Sequence [ANALYSIS] 贪心DONE 2008.01.27 PROB Healthy Holsteins [ANALYSIS] 搜索DONE 2008.01.27 PROB Hamming Codes [ANALYSIS] 枚举(位运算)Section 2.2 DONE 2008.01.27 TEXT Data StructuresDONE 2008.01.27 TEXT Dynamic ProgrammingDONE 2008.01.28 PROB Preface Numbering [ANALYSIS] 模拟DONE 2008.01.28 PROB Subset Sums [ANALYSIS] 动态规划DONE 2008.01.28 PROB Runaround Numbers [ANALYSIS] 模拟DONE 2008.01.28 PROB Party Lamps [ANALYSIS] 枚举(位运算)Section 2.3 DONE 2008.01.28 PROB The Longest Prefix [ANALYSIS] 动态规划 DONE 2008.01.29 PROB Cow Pedigrees [ANALYSIS] 动态规划DONE 2008.01.29 PROB Zero Sum [ANALYSIS] 搜索DONE 2008.01.29 PROB Money Systems [ANALYSIS] 动态规划(背包模型)DONE 2008.01.29 PROB Controlling Companies [ANALYSIS] 搜索Section 2.4 DONE 2008.01.29 TEXT Shortest PathsDONE 2008.01.30 PROB The Tamworth Two [ANALYSIS] 搜索DONE 2008.01.30 PROB Overfencing [ANALYSIS] 搜索DONE 2007.11.25 PROB Cow Tours [ANALYSIS] 最短路DONE 2007.11.03 PROB Bessie Come Home [ANALYSIS] 最短路DONE 2008.01.30 PROB Fractions to Decimals [ANALYSIS] 模拟Chapter 3,更多的算法,最小生成树的Agri‐Net,欧拉回路的Riding The Fences, Sweet Butter这一题是最短路径,不过这题完全可以作为从初级图论题到中级图论题的一个过渡,需要用到bellman‐ford或SPFA,当然heap dijkstra也可以,再高级的Chapter 3的程度还未到,可以先不学.Home on the Range这题的动态规划是USACO 从Chapter1 开始以来新的一种动态规划方式,是在一个矩阵中判断一个位置和附近位置关系得到的状态转移方程. Feed Ratios这题可以枚举,但是有更好的方法(高斯消元,克莱姆法则…关于克莱姆法则请参见附录).closed fences是USACO的第一道几何题,详细题解看附录.Section 3.1 DONE 2008.01.30 TEXT Minimal Spanning TreesDONE 2007.11.03 PROB Agri‐Net [ANALYSIS] MSTDONE 2008.01.31 PROB Score Inflation [ANALYSIS] 动态规划DONE 2008.01.31 PROB Humble Numbers [ANALYSIS] 枚举DONE 2008.01.31 PROB Shaping Regions [ANALYSIS] 线段树or矩形覆盖DONE 2008.02.01 PROB Contact [ANALYSIS] 模拟DONE 2008.02.01 PROB Stamps [ANALYSIS] 动态规划(背包模型)Section 3.2 DONE 2008.02.01 TEXT Knapsack ProblemsDONE 2007.12.02 PROB Factorials [ANALYSIS] 可以用错误方法(保留部分位)过这题,但是这样做是错误的,仅仅对于小数据有效,正确方法是统计2和5 的个数然后计算DONE 2008.02.01 PROB Stringsobits [ANALYSIS] 康托展开DONE 2008.02.02 PROB Spinning Wheels [ANALYSIS] 模拟DONE 2007.11.19 PROB Feed Ratios [ANALYSIS] 枚举or高斯消元or克莱姆法则 DONE 2008.02.02 PROB Magic Squares [ANALYSIS] 搜索DONE 2008.02.05 PROB Sweet Butter [ANALYSIS] 最短路Section 3.3 DONE 2008.02.05 TEXT Eulerian ToursDONE 2008.02.05 PROB Riding The Fences [ANALYSIS] 欧拉路DONE 2008.02.08 PROB Shopping Offers [ANALYSIS] 动态规划(背包模型)DONE 2008.02.09 PROB Camelot [ANALYSIS] 搜索+贪心DONE 2008.02.09 PROB Home on the Range [ANALYSIS] 动态规划DONE 2008.02.09 PROB A Game [ANALYSIS] 动态规划Section 3.4 DONE 2008.02.12 TEXT Computational GeometryDONE 2008.02.12 PROB Closed Fences [ANALYSIS] 几何DONE 2007.11.22 PROB American Heritage [ANALYSIS] 递归,经典,入门必做 DONE 2008.02.15 PROB Electric Fence [ANALYSIS] pick公式(其实直接枚举效率更高且简单)DONE 2008.02.15 PROB Raucous Rockers [ANALYSIS] 动态规划(背包模型)Chapter 4,可以找到一点点竞赛感觉了…算法方面有网络流Drainage Ditches,二分图最大匹配The Perfect Stall,很多经典问题,例如Pollutant Control的求最小割集. Chapter 4的每一题都很有价值,对于初学者能长很多经验的比如dfsid这种搜索技巧.Section 4.1 DONE 2008.02.18 TEXT Optimization TechniquesDONE 2008.02.19 PROB Beef McNuggets [ANALYSIS] 动态规划+枚举DONE 2008.03.01 PROB Fence Rails [ANALYSIS] 搜索(dfsid)DONE 2008.02.20 PROB Fence Loops [ANALYSIS] 最小环(它给出的是边的联通关系而不是点的联通关系)对于这种需要自己构图的题目可以用搜索.DONE 2008.02.22 PROB Cryptcowgraphy [ANALYSIS] 搜索+elfhashSection 4.2 DONE 2008.03.01 TEXT "Network Flow" AlgorithmsDONE 2008.02.22 PROB Drainage Ditches [ANALYSIS] 网络流DONE 2007.12.11 PROB The Perfect Stall [ANALYSIS] 二分图匹配DONE 2008.03.02 PROB Job Processing [ANALYSIS] 动态规划+贪心DONE 2008.03.02 PROB Cowcycles [ANALYSIS] 搜索Section 4.3 DONE 2008.03.03 TEXT Big NumbersDONE 2007.12.02 PROB Buy Low, Buy Lower [ANALYSIS] 动态规划(最长不下降子序列)DONE 2008.03.05 PROB The Primes [ANALYSIS] 搜索,优化可以很多的,很有趣味性 DONE 2008.03.07 PROB Street Race [ANALYSIS] 求割点,搜索DONE 2008.03.07 PROB Letter Game [ANALYSIS] 枚举,我觉得它主要考预处理,预处理后其实只需枚举几十个Section 4.4 DONE 2008.03.07 PROB Shuttle Puzzle [ANALYSIS]DONE 2008.03.08 PROB Pollutant Control [ANALYSIS] 最小割DONE 2008.03.09 PROB Frame Up [ANALYSIS] 拓扑排序Chapter 5,很耐人寻味的一个章节,全是好题Section 5.1 DONE 2008.03.14 TEXT Convex HullsDONE 2008.03.11 PROB Fencing the Cows [ANALYSIS] 凸包DONE 2008.03.14 PROB Starry Night [ANALYSIS] flood fillDONE 2008.03.15 PROB Musical Themes [ANALYSIS] 动态规划or枚举Section 5.2 DONE 2008.03.16 PROB Snail Trail [ANALYSIS] 搜索DONE 2008.03.16 PROB Electric Fences [ANALYSIS] 几何DONE 2008.03.17 PROB Wisconsin Squares [ANALYSIS] 搜索,数据结构上如果用表能有很好的效果Section 5.3 DONE 2008.03.19 TEXT Heuristics & Approximate SearchesDONE 2008.03.20 PROB Milk Measuring [ANALYSIS] 动态规划or dfsid+动态规划/dfs(用dfs对于这题数据能有很好的效果0s出解)DONE 2008.03.21 PROB Window Area [ANALYSIS] 模拟+矩形覆盖DONE 2008.03.22 PROB Network of Schools [ANALYSIS] 图的连通性DONE 2008.03.22 PROB Big Barn [ANALYSIS] 动态规划Section 5.4 DONE 2008.03.23 PROB All Latin Squares [ANALYSIS] 搜索or错排(数学性很强,推广很难)DONE 2008.03.25 PROB Canada Tour [ANALYSIS] 网络流or动态规划DONE 2008.04.04 PROB Character Recognition [ANALYSIS] 统计+动态规划DONE 2008.03.28 PROB Betsy's Tour [ANALYSIS] 搜索DONE 2008.03.29 PROB TeleCowmunication [ANALYSIS] 最小割Section 5.5 DONE 2008.03.30 PROB Picture [ANALYSIS] 线段树DONE 2008.03.30 PROB Hidden Passwords [ANALYSIS] 枚举+KMP思想优化 DONE 2008.04.04 PROB Two Five [ANALYSIS] 搜索+康托展开Chapter 6,只有几题Section 6.1 DONE 2008.04.01 PROB Postal Vans [ANALYSIS] 动态规划DONE 2008.04.02 PROB A Rectangular Barn [ANALYSIS] 动态规划DONE 2008.04.03 PROB Cow XOR [ANALYSIS] 枚举+优化Usaco 总结 lzoi leokan /leokan附录一:题解索引Section2.1 DONE 2008.01.26 TEXT Graph TheoryDONE 2008.01.26 TEXT Flood Fill AlgorithmsDONE 2008.01.27 PROB The Castle [ANALYSIS]Section 1.0 DONE 2007.10.25(1.1的题目程序丢了,不必看1.1的题解)Section 1.1 DONE 2008.03.16TEXT Submitting SolutionsDONE 2007.10.26PROB Your Ride Is Here [ANALYSIS]DONE 2007.10.26TEXT Contest Problem TypesDONE 2007.10.26TEXT Ad Hoc ProblemsDONE 2007.10.26PROB Greedy Gift Givers [ANALYSIS]DONE 2007.10.27PROB Friday the Thirteenth [ANALYSIS]DONE 2007.10.27PROB Broken Necklace [ANALYSIS]Section 1.2 DONE 2007.10.27TEXT Complete SearchDONE 2007.12.30PROB Milking Cows [ANALYSIS]DONE 2007.12.30PROB Transformations [ANALYSIS]DONE 2007.12.31PROB Name That Number [ANALYSIS]DONE 2007.12.31PROB Palindromic Squares [ANALYSIS]DONE 2007.12.31PROB Dual Palindromes [ANALYSIS]Section 1.3 DONE 2007.12.31TEXT Greedy AlgorithmDONE 2007.12.31PROB Mixing Milk [ANALYSIS]DONE 2007.12.31PROB Barn Repair [ANALYSIS]DONE 2007.12.31TEXT Winning SolutionsDONE 2008.01.01PROB Calf Flac [ANALYSIS]DONE 2008.01.01PROB Prime Cryptarithm [ANALYSIS]Section 1.4 DONE 2008.01.01TEXT More Search TechniquesDONE 2008.01.25PROB Packing Rectangles [ANALYSIS]DONE 2008.01.14PROB The Clocks [ANALYSIS]DONE 2008.01.25PROB Arithmetic Progressions [ANALYSIS]DONE 2008.01.04PROB Mother's Milk [ANALYSIS]Section 1.5 DONE 2008.01.25TEXT Introduction to Binary NumbersDONE 2008.01.25PROB Number Triangles [ANALYSIS]DONE 2008.01.26PROB Prime Palindromes [ANALYSIS]DONE 2008.01.26PROB SuperPrime Rib [ANALYSIS]DONE 2008.01.26PROB Checker Challenge [ANALYSIS]DONE 2008.01.27 PROB Ordered Fractions [ANALYSIS]DONE 2008.01.27 PROB Sorting A Three-Valued Sequence [ANALYSIS]DONE 2008.01.27 PROB Healthy Holsteins [ANALYSIS]DONE 2008.01.27 PROB Hamming Codes [ANALYSIS]Section2.2 DONE 2008.01.27 TEXT Data StructuresDONE 2008.01.27 TEXT Dynamic ProgrammingDONE 2008.01.28 PROB Preface Numbering [ANALYSIS]DONE 2008.01.28 PROB Subset Sums [ANALYSIS]DONE 2008.01.28 PROB Runaround Numbers [ANALYSIS]DONE 2008.01.28 PROB Party Lamps [ANALYSIS]Section2.3 DONE 2008.01.28 PROB The Longest Prefix [ANALYSIS]DONE 2008.01.29 PROB Cow Pedigrees [ANALYSIS]DONE 2008.01.29 PROB Zero Sum [ANALYSIS]DONE 2008.01.29 PROB Money Systems [ANALYSIS]DONE 2008.01.29 PROB Controlling Companies [ANALYSIS]Section2.4 DONE 2008.01.29 TEXT Shortest Paths DONE 2008.01.30 PROB The Tamworth Two [ANALYSIS]DONE 2008.01.30 PROB Overfencing [ANALYSIS]DONE 2007.11.25 PROB Cow Tours [ANALYSIS]DONE 2007.11.03 PROB Bessie Come Home [ANALYSIS]DONE 2008.01.30 PROB Fractions to Decimals [ANALYSIS]Section 3.1 DONE 2008.01.30TEXT Minimal Spanning TreesDONE 2007.11.03PROB Agri-Net [ANALYSIS]DONE 2008.01.31PROB Score Inflation [ANALYSIS]DONE 2008.01.31PROB Humble Numbers [ANALYSIS]DONE 2008.01.31PROB Shaping Regions [ANALYSIS]DONE 2008.02.01PROB Contact [ANALYSIS]DONE 2008.02.01PROB Stamps [ANALYSIS]Section 3.2 DONE 2008.02.01TEXT Knapsack ProblemsDONE 2007.12.02PROB Factorials [ANALYSIS]DONE 2008.02.01PROB Stringsobits [ANALYSIS]DONE 2008.02.02PROB Spinning Wheels [ANALYSIS]DONE 2007.11.19PROB Feed Ratios [ANALYSIS]DONE 2008.02.02PROB Magic Squares [ANALYSIS](程序丢了)DONE 2008.02.05PROB Sweet Butter [ANALYSIS]Section 3.3 DONE 2008.02.05TEXT Eulerian ToursDONE 2008.02.05PROB Riding The Fences [ANALYSIS]DONE 2008.02.08PROB Shopping Offers [ANALYSIS]DONE 2008.02.09PROB Camelot [ANALYSIS]DONE 2008.02.09PROB Home on the Range [ANALYSIS]DONE 2008.02.09PROB A Game [ANALYSIS]Section 3.4 DONE 2008.02.12TEXT Computational GeometryDONE 2008.02.12PROB Closed Fences [ANALYSIS]DONE 2007.11.22PROB American Heritage [ANALYSIS]DONE 2008.02.15PROB Electric Fence [ANALYSIS]DONE 2008.02.15PROB Raucous Rockers [ANALYSIS]Section 4.1 DONE 2008.02.18 TEXT Optimization TechniquesDONE 2008.02.19 PROB Beef McNuggets [ANALYSIS]DONE 2008.03.01 PROB Fence Rails [ANALYSIS]DONE 2008.02.20 PROB Fence Loops [ANALYSIS]DONE 2008.02.22 PROB Cryptcowgraphy [ANALYSIS]Section 4.2 DONE 2008.03.01 TEXT "Network Flow" AlgorithmsDONE 2008.02.22 PROB Drainage Ditches [ANALYSIS]DONE 2007.12.11 PROB The Perfect Stall [ANALYSIS]DONE 2008.03.02 PROB Job Processing [ANALYSIS]DONE 2008.03.02 PROB Cowcycles [ANALYSIS]Section 4.3 DONE 2008.03.03 TEXT Big NumbersDONE 2007.12.02 PROB Buy Low, Buy Lower [ANALYSIS]DONE 2008.03.05 PROB The Primes [ANALYSIS]DONE 2008.03.07 PROB Street Race [ANALYSIS]DONE 2008.03.07 PROB Letter Game [ANALYSIS]Section 4.4 DONE 2008.03.07 PROB Shuttle Puzzle [ANALYSIS]DONE 2008.03.08 PROB Pollutant Control [ANALYSIS]DONE 2008.03.09 PROB Frame Up [ANALYSIS]Section 5.1 DONE 2008.03.14 TEXT Convex HullsDONE 2008.03.11 PROB Fencing the Cows [ANALYSIS]DONE 2008.03.14 PROB Starry Night [ANALYSIS]DONE 2008.03.15 PROB Musical Themes [ANALYSIS]Section 5.2 DONE 2008.03.16 PROB Snail Trail [ANALYSIS]DONE 2008.03.16 PROB Electric Fences [ANALYSIS]DONE 2008.03.17 PROB Wisconsin Squares [ANALYSIS]Section 5.3 DONE 2008.03.19 TEXT Heuristics & Approximate Searches DONE 2008.03.20 PROB Milk Measuring [ANALYSIS]DONE 2008.03.21 PROB Window Area [ANALYSIS]DONE 2008.03.22 PROB Network of Schools [ANALYSIS]DONE 2008.03.22 PROB Big Barn [ANALYSIS]Section 5.4 DONE 2008.03.23 PROB All Latin Squares [ANALYSIS]DONE 2008.03.25 PROB Canada Tour [ANALYSIS]DONE 2008.04.04 PROB Character Recognition [ANALYSIS]DONE 2008.03.28 PROB Betsy's Tour [ANALYSIS]DONE 2008.03.29 PROB TeleCowmunication [ANALYSIS]Section 5.5 DONE 2008.03.30 PROB Picture [ANALYSIS]DONE 2008.03.30 PROB Hidden Passwords [ANALYSIS]DONE 2008.04.04 PROB Two Five [ANALYSIS]Section 6.1 DONE 2008.04.01 PROB Postal Vans [ANALYSIS]DONE 2008.04.02 PROB A Rectangular Barn [ANALYSIS]DONE 2008.04.03 PROB Cow XOR [ANALYSIS]附录二:我写得比较详细的题解 USACO 3.1.4 Shaping Regions阅读了资料：薛矛的集训队论文参考了的方法：《信息学奥林匹克竞赛典型试题剖析》中的noi 97 年卫星覆盖解法，卫星覆盖是立体的立方体覆盖，它的退化就是矩形覆盖。

软件工程上机报告实验名称：八皇后问题图形界面求解姓名：郭恂学号：2011011435班级：11级数学班中国石油大学（北京）计算机科学与技术系一、试验程序截图：点击显示下一组解即可显示下一组解：同样的，如果点击上一组解即可显示上一组解。

若在第1组解时点击显示上一组解会弹出报错提示框。

同样，若在第92组解点击显示下一组解也会弹出报错提示框：二、程序代码程序使用Java语言编写，编写环境为jdk1.6.0_18。

使用编程开发环境eclipse.exe编写。

本程序创建了两个类，两个类在同一个工程中。

其中Queen类的作用仅仅用来保存八皇后问题计算结果的数据，便于画图时使用。

本程序大概由两部分组成，第一部分是解八皇后问题，第二部分是画图。

程序源代码为：类1：public class Queen{public int[] x=new int[8];public int[] y=new int[8];public String name;}类2：import javax.swing.*;import java.awt.event.*;import java.awt.*;import javax.swing.JOptionPane;public class bahuanghou extends JFrame implements ActionListener {//JLabel[] l;int number=0; //当前显示的解的编号int sum=0; //所有解得数量JLabel l2;JButton b1,b2; //b1为显示下一组解得按钮，b2为显示上一组解得按钮。

Queen[] q=new Queen[128]; //得到的解储存在Queen类的数组里面。

private Image bomb1=Toolkit.getDefaultToolkit().getImage("D:\\qizi1.JPG"); //黑格棋子为bomb1private Image bomb2=Toolkit.getDefaultToolkit().getImage("D:\\qizi2.JPG"); //白格棋子为bomb2public bahuanghou() //构造方法，初始化窗口。

6 八皇后问题【问题描述】在一个8×8的国际象棋棋盘上放置8个皇后，要求每个皇后两两之间不“冲突”，即没有一个皇后能“吃掉”任何其他一个皇后，简单的说就是没有任何两个皇后占据棋盘上的同一行或同一列或同一对角线，即在每一横列、竖列、斜列都只有一个皇后。

/*file name:Queen.cDescription:利用递归法求出8个皇后问题的解*/#include<stdio.h>#include<conio.h>#define TRUE 1#define FALSE 0#define MAXQUEEN 8#define ABS(x) ((x>0)?(x):-(x)) /*求x的绝对值*//*存放8个皇后的列位置，数组注标为皇后的列位置*/int queen[MAXQUEEN];int total_solution; /*计算共有几组解*//*函数原型声明*/void place(int);int attack(int,int);void output_solution();void main(){place(0); /*从第0个皇后开始摆放至棋盘*/getch();}void place(int q){C语言大学实用教程学习指导·268·int i=0;while(i<MAXQUEEN){if(!attack(i,q)) /*皇后未受攻击*/{queen[q]=i; /*储存皇后所在的列位置*//*判断是否找到一组解*/if(q==MAXQUEEN-1)output_solution(); /*列出此组解*/elseplace(q+1); /*否则继续摆下一个皇后*/}i++;}}/*测试在（row,col）上的皇后是否遭受攻击若遭受攻击则返回值为1，否则返回0*/int attack(int row,int col){int i,atk=FALSE;int offset_row,offset_col;i=0;while(!atk&&i<col){offset_col=ABS(i-col);offset_row=ABS(queen[i]-row);/*判断两皇后是否在同一列，是否在同一对角线*//*若两皇后在同列或同对角线，则产生攻击，atk==TRUE*/atk=(queen[i]==row)||(offset_row==offset_col);i++;}return atk;}/*列出8个皇后的解*/void output_solution()第3章学习指导·269·{int x,y;total_solution+=1;printf("Solution#%3d\n\t",total_solution);for(x=0;x<MAXQUEEN;x++){for(y=0;y<MAXQUEEN;y++)if(x==queen[y])printf("Q"); /*用字母Q表示皇后*/elseprintf("-"); /*用-表示空白*/printf("\n\t");}printf("\n");}。

描述在一个夜黑风高,下着暴风雨的夜晚,farmer John的牛棚的屋顶、门被吹飞了。

好在许多牛正在度假，所以牛棚没有住满。

牛棚一个紧挨着另一个被排成一行，牛就住在里面过夜。

有些牛棚里有牛，有些没有。

所有的牛棚有相同的宽度。

自门遗失以后,farmer John必须尽快在牛棚之前竖立起新的木板。

他的新木材供应商将会供应他任何他想要的长度,但是吝啬的供应商只能提供有限数目的木板。

farmer John想将他购买的木板总长度减到最少。

给出:可能买到的木板最大的数目M(1<= M<=50);牛棚的总数S(1<= S<=200); 牛棚里牛的总数C(1 <= C <=S);和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。

输出所需木板的最小总长度作为答案。

[编辑]格式PROGRAM NAME: barn1INPUT FORMAT:(file barn1.in)1 行: 木板最大的数目M ,牛棚的总数S 和牛的总数C(用空格分开)2 到C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。

OUTPUT FORMAT:(file barn1.out)单独的一行包含一个整数表示所需木板的最小总长度。

[编辑]SAMPLE INPUT4 50 1834681415161721252627303140414243[编辑]SAMPLE OUTPUT25//逆向思维#include<iostream>#include<fstream>#define max 202using namespace std;ifstream fin("barn1.in");ofstream fout("barn1.out");int a[max];//有牛的编号int b[max];//间隙int now;//最大长度int m,s,c;int cmp2(const void *va,const void *vb){return * (int *)vb - *(int *)va;}int main(){int i;fin>>m>>s>>c;for( i = 0; i < c; i ++) fin>>a[i];qsort( a, c, sizeof( a[0] ), cmp2);//编号从大到小for( i = 0;i < c - 1; i ++)b[i - 1] = a[i] - a[i + 1] - 1;//所有间隔qsort( b, c, sizeof( b[0] ), cmp2);//所有间隔按从大到小排列now = a[0] - a[c - 1] + 1;for( i = 0 ; i < m - 1 ; i ++)now = now - b[i]; //减去那些间隔从大到小，直到块数等于最大购入量fout<<now<<endl;return 0;}或#include <iostream>using namespace std;const int MAXS=200+10;int main(){freopen("barn1.in","r",stdin);freopen("barn1.out","w",stdout);int m,s,c;cin >> m >> s >> c;bool a[MAXS];memset(a,0,sizeof(a));int x;for (int i=0;i<c;i++) cin >> x, a[x]=1;int cou[MAXS];memset(cou,0,sizeof(cou));x=1;while (!a[x]) x++;for (int i=x+1;i<MAXS;i++)if (a[i]) ++cou[i-x-1], x=i;if (m>=c) { cout << c << endl;return 0;}x=c-m;int ans=0;for (int i=0;i<MAXS;i++){x-=cou[i];ans+=i*cou[i];if (x<=0) {ans-=(-x)*i;break;}}cout << ans+c << endl;return 0;}不过应该是先每牛一个栏，再填空隙，数量减到为止，因为不需要标志哪些是牛哪些是空栏，填满的就算作栏。