USACO题目Friday the Thirteenth及代码解析

描述排序是一种很频繁的计算任务。

现在考虑最多只有三值的排序问题。

一个实际的例子是，当我们给某项竞赛的优胜者按金银铜牌排序的时候。

在这个任务中可能的值只有三种1，2和3。

我们用交换的方法把他排成升序的。

写一个程序计算出，给定的一个1,2,3组成的数字序列，排成升序所需的最少交换次数。

[编辑]格式PROGRAM NAME: sort3INPUT FORMAT:(file sort3.in)第一行：奖牌个数N (1 <= N <= 1000)第2行到第N+1行:每行一个数字，表示奖牌。

共N行。

（1..3）OUTPUT FORMAT:(file sort3.out)共一行，一个数字。

表示排成升序所需的最少交换次数。

[编辑]SAMPLE INPUT9221333231[编辑]SAMPLE OUTPUT4分析题意求排序所需的最少移动次数，可以先将输入的数字排序，然后得到不同的地方比如：2 2 13 3 3 2 3 11 12 2 23 3 3 3用一个组合(a,b)表示应该排序后某个位置应该是a，但之前的是b则我们得到(1,2), (1,2), (2,1), (2,3), (2,3), (3,2), (3,1)然后求这些组合能组成的环，结果就是所有环的长度和减去环的个数(1,2), (2,1) ---长度为2(1,2), (2,3), (3,1) ---长度为3(2,3), (3,2) ---长度为2结果2+3+2-3=4这个不怕题目改为1234排序。

下面的就怕：另一个简单的思路我是没看懂前面的...所以自己想了一个首先如果两数位置都错了，并且交换后都在正确的位置，这一次交换肯定是必然的跑一遍把所有的符合上述条件的数交换回来每次交换ANS++；剩下的就是3个数的位置都是错的，也可以通过两次交换达到正确位置每次交换ans+=2；（其实可以不用交换，就检查一下在1的位置上有多少个不是1的，乘2即可）：#include<fstream>using namespace std;ifstream fin("sort3.in");ofstream cout("sort3.out");int n,a[1001],b[1001],num[4][4]={0},ans=0;int main(){int i,j;fin>>n;for(i=1;i<=n;i++){fin>>a[i];b[i]=a[i];}for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)if(b[i]>b[j]) swap(b[i],b[j]);for(i=1;i<=n;i++)num[b[i]][a[i]]++;j=min(num[1][2],num[2][1]);num[1][2]-=j;num[2][1]-=j;ans+=j;j=min(num[1][3],num[3][1]);num[1][3]-=j;num[3][1]-=j;ans+=j;j=min(num[3][2],num[2][3]);num[3][2]-=j;num[2][3]-=j;ans+=j;ans+=max(num[1][2],num[2][1])*2;cout<<ans<<endl;// system("pause");return 0;}。

“初学者平台-USACO”的相关说明一、如何进入USACO平台1、直接在IE浏览器中键入网址/usacogate；2、如首次使用，请直接点击“Register here for a username/password”项，注册你的用户名和密码；否则，请输入用户名和密码（username/password）进行登陆。

二、可供题目（共100题左右，注意必须按顺序完成，否则将不能继续进行）Section 1.1.1PROB: Your Ride Is HerePROB: Greedy Gift GiversSection 1.1.2PROB: Broken NecklacePROB: Prime PalindromesPROB: The Errant PhysicistSection 1.1.3PROB: Mixing MilkPROB: Barn RepairPROB: What Time Is It?Section 1.1.4PROB: Checker ChallengePROB: SuperPrime RibPROB: Number TrianglesSection 1.2.1PROB: Shaping RegionsPROB: The CastlePROB: Ordered FractionsPROB: ContactSection 1.2.2PROB: Preface NumberingPROB: Runaround NumbersPROB: Money SystemsPROB: The Tamworth TwoPROB: Milking CowsSection 1.2.3PROB: OverfencingPROB: Bessie Come HomePROB: The ClocksPROB: Fractions to DecimalsSection 1.2.4PROB: Score InflationPROB: Mother's MilkPROB: Name That NumberPROB: Humble NumbersPROB: Palindromic SquaresPROB: FactorialsPROB: StringsobitsPROB: Prime CryptarithmPROB: Sorting A Three-Valued Sequence Section 1.3.1PROB: Riding The FencesPROB: Party LampsPROB: Dual PalindromesSection 1.3.2PROB: Agri-NetPROB: Home on the RangePROB: Calf FlacPROB: A GameSection 1.3.3PROB: CamelotPROB: Friday the ThirteenthPROB: Packing RectanglesPROB: Zero SumPROB: Controlling CompaniesSection 1.3.4PROB: Closed FencesPROB: Cow ToursPROB: American HeritagePROB: TransformationsSection 1.4.1PROB: Beef McNuggetsPROB: Fence RailsPROB: Fence LoopsPROB: CryptcowgraphyPROB: Arithmetic Progressions Section 1.4.2PROB: Drainage DitchesPROB: The Perfect StallPROB: Buy Low, Buy LowerPROB: Job ProcessingPROB: Frame UpSection 1.4.3PROB: The PrimesPROB: The Longest PrefixPROB: CowcyclesPROB: Shopping OffersPROB: Street RacePROB: Spinning WheelsPROB: Feed RatiosPROB: Shuttle PuzzlePROB: Magic SquaresPROB: Pollutant Control Section 1.5.1PROB: Healthy HolsteinsPROB: Subset SumsPROB: Starry NightPROB: All Latin Squares Section 1.5.2PROB: Fencing the CowsPROB: Canada TourSection 1.5.3PROB: Snail TrailPROB: PicturePROB: Window AreaPROB: Electric FencesPROB: Wisconsin SquaresPROB: Hamming Codes Section 1.5.4PROB: Avoiding Les EntarteursPROB: Map LabellingPROB: Milk MeasuringPROB: Network of SchoolsPROB: Big BarnSection 1.5.5PROB: StampsPROB: The CirclePROB: Character RecognitionPROB: Electric FencePROB: Betsy's TourPROB: TeleCowmunicationPROB: Wires and Switches Section 1.5.6PROB: Cow ScansPROB: PolygonPROB: Musical ThemesPROB: Raucous RockersPROB: Amazing BarnPROB: Letter Game。

五年级美国大联盟第一阶段-计算+几何专题（教师版）学生/课程年级学科授课教师日期时段核心内容null 课型null教学目标1、掌握分数、百分数、乘方的计算。

2、掌握因数倍数、质数合数、奇数偶数、最大公因数和最小公倍数、倍数关系。

3、掌握组合图形的面积。

重、难点1、掌握分数、百分数、乘方的计算。

2、掌握因数倍数、质数合数、奇数偶数、最大公因数和最小公倍数、倍数关系。

3、掌握组合图形的面积。

导学一知识点讲解计算数的计算：整数、分数、百分数的计算与乘方例题1.[单选题] [整数的加法和减法] [难度：★★★ ] The sum of 5 consecutive one-digit integers is at most （）A、15B、25C、35D、45【参考答案】C【题目解析】5个连续的一位数的整数之和最大是（）2.[单选题] [数的运算] [难度：★★★ ] I have read 1/3 of the total chapters in my 120-page book. If each chapter has the same whole number of pages, then the total number of chapters I have left could be （）A、16B、24C、32D、50【参考答案】A【题目解析】我已经阅读了120页的书的章节总数的1/3。

如果每一章都有相同的总页数，那么我剩下的章节总数可以是（）3.[单选题] [数的运算] [难度：★★★ ] Which of the following has the greatest value?A 、2017B、2017 C、20×17D、20+17【参考答案】B【题目解析】下面的数中，哪个数的值最大？我爱展示1. [单选题] [数的运算] [难度：★★★ ] Which of the following when rounding to the nearestthousands,hundreds, and tens, equals 3000, 3500, and 3460, respectively?A、3210B、3333C、3456D、3517【参考答案】C【题目解析】下面的数中，哪个数分别四舍五入到千位、百位、十位，结果是3000、3500、3460？2000 2017 20002. [单选题] [数的运算] [难度：★★★ ] 2 ×5= 10 ×?17 1000 2000 2017A、5B、5C、5D、5【参考答案】A3. [单选题] [数的运算] [难度：★★★ ] The number that is 10% of 1000 is 10 more than 10% of（）A、90B、100C、900D、990【参考答案】A【题目解析】1000的10%大于（）的10%的10倍。

USACO 题解Chapter1Section 1.1Your Ride Is Here (ride)这大概是一个容易的问题，一个“ad hoc”问题，不需要特殊的算法和技巧。

Greedy Gift Givers (gift1)这道题的难度相当于联赛第一题。

用数组incom、outcom记录每个人的收入和支出，记录每个人的名字，对于送礼人i，找到他要送给的人j，inc(incom[j],outcom[i] div n)，其中n 是要送的人数，最后inc(incom[i],outcom[i] mod n)，最后输出incom[i]-outcom[i]即可。

（复杂度O(n^3)）。

用Hash表可以进行优化，降复杂度为O(n^2)。

Friday the Thirteenth (friday)按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1) mod 7+1的星期。

因为数据小，所以不会超时。

当数据比较大时，可以以年为单位计算，每年为365天，mod 7的余数是1，就是说每过一年所有的日和星期错一天，闰年第1、2月错1天，3月以后错2天。

这样，只要先求出第一年的解，错位添加到以后的年即可。

详细分析：因为1900.1.1是星期一，所以1900.1.13就等于(13-1) mod7+1=星期六。

这样讲可能不太清楚。

那么，我来解释一下：每过7天是一个星期。

n天后是星期几怎么算呢？现在假设n是7的倍数，如果n为14，那么刚好就过了两个星期，所以14天后仍然是星期一。

但如果是过了15天，那么推算就得到是星期二。

这样，我们就可以推导出一个公式来计算。

(n天mod 7（一个星期的天数）+ 现在日期的代号) mod 7 就等于现在日期的代号。

当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，我们可以得出题目的算法：int a[13]={0，31，28，31，30，31，30，31，31，30，31，30，31}int b[8]={0}a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。

在威斯康辛州牛大农场经营者之中，都习惯于请会计部门用连续数字给母牛打上烙印。

但是,母牛本身并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴，而不是用像这个的语句"C'mon, #4734, get along."。

请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。

因为母牛们现在都有手机了，使用那标准的按键的排布来把将数目翻译为文字:( 除了"Q" 和"Z")2: A,B,C 5: J,K,L 8: T,U,V3: D,E,F 6: M,N,O 9: W,X,Y4: G,H,I 7: P,R,S可接受的名字都被放在这样一个叫作"dict.txt" 的文件中，它包含一连串的少于5,000个（准确地说是4617个）可被接受的牛的名字。

(所有的名字都是大写的且已按字典序排列) 请读入母牛的编号并返回那些能从编号翻译出来并且在字典中的名字。

举例来说,编号4734 能产生的下列各项名字: GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI碰巧，81个中只有一个"GREG"是有效的(在字典中)。

USACO（The USA Computing Olympiad）是美国计算机奥林匹克竞赛，它是一个为美国中学生提供计算机科学培训和竞赛的组织。

USACO 题目是该竞赛的一部分，它要求参赛者解决一系列算法和编程问题，这些问题需要运用数学知识和编程技巧来解决。

USACO 题目的结果是指对每个测试用例给出的程序输出。

因为USACO 题目通常包含多个测试用例，每个测试用例都有一个特定的输入和对应的输出。

解决 USACO 题目时，参赛者需要编写程序来处理输入数据，并将计算结果输出为符合要求的格式。

每个测试用例的结果通常以成绩的形式提交，用于评判解答的正确性和效率。

下面将通过以下几个方面来介绍USACO 题目每个test case 的结果：1. test case 的生成2. 对 test case 的处理3. 结果的验证1. test case 的生成test case 是用来测试程序正确性的一组输入数据和对应的标准输出。

在 USACO 题目中，通常会给出测试用例的范围和要求，参赛者需要编写程序来生成符合要求的测试用例。

通常情况下，参赛者需要考虑各种边界情况和特殊情况，以确保程序在各种情况下都能正确运行。

2. 对 test case 的处理参赛者需要编写程序来对每个测试用例进行处理。

这需要参赛者熟练掌握编程语言的基本语法和数据结构，以便能够高效地处理输入数据并产生正确的输出。

在处理 test case 时，参赛者需要注意错误处理和边界条件，以确保程序的健壮性和正确性。

3. 结果的验证参赛者需要编写程序来验证每个 test case 的结果。

这包括将程序输出与标准输出进行比较，以判断程序的正确性。

在 USACO 题目中，结果的验证通常会包括对程序输出的各种情况进行检查，以确保程序的正确性和稳定性。

处理USACO 题目每个test case 的结果需要参赛者具备扎实的编程基础和分析问题的能力。

通过对每个测试用例的生成、处理和结果验证，参赛者可以提高自己的算法和编程水平，同时也能在竞赛中取得更好的成绩。

【usaco2023 12月银组题解】一、题目概况1.1 题目背景12月份的usaco银级比赛是每年一度的重要赛事，题目难度适中，涵盖了很多经典算法和数据结构的应用。

1.2 题目数量本次比赛共包含5道题目，涉及动态规划、贪心算法、图论等多个领域。

二、题目详解2.1 第一题 - 最小差值本题要求给定一个包含n个正整数的数组，求该数组中两个元素的最小差值。

2.1.1 解题思路我们可以先对数组进行排序，然后遍历数组中相邻的两个元素，计算它们之间的差值，并更新最小差值。

2.1.2 代码实现```c++int minDiff(vector<int> nums) {sort(nums.begin(), nums.end());int minDiff = INT_MAX;for (int i = 1; i < nums.size(); i++) {minDiff = min(minDiff, nums[i] - nums[i-1]);}return minDiff;}```2.2 第二题 - 运动员配对本题要求给定一个包含n个正整数的数组，表示n个运动员的实力值，要求找出一种最优的配对方案，使得每对运动员的实力差值最小。

2.2.1 解题思路我们可以先对数组进行排序，然后使用双指针法找出实力差值最小的配对方案。

2.2.2 代码实现```c++int minP本人ring(vector<int> strength) {sort(strength.begin(), strength.end());int minDiff = INT_MAX;int l = 0, r = strength.size()-1;while (l < r) {minDiff = min(minDiff, strength[r] - strength[l]);l++;r--;}return minDiff;}```2.3 第三题 - 最小生成树本题给定一个无向连通图，要求求出该图的最小生成树的权值之和。

USACO 三月份试题简体中文版本By xzh************************************华丽的分割线*******************************青铜组问题************************************华丽的分割线*******************************四道题目，编号从11到14************************************华丽的分割线*******************************问题11：极品飞车贝西正在为一场即将到来的大奖赛准备她的赛车。

她希望购买一些部件来提高这辆赛车的性能。

他的赛车质量为M (1 <= M <= 1,000)，加速度为(1 <= F <= 1,000,000)。

在赛车的配件店有N(1 <= N <= 20)个零件，编号分别为1到N。

只要他愿意，贝西可以买任意多个或者任意少个零件。

第P_i个零件增加加速度F_i (1 <= F_i <= 1,000,000)，同时重量为M_i (1 <= M_i <= 1,000)。

根据牛顿第二定律，F=MA，F为加速度，M为质量，A为速度。

为了使她的赛车最大限度的发挥它的加速度的同时减少重量，她应该安装哪些组件？假设一辆赛车，他的初始加速度为1500，初始重量为100，有四种零件可以选择：i F_i M_i1 250 252 150 93 120 54 200 8如果只添加零件2，他的速度将是(1500+150)/(100+9) = 1650/109 = 15.13761。

下面是一个表格，表现了添加或不添加不同的零件后赛车的速度。

（0表示未添加，1表示已添加）部件总和总和1234 F M F/M0000 1500 100 15.00000001 1700 108 15.74070010 1620 105 15.42860011 1820 113 16.10620100 1650 109 15.13760101 1850 117 15.81200110 1770 114 15.52630111 1970 122 16.1475 <-- 最高的F/M1000 1750 125 14.00001001 1950 133 14.66171010 1870 130 14.38461011 2070 138 15.00001100 1900 134 14.17911101 2100 142 14.78871110 2020 139 14.53241111 2220 147 15.1020最终，最佳的方案是选择2，3和4号部件问题名称: boost输入格式：第一行：三个整数：F,M和N从第二行到第N+1行：第I+1行有两个整数：F_i和M_i样例输入：(文件boost.in):1500 100 4250 25150 9120 5200 8输出格式第一到P行：P个贝西应该给他的赛车增加的额外部件的编号，每个一行。

USACO原题Chapter1Section1.1YourRideIHere你的飞碟在这儿！问题描述科学家们在研究彗星后惊讶地发现，在每一个彗星后面都有一个不明飞行物UFO。

这些不明飞行物时常来带走来自地球上的一些支持者。

不幸地，他们的空间在每次旅行只能带上一群支持者。

他们要做的是用一种聪明的方案让某个支持彗星UFO的团体都被彗星带走。

他们为每个彗星起了一个名字，通过这些名字来决定一个团体是不是特定的彗星带走。

那个相配方案的细节是这样的:所有团体的名字和彗星的名字都以下列各项方式转换成一个数字:这个最后的数字代表名字中所有字母的信息，\是1和\是26。

举例来说，团体\会是21某19某1某3某15=17955如果团体的数字mod47等于慧星的数字mod47,那么你要告诉这个团体：准备好行李，走吧!现在，你要写一个程序来通过团体的名字和彗星的名字来决定一个组是否应该与在那一颗彗星后面的不明飞行物搭配。

写一个程序读入彗星的名字和团体的名字，如果搭配打印\否者打印\团体的名字和彗星的名字将会是没有空格或标点的一串大写字母（不超过6个字母）。

样例样例1:输入:COMETQHVNGAT输出:GO样例2:输入:ABSTARUSACO输出:STAY格式文件名：ride(.pa/.c/.cpp)输入格式：(输入文件名ride.in）第1行:彗星的名字（一个长度为1到6的字符串）第1页共53页第2行:团体的名字（一个长度为1到6的字符串）输出格式:(输出文件名ride.out)只有一行----\或\GreedyGiftGiver贪婪的送礼者描述对于一群要互送礼物的朋友，你要确定每个人收到的礼物比送出的多多少,反之亦然对于那些用贪婪的眼光来看礼物的人(byJohn)。

在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。

然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。