蓝桥杯之模拟与枚举day1

Question1卡片(C/C++A组第一题)

file 这个是一道简单的模拟枚举题目，只要把对应每次的i的各个位都提取出来，然后对应的卡片数目减去1即可。属于打卡题目。注意for循环的特殊使用即可

#include <iostream>
using namespace std;
bool solve(int a[],int n)
{
  //模拟枚举
  while(n!=0)
  {
    int tmp = n % 10;
    n /= 10;
    a[tmp]--;
    if(a[tmp]<0)
      return false;
  }
  return true;
}
int main()
{
  int cnt[10] = {0};
  // 请在此输入您的代码
  for(int i = 0; i <= 9 ;i++)
    cnt[i] = 2021;
  // int ret = 1;
  // bool flag = true;
  // flag = solve(cnt,1);
  // while(flag)
  // {
  //   ret++;
  //   flag = solve(cnt,ret);
  // }
  /*
  也可以用for循环
  */
  for(int i = 1; ;i++)
    if(!solve(cnt,i)){
    cout<<i-1<<endl;
    return 0;}
  //记得最后要减去1
  // cout<<ret-1<<endl;
  return 0;
}

file

Question2回文日期(C/C++A组第七题)

file 在蓝桥杯官网上面显示这个题目属于困难，但是实际上很简单。直接枚举就行，但是注意要如何进行枚举，日期30进1，月份12进1。想清楚这个就是很简单的枚举了

//
// Created by jjh on 2023/11/10.
//
#include<iostream>
using namespace std;
/*
思路:
1、难点在于日期的遍历，要考虑好怎么进行进位
2、回文日期的判断，用一个八位数组就行
3、ABABBABA型特殊判断
*/
bool huiwen(int d)//回文字符串
{
    int a[8];
    for(int i = 0; i < 8; i++)
    {
        int tmp = d % 10;
        a[7 - i] = tmp;
        d = d / 10;
    }
    int i = 0;
    while(a[i] == a[7-i])
        i++;
    return i>4;
}
bool huiwen1(int d)//特殊回文串判断
{

    int a[8];
    for(int i = 0; i < 8; i++)
    {
        int tmp = d % 10;
        a[7 - i] = tmp;
        d = d / 10;
    }
    if(a[0] == a[2] && a[2] == a[5] && a[5] == a[7] )
        if(a[1] == a[3] && a[3] == a[4] && a[4] == a[6])
            if(a[0]!=a[1])
                return true;
    return false;
}
int main(){
    /*
    遍历日期，年 月 日
    日是30进一位，月是12进一位
    */
    bool flag = false,flag1 = false;
    int ans1 = 0,ans = 0,d0;
    string d;
    cin>>d;
    d0 = stoi(d);//转化为数组
    int first = d0;
    while(true)
    {
        if(huiwen(d0)&&!flag&&d0!=first){
            ans = d0;
            flag = true;
        }
        if(huiwen1(d0)&&!flag1&&d0!=first)
        {
            ans1 = d0;
            flag1 = true;
        }
        if(flag&&flag1)
        {
            cout<<ans<<endl<<ans1<<endl;
            return 0;
        }
        int tmp = d0 % 100;//获取日期最后两位
        tmp++;
        if(tmp > 30)
        {
            int tmp1 = d0/100;
            int tmp2 = tmp1;
            tmp1 %= 100;
            tmp1++;
            if(tmp1 > 12)
            {
                d0 = (((tmp2/100)+1)*100 + 1)*100 + 1;
                continue;
            }
            else
            {
                d0 = (tmp2 +1)*100 + 1;
                continue;
            }
        }
        d0++;
    }

    return 0;
}

Question3(C/C++A组第四题)赢球票

file 这个也是一道模拟的题目，难点在于如何拆分问题。面对这个问题，要有几个思考。

怎么在链上模拟环的移动？

这个是好办的，当pos = n的时候，我们将其归为为1即可。pos = 1

如何表示被拿走的卡片？

被拿走的卡片我们是不能访问计数的，用一个flag数组表示即可解决问题，但是在不同位置开始遍历的时候记得清零

哪个位置开始取得最大值？

这个问题我们是不知道的，所以要进行枚举，每一个位置都模拟一轮

游戏如何结束？

当我们选择的卡片数量为n的时候或者当我们数到的数比所有卡片的数量还要多！

tips:注意输出的答案不是能选择的最多卡片数目，而是能够赢得的最多球票数目，及卡片所代表的值!

代码:

//
// Created by jjh on 2023/11/10.
//
#include <iostream>
#include <cstring>

using namespace std;
/*
 * 思路:
 * 1、数组模拟环上面的移动
 * 2、flag[i] = 1表示i处已经被移走
 * 3、当已经移走所有卡片或者当前数的数大于n
 * */
int main(){
    int n,maxx = INT_MIN;
    cin>>n;
    int flag[n+1],a[n+1];

    memset(a,0,sizeof(a));
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    for(int i = 1; i <= n; i++)
    {
        memset(flag,false,sizeof(flag));
        int pos = i,cnt = 1,ans = 0,sum = 0;
//        while(cnt <= n && ans < n)
            while(1)
            {
              if(!flag[pos])
              {
                  if(a[pos] == cnt)
                  {
                      sum += a[pos];
                      flag[pos] = true;
                      pos++;
                      ans++;
                      if(pos > n)
                          pos = 1;
                      cnt = 1;
                  }else
                  {
                      cnt++;
                      pos++;
                      if(pos > n)
                          pos = 1;
                  }
              }
              else
              {
                  pos++;
                  if(pos > n)
                      pos = 1;
              }
                if(cnt > n || ans == n)
                    break;
            }
            maxx = max(maxx,sum);

    }
    cout<<maxx<<endl;
    return 0;
}

Question4（C/C++A组第二题）

file 实质上就是看你会不会求最大公约数！打卡题

//
// Created by jjh on 2023/11/10.
//
#include <iostream>
using namespace std;
/*
 * 思路:本质上就是一个判断最大公约数的题目，暴力枚举就行
 * */
int check(int i,int j)
{
    return j == 0 ? i : check(j,i%j);
}
long long ans;
int main(){
    for(int i = 1; i <= 2020;i++)
        for(int j = 1; j <= 2020;j++)
            if(check(i,j) == 1)
                ans++;
    cout<<ans<<endl;
    return 0;
}

Question5(C/C++A组第4题)数的分解

file 这个显然是一个暴力枚举法,记得去重就可。

易得：

   for(int i = 1; i <= 2019;i++)
        for(int j = 1 ;j <= 2019 ;j++)
            for(int k = 1; k <= 2019;k++)
                if(i + j + k == 2019 && !check(i)&&!check(j)&&!check(k)&&i!=j&&j!=k&&i!=k)
                    ans++;
       ans/=6;

但是这个复杂度太高了，那能不能进行优化呢？当然是可以的！

首先我们可以确定i,j,k的次序，省去去重操作了。

还有就是我们可以利用flag数组提前计算出哪些数字包含有2/4。进一步，我们实际上可以利用两重循环来解决问题，k那层直接用 2019 -i - j代替.!

//
// Created by jjh on 2023/11/10.
//
#include <iostream>
using namespace std;
int n;
/*
 * 题目关键点:
 * 1、如何去重
 * 2、如何判断是否含有数字2或者4
 * */
bool check(int n)
{
    bool flag = false;
    while(n!=0&&!flag)
    {
        int tmp = n % 10;
        n /= 10;
        if(tmp == 2 || tmp == 4)
            flag = true;
    }
    return flag;
}
long long ans;
bool flag[2020];
int main(){

    for(int i = 1 ;i <= 2019;i++)if(check(i))flag[i] = true;
//    for(int i = 1; i <= 2019;i++)
//        for(int j = 1 ;j <= 2019 ;j++)
//            for(int k = 1; k <= 2019;k++)
//                if(i + j + k == 2019 && !check(i)&&!check(j)&&!check(k))
//                    ans++;
    //去重

//    cout<<ans / 6<<endl;
    for(int i = 1; i <= 2019;i++)
        for(int j = i+1;j < 2019 - i - j;j++)
            if(!flag[i] && !flag[j] &&!flag[2019 - i - j])
                ans++;
    cout<<ans<<endl;
    return 0;
}