01 班级活动

题目来源：蓝桥杯真题
做题时间：250201
解题用时：1h44min

![[Pasted image 20250201191646.png]]

题目标签： 2023，思维，国赛

题意整理：

输入n个整数，每个整数的范围是1~n，现修改整数的值，使其两两相等（n为偶数，>=2个数相等的情况不存在），问最少修改次数。[[map的用法]]

解题思路：

统计每个数出现的次数，若次数为1，则可以与同为1 的另一个数相互配对，或者与>=2的数相互配对，要分别统计count1和count3（>=2总量）

AC代码：

#include <iostream>
#include <map>
using namespace std;
int main()
{
  int n;
  int count=0;
  int count1=0;
  int count3=0;
  cin>>n;
  map<int,int>myMap;
  for(int i=0;i<n;i++)
  {
    int temp;
    cin>>temp;
    myMap[temp]++;
  }
  for(int i=1;i<=n;i++)
  {
    if(myMap[i]<2){
      if(myMap[i]==1)count1++;
    }
    else{
      count3+=myMap[i]-2;
    }
  }
  if(count1<=count3)count=count3;
  else count=(count1+count3)/2;
  cout<<count;
  return 0;
}

02 好数

解题日期：250201
解题用时：66min
题目来源：蓝桥杯省赛真题
题目难度：简单
题目标签：暴力，枚举，省赛，2024

题意整理

如图所示，比较清楚了。
![[Pasted image 20250201203855.png]]

解题思路

数据范围不是很大，可以直接暴力枚举。
（原先往错误的方向思考了很久，一直想要通过构造的方法来解决，复杂性较高，需要额外的约束和管理）
暴力枚举写了大概不到十分钟，加上调试的时间是14min。

AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  int countsum=0;
  for(int i=1;i<=N;i++)
  {
    int n=i;
    int temp;
    int count=0;
    int flag=0;
    while(n>0)
    {
      count++;
      temp=n%10;
      n/=10;
      int a=count%2;
      int b=temp%2;
      if(a!=b){
        flag=1;
        break;
      }
    }
    if(flag!=0){
      continue;
    }
    else{
      countsum++;
    }
  }
  cout<<countsum;
  return 0;
}

03 回文字符串

解题日期：250202
解题用时：55min
题目来源：蓝桥杯省赛真题
题目难度：简单
题目标签：字符串hash，前缀和，省赛，2024

题意整理

![[Pasted image 20250202104542.png]]

解题思路

逆向思考，增加即是删，但是不是全部删除再判断是否是回文，有漏洞bablab，要删除一个判断一个

AC代码

#include <iostream>
#include <string>
using namespace std;

// 判断字符串是否是回文
bool isPalindrome(string s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

void solve(){
  string s;
  cin>>s;
  if(isPalindrome(s))
  {
    cout<<"Yes"<<endl;
    return;
  }
  while((!s.empty())&&(s.back()=='l'||s.back()=='q'||s.back()=='b'))
  {
    s.pop_back();
    if(isPalindrome(s)){
      cout<<"Yes"<<endl;
      return;
    }
  }
  cout<<"No"<<endl;
  return;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--){
    solve();
    }
    return 0;
}

04 纯职业小组

解题日期：250203
解题用时：-min
题目来源：蓝桥杯真题省赛
题目难度：困难
题目标签：思维，省赛，2024

题意整理

![[Pasted image 20250203194701.png]]

AC代码

#include <bits/stdc++.h>//题意就是说找一些人,且刚好能凑成k队(所以需要考虑最坏的情况,就是都找一些不能凑成一队的人)(题意表述不太清晰)
#define int long long//思路:先拿走少于3的队伍的人数
using namespace std;//再在大于3个人的队伍中拿走尽可能多的人数,剩下的人数再存起来;比如有两个队(6,4),如果需要拿走两个队,就在6中拿走5个人,4中拿走2个人,意思就是尽可能拿走一个队伍再余2个人
const int N=2e5+10;//最后如果队伍数还凑不够的话,再从剩下的人数中拿,每拿一个人队伍数就会加一
int a[N];
void solve()
{
  int n,k,m=0;
  cin>>n>>k;
  map<int,int>mp,book;//因为x最大1e9,所以不能用数组存
  for(int i=1;i<=n;i++)
  {
    int x,y;
    cin>>x>>y;
    if(!book[x])//防止职业重复存
    {
      book[x]=1;
      a[++m]=x;//用数组记录下职业
    }
    mp[x]+=y;
  }
  int cnt=0;
  for(int i=1;i<=m;i++)
  {
    if(mp[a[i]]>=3)
    cnt+=mp[a[i]]/3;
  }
  if(cnt<k)//算算够不够凑成k队
  {
    cout<<-1<<'\n';
    return;
  }
  priority_queue<int,vector<int>>q,qq,qqq;//从大到小排序
  for(int i=1;i<=m;i++)
  {
    q.push(mp[a[i]]);
  }
  int ans=0;
  while(q.size())
  {
    auto x=q.top();
    q.pop();
    if(x>=3)//将比3大的存起来进行计算
    qq.push(x);
    else
    ans+=x;//比3小的直接加起来,因为他们不可能组成一个队(题意说3个相同的职业才能组成一个队)
  }
  while(qq.size())
  {
    auto x=qq.top();
    qq.pop();
    int kk=(x+1)/3-1;//这里意思是比如说一个队6个人(或7个人,8个人),想只凑成一队,最多可以拿5个人;x+1是考虑到一个队5个人,要凑成一队可以直接拿走5个人,如果不加一,就会拿走2个人
    int t=min(kk,k-1);//这里k-1意思是空一个队伍,方便以后还有大于3人的队伍取不到(剩下的队伍都还能取2个,增添一下人数),要不后面k=0直接退出循环了
   // int res=t*3;
    k-=t;//队伍数减去t
    ans+=(t*3+2);//尽量每次多取两个,人数最大化
    x-=(t*3+2);
    if(x)
    qqq.push(x);//把剩下的人单独拿出来
    if(k==0)break;
  }
  while(qqq.size())//这里放着的都是从大于3个的中拿剩下的,在这里随便拿一个,就会使队伍数量加一
  {
    auto x=qqq.top();
    qqq.pop();
    if(k==0)
    break;
   // int t=min(k,x);
   // cout<<k<<" "<<x<<" "<<t<<'\n';
    ans++;//假如本来有4个,存到这里时变成了2个,但是你只能取一个,不能2个都取走(2个都取走会不符合题意)(下面样例自己带入一下可能会清楚一些)
    k--;
  }
  cout<<ans<<'\n';
/*
比如样例:
3 3
1 4
2 4
3 4
*/
  return;
}
signed main()
{
  ios::sync_with_stdio(0);//快输
  cin.tie(0),cout.tie(0);
  int T=1;
  cin>>T;
  while(T--)
  solve();
  return 0;
}

你的代码核心思想是 尽量选择合适的士兵，使其能刚好组成 k 个纯职业小组。我们从 最坏的情况 出发，考虑如何选择士兵，确保 k 个小组可以被组成。下面详细解析代码的逻辑和思路：

1. 题目分析

每个小队由相同职业的士兵组成。
目标是至少选 k 个士兵队伍，每个队伍至少由 3 个相同职业的士兵 组成。
最坏情况 下，可能会遇到一些士兵无法凑满 3 人的小组，这会影响队伍数量。
我们需要找到 最少的士兵人数 来确保 k 个小组可以组建成功。

2. 代码逻辑分析

(1) 读取输入 & 统计每种职业的士兵数量

int n, k, m = 0;
cin >> n >> k;
map<int, int> mp, book;
for (int i = 1; i <= n; i++) {
    int x, y;
    cin >> x >> y;  // x: 职业，y: 该职业的士兵数量
    if (!book[x]) { // 防止重复存储相同职业
        book[x] = 1;
        a[++m] = x; // 记录职业种类
    }
    mp[x] += y; // 统计每个职业的士兵总数
}

解析：

mp[x] 记录 职业 x 的士兵总数。
book[x] 避免 重复统计相同职业，因为可能存在多个小队有相同职业。
a[] 记录 所有不同职业的编号。

(2) 计算能完整组成 `k` 组的职业数

int cnt = 0;
for (int i = 1; i <= m; i++) {
    if (mp[a[i]] >= 3)
        cnt += mp[a[i]] / 3; // 每 3 人可以组成 1 队
}
if (cnt < k) { // 如果连 k 组都凑不出来，直接输出 -1
    cout << -1 << '\n';
    return;
}

解析：

计算所有职业 能组成多少完整的小队，即 cnt。
如果 cnt < k，表示无论如何 都无法组成 k 组，直接输出 -1。

(3) 按照职业的士兵数量进行分类

priority_queue<int, vector<int>> q, qq, qqq;
for (int i = 1; i <= m; i++) {
    q.push(mp[a[i]]); // 大顶堆，优先选择士兵最多的职业
}

解析：

使用 优先队列（大顶堆），保证 尽可能先从士兵多的职业选取。

(4) 处理士兵数量小于 3 的情况

int ans = 0;
while (q.size()) {
    auto x = q.top();
    q.pop();
    if (x >= 3)
        qq.push(x);  // 将数量 ≥3 的放入新的堆
    else
        ans += x;    // 数量小于 3 的，直接累加到最终答案
}

解析：

数量小于 3 的士兵 不能组成小组，所以他们的数量直接累加。
数量大于等于 3 的士兵 可以尝试组成小组，存入 qq。

(5) 处理士兵数量 `>=3` 的情况

while (qq.size()) {
    auto x = qq.top();
    qq.pop();
    
    int kk = (x + 1) / 3 - 1; // 计算最多可以拿走多少人
    int t = min(kk, k - 1);  // 不能超过剩余需要的小组数（k-1）
    
    k -= t;  // 剩余需要的小组数减少 t
    ans += (t * 3 + 2); // 每次尽量多取 3 人，同时多加 2 人
    
    x -= (t * 3 + 2);
    if (x) qqq.push(x); // 还剩下的人存入另一个队列
    if (k == 0) break;
}

解析：

优先从大于 3 人的职业中拿走尽可能多的士兵，确保先组 k-1 个队伍。
kk = (x+1)/3 -1：
- 计算该职业可以 优先组出几个队伍，留下 2 个士兵。
t = min(kk, k-1)：
- 不能超过剩余需要的小组数 (k-1)，否则有浪费。
ans += (t * 3 + 2)：
- 选 t 组小队，每组 3 人，同时多选 2 人。
剩余士兵数量 x 仍然大于 0，放入 qqq 队列，等待后续分配。

(6) 处理剩余士兵

while (qqq.size()) {
    auto x = qqq.top();
    qqq.pop();
    if (k == 0) break;
    ans++;  // 每次选一个士兵
    k--;
}

解析：

qqq 队列中的士兵是之前剩余的，这里 每选 1 个士兵，就增加 1 组。
直到 k==0 时，说明 k 组小队已经全部组好，停止。

3. 复杂度分析

读取输入： O(n)
统计职业人数： O(n)
排序（堆操作）： O(n log n)
总时间复杂度： O(n log n)

4. 代码总结

首先统计各个职业的士兵数量。
先处理不足 3 人的职业士兵，他们无法组成队伍，因此直接计算进 ans。
优先选择士兵数量最多的职业，尽可能组成 k-1 个完整的小队。
若仍不足 k 个队伍，就从剩余士兵中一个个拿，直到满足 k 个小队的需求。
最终输出最少的士兵数量 ans。

5. 示例分析

输入：

解析：

统计士兵数量：
- 职业 1: 4 人
- 职业 2: 4 人
- 职业 3: 4 人
优先拿 4 人 的职业，每次取 3+2=5，保证 k=3 的小组数。
最终选择的士兵数：**6**。

输出：

6. 结论

代码通过 优先队列+贪心策略，确保选出的士兵 刚好满足 k 组的需求，并且 士兵数量最少。
题目关键点在于：
1. 处理不能组成 3 人小队的士兵。
2. 优先从士兵数量最多的职业中选人。
3. 剩余士兵尽可能高效利用，凑成 k 组。

这道题涉及 贪心+优先队列，是一个比较好的算法练习题！🎯

05 奇怪的捐赠

解题日期：250204
解题用时：15min
题目来源：蓝桥杯真题
题目难度：简单
题目标签：填空题

题意整理

![[Pasted image 20250204193727.png]]

解题思路

转换为7进制，每一位相加即可

AC代码

#include <iostream>
using namespace std;
int main()
{
  int x=1000000;
  int temp=0;
  int res=0;
  while(x>0)
  {
    temp=x%7;
    res+=temp;
    x/=7;

  }
  cout<<res;
  return 0;
}

06 握手问题

解题日期：250204
解题用时：5min
题目来源：蓝桥杯真题
题目难度：简单
题目标签：省赛，数学，2024

题意整理

![[Pasted image 20250204194959.png]]

解题思路

排列组合，两两相减即可

AC代码

#include <iostream>
using namespace std;
int main()
{
  int temp1=50*49/2;
  int temp2=7*6/2;
  int res=temp1-temp2;
  cout<<res;
  return 0;
}

07 最大区间

解题日期：250204
解题用时：-min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2023，单调栈，国赛[[单调栈]]

题意整理

![[Pasted image 20250204203247.png]]

AC代码

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll N = 1e5 + 5, mod = 998244353, inf = 2e18;

il void solve() {
    int n,top=0;
    cin>>n;
    vector<ll>a(n+5),stak(n+5),dpl(n+5),dpr(n+5);
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++){
        while(top&&a[stak[top]]>=a[i])top--;
        dpl[i]=stak[top];
        //cout<<dpl[i]<<" \n"[i==n];
        stak[++top]=i;
    }
    top=0;

    for(int i=n;i>=1;i--){
        while(top&&a[stak[top]]>=a[i])top--;
        dpr[i]=stak[top];
        //cout<<dpr[i]<<" \n"[i==1];
        stak[++top]=i;
    }

    ll ans=0;

    for(int i=1;i<=n;i++){
        ans=max(ans,(dpr[i]-dpl[i]-1)*a[i]);
    }

    cout<<ans<<'\n';

}


int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}

这段代码是解决了一个典型的“区间最小值问题”的题目。具体来说，它通过使用单调栈来计算每个元素在其左侧和右侧的第一个小于自己的元素的位置，利用这些信息来推导出每个元素在区间中的最大贡献值。

解题思路分析：

问题描述简化：
- 给定一个数组 a[]，要求在每个位置 i 上找出一个区间 [l, r]，使得 a[i] 是该区间的最小值，并且要找出这个区间的面积。
- 这个面积即为 (r - l - 1) * a[i]，其中 l 是区间的左端点，r 是区间的右端点。
单调栈的应用：
- 左侧第一个小于自己的数：
  - 通过栈从左到右遍历数组，维护一个栈，栈内的元素是数组索引，栈内的元素是单调递增的（即栈内元素对应的 a[] 值递增）。这样每次遇到一个比栈顶元素小的数，就可以确定当前数的左边第一个比它小的数的位置。
- 右侧第一个小于自己的数：
  - 通过栈从右到左遍历数组，操作方式与左侧相似，栈内保持单调递增。遍历时，每次遇到比栈顶元素小的数，可以确定当前数的右边第一个比它小的数的位置。
详细步骤：
- 计算左边第一个小于自己的数（dpl[]）：
  - 维护一个栈 stak，遍历数组 a[]，如果当前栈顶元素比 a[i] 大，则弹出栈顶元素。这样栈顶的元素就是左侧第一个比 a[i] 小的元素的下标。记录这个下标为 dpl[i]，表示左侧第一个小于 a[i] 的位置。
- 计算右边第一个小于自己的数（dpr[]）：
  - 从右向左遍历数组，和左边的操作类似，维护一个栈 stak，找到每个元素右侧第一个小于自己的数的下标，记录在 dpr[i] 中。
- 计算面积：
  - 对于每个位置 i，其能够代表最小值的区间范围是从 dpl[i] + 1 到 dpr[i] - 1，因此它的贡献值（即面积）为 (dpr[i] - dpl[i] - 1) * a[i]。遍历所有位置，找到最大的贡献值即为最终答案。
时间复杂度分析：
- 单调栈的操作每个元素入栈和出栈最多一次，因此时间复杂度是 O(n)，整个过程遍历两遍数组（一次从左到右，另一次从右到左），所以总时间复杂度是 O(n)，效率较高。

代码关键部分：

for(int i=1;i<=n;i++){
    while(top && a[stak[top]] >= a[i]) top--; // 保持栈是单调递增的
    dpl[i] = stak[top]; // 栈顶元素就是左边第一个小于 a[i] 的下标
    stak[++top] = i; // 将当前元素的索引压栈
}

for(int i=n;i>=1;i--){
    while(top && a[stak[top]] >= a[i]) top--; // 保持栈是单调递增的
    dpr[i] = stak[top]; // 栈顶元素就是右边第一个小于 a[i] 的下标
    stak[++top] = i; // 将当前元素的索引压栈
}

for(int i=1;i<=n;i++){
    ans = max(ans, (dpr[i] - dpl[i] - 1) * a[i]); // 计算最大面积
}

总结：

核心思想：通过单调栈分别计算每个位置的左边和右边第一个小于它的数的位置，结合这些位置可以计算每个数作为最小值的最大区间面积，最终取最大值。
时间复杂度：O(n)，其中 n 是数组长度。

08 模拟

解题日期：250204
解题用时：5min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2022，模拟

题意整理

![[Pasted image 20250204224451.png]]
#### 解题思路
直接模拟即可
#### AC代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  int x=0;
  int y=0;
  int n=s.length();
  for(int i=0;i<n;i++)
  {
    if(s[i]=='U')x-=1;
    if(s[i]=='D')x+=1;
    if(s[i]=='L')y-=1;
    if(s[i]=='R')y+=1;
  }
  cout<<x<<" "<<y;
  return 0;
}

09 天干地支

解题日期：250204
解题用时：7min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，模拟，国赛

题意整理

![[Pasted image 20250205092750.png]]

解题思路

简单计算，注意x-2020可能<0

AC代码

#include <iostream>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int count=(n-2020+6000)%60;
  int counttg=count%10;
  int countdz=count%12;
  string tg;
  string dz;
  if(counttg==0)tg="geng";
  if(counttg==1)tg="xin";
  if(counttg==2)tg="ren";
  if(counttg==3)tg="gui";
  if(counttg==4)tg="jia";
  if(counttg==5)tg="yi";
  if(counttg==6)tg="bing";
  if(counttg==7)tg="ding";
  if(counttg==8)tg="wu";
  if(counttg==9)tg="ji";

  if(countdz==0)dz="zi";
  if(countdz==1)dz="chou";
  if(countdz==2)dz="yin";
  if(countdz==3)dz="mao";
  if(countdz==4)dz="chen";
  if(countdz==5)dz="si";
  if(countdz==6)dz="wu";
  if(countdz==7)dz="wei";
  if(countdz==8)dz="shen";
  if(countdz==9)dz="you";
  if(countdz==10)dz="xu";
  if(countdz==11)dz="hai";

  cout<<tg<<dz;

  return 0;
}

10 答疑

解题日期：250205
解题用时：230min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2020，贪心，国赛

题意整理

![[Pasted image 20250205203805.png]]

解题思路

同学消耗的总时间越短，优先级越高
总时间相等时，优先级相同，无所谓前后
证明：
假设同学 i 进入办公室的时间于解答时间的和为 Ai , 离开办公室的时间为 Bi
对于同学 1 与同学 2 而言，所用时间为：
A1, B1
A2, B2
若同学 1 先进教室，则答案为 ans1 = (A1) + (A1 + B1 + A2)
若同学 2 先进教室，则答案为 ans2 = (A2) + (A2 + B2 + A1)
可以发现 ans1 与 ans2 的关系等同于 (A1 + B1) 与 (A2 + B2) 的关系
所以：每名同学进入教室的优先级只与其所消耗的时间和有关，和越小，优先级越高

假如 (A1 + B1) == (A2 + B2)
此时有同学 3 所用时间为：A3, B3 且 (A3 + B3) > (A2 + B2)
那么同学 3 发消息的时刻为 (A1 + B1 + A2 + B2 + A3)
可知，同学 1 与同学 2 的顺序不会影响答案

AC代码

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

struct Num {
    long long sum;
    long long s;
    long long a;
    long long e;
};

// 用于排序的比较函数
bool compare(const Num& x, const Num& y) {
    return x.sum < y.sum;  // 按照 sum 从小到大排序
}

int main()
{
    ios::sync_with_stdio(false);  // 优化 I/O
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;

    Num num[1010];  // 使用结构体数组
    
    // 输入数据
    for (int i = 0; i < n; i++) {
        cin >> num[i].s >> num[i].a >> num[i].e;
        num[i].sum = num[i].s + num[i].a + num[i].e;
    }

    // 按照 sum 从小到大排序
    sort(num, num + n, compare);

    // 计算结果
    long long res = 0;
    long long k=0;
    for (int i = 0; i < n - 1; i++) {
        res+=num[i].a+num[i].s;

    }
    for(int i=0;i<n-1;i++){
      k+=num[i].sum;
      res+=k;
    }

    // 处理最后一个元素
    res += num[n - 1].sum - num[n - 1].e;

    cout << res << endl;

    return 0;
}

01 班级活动

题意整理：

解题思路：

AC代码：

02 好数

题意整理

解题思路

AC代码

03 回文字符串

题意整理

解题思路

AC代码

04 纯职业小组

题意整理

AC代码

1. 题目分析

2. 代码逻辑分析

(1) 读取输入 & 统计每种职业的士兵数量

(2) 计算能完整组成 k 组的职业数

(3) 按照职业的士兵数量进行分类

(4) 处理士兵数量小于 3 的情况

(5) 处理士兵数量 >=3 的情况

(6) 处理剩余士兵

3. 复杂度分析

4. 代码总结

5. 示例分析

6. 结论

05 奇怪的捐赠

题意整理

解题思路

AC代码

06 握手问题

题意整理

解题思路

AC代码

07 最大区间

题意整理

AC代码

解题思路分析：

代码关键部分：

总结：

08 模拟

题意整理

09 天干地支

题意整理

解题思路

AC代码

10 答疑

题意整理

解题思路

AC代码

(2) 计算能完整组成 `k` 组的职业数

(5) 处理士兵数量 `>=3` 的情况