本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2701 [USACO5.3] 巨大的牛棚 Big Barn【题目描述】FJ 有一个大小为n × n n\times nn×n的农场1 ≤ n ≤ 1000 1\le n\le 10001≤n≤1000他想要在他的农场上建造一座正方形大牛棚。他的农场中有t tt棵果树1 ≤ t ≤ 10000 1\le t\le100001≤t≤10000但他为了不破坏果树就想找一个空旷无树的地方修建牛棚。你的任务是计算并输出在他的农场中不需要砍树却能够修建的最大正方形牛棚的边长。当然牛棚的边必须和水平轴和垂直轴平行。考虑下面的农场.表示没有树的方格#表示有树的方格。0 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # . . . # . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 . . # . . . . . 7 . . . . . . . . 8 . . . . . . . .最大的牛棚是边长为5 55的可以建造在农场右下角的两个位置其中一个。【输入】第1 11行输入两个正整数n nn和t tt。第2 ∼ t 1 2\sim t12∼t1行输入两个正整数x , y ( 1 ≤ x , y ≤ n ) x,y\ (1\le x,y\le n)x,y(1≤x,y≤n)。【输出】只由一行组成约翰的牛棚的最大边长。【输入样例】8 3 2 2 2 6 6 3【输出样例】5【核心思想】问题分析给定n × n n \times nn×n的网格其中有t tt个位置有树障碍物求边与坐标轴平行的最大正方形空区域不含树的边长。这是一个二维 DP问题关键在于状态设计能递推地利用子问题的最优解。算法选择二维动态规划设d p [ i ] [ j ] dp[i][j]dp[i][j]表示以( i , j ) (i, j)(i,j)为右下角的最大无树正方形边长状态转移当前位置能扩展的正方形边长受限于上方、左方、左上方三个相邻位置的最小值关键步骤初始化读取n nn农场边长、t tt果树数量标记有树的位置g [ x ] [ y ] 1 g[x][y] 1g[x][y]1DP 数组初始化d p [ i ] [ j ] dp[i][j]dp[i][j]初始化为较大值边界处理a n s 0 ans 0ans0递推计算遍历i ii从1 11到n nnj jj从1 11到n nn若g [ i ] [ j ] 1 g[i][j] 1g[i][j]1有树d p [ i ] [ j ] 0 dp[i][j] 0dp[i][j]0若i 1 i 1i1或j 1 j 1j1边界d p [ i ] [ j ] 1 dp[i][j] 1dp[i][j]1无树位置否则状态转移d p [ i ] [ j ] min ⁡ ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j − 1 ] ) 1 dp[i][j] \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1dp[i][j]min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])1更新全局答案a n s max ⁡ ( a n s , d p [ i ] [ j ] ) ans \max(ans, dp[i][j])ansmax(ans,dp[i][j])输出答案a n s ansans时间/空间复杂度时间复杂度O ( n 2 ) O(n^2)O(n2)双层循环遍历整个网格空间复杂度O ( n 2 ) O(n^2)O(n2)d p dpdp二维数组和g gg标记数组二维 DP 的核心思想子结构重叠以( i , j ) (i, j)(i,j)为右下角的正方形其边长受限于三个方向上、左、左上能形成的最小正方形因为这三个方向必须同时满足无树才能扩展最小值约束d p [ i ] [ j ] dp[i][j]dp[i][j]取三者最小值加1 11因为只要任一方向存在树或边界限制当前正方形就无法突破该限制边界处理第一行和第一列的无树位置最大只能形成1 × 1 1 \times 11×1的正方形作为递推基础贪心最优性每个位置记录以它为右下角的最大正方形全局取最大即得答案适用于最大正方形/矩形、矩阵覆盖、障碍物规避类问题【算法标签】#普及 #线性DP-二维【代码详解】#includebits/stdc.husingnamespacestd;constintN1005;// 最大农场尺寸intn,t,ans;// n:农场边长, t:果树数量, ans:最大正方形牛棚边长intg[N][N];// g[i][j]:标记该位置是否有树1表示有树0表示无树intdp[N][N];// dp[i][j]:以(i,j)为右下角的最大无树正方形边长intmain(){cinnt;// 读入农场边长和果树数量for(inti1;it;i)// 读入每棵果树的位置{intx,y;cinxy;g[x][y]1;// 标记该位置有树}// 初始化dp数组为较大值用于边界处理memset(dp,0x3f,sizeof(dp));for(inti1;in;i)// 外层循环枚举行for(intj1;jn;j)// 内层循环枚举列{if(g[i][j])// 如果当前位置有树{dp[i][j]0;// 以该位置为右下角的正方形边长为0不能建牛棚}elseif(i1||j1)// 边界位置第一行或第一列dp[i][j]1;// 边界上无树的位置最大正方形边长为1else{// 状态转移以(i,j)为右下角的最大正方形边长// 取决于上方、左方、左上方三个位置的最小值加1// 原理如果这三个方向都能形成边长为k的正方形则当前可形成边长为k1的正方形dp[i][j]min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})1;}ansmax(ans,dp[i][j]);// 更新全局最大边长}coutansendl;// 输出最大正方形牛棚的边长return0;}【运行结果】8 3 2 2 2 6 6 3 5