2025算法练题记录11~20

11 分球

解题日期：250206
解题用时：34min
题目来源：蓝桥云课题库
题目难度：简单
题目标签：数学，排列组合

题意整理

![[Pasted image 20250206162600.png]]

解题思路

高中数学排列组合，第一反应隔板法。
将n个球和k-1个隔板进行排序，总数为n+k-1 组合数公式为C(m,r)=m!/r!(m-r)! 此时m=n+k-1;r=k-1;
但是后来尝试之后发现这道题目有很多坑。比如整数除法。
将res存为double之后，最后不能使用cout输出。一定要使用printf。
#### AC代码

#include <iostream>
using namespace std;

double factor(int n)
{
  int k=n;
  double res=1;
  while(k>=1)
  {
    res*=k;
    k--;
  }
  return res;
}


int main()
{
  int n,k;
  cin>>n>>k;
  double res=factor(n+k-1)/factor(k-1);
  res/=factor(n);
  printf("%.0f",res);
}

12 购物车里的宝贝

解题日期：250215
解题用时：9min
题目来源：蓝桥题库
题目难度：简单
题目标签：位运算

题意整理

输入一个整数n，代表集合中元素的数目，现在问集合中的元素能否被划分成两个异或和相等的集合。

解题思路

能分成两个异或和相等的集合，即整体集合的异或和等于0.

AC代码

#include <iostream>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[100010];
  cin>>a[0];
  int count=a[0];
  for(int i=1;i<n;i++){
    cin>>a[i];
    count=count^a[i];
  }
  if(count==0){
    cout<<"YES";
  }
  else{
    cout<<"NO";
  }
  return 0;
}

---

13 消灭卡片

解题日期：250215
解题用时：230min
题目来源：蓝桥题库
题目难度：简单
题目标签：思维，数学，算法赛

题意整理

一共t组测试数据。每个测试数据包含n张需要消灭的卡片。每次可以消灭3张或者5张卡片，要用最少的行动次数消灭所有卡片。如果不能消灭则输出-1，如果可以消灭则输出最少次数。

解题思路

找规律。0~12注意8和11特例，其他全部n/5或者n/3即可。12以上的全部都可以表示，按照n%5的结果分成五类，简单计算讨论即可。

AC代码

#include <iostream>

using namespace std;

  

void solve()

{

  int n;

  cin>>n;

  if(n<12){

    int count=0;

    if(n%5==0){

      count=n/5;

      cout<<count<<endl;

      return;

    }

    if(n%3==0){

      count=n/3;

      cout<<count<<endl;

      return;

    }

    if(n%5==3){

      count=n/5+1;

      cout<<count<<endl;

      return;

    }

    if(n==11){

      count=3;

      cout<<count<<endl;

      return;

    }

    cout<<-1<<endl;

    return;

  }

  else{

    int count=0;

    if(n%5==0){

      count=n/5;

    }

    if(n%5==1){

      count=n/5+1;

    }

    if(n%5==2){

      count=n/5+2;

    }

    if(n%5==3){

      count=n/5+1;

    }

    if(n%5==4){

      count=n/5+2;

    }

    cout<<count<<endl;

    return;

  }

}

  
  
  

int main()

{

  int T;

  cin>>T;

  while(T--){

    solve();

  }

  return 0;

}

---

14 k倍区间

解题日期：250215
解题用时：50min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2017，暴力，省赛。

题意整理

输入n,k，序列长度为n，如果其中一段连续子序列之和为K的倍数，就称这个区间 [ i , j ] 为K倍区间。

解题思路

直接暴力三重循环会运行超时，需要优化。
原先运行超时的代码：

#include <iostream>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int a[100010];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int count=0;
  for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
      int cotemp=0;
      for(int m=i;m<=j;m++){
        cotemp+=a[m];
      }
      if(cotemp%k==0)count++;
    }
  }
  cout<<count;
  return 0;
}

想一下当两个数除以K的余数相同时，将他们相减之后是不是能被K整除（如：k=3,a1=4,b=7），我们会惊奇的发现是可以的，利用这个技巧，我们可以在求前缀和的时候判断一下这个前缀区间模上K的余数，并计数（cnt[]）,然后再想一下，我们用前缀和求任意一个区间是怎么求得？这样当我们再在判断余数的时候，加上之前也是这个余数的前缀区间的集合数量，因为只要我这个有和前面任何一个余数相同，都能得到一个被K整除的区间（并且还不一样），利用这个我们可得到优化。

AC代码

#include <iostream>
using namespace std;
const int N=100010;
//因为是前缀和，数还是比较大的
long long  a[N];
//这里cnt[]最差情况也就所有数的余数相同（最大也就100000），不需要long long
int cnt[N];
int main()
{
  int n,m;
  cin>>n>>m;
//余数为0说明本身就是可已被整除（可以模拟一下，如果初始为零会有有什么后果，这里就不说了）
  cnt[0]=1;
//一般像求这种区间数量的，都非常大要long long
  long long res=0;
  for(int i=1;i<=n;i++){
//自己前缀自己
    scanf("%d",&a[i]);
    a[i]+=a[i-1];
    //加上之前和自己有相同余数的区间数量（两个构成一个可以被K整除的区间）
    res+=cnt[a[i]%m];
//累加自己，因为后面还有可能有可以和他组成可被K整除的区间
    cnt[a[i]%m]++;
  }
  cout<<res<<endl;
  return 0;
}

---

15 分巧克力

解题日期：250215
解题用时：50min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2017，省赛，二分

题意整理

共有N块巧克力，输入每一块的长和宽，现在需要将其分成k块，每块都是大小相等的正方形，求最大边长。

解题思路

先确定每一块巧克力可以分成的数量是(a/m)* (b/m)，根据这个可以枚举出来结果。再使用二分算法优化，初始最短为1，最长为10000，对于确定的边长计算出可以分成的总数，与k进行判断比较，如果符合条件就往大取，不符合往小取。最后取r即为答案。

AC代码

#include <iostream>
using namespace std;

const int N = 100010;
int n,k;
int h[N],w[N];

bool check(int mid) //边长为mid的正方形
{
int res = 0;
for(int i = 0;i < n;i++)  //n块巧克力的切块
{
  res += (h[i]/mid) * (w[i]/mid); //计算切一块巧克力的可获得的块数

 if(res >= k)  return true; //如果达到要求，则可以直接提前退出
}
return false; //如果n块已经全部切完，且退出循环res < k,则不符合要求
} 
int main()
{
  // 请在此输入您的代码
  scanf("%d%d",&n,&k);
  for(int i = 0;i < n;i++)  scanf("%d%d",&h[i],&w[i]);
//二分法判断边长
  int l = 1,r = 1e5;  //至少获得1*1的边长的.
while(l < r)
{
  int mid = l + r + 1 >> 1;
  if(check(mid)) l = mid; //判断是否满足，找可满足要求的最大边长切块，mid边长是满足的
  else r = mid - 1;//说明不满足，需要缩减边长
}

 printf("%d\n",r); 
  return 0;
}

---

16 拉马车

解题日期：250216
解题用时：40min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2017，模拟，省赛

题意整理

马拉车纸牌游戏，过程如你熟悉。输入A和B的初始牌组，求最后赢家的牌组，如果不能分出胜负，则输出-1

解题思路

直接模拟，难点是字符串指针，以及栈数据结构的使用。

AC代码

#include <bits/stdc++.h>
using namespace std; 
bool a[128]; // a[i]表示牌堆中是否存在i这张牌 
int main() { 
  string A,B; 
  cin>>A>>B; 
  stack<char> S; // 用栈作为牌堆
  S.push(A[0]); a[A[0]-0]=1; A.erase(0,1); // A先出牌
  bool flag=1; // flag控制到谁出牌 
  int times=0; // times表示出牌次数，超过10000认为会无限循环 
  while(A.length() && B.length() && times<10000){ 
    //cout<<A<<","<<B<<endl; 
    string* sp=flag?&B:&A; // flag为1时B出牌，将string指针指向B，方便实现B的出牌和收牌 
    char tmp=(*sp)[0];
    S.push(tmp); sp->erase(0,1); // 玩家出牌 
    if(a[tmp-0]==0) { a[tmp-0]=1; flag = !flag; } // 牌堆中没有当前出的牌，牌权更换 
    else{ // 若包含当前字符，收回一部分牌 
      *sp += S.top(); S.pop(); // 收回刚出的那张牌，位于栈顶 
      while(S.top()!=tmp){ *sp += S.top(); a[S.top()-0] = 0; S.pop(); } //一直收牌到与所出牌相同的另一张牌处 
      *sp += S.top(); a[S.top()-0] = 0; S.pop(); 
    } 
    times++; 
  } 
  if(times>=10000) return -1; 
  if(A.length()) cout<<A; else cout<<B; 
  return 0; 
}

---

17 分考场

解题日期：250216
解题用时：45min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2017，搜索，国赛

题意整理

n个人分考场，两两相互认识不能在同一考场，输入相互认识的信息，求最少需要多少考场。

解题思路

使用深度优先搜索即可。

AC代码

#include<iostream>
using namespace std;
const int N = 110;
int a[N][N];//关系表 如：a[u][v]=1，表示第u个人与第v个人认识
int p[N][N];//考场状态，p[j][k]=y:表示第j个考场的第k个座位，坐第y个人
int num = N;//最优考场数量
int n, m;
void dfs(int x, int room)//试试把第x个人安排到第1到room考场
{
    if (room >= num)return;
    if (x > n)//已经安排了n个人，结束
    {
        num = min(num, room);//更新最优解
        return;
    }
    int j, k;
    for (j = 1; j <= room; j++)//枚举考场,把第x个人放入第j个考场里
    {
        k = 1;
        while (p[j][k] && !a[x][p[j][k]])//表示j考场第k个位置有人坐并且二者并不认识
            k++;//第x个人去做下一个位置
        if (p[j][k] == 0)//如果没人坐
        {
            p[j][k] = x;//让x坐在这里
            dfs(x + 1, room);//继续去安排下一个人
            p[j][k] = 0;//回溯，释放这个座位
        }
    }
    //如果安排不了，就再加一个考场
    p[room + 1][1] = x;
    dfs(x + 1, room + 1);//继续去安排下一个人
    p[room + 1][1] = 0;//回溯
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        a[u][v] =a[v][u]= 1;
    }
    dfs(1, 1);
    printf("%d", num);
    return 0;
}

---

18 合根植物

解题日期：250217
解题用时：30min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2017，并查集，国赛

题意整理

种植园中共有m* n棵合根植物，连根则合为一颗植物，输入m，n，以及k组数据表示a与b连根，问共有多少颗合根植物

解题思路

并查集模板题

并查集

AC代码

#include <iostream>
using namespace std;
const int N=1000010;
//记录父根
int p[N];
//查找加优化，不知道的可以先学一下这个算法
int find(int x){
  if(p[x]!=x)p[x]=find(p[x]);
  return p[x];
}
int main()
{
  int n,m,k;
  cin>>n>>m>>k;
//并查集初始化，所有植物自成一类
  for(int i=1;i<=n*m;i++){
    p[i] = i;
  }

  for(int i=0;i<k;i++){
    int a , b;
    scanf("%d%d",&a,&b);
    int pa = find(a), pb = find(b);
 //合并集合
    if(pa ! = pb)  p[pa] = pb; 
  }
  int res=0;
//当p[i]=i 说明他是父根，也说明他代表一种植物
  for(int i=1;i<=n*m;i++){
    if(p[i]==i) res++;
  }
  cout<<res<<endl;
  return 0;
}

---

19 区间移位

解题日期：250217
解题用时：45min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2017，枚举，国赛，二分

题意整理

数轴上n个闭区间，已知区间长度之和至少又10^4 ，移动区间使其并集覆盖[0，10^4]，找到一种方法使移动距离最大的区间的移动距离最小。

解题思路

不用关心区间怎么移动。只要去寻找最小的能满足覆盖0~10000的移动距离

AC代码

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int a;
    int    b;
};
int n;
vector<Node> nv;//node vector
bool ngreater(Node a,Node b) {
    return a.b < b.b;
}
bool check(int mid) {
    int mr = 0;//most right node，指的是目前可移动距离为mid下，最右点可以达到的位置，是满足0-mr区间内没有空白区域的
    vector<Node> temp(nv);//临时复制品
    while (true)//存在特殊区间，多判断几次
    {
        bool flag = false;//如果所有循环结束后还是false，说明这个mid不合格
        for (int i = 0;i < temp.size();i++) {
            Node node = temp[i];
            int na = node.a, nb = node.b;
            int len = nb - na;
            if (na - mid <= mr && mr <= nb + mid) {//目前最右点可以达到的位置如果不在这个区间内，就意味着这个区间之前的位置存在空白区域，无法连接，就跳过，试下一个区间
                flag = true;//这个区间目前合格
                if (na + mid >= mr)//假如对于这个区间q而言，最左端a向右最多移动mid距离后
                    mr += len;//，能超过当前最右点可以达到的位置，那么mr能到达的新的最右点即使是首尾相连后的b点，相当于新增了len的长度
                else//若是不能超过，那么mr的位置最多到b+mid的位置
                    mr = nb + mid;
                temp.erase(temp.begin() + i);//避免重复判断
                break;
            }

        }
        if (mr >= 20000 || !flag) break;//当没有能满足条件的区间存在时或者mr已经满足条件后，就break
    }
    return mr >= 20000;
}

int main()
{
    cin >> n;
    for (int i = 0;i < n;i++) {
        int a, b;
        cin >> a >> b;
        nv.push_back({ a * 2,b * 2 });
    }
    int l = 0, r = 20000,mid;
    sort(nv.begin(), nv.end(), ngreater);//node按照最右点，从小到大排序
    while (r >= l) {
        mid = (l + r) / 2;
        if (check(mid)) r = mid - 1;//寻找的是尽可能小的移动范围，所以mid成立的情况下移动范围收缩
        else l = mid + 1;//不成立说明mid移动太小了
    }
    double m = ((double)r + 1) / 2;//前面翻倍了，这里返回。+1是因为前面当r==l==mid时，如果mid满足，r会-1这里加回来，如果mid不满足，那么由于r是逐渐由mid-1来的
                            //那我们知道比r大的区域肯定是满足的，所以虽然这个r不满足，但是r+1肯定满足
    cout << m;
    return 0;
}

---

20 数组操作

解题日期：250217
解题用时：26min
题目来源：蓝桥杯真题
题目难度：中等
题目标签：2017，线段树，国赛

题意整理

给出一个长度为n的数组，从1到n标号，需要维护m个操作。
l到r都加上d
l1到r1的位置赋值成l2到r2的值
求出数组中下标l到r的位置的和

解题思路

线段树模板题目

线段树

AC代码

#include <stdio.h>
#define int long long
int v[100005];
inline int read()
{
  int x=0;char c=getchar();
  while(c>='0'&&c<='9')
  {
    x=(x<<3)+(x<<1)+c-'0';c=getchar();
  }
  return x;
}
signed main()
{
  int m=read(),n=read();m=read();
  for(int i=1;i<=n;i++)
  v[i]=read();
  int a,b,c,d,op;
  while(m--)
  {
    op=read();
    a=read();b=read();
    if(op==2)
    {
      c=read();d=read();
      if(a<c)
      {
      for(int i=a;i<=b;i++)
      v[i]=v[c++];
      }
      else
      {
        for(int i=b;i>=a;i--)
        v[i]=v[d--];
      }
    }
    else if(op==1)
    {
      c=read();
      for(int i=a;i<=b;i++)
      v[i]+=c;
    }
    else 
    {
      int sum=0;
      for(int i=a;i<=b;i++)
      sum+=v[i];
      printf("%lld\n",sum);
    }
  }
  return 0;
}