企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：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

【核心思想】

1. 问题分析：给定N NN块草地和M MM头奶牛，每头奶牛喜欢两块草地，要求这两块草地种植不同草种。有4 44种草种可选，每块草地最多被3 33头奶牛喜欢。求字典序最小的合法种植方案。这是一个图着色/贪心构造问题，关键在于利用"每块草地最多3 33条关联边"的性质，保证贪心时总能找到可用颜色。

2. 算法选择：

   • 贪心着色：按草地编号1 11到N NN顺序，为每块草地选择最小的可用颜色（1 11到4 44）
   • 邻接矩阵存储：a 1 [ i ] [ j ] = 1 a1[i][j] = 1a1[i][j]=1表示草地i ii和j jj被同一头奶牛喜欢（不能同色）

3. 关键步骤：

   • 读取输入：N , M N, MN,M和M MM对草地( a , b ) (a, b)(a,b)
   • 建图：无向边，a 1 [ a ] [ b ] = a 1 [ b ] [ a ] = 1 a1[a][b] = a1[b][a] = 1a1[a][b]=a1[b][a]=1
   • 贪心着色（i ii从1 11到N NN）：
     • 尝试颜色k kk从1 11到4 44：
       • 检查所有邻接点j jj：若a 1 [ i ] [ j ] = 1 a1[i][j] = 1a1[i][j]=1且G [ j ] = k G[j] = kG[j]=k，则颜色k kk冲突
       • 若不存在冲突，选择k kk并跳出
     • G [ i ] = k G[i] = kG[i]=k
   • 输出：按顺序输出G [ 1 ] G[1]G[1]到G [ N ] G[N]G[N]

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ⋅ ( 4 ⋅ N + M ) ) = O ( N 2 ) O(N \cdot (4 \cdot N + M)) = O(N^2)O(N⋅(4⋅N+M))=O(N2)，对每个点尝试4 44种颜色，每种检查N NN个邻接点
   • 空间复杂度：O ( N 2 ) O(N^2)O(N2)，邻接矩阵

5. 贪心图着色的核心思想：

   • 四色定理的弱化应用：题目保证每点度数≤ 3 \le 3≤3，而可用颜色为4 44种，因此每个点最多有3 33个邻接点占用不同颜色，至少剩余1 11种颜色可用，贪心必然成功
   • 字典序最小保证：按编号顺序处理，每次选择最小可用颜色，天然保证最终方案是字典序最小的N NN位数
   • 邻接矩阵简化：N ≤ 100 N \le 100N≤100，邻接矩阵的O ( N 2 ) O(N^2)O(N2)空间可接受，且实现简单
   • 适用于"低度图着色 + 字典序最小解"类问题，核心是利用度数限制保证贪心可行性

【解题思路】

【算法标签】

#普及 #贪心

【代码详解】

// 尝试用过贪心算法，后发现只有3个测试点通过，其余均超时#include<bits/stdc++.h>usingnamespacestd;inta1[105][105],G[105];intn,m;// ifstream filein("revegetate.in");// ofstream fileout("revegetate.out");intmain(){cin>>n>>m;// 输入n和mfor(inti=1;i<=m;i++){// 遍历m条边inta,b;cin>>a>>b;// 输入边的端点a1[a][b]=1;// 因为是无向图，所以边的两个方向均置为1a1[b][a]=1;}for(inti=1;i<=n;i++){// 遍历n个顶点intk;// 定义颜色（没放到循环中是因为后面要通过G[i]来赋值）for(k=1;k<=4;k++){// 遍历4个颜色boolok=true;// 定义ok，用于判断边的两个端点颜色是否冲突for(intj=1;j<=n;j++){// 再遍历n个顶点if(a1[i][j]==1&&G[j]==k){// 如果i和j是一条边上的两个顶点，且j这个点的颜色为k（即已经有颜色了）ok=false;// 修改ok为false}}if(ok)break;// 没有一条边上的两个顶点颜色冲突，则退出循环，即颜色留在当前k上}G[i]=k;// 将这个k赋值给G[i]}for(inti=1;i<=n;i++){// 遍历n个顶点cout<<G[i];// 将每个顶点的颜色打印出来，中间不空格}cout<<endl;return0;}

【运行结果】

5 6 4 1 4 2 4 3 2 5 1 2 1 5 12133