2024年蓝桥杯真题C/C++/java组部分真题解析（一）

P10391 [蓝桥杯 2024 省 A] 零食采购

零食采购

节点个数为n，边的条数为n-1，且图是连通的（任意两个节点可达），得出结论，此图是树。

因为要求最短航路，很容易想到此题应该使用LCA算法，也就是求两个节点之间的最近公共祖先，这样就可以求出最短的路径：

如下图，节点6和节点4的最近公共祖先就是2。

暴力求法：常规的做法求节点m和n的最近公共祖先，就是让其一直回退，保存父节点。然后求交集中最靠下的那个节点就是最近公共祖先。这种做法的时间复杂度为O(N)。本题q（采购方案数）也就是给出的起点和终点数据量可能到10^{5量级，O(N}2)的时间复杂度肯定过不了，我们需要优化。

LCA算法–每次查询消耗logN

基本思路：

1. 先预处理出每一个节点跳跃2^i的祖先，我们创建二维数组parent：

   

预处理时记录每个节点的深度。

每个节点最多计算17次就够了：

对于节点a来说，有：
$$\begin{gathered} parent[a][i]:节点a向上跳跃了2^i次。我们是从根节点开始处理的，a之前的节点肯定已经处理完了。又2^i=2^{i-1}+2^{i-1}。 \\ 所以parent[a][i]=parent[parent[a][i-1]][i-1]（a先向上跳2^{i-1}次得到祖先节点m,祖先m又跳跃2^{i-1}次） \\ 一共跳跃2^{i-1}+2^{i-1}=2^i次 \end{gathered}$$

2. 预处理完成后，我们就可以来求节点m、n的最近公共祖先了：

   • 先将节点m、n的高度调到同一高度。
   • 然后让自顶向下遍历parent[m]、parent[n]，也就是先跳2^17步，设此时遍历的祖先为fm、fn。
     • fm =fn，是m、n的祖先，但不一定是最近的公共祖先，此时不能改变m、n，因为不能超过最近公共祖先的深度。
     • fm != fn，说明已经来到最近公共祖先下面的深度的节点了，调整m、n为祖先fm、fn。
   • 最终遍历完，m、n指向最近公共祖先。

   

树上差分

找到最近公共节点了，如何知道这条路径上的零食的种树呢？遍历是不够理性的，因为会TLE,O(N^2)的时间复杂度无法通过，我们使用空间换时间，进行树上差分：
$$\begin{gathered} 设cnt[i][j]:表示从根节点到i零食j的数量。则从起点m到终点n是否有零食j呢？假设此时已经求出最近公共祖先为p,则m->n的 \\ 最短路径上零食j的数量可以表示为: \\ cnt[m][j]+cnt[n][j]-2\ast cnt[p][j]+snack[p]==j?1:0 \end{gathered}$$
如果这个数量大于0，就代表条路径上有j类零食，结果增加1，零食的总类数 <= 20，遍历20次即可。

完整代码

#include <bits/stdc++.h>

using namespace std;

#define MAX_SNACK 20        // 最大零食种类数
#define MAX_NUM 100007      // 最大节点数
#define K 17                // 预处理祖先的最大深度（log2(MAX_NUM)）

int n, q;                         // n: 星球数量，q: 查询次数
int snack[MAX_NUM];               // snack[i]: 第 i 颗星球上的零食种类
int parent[MAX_NUM][K+2];         // parent[i][j]: 第 i 颗星球的 2^j 祖先节点
int cnt[MAX_NUM][MAX_SNACK+2];    // cnt[i][j]: 从根节点到第 i 颗星球的路径上零食种类 j 的出现次数
int dep[MAX_NUM];                 // dep[i]: 第 i 颗星球的深度

vector<int> g[MAX_NUM];           // 存储图的邻接表表示，g[i] 存储与第 i 颗星球相连的星球

// 深度优先遍历，计算每个节点的深度、2^i 祖先、零食种类计数
void dfs1(int cur, int pre)
{
    dep[cur] = dep[pre] + 1;                // 当前节点的深度是父节点深度加 1
    // 继承父节点的零食计数
    for (int s = 1; s <= MAX_SNACK; ++s)
        cnt[cur][s] = cnt[pre][s];          // 将父节点的零食计数复制到当前节点
    
    cnt[cur][snack[cur]]++;                 // 当前节点增加自己的零食种类计数
    
    parent[cur][0] = pre;                   // 当前节点的 2^0 祖先是父节点
    // 计算当前节点的 2^i 祖先
    for (int i = 1; i <= K; ++i)//注意数组别越界
        parent[cur][i] = parent[parent[cur][i - 1]][i - 1];  // 利用动态规划填充 2^i 祖先

    // 遍历当前节点的所有邻居节点
    for (auto next : g[cur])
    {
        if (next != pre)                    // 避免回到父节点
            dfs1(next, cur);                // 递归深度优先遍历
    }
}

// 计算节点 n 和 m 的最近公共祖先（LCA）
int lca(int n, int m)
{
    if (dep[n] < dep[m]) swap(n, m); // 保证 n 总是深度较大的节点
    
    // 让 n 和 m 在同一深度
    for (int i = K; i >= 0; --i)      // 从大的 2^i 开始处理
    {
        if (dep[parent[n][i]] >= dep[m]) 
            n = parent[n][i];        
    }
    
    if (n == m) 
        return n;                      // 如果 n 和 m 已经相同，返回当前节点
    
    // 从上到下寻找最近公共祖先
    for (int i = K; i >= 0; --i)
    {
        int fm = parent[m][i], fn = parent[n][i];
        if (fm != fn)                  // 如果 n 和 m 的 2^i 祖先不同
        {
            m = fm;
            n = fn;                    // 同时提升 n 和 m
        }
    }
    
    return parent[n][0];               // 返回它们的父节点，即为最近公共祖先
}

int main()
{
    cin >> n >> q;                    // 输入星球数量 n 和查询次数 q
    for (int i = 1; i <= n; ++i)
        cin >> snack[i];               // 输入每颗星球上的零食种类

    // 构建图，存储每颗星球之间的连接关系
    for (int i = 0; i < n - 1; ++i)
    {
        int v, u;
        cin >> v >> u;
        g[v].push_back(u);
        g[u].push_back(v);              // 无向图，两个方向都加入
    }
    
    dfs1(1, 1);                        // 从根节点（1号星球）开始，进行深度优先遍历，计算深度、父节点和零食计数

    // 处理每个查询
    while (q--)
    {
        int n, m;                      // 查询的两个节点
        cin >> n >> m;
        int p = lca(n, m);             // 获取节点 n 和 m 的最近公共祖先
        int ans = 0;                   // 零食种类计数的答案
        // 遍历所有零食种类，计算从节点 n 和 m 路径上出现的零食种类
        for (int i = 1; i <= MAX_SNACK; ++i)
        {
            int snackp = snack[p] == i ? 1 : 0;  // 如果最近公共祖先有零食种类 i，则 snackp 为 1，否则为 0
            // 检查节点 n 和 m 路径上零食种类 i 的总计数是否大于 0
            if ((cnt[n][i] + cnt[m][i] - 2 * cnt[p][i] + snackp) > 0)
                ans++;                // 如果种类 i 出现，答案加 1
        }
        cout << ans << endl;           // 输出该查询的结果
    }
}

P10387 [蓝桥杯 2024 省 A] 训练士兵

训练士兵

求总消耗。

每一次我们其实都面临这样一个问题：当前所有还为完成训练的士兵全部训练一次的消耗金币总量sum和组团训练一次的消耗S哪一个更少的问题。考虑贪心来做。

具体思路:

1. 需要先按照训练次数排序，因为假设此时团购更优惠，我们需要考虑这样的一个问题：
   • 本次可以团购几次?（本次团购更优惠，那么意味着此时剩余士兵最小的训练次数没有耗尽完之前，一直都是团购最优惠），此时的最大团购次数由最小训练次数的士兵决定（木桶效应）。我们如果去遍历找最小就还需要N次，太慢了。
2. 排序后按照训练次数从小到大遍历，团购之后，每一个士兵的训练次数都需要更新，但是遍历一遍是没必要的，我们记录已经团购的次数，下一次遍历到该士兵时，它的真实剩余训练次数就是当前训练次数减去已经团购的次数。
3. 如果团购不再更优惠，当前士兵的训练消耗就是p*c（每一次训练的消耗*剩余训练次数）。

代码参考：

#include <bits/stdc++.h>

using namespace std;

// 比较函数，返回值应为 bool
bool compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second; //升序
}

typedef long long LL;
int main()
{
		// 关闭输入输出同步
    ios::sync_with_stdio(false);

    // 禁止流的同步，使得输出流更高效
    cin.tie(0);  // 取消 cin 和 cout 的绑定
	LL n,S;
	LL sum = 0;
	cin >> n >> S;
    
	vector<pair<int,int>> _q;
	for(int i = 0;i < n;++i)
	{
		pair<int,int> p;
		cin >> p.first >> p.second;
		sum += p.first;
		_q.push_back(p);
	}
	LL ans = 0;
	LL subcount = 0;//团购的次数
    sort(_q.begin(),_q.end(),compare);//按照次数升序排序，优先处理训练次数少的，木桶效应，每次能团购几次呢？由最小的决定
    for(int i = 0;i < _q.size();++i)
    {
    	
    	if(subcount >= _q[i].second)
		{
			sum -= _q[i].first;
			continue;
		}
    	if(sum > S)//团购更优惠此时
    	{
    		_q[i].second -= subcount;//更新真实的剩余训练次数
    		ans += S*_q[i].second;
    		subcount += _q[i].second;//加上此时可以团购的最大次数
    		sum -= _q[i].first;//更新sum
		}
		else//团购不吃香了
		{
			ans += _q[i].first*(_q[i].second-subcount);//必须把之前团购的次数减掉
			sum -= _q[i].first;//更新sum,其实此时更新也没必要了
		}
	}
	cout << ans << endl;
	return 0;
}

P10389 [蓝桥杯 2024 省 A] 成绩统计

成绩统计

二分算法

• 1. 定义l = 0，r = n-1,mid是l和r的中点。
• 2. 如果mid满足[0,mid]下标中存在k个数，这k个数的方差小于K，则让r = mid，因为右边界可能可以缩的更小。题目求最小的那个满足条件的右边界。
• 3. 如果mid不满足题意，则让l = mid+1，因为mid及其之前的值一定不会成为我们最终的答案，我们的答案肯定在mid的右侧。

接下来要面临的问题是如何快速的判断区间[0,mid]中是否有满足条件的k个值，我们这样来考虑：

• 1. 先将区间排序。排序的时间复杂度是N*logN。
• 2. 然后滑动窗口，窗口大小为k，在所有的窗口中找到一个符合条件的长度为k的数组即可。
• 3. 排序在这种问题中的应用，其实可以理解为一种贪心策略。通过先将区间排序，我们能够确保在滑动窗口中选择的是最优的候选子集，使得在固定窗口大小 k 时，后续检查的子数组有更高的机会满足方差小于 T 的条件。排序能够把数值较小的元素聚集在一起，从而减少数值之间的差异，增加方差小于 T 的可能性。

如何快速的计算方差成为我们要解决的另外一个问题？：难道每次都要遍历一遍滑动窗口中的元素吗？这样算法最坏时间复杂度到了O(N^2)，肯定会TLE，我们可以做如下公式推导：
$$\begin{gathered} {\sigma }^2=\frac{1}{k}\sum _{i=1}^k(v_i-\bar{v}{)}^2,我们将公式展开: \\ =\frac{1}{k}\sum _{i=1}^k(v_i^2-2\ast v_i\ast \bar{v}+{\bar{v}}^2) \\ =\frac{1}{k}(\sum _{i=1}^k{v}_i^2-2\ast \bar{v}\sum _{i=1}^k{v}_i+k\ast {\bar{v}}^2) \end{gathered}$$

我们用sum表示长度为k的数组的和，用square_sum表示平方和，只要在滑动窗口更新时不断动态维护它们，我们就可以以O(1)的时间复杂度求出某一段长为k的子数组的方差，这就是空间换时间。

注意sum、square_sum是可能溢出的，如果使用int：
$$\begin{gathered} 题目中有a_i<=n，而n,k<=10^5， \\ sum<=a_i\ast n=10^{10},而10^{10}>2^{31}-1，所以可能会溢出，但如果开longlong则没有溢出的风险 \\ 因为sum<=10^{10}<2^{63}-1(符号位有一位) \\ 开longlongsquare\_sum也不会溢出，因为{a_i}^2<=10^{10},而n<=10^5，所以square\_sum<=10^{15}<2^{63}-1 \end{gathered}$$

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;  // 定义最大输入大小
typedef long long LL;  // 使用长整型 LL 来避免溢出
LL n, k, T;  // n 为总元素个数，k 为选择的元素个数，T 为阈值
vector<int> arr(N);  // 存储元素的数组
LL sqrt_sum;  // 保存平方和
LL sum;  // 保存和

// 计算给定一组数的方差
LL Calvariance(LL sum, LL sqrt_sum) {
    // 根据方差公式：(sum_sq - 2 * average * sum + k * average^2) / k
    // average = sum / k
    return (sqrt_sum - 2.0* (sum / k) * sum +1.0*k * (sum / k) * (sum / k)) / k;
}

// 检查前 x 个元素中是否存在任意 k 个元素的方差小于K
bool check(int x) {
    // 先对前 x 个元素排序，便于之后的滑动窗口操作
    vector<int> a(arr.begin(), arr.begin() + x + 1);  // 取出前 x + 1 个元素
    sort(a.begin(), a.end());  // 对这些元素进行排序
    a.resize(x + 5);  // 为了防止越界，额外增加一点空间

    // 使用滑动窗口来检查每一段连续的 k 个成绩的方差
    for (int start = 0, end = 0; end <= x;) {
        // 维护 sum 和 sqrt_sum
        sum += a[end];  // 更新当前窗口的元素和
        sqrt_sum += 1LL * a[end] * a[end];  // 更新当前窗口的平方和
        
        // 如果当前窗口大小为 k，检查方差是否满足条件
        if (end - start + 1 == k) {
            if (Calvariance(sum, sqrt_sum) < T)  // 如果方差小于 T，则返回 true
                return true;
            
            // 更新滑动窗口：移除窗口的左边元素
            sum -= a[start];  // 从 sum 中减去左边的元素
            sqrt_sum -= 1LL * a[start] * a[start];  // 从 sqrt_sum 中减去左边元素的平方
            
            start++;  // 窗口左边界右移
        }
        end++;  // 窗口右边界右移
    }
    return false;  // 没有找到满足条件的窗口
}

// 使用二分法查找最小的 x，使得前 x 个元素中存在方差小于 T 的连续 k 个元素
int binary() {
    int l = k - 1, r = n - 1;  // 二分法的初始范围，l 为 k-1，r 为 n-1
    bool flag = false;  // 标记是否找到解
    
    // 开始二分查找
    while (l < r) {
        int mid = (l + r) >> 1;  // 计算中间位置
        if (check(mid)) {  // 如果前 mid 个元素存在方差小于 T 的连续 k 个元素
            flag = true;  // 标记找到解
            r = mid;  // 收缩右边界
        } else {
            l = mid + 1;  // 否则，收缩左边界
        }
        sum = 0;  // 每次调用 check 后，重置 sum 和 sqrt_sum
        sqrt_sum = 0;
    }
    return flag ? r + 1 : -1;  // 如果找到解，则返回 r+1；否则返回 -1
}

int main() {
    cin >> n >> k >> T;  // 输入总元素数 n、选择的元素数 k 和方差阈值 T
    
    // 输入数组 arr
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    
    // 调用二分法求解，并输出结果
    int ans = binary();
    cout << ans << endl;
    return 0;
}

时间复杂度

$$O(N\ast logN\ast logN)$$

P11045 [蓝桥杯 2024 省 Java B] 最优分组

最优分组

题解

此题涉及一些概率论的简单期望推导，题目让我们求测试剂的消耗数目的期望值的最小值，我们可以先考虑每一组的消耗数目的期望。

已知条件：有n个宠物，这n个宠物被平均分成k组，每个宠物患病的概率为p。
$$\begin{gathered} 每组消耗的试剂数只有两种情况：1、k+1 \\ 1对应一个宠物都没得病，概率为p_1 \\ k+1对应至少有一个宠物得病了,概率为p_2 \\ {p}_1=(1-p{)}^k \\ {p}_2=1-(1-p{)}^k \\ 每组检测数量的期望值E(k)=p_1\ast 1+p_2\ast (k+1) \\ 所有的宠物检测数量的期望值为E(x)=\frac{n}{k}\ast E(k)=\frac{n}{k}\ast ((1-p{)}^k+(k+1)\ast (1-(1-p{)}^k) \end{gathered}$$
我们依次枚举k，维护期望最小时最小的那个k即可。

注意n必须要可以整除k，题目说了是平均分组。

特殊情况

如果期望值比N还大，k应该为1，因为题目说了，当k为1时，只会检测一次（不会重复检测），此时期望值为N。

代码参考

#include <bits/stdc++.h>

using namespace std;

typedef  double D;

const D EPS = 1e-6;//精度容忍度

int main()
{
	int N;
	D p;
	cin >> N >> p;
	
	D Ex = N;
	int min_k = 1;
	for(int k = 2;k <= N;++k)
	{
	    if(N % k == 0)
	    {
		  D curEx = 1.0*N/k*(pow(1.0-p,k)+(k+1)*(1.0-pow(1.0-p,k)));
		  if( (Ex-curEx) > EPS )//Ex > curEx 
		  {
		
			min_k = k;
			Ex = curEx;
		   }
	    }
	}
	
	cout << min_k << endl;
	return 0;
}

P11047 [蓝桥杯 2024 省 Java B] LITS 游戏

LITS游戏

题解

（据说是java B组去年最难的一道题）,虽然只考察了简单的dfs和回溯，但是这题的代码可谓是相当难敲，稍不注意可能就敲错了，所以在代码编写时应该细心一点，下面是我的思路：

1. 四种图案都是可以旋转的，所以会有不同的情况，我们可以将其下标相对于起点的增值一一列出来，为了不重不漏，约定每个图案的最上面最左边的那个方块为起点，比如我们以图案1为例：

   

2. 然后就可以开始dfs了，注意dfs时，如果找到一个图案，需要记录已经这个图案使用过的格子，并且下一次寻找不用从头开始，从当前下标的下一个位置作为起点往下找就行了，因为前面的情况我们已经考虑过了，不用重复考虑。

3. 另外，当找到一个图案，并且往下dfs之后，发现还是无法找到符合题意的四个图案（不能有重叠），我们需要恢复used数组（记录已经使用过的方格的数组）到之前的状态，也就是把这些位置的下标置为0即可（0表示未使用），我们在check函数（判断以当前下标为起点能否找到还未找到的图案的函数）中记录使用过的下标即可，不用保存完整的used数组，这样很耗时间，容易超时。

4. 最后，因为这题是多组测试用例，T是大于1的，所以如果是全局变量，在一次遍历dfs后，不要忘了将其重置状态。

参考代码

c++：

#include <bits/stdc++.h>
using namespace std;

const int n = 52;
int T, N;
int a[n][n];
int cnt[4];  // 记录当前找到的四种图案的状态
// 定义LITS四种形状的旋转（4个方向，每个方向上有4个格子）
int idx[4][4][4][2] = {
      {
            {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
            {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
            {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
            {{0, 0}, {1, 0}, {1, -1}, {1, -2}}
        },
        {
            {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
            {{0, 0}, {0, 1}, {0, 2}, {0, 3}}
        },
        {
            {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
            {{0, 0}, {1, 0}, {1, -1}, {2, 0}},
            {{0, 0}, {1, 0}, {1, -1}, {1, 1}},
            {{0, 0}, {1, 0}, {1, 1}, {2, 0}}
        },
        {
            {{0, 0}, {0, 1}, {1, 0}, {1, -1}},
            {{0, 0}, {1, 0}, {1, 1}, {2, 1}}
        }
    };


// 判断当前方块能否放置
bool check(int idx_, int x, int y, vector<vector<int>>& used, vector<pair<int, int>>& occupy) {
    int i_max = 4;  // 默认最多有四种旋转
    if (idx_ == 1 || idx_ == 3) {
        i_max = 2;  // 这两种形状只有两种旋转
    }

    // 遍历每种旋转
    for (int i = 0; i < i_max; ++i) {
        bool flag = true;
        for (int j = 0; j < 4; ++j) {
            int newx = idx[idx_][i][j][0] + x;
            int newy = idx[idx_][i][j][1] + y;
            if (newx < 0 || newy < 0 || newx >= N || newy >= N || !a[newx][newy] || used[newx][newy]) {
                flag = false;  // 如果位置不合法，标记为不可放置
                break;
            }
        }
        if (flag) {
            // 如果当前位置可以放置，则将占用的格子标记为已用，并记录这些格子
            for (int j = 0; j < 4; ++j) {
                int newx = idx[idx_][i][j][0] + x;
                int newy = idx[idx_][i][j][1] + y;
                occupy.push_back({newx, newy});
                used[newx][newy] = 1;  // 标记这些格子为已使用
            }
            return true;
        }
    }
    return false;
}

// 判断是否已经找到了所有四个方块
bool is_full() {
    return cnt[0] && cnt[1] && cnt[2] && cnt[3];  // 如果四种方块都已放置，则返回true
}

// 深度优先搜索
bool dfs(int x, int y, vector<vector<int>>& used) {
    // 遍历从当前位置开始的每个格子
    for (int i = x, j = y; i < N;) {
        if (!a[i][j] || used[i][j]) {
            j++;
            j %= N;  // 如果当前格子为空或者已经被占用，跳到下一个格子
            if (j == 0) i++;  // 如果列越界，则跳到下一行
            continue;
        }

        if (is_full()) {
            return true;  // 如果已经找到了所有方块，直接返回true
        }

        // 尝试放置每种图案
        for (int k = 0; k < 4; ++k) {
            vector<pair<int, int>> occupy;  // 存储当前图案占用的格子
            if (!cnt[k] && check(k, i, j, used, occupy)) {
                cnt[k] = true;  // 标记当前图案已经被放置
                int newy = (y + 1) % N;  // 移动到下一个格子
                int newx = x;
                if (newy == 0) newx++;  // 如果列越界，则跳到下一行
                if (dfs(newx, newy, used)) {
                    return true;  // 如果找到解，返回true
                }
                cnt[k] = false;  // 如果递归未找到解，撤销当前图案的放置
            }

            // 恢复当前占用的格子
            for (auto& [i_, j_] : occupy) {
                used[i_][j_] = 0;  // 恢复格子为未使用状态
            }
        }

        j++;
        j %= N;
        if (j == 0) i++;  // 继续遍历下一个格子
    }
    return false;  // 如果没有找到解，返回false
}

int main() {
    ios::sync_with_stdio(false);  // 关闭同步，提升输入输出效率
    cin.tie(0);  // 解除 cin 和 cout 的绑定

    cin >> T;  // 输入测试用例数量
    while (T--) {
        cin >> N;  // 输入网格大小

        memset(a, 0, sizeof(a));//重置一下
        memset(cnt, 0, sizeof(cnt));  // 初始化 cnt 数组
        vector<vector<int>> used(N, vector<int>(N, 0));  // 创建 used 数组，记录哪些格子被占用

        // 读取网格数据
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cin >> a[i][j];  // 输入每个格子的值（是否为空）
            }
        }

        // 调用深度优先搜索，尝试从 (0, 0) 开始放置图案
        if (dfs(0, 0, used)) {
            cout << "Yes" << endl;  // 如果找到解，输出"Yes"
        } else {
            cout << "No" << endl;  // 如果没有解，输出"No"
        }
    }

    return 0;
}

java：

import java.util.*;

public class Main {
    static final int n = 52;
    static int T, N;
    static int[][] a = new int[n][n];
    static boolean[] cnt = new boolean[4];  // 记录当前找到的四种图案的状态
    
    // 定义LITS四种形状的旋转（4个方向，每个方向上有4个格子）
    static int[][][][] idx = {
        {
            {{0, 0}, {1, 0}, {2, 0}, {2, 1}},
            {{0, 0}, {1, 0}, {0, 1}, {0, 2}},
            {{0, 0}, {0, 1}, {1, 1}, {2, 1}},
            {{0, 0}, {1, 0}, {1, -1}, {1, -2}}
        },
        {
            {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
            {{0, 0}, {0, 1}, {0, 2}, {0, 3}}
        },
        {
            {{0, 0}, {0, 1}, {0, 2}, {1, 1}},
            {{0, 0}, {1, 0}, {1, -1}, {2, 0}},
            {{0, 0}, {1, 0}, {1, -1}, {1, 1}},
            {{0, 0}, {1, 0}, {1, 1}, {2, 0}}
        },
        {
            {{0, 0}, {0, 1}, {1, 0}, {1, -1}},
            {{0, 0}, {1, 0}, {1, 1}, {2, 1}}
        }
    };

    // 判断当前方块能否放置
    static boolean check(int idx_, int x, int y, boolean[][] used, List<int[]> occupy) {
        int i_max = 4;  // 默认最多有四种旋转
        if (idx_ == 1 || idx_ == 3) {
            i_max = 2;  // 这两种形状只有两种旋转
        }

        // 遍历每种旋转
        for (int i = 0; i < i_max; i++) {
            boolean flag = true;
            for (int j = 0; j < 4; j++) {
                int newx = idx[idx_][i][j][0] + x;
                int newy = idx[idx_][i][j][1] + y;
                if (newx < 0 || newy < 0 || newx >= N || newy >= N || a[newx][newy] == 0 || used[newx][newy]) {
                    flag = false;  // 如果位置不合法，标记为不可放置
                    break;
                }
            }
            if (flag) {
                // 如果当前位置可以放置，则将占用的格子标记为已用，并记录这些格子
                for (int j = 0; j < 4; j++) {
                    int newx = idx[idx_][i][j][0] + x;
                    int newy = idx[idx_][i][j][1] + y;
                    occupy.add(new int[]{newx, newy});
                    used[newx][newy] = true;  // 标记这些格子为已使用
                }
                return true;
            }
        }
        return false;
    }

    // 判断是否已经找到了所有四个方块
    static boolean is_full() {
        return cnt[0] && cnt[1] && cnt[2] && cnt[3];  // 如果四种方块都已放置，则返回true
    }

    // 深度优先搜索
    static boolean dfs(int x, int y, boolean[][] used) {
        // 遍历从当前位置开始的每个格子
        for (int i = x, j = y; i < N;) {
            if (a[i][j] == 0 || used[i][j]) {
                j++;
                j %= N;  // 如果当前格子为空或者已经被占用，跳到下一个格子
                if (j == 0) i++;  // 如果列越界，则跳到下一行
                continue;
            }

            if (is_full()) {
                return true;  // 如果已经找到了所有方块，直接返回true
            }

            // 尝试放置每种图案
            for (int k = 0; k < 4; k++) {
                List<int[]> occupy = new ArrayList<>();  // 存储当前图案占用的格子
                if (!cnt[k] && check(k, i, j, used, occupy)) {
                    cnt[k] = true;  // 标记当前图案已经被放置
                    int newy = (y + 1) % N;  // 移动到下一个格子
                    int newx = x;
                    if (newy == 0) newx++;  // 如果列越界，则跳到下一行
                    if (dfs(newx, newy, used)) {
                        return true;  // 如果找到解，返回true
                    }
                    cnt[k] = false;  // 如果递归未找到解，撤销当前图案的放置
                }

                // 恢复当前占用的格子
                for (int[] pos : occupy) {
                    used[pos[0]][pos[1]] = false;  // 恢复格子为未使用状态
                }
            }

            j++;
            j %= N;
            if (j == 0) i++;  // 继续遍历下一个格子
        }
        return false;  // 如果没有找到解，返回false
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        T = sc.nextInt();  // 输入测试用例数量
        while (T-- > 0) {
            N = sc.nextInt();  // 输入网格大小

            // 初始化数组
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    a[i][j] = sc.nextInt();  // 输入每个格子的值（是否为空）
                }
            }

            Arrays.fill(cnt, false);  // 初始化 cnt 数组
            boolean[][] used = new boolean[N][N];  // 创建 used 数组，记录哪些格子被占用

            // 调用深度优先搜索，尝试从 (0, 0) 开始放置图案
            if (dfs(0, 0, used)) {
                System.out.println("Yes");  // 如果找到解，输出"Yes"
            } else {
                System.out.println("No");  // 如果没有解，输出"No"
            }
        }

        sc.close();
    }
}

P11044 [蓝桥杯 2024 省 Java B] 食堂

P11044 [蓝桥杯 2024 省 Java B] 食堂

贪心实现

此题求最大的能够容纳的就餐人数，要求每个宿舍的人都在一个桌，可以这样来贪心

1. 优先消耗6人桌，减少资源分配的难度。
2. 两种桌子可以容纳的情况：6 = 3+3，6 = 4+2，6=2+2+2，6 = 2+3，6=4（2+2），6=3，4 = 4，4 = 2+2，4 = 3，4 = 2。
3. 对于6人桌，肯定要先考虑坐满人的组合，这样能最小化资源浪费，桌子的总数固定，意味着能坐的人是固定的，我们要做的就是最小化资源浪费的情况。：
   • 先枚举3+3的，因为3+3组合在6人桌不会造成浪费，如果进入4人桌，肯定会浪费（4+2，2+2+2进入四人桌不会浪费）。
   • 4+2组合和2+2+2组合都一样，它们的顺序无所谓，因为它们进入4人桌都不会浪费。
   • 最后考虑6人桌浪费的情况（寝室数有限了）：
     • 还剩下6人桌，但是只有2+3或者4或者3或者2组合了。
     • 优先让人数多的组合先使用桌子（2+3、4（2+2）、3、2）。
4. 对于4人桌，还是一个原则最大化桌子能坐人的数量
   • 4（2+2）组合先坐。
   • 然后是单3。
   • 最后是2。

参考代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while(q--) {
        int a2, a3, a4, b4, b6;
        cin >> a2 >> a3 >> a4 >> b4 >> b6;
        int res = 0;

        // 优先使用6人桌
        // 处理3+3组合
        int pair_3_3 = min(a3/2,b6);
        res += pair_3_3 * 6;
        a3 -= pair_3_3 * 2;
        b6 -= pair_3_3;

        // 处理4+2
        int pair_4_2 = min(a2, min(a4, b6));
        res += pair_4_2 * 6;
        a2 -= pair_4_2;
        a4 -= pair_4_2;
        b6 -= pair_4_2;

        // 处理2+2+2
        int pair_2_2_2 = min(a2 / 3, b6);
        res += pair_2_2_2 * 6;
        a2 -= pair_2_2_2 * 3;
        b6 -= pair_2_2_2;

        // 处理3+2
        int pair_3_2 = min(a2, min(a3, b6));
        res += pair_3_2 * 5;
        a2 -= pair_3_2;
        a3 -= pair_3_2;
        b6 -= pair_3_2;

        // 处理4
        int pair_4 = min(a4, b6);
        res += pair_4 * 4;
        a4 -= pair_4;
        b6 -= pair_4;

        // 处理2+2
        int pair_2_2 = min(a2 / 2, b6);
        res += pair_2_2 * 4;
        a2 -= pair_2_2 * 2;
        b6 -= pair_2_2;

        // 处理单个3
        int pair_3 = min(a3, b6);
        res += pair_3 * 3;
        a3 -= pair_3;
        b6 -= pair_3;

        // 处理单个2
        int pair_2 = min(a2, b6);
        res += pair_2 * 2;
        a2 -= pair_2;
        b6 -= pair_2;

        // 处理4人桌
        // 处理4
        int pair_4_b4 = min(a4, b4);
        res += pair_4_b4 * 4;
        a4 -= pair_4_b4;
        b4 -= pair_4_b4;

        // 处理2+2
        int pair_2_2_b4 = min(a2 / 2, b4);
        res += pair_2_2_b4 * 4;
        a2 -= pair_2_2_b4 * 2;
        b4 -= pair_2_2_b4;

        // 处理单个3
        int pair_3_b4 = min(a3, b4);
        res += pair_3_b4 * 3;
        a3 -= pair_3_b4;
        b4 -= pair_3_b4;

        // 处理单个2
        int pair_2_b4 = min(a2, b4);
        res += pair_2_b4 * 2;
        a2 -= pair_2_b4;
        b4 -= pair_2_b4;

        cout << res << endl;
    }
    return 0;
}