核心内容摘要
小樱36776,22905：不止于数字，是关于美好的无限可能
欢迎大家订阅我的专栏算法题解C与Python实现本专栏旨在帮助大家从基础到进阶 逐步提升编程能力助力信息学竞赛备战专栏特色
经典算法练习根据信息学竞赛大纲精心挑选经典算法题目提供清晰的代码实现与详细指导帮助您夯实算法基础。
系统化学习路径按照算法类别和难度分级从基础到进阶循序渐进帮助您全面提升编程能力与算法思维。
适合人群准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生希望系统学习C/Python编程的初学者想要提升算法与编程能力的编程爱好者附上汇总贴USACO历年青铜组真题解析 | 汇总-CSDN博客P5831 Cow Gymnastics【题目来源】洛谷[P5831 USACO19DEC] Cow Gymnastics B - 洛谷【题目描述】为了提高健康水平奶牛们开始进行体操训练了Farmer John 选定了他最喜爱的奶牛 Bessie 来执教其他N NN头奶牛同时评估她们学习不同的体操技术的进度。
K KK次训练课的每一次Bessie 都会根据N NN头奶牛的表现给她们进行排名。
之后她对这些排名的一致性产生了好奇。
称一对不同的奶牛是一致的如果其中一头奶牛在每次训练课中都表现得都比另一头要好。
请帮助 Bessie 计算一致的奶牛的对数。
【输入】输入的第一行包含两个正整数K KK和N NN。
以下K KK行每行包含整数1 … N 1\dots N1…N的某种排列表示奶牛们的排名奶牛们用编号1 … N 1\dots N1…N进行区分。
如果在某一行中A AA出现在B BB之前表示奶牛A AA表现得比奶牛B BB要好。
【输出】输出一行包含一致的奶牛的对数。
【输入样例】3 4 4 1 2 3 4 1 3 2 4 2 1 3【输出样例】4【解题思路】【算法标签】《洛谷 P5831 Cow Gynmnastics》 #枚举# #USACO# #2019#【代码详解】#includebits/stdc.husingnamespacestd;intk,n,a[25][25]{0},t[25]{0},ans0;intmain(){cinkn;// 输入k和nwhile(k--){// 依次读入k行数据for(inti1;in;i){// 依次记录n个数据cint[i];}for(inti1;in;i){// 定义二维矩阵分别记录每2个数的先后关系for(intji1;jn;j){a[t[j]][t[i]]1;// t[j]在t[i]后面将表现不好的标记为1}}}for(inti1;in;i){// 处理二维矩阵的斜线位置左上到右下的斜线for(intj1;jn;j){if(ij)a[i][j]1;// 这些也标记为1}}for(inti1;in;i){// 遍历二维矩阵for(intj1;jn;j){if(a[i][j]
ans;// 对于值为0的单元格就是一对A优于B的存在。
统计ans就是一致的奶牛的对数}}coutansendl;return0;}【运行结果】3 4 4 1 2 3 4 1 3 2 4 2 1 3 4P5832 Where Am I?【题目来源】洛谷[P5832 USACO19DEC] Where Am I? B - 洛谷【题目描述】Farmer John 出门沿着马路散步但是他现在发现可能迷路了沿路有一排共N NN个农场。
不幸的是农场并没有编号这使得 Farmer John 难以分辨他在这条路上所处的位置。
然而每个农场都沿路设有一个彩色的邮箱所以 Farmer John 希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。
每个邮箱的颜色用A . . Z A..ZA..Z之间的一个字母来指定所以沿着道路的N NN个邮箱的序列可以用一个长为N NN的由字母A . . Z A..ZA..Z组成的字符串来表示。
某些邮箱可能会有相同的颜色。
Farmer John 想要知道最小的K KK的值使得他查看任意连续K KK个邮箱序列他都可以唯一确定这一序列在道路上的位置。
例如假设沿路的邮箱序列为ABCDABC。
Farmer John 不能令K 3 K3K3因为如果他看到了ABC沿路有两个这一连续颜色序列可能所在的位置。
最小可行的K KK的值为K 4 K4K4因为如果他查看任意连续4 44个邮箱这一颜色序列可以唯一确定他在道路上的位置。
【输入】输入的第一行包含N NN第二行包含一个由N NN个字符组成的字符串每个字符均在A . . Z A..ZA..Z之内。
【输出】输出一行包含一个整数为可以解决 Farmer John 的问题的最小K KK值。
【输入样例】7 ABCDABC【输出样例】4【解题思路】【算法标签】《洛谷 P5832 Where Am I?》 #字符串# #USACO# #2019#【代码详解】#includebits/stdc.husingnamespacestd;intn;string s;intmain(){cinns;// 输入n和字符串sfor(inti1;is.length();i){// 遍历1-n的长度intmark0;// 定义mark用来指示是否查找到相同子串for(intj0;js.length();j){// 从0开始遍历字符串string s1s.substr(j,i);// 截取字符串s1for(intkj1;ks.length();k){// 从j1的位置遍历字符串string s2s.substr(k,i);// 截取字符串s2if(s1s
{// 如果两个字符串相等mark1;// 修改mark为1表示找到相同内容break;// 退出循环}}}if(mark
{// 每轮都会检查mark是否为0如果为0则说明没有相等的字符串coutiendl;// 输入此时字符串长度return0;// 退出程序}}return0;}【运行结果】7 ABCDABC 4P5833 Livestock Lineup【题目来源】洛谷[P5833 USACO19DEC] Livestock Lineup B - 洛谷【题目描述】每天Farmer John 都要给他的8 88头奶牛挤奶。
她们的名字分别是 BessieButtercupBelindaBeatriceBellaBlueBetsy和 Sue。
不幸的是这些奶牛相当难以伺候她们要求 Farmer John 以一种符合N NN条限制的顺序给她们挤奶。
每条限制的形式为“X XX必须紧邻着Y YY挤奶”要求奶牛X XX在挤奶顺序中必须紧接在奶牛Y YY之后或者紧接在奶牛Y YY之前。
请帮助 Farmer John 求出一种满足所有限制的奶牛挤奶顺序。
保证这样的顺序是存在的。
如果有多种顺序都满足要求请输出字典序最小的一种。
也就是说第一头奶牛需要是所有可能排在任意合法奶牛顺序的第一位的奶牛中名字字典序最小的。
在所有合法的以这头字典序最小的奶牛为首的奶牛顺序中第二头奶牛需要是字典序最小的以此类推。
【输入】输入的第一行包含N NN。
以下N NN行每行包含一句句子以 “X XXmust be milked besideY YY” 的格式描述了一条限制其中X XX和Y YY为 Farmer John 的某些奶牛的名字上文列举了八个可能的名字。
【输出】请用8 88行输出一个奶牛的顺序每行输出一头奶牛的名字满足所有的限制。
如果由多种顺序符合要求输出字典序最小的奶牛顺序。
【输入样例】3 Buttercup must be milked beside Bella Blue must be milked beside Bella Sue must be milked beside Beatrice【输出样例】Beatrice Sue Belinda Bessie Betsy Blue Bella Buttercup【解题思路】【算法标签】《洛谷 P5833 Livestock Lineup》 #字符串# #USACO# #2019#【代码详解】#includebits/stdc.husingnamespacestd;intn;string a[9]{,Bessie,Buttercup,Belinda,Beatrice,Bella,Blue,Betsy,Sue};string b[10];intbook[10]{0};structnode{string x,y;}p[10];voiddfs(intstep)// 排列模板{if(step