​欢迎大家订阅我的专栏算法题解C与Python实现本专栏旨在帮助大家从基础到进阶 逐步提升编程能力助力信息学竞赛备战专栏特色1.经典算法练习根据信息学竞赛大纲精心挑选经典算法题目提供清晰的代码实现与详细指导帮助您夯实算法基础。2.系统化学习路径按照算法类别和难度分级从基础到进阶循序渐进帮助您全面提升编程能力与算法思维。适合人群准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生希望系统学习C/Python编程的初学者想要提升算法与编程能力的编程爱好者附上汇总贴USACO历年青铜组真题解析 | 汇总-CSDN博客P1693 Sleepy Cow Herding【题目来源】洛谷[P1693 USACO19FEB] Sleepy Cow Herding B - 洛谷 (luogu.com.cn)【题目描述】Farmer John的三头获奖奶牛Bessie、Elsie和Mildred总是会迷路走到农场上遥远的地方去他需要你帮助将她们一起赶回来。农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴奶牛可以占据数轴上的任意整数位置。这3头奶牛现在正位于不同的整数位置Farmer John想要移动她们使得她们占据三个相邻的位置例如位置6 66、7 77、8 88。不幸的是奶牛们现在很困Farmer John要让她们集中精力听从命令移动并不容易。任意时刻他只能使得一头处在“端点”在所有奶牛中位置最小或最大位置的奶牛移动。当他移动奶牛时他可以命令她走到任意一个未被占用的整数位置只要在新的位置上她不再是一个端点。可以看到随着时间的推移这样的移动可以使奶牛们趋向越来越近。请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。【输入】输入包含一行包括三个空格分隔的整数为Bessie、Elsie和Mildred的位置。每个位置均为一个范围**1 … 10 9 1\dots 10^91…109**内的整数。【输出】输出的第一行包含Farmer John需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。【输入样例】4 7 9【输出样例】1 2【解题思路】【算法标签】《洛谷 P1693 Sleepy Cow Herding》 #USACO# #O2优化# #2019#【代码详解】#includebits/stdc.husingnamespacestd;inta[5];// 存储三个奶牛的位置intminn0;// 最小移动次数intmaxn0;// 最大移动次数// 文件输入输出流注释掉的代码// ifstream filein(herding.in);// ofstream fileout(herding.out);intmain(){// 输入三个奶牛的位置for(inti1;i3;i){// cin a[i];// filein a[i];cina[i];}// 对三个位置进行排序从小到大sort(a1,a31);// 情况1三个奶牛已经连续相邻间隔都为1if(a[2]-a[1]1a[3]-a[2]1){// 无需移动cout0endl0endl;}// 情况2两个间隔分别为2和1如1,3,4 或 1,2,4elseif((a[2]-a[1]2a[3]-a[2]1)||(a[2]-a[1]1a[3]-a[2]2)){// 只需要移动一次即可使三个奶牛连续cout1endl1endl;}// 情况3两个间隔都为2如1,3,5elseif(a[2]-a[1]2a[3]-a[2]2){// 只需要移动一次即可使三个奶牛连续cout1endl1endl;}// 情况4一个间隔大于2另一个间隔为1如1,4,5 或 1,2,5elseif((a[2]-a[1]2a[3]-a[2]1)||(a[2]-a[1]1a[3]-a[2]2)){minn2;// 最小需要移动2次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移动次数为较大间隔减1coutminnendlmaxnendl;}// 情况5一个间隔大于2另一个间隔为2如1,4,6 或 1,3,6elseif((a[2]-a[1]2a[3]-a[2]2)||(a[2]-a[1]2a[3]-a[2]2)){minn1;// 最小需要移动1次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移动次数为较大间隔减1coutminnendlmaxnendl;}// 情况6两个间隔都大于2如1,5,10elseif(a[2]-a[1]2a[3]-a[2]2){minn2;// 最小需要移动2次maxnmax(a[2]-a[1]-1,a[3]-a[2]-1);// 最大移动次数为较大间隔减1coutminnendlmaxnendl;}return0;}【运行结果】4 7 9 1 2P1694 The Great Revegetation【题目来源】洛谷[P1694 USACO19FEB] The Great Revegetation B - 洛谷【题目描述】长时间的干旱使得 Farmer John 的N NN块草地上牧草匮乏。随着雨季即将到来现在应当是重新种植的时候了。在 Farmer John 的储物棚里有四个桶每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶农Farmer John 想要确保他的每头奶牛都能得到丰富的食谱。他的M MM头奶牛每一头都有两块喜爱的草地他想要确保这两块草地种植不同种类的草从而每头奶牛都可以有两种草可供选择。Farmer John 知道没有一块草地受到多于3 33头奶牛的喜爱。请帮助 Farmer John 选择每块草地所种的草的种类使得所有奶牛的营养需求都得到满足。【输入】输入的第一行包含2 ≤ N ≤ 100 2 \leq N \leq 1002≤N≤100和1 ≤ M ≤ 150 1 \leq M \leq 1501≤M≤150。以下M MM行每行包含两个范围为1 … N 1 \dots N1…N的整数为 Farmer John 的一头奶牛喜欢的两块草地。【输出】输出一个N NN位数每一位均为1 … 4 1\ldots 41…4之一表示每一块草地上所种的草的种类。第一位对应草地1 11的草的种类第二位对应草地2 22以此类推。如果有多种可行的解只需输出所有解中最小的N NN位数。【输入样例】5 6 4 1 4 2 4 3 2 5 1 2 1 5【输出样例】12133【解题思路】【算法标签】《洛谷 P1694 The Great Revegetation》 #贪心# #USACO# #O2优化# #2019#【代码详解】// 尝试用过贪心算法后发现只有3个测试点通过其余均超时#includebits/stdc.husingnamespacestd;inta1[105][105],G[105];intn,m;// ifstream filein(revegetate.in);// ofstream fileout(revegetate.out);intmain(){cinnm;// 输入n和mfor(inti1;im;i){// 遍历m条边inta,b;cinab;// 输入边的端点a1[a][b]1;// 因为是无向图所以边的两个方向均置为1a1[b][a]1;}for(inti1;in;i){// 遍历n个顶点intk;// 定义颜色没放到循环中是因为后面要通过G[i]来赋值for(k1;k4;k){// 遍历4个颜色booloktrue;// 定义ok用于判断边的两个端点颜色是否冲突for(intj1;jn;j){// 再遍历n个顶点if(a1[i][j]1G[j]k){// 如果i和j是一条边上的两个顶点且j这个点的颜色为k即已经有颜色了okfalse;// 修改ok为false}}if(ok)break;// 没有一条边上的两个顶点颜色冲突则退出循环即颜色留在当前k上}G[i]k;// 将这个k赋值给G[i]}for(inti1;in;i){// 遍历n个顶点coutG[i];// 将每个顶点的颜色打印出来中间不空格}coutendl;return0;}【运行结果】5 6 4 1 4 2 4 3 2 5 1 2 1 5 12133