​欢迎大家订阅我的专栏算法题解C与Python实现本专栏旨在帮助大家从基础到进阶 逐步提升编程能力助力信息学竞赛备战专栏特色1.经典算法练习根据信息学竞赛大纲精心挑选经典算法题目提供清晰的代码实现与详细指导帮助您夯实算法基础。2.系统化学习路径按照算法类别和难度分级从基础到进阶循序渐进帮助您全面提升编程能力与算法思维。适合人群准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生希望系统学习C/Python编程的初学者想要提升算法与编程能力的编程爱好者附上汇总贴USACO历年青铜组真题解析 | 汇总-CSDN博客P9944 Comfortable Cows【题目来源】洛谷[P9944 USACO21FEB] Comfortable Cows B - 洛谷【题目描述】Farmer John 的草地可以被看作是一个由正方形方格组成的巨大的二维方阵想象一个巨大的棋盘。初始时草地上是空的。Farmer John 将会逐一地将N NN1 ≤ N ≤ 10 5 1\le N\le 10^51≤N≤105头奶牛加入到草地上。第i ii头奶牛将会占据方格( x i , y i ) (x_i,y_i)(xi​,yi​)不同于所有已经被其他奶牛占据的方格0 ≤ x i , y i ≤ 1000 0\le x_i,y_i\le 10000≤xi​,yi​≤1000。一头奶牛被称为是「舒适的」如果它水平或竖直方向上与恰好三头其他奶牛相邻。Farmer John 对他的农场上舒适的奶牛数量感兴趣。对1 … N 1\ldots N1…N中的每一个i ii输出第i ii头奶牛加入到草地上之后舒适的奶牛的数量。【输入】输入的第一行包含一个整数N NN。以下N NN行每行包含两个空格分隔的整数表示一头奶牛所在的方格坐标( x , y ) (x,y)(x,y)。输入保证所有方格的坐标是不同的。【输出】输出的第i ii行包含前i ii头奶牛加入到草地上之后舒适的奶牛的数量。【输入样例】8 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2【输出样例】0 0 0 1 0 0 1 2【解题思路】【算法标签】《洛谷 P9944 Comfortable Cows》 #USACO# #O2优化# #2021#【代码详解】#includebits/stdc.husingnamespacestd;intn,res0,cnt0;inta[1005][1005];intdx[4]{-1,0,1,0},dy[4]{0,1,0,-1};intmain(){cinn;// 输入nfor(inti1;in;i){// 遍历n头奶牛intx,y;// 定义每头奶牛的坐标x和yintcnt10,cnt20;// 定义添加前和添加后舒适量的统计cinxy;// 输入奶头的坐标for(intix-1;ix1;i){// 遍历这台奶牛周围计算添加之前的舒适量for(intjy-1;jy1;j){intans0;// 定义周围奶牛的数量初始为0if(a[i][j]1){// 如果该位置有奶牛for(intk0;k4;k){// 则判断周围4个方向是否有奶牛intxxidx[k];intyyjdy[k];if(xx0||yy0)continue;if(a[xx][yy]1)ans;// 有的话ans自增}if(ans3)cnt1;// 如果ans为3则舒适的奶牛数量加1}}}a[x][y]1;// 添加输入的奶牛for(intix-1;ix1;i){// 再次遍历这台奶牛周围计算添加之后的舒适量for(intjy-1;jy1;j){intans0;if(a[i][j]1){for(intk0;k4;k){intxxidx[k];intyyjdy[k];if(xx0||yy0)continue;if(a[xx][yy]1)ans;}if(ans3)cnt2;// 如果ans为3则舒适的奶牛数量加1}}}rescnt2-cnt1;// 计算前后的变化并累加到ans中有时相减会变为负数coutresendl;// 最后打印结果}return0;}【运行结果】8 0 1 0 1 0 0 1 1 0 1 2 1 2 1 0 2 2 0 3 1 1 3 2 2P9945 Clockwise Fence【题目来源】洛谷[P9945 USACO21FEB] Clockwise Fence B - 洛谷【题目描述】围绕 Farmer John 最大的草地的栅栏已经损坏了如今他终于决定要换一个新的栅栏。不幸的是当 Farmer John 在铺设新栅栏时一只巨大的蜜蜂突然出现在他的草地上追着他跑导致最后栅栏被沿着一条相当不规则的路径铺设。栅栏可以用一个字符串表示每个字符为Nnorth北、Eeast东、Ssouth南、Wwest西之一。每个字符表示一米长的一段栅栏。举例来说如果字符串为NESW这表示栅栏从起点开始向北延伸1 11米然后向东延伸1 11米然后向南延伸1 11米然后向西延伸1 11米回到栅栏的起点。栅栏的结束位置与开始位置相同而这是栅栏的路径上唯一会被到达多次的位置从而起始位置是唯一会被再次到达的位置在栅栏结束之时。结果栅栏确实围起了一个草地上连通的区域尽管这个区域可能形状十分奇特。Farmer John 想要知道他铺设栅栏的路径是顺时针当按字符串表示的顺序沿着栅栏的路径行走时被围起的区域位于右侧还是逆时针被围起的区域位于左侧。【输入】输入的第一行包含一个整数N NN1 ≤ N ≤ 20 1\le N\le 201≤N≤20。以下N NN行每行包含一个长度不小于4 44且不超过100 100100的字符串表示一个栅栏的路径。【输出】对N NN条输入的栅栏路径的每一条输出一行为CWclockwise顺时针或CCWcounterclockwise逆时针。【输入样例】2 NESW WSSSEENWNEESSENNNNWWWS【输出样例】CW CCW【算法标签】《洛谷 P9945 Clockwise Fence》 #USACO# #O2优化# #2021#【代码详解】#includebits/stdc.husingnamespacestd;intn,ans;string s;intd[4][4]{// 定义二维数组E为0W为1S为2N为3每个单元格的值为方向变化后的角度变化{0,0,90,-90},{0,0,-90,90},{-90,90,0,0},{90,-90,0,0}};intmain(){cinn;// 输入nfor(inti1;in;i){// for循环遍历n次询问cins;// 输入字符串ssss[0];// 因为最后要回到原点所以在字符串最后加上起始字符ans0;// 每轮询问角度统计都要归零for(inti0;is.length()-1;i){// for循环遍历s.length()-2个字符因为要比较i与i1intx,y;// 定义x和y坐标if(s[i]E)x0;// 根据i的字符确定x坐标if(s[i]W)x1;if(s[i]S)x2;if(s[i]N)x3;if(s[i1]E)y0;// 根据i1的字符确定y坐标if(s[i1]W)y1;if(s[i1]S)y2;if(s[i1]N)y3;if(d[x][y])ansd[x][y];// 当掉转角度不为0时加上角度的变化。}if(ans360)coutCWendl;// 当为360度时说明是顺时针转回来elseif(ans-360)coutCCWendl;// 当为-360度时说明是逆时针转回来}return0;}【运行结果】2 NESW CW WSSSEENWNEESSENNNNWWWS CCW