蓝桥杯蓝桥杯大赛集训一 题解（校内）

1. 日期统计

题目：

numbers[100] = {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3};

从numbers这个序列中找到子序列，满足下列条件：

1. 子序列的长度为8；
2. 这个子序列可以按照下标顺序组成一个yyyymmdd 格式的日期，并且要求这个日期是2023 年中的某一天的日期，例如20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。

暴力解法

构造每一天的yyyymmdd然后在numbers中查找。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int numbers[100] = {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3};
const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int main()
{
    int ans = 0;
    for (int i = 1; i <= 12; i++)// month循环用于构造所有的月份
    {
        for (int j = 1; j <= days[i]; j++)// day循环用于构造所有的日期（按照月份大还是小）
        {
            // 以下：构造日期2023mmdd
            string str = "2023";
            if (i < 10)
                str += "0";
            str += to_string(i);
            if (j < 10)
                str += "0";                                                                                  
            str += to_string(j);
            // 以上：构造日期mmdd2023
            // 以下：构造好一个日期后，判断是目标字符串中是否含有这个字串
            int k = 0;
            for (int l = 0; l < 100 && k < 8; l++)
            {
                if (numbers[l] == str[k] - '0')
                    k++;
            }
            if (k >= 8)
                ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

2. 01串的熵

题目:

解法1：枚举 0 的概率（应该快一点）

由于只有0和1，所以只需要枚举0的概率，每次递增1e-9。（但是不知道为什么当时没过）

解法1：枚举 0 的个数（应该慢一点）

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int total = 23333333;
const double H = 11625907.5798;

int main()
{
    for (int i = 0; i < total / 2; i++)
    {
        double ans = 0;
        ans -= 1.0 * i * i / total * log2(1.0 * i / total);
        ans -= 1.0 * (total - i) * (total - i) / total * log2(1.0 * (total - i) / total);
        if (abs(ans - H) < 1e-4)
        {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

// 二分：
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const int total = 23333333;
const double H = 11625907.5798;

int main() {
  int l = 0, r = total / 2;
  while (l < r) {
    int mid = (l + r) >> 1;
    double ans = 0;
    ans -= 1.0 * mid * mid / total * log2(1.0 * mid / total);
    ans -= 1.0 * (total - mid) * (total - mid) / total * log2(1.0 * (total - mid) / total);
    if (abs(ans - H) < 1e-4) {
      cout << mid << endl;
      return 0;
    }
    if (ans > H) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return 0;
}

3. 子2023

题目:
小蓝在黑板上连续写下从1到2023之间所有的整数，得到了一个数字序列:

S = 12345678910111213...20222023   

小蓝想知道S中有多少种子序列恰好等于2023?

提示，以下是3种满足条件的子序列(用中括号标识出的数字是子序列包含的数字) :

1[2]34567891[0111[2]1[3)14151617181920212223   
   
1[2]34567891[0]111[2]131415161718192021222[3]   
   
1[234567891[0]111213141516171819[2]021222[3]   

注意以下是不满足条件的子序列，虽然包含了2、0、2、3四个数字，但是顺序不对:

1[2]345678910111[2]131415161718192[0]21222[3]

解题：动态规划

#include <iostream>
#include <string>

using namespace std;

int main() {
    // 构建序列 S
    string S = "";
    for(int i = 1; i <= 2023; ++i){
        S += to_string(i);
    }

    // 初始化计数器
    long long count_2 = 0;
    long long count_20 = 0;
    long long count_202 = 0;
    long long count_2023 = 0;

    // 遍历序列 S
    for(char c : S){
        if(c == '3'){
            count_2023 += count_202;// 能够构成202 3，那么当前这个 “3” 可以和前面的 “202” 组成 %count_202% 个 2023。
            
        }
        if(c == '2'){
            count_202 += count_20;// 同上
            count_2 += 1;// 同上
        }
        if(c == '0'){
            count_20 += count_2;// 同上
        }
    }

    // 输出结果
    cout <<  count_2023 << endl;

    return 0;
}

4. 双子数

题目：
若一个正整数x可以被表示为x=p^2*q^2其中p、q为质数,则x是个“双子数”。请计算区间[2333, 233333333333]内有多少个“双子数”?

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

解题：欧拉筛+暴力组合枚举

#include <bits/stdc++.h>
#define int __int128

using namespace std;

const int N = 1e7 + 10;

int n, ans, cnt;
int prime[N];
bool st[N];

void init()
{
  for(int i = 2; i < N; i ++)
  {
    if(!st[i]) prime[cnt ++] = i;
    for(int j = 0; j < cnt&&prime[j] * i < N; j ++)
    {
      st[prime[j] * i] = true;
      if(i % prime[j] == 0) break;
    }
  }
}

void solve()
{
  int ans = 0;
  for(int i = 0; i < cnt; i ++)
    for(int j = i + 1; j < cnt; j ++)
    {
      int a = prime[i], b = prime[j];
      if(a * a * b * b > 23333333333333) break;
      if(a * a * b * b < 2333) continue;
      ans ++;
    }
  cout << (long long)ans << '\n';
}

signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  init();
  int _ = 1;
  while(_ --)
    solve();
  return _ ^ _;
}

5. 握手问题

小蓝组织了一场算法交流会议，总共有 50 人参加了本次会议。
在会议上，大家进行了握手交流。按照惯例他们每个人都要与除自己以外的其他所有人进行一次握手（且仅有一次）。但有 7 个人，这 7 人彼此之间没有进行握手（但这 7 人与除这 7 人以外的所有人进行了握手）。
请问这些人之间一共进行了多少次握手?注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手。
问题分析：
这个问题可以直接由计算得到。首先，总共有 50 个人，每个人要与除自己以外的其他所有人进行一次握手，那么总的握手次数为5049/2=1225。
但是有 7 个人彼此之间没有进行握手，这意味着这 7 个人之间本应该进行67/2=21次握手，但是实际上没有进行握手。
所以最终的握手次数为 1225-21=1204。

简单的数学手算就行了

6. 小球反弹

题目：

解题：暴力枚举比例

由于碰撞是满足反射定律的，所以可以视为按碰撞边对称（也就是扩展空间的意思，这个时候小球就走直线了）。如果小球最后直线走到对角，那么此时速度方向反向（因为Vx和Vy都反向了），然后就会原路返回了，所以就要求扩展的长宽各自的倍数,可以使用暴力求解。

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

int main()
{
  long long w = 233333;
  long long l = 343720;
  for(long long x = 0; x <= 10000; x ++)
  {
    for(long long y = 0; y <= 10000; y ++)
    {
      // 偶数 && 均不为 0
      if(15 * w * y == 17 * l * x && x % 2 == 0 && y % 2 == 0 && x != 0 && y != 0)// 使拓展后的矩形的长和宽和速度成比例，此时小球直接沿对角线走。
      {
        cout << x << " " << y << endl;
        double res = sqrt((l * x) * (l * x) + (w * y) * (w * y));
        printf("%llf", res);
        return 0;
      }
    }
  }

  return 0;
} 

7. 合法密码检查

题目：

小蓝正在开发自己的OJ网站。他要求网站用户的密码必须符合以下条件:

1. 长度大于等于8个字符，小于等于16个字符。

2. 必须包含至少1个数字字符和至少1个符号字符。

例如lanqiao2024!、+-*/0601、 8((>w<))8都是合法的密码。

而12345678 、##** ##**、abc0!#、lanqiao20240601!? 都不是合法的密码。

请你计算以下的字符串中，有多少个子串可以当作合法密码?只要两个子串的开头字符和末尾字符在原串中的位置不同，就算作不同的子串。

字符串为:

kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th

暴力枚举

由于这个字串指的是连续的字串。所以枚举长度和起始位置即可

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool isValid(const string &s)
{
    int num = 0, sym = 0;
    for (char c : s)
    {
        if (isdigit(c))
            num += 1;
        if (!isalnum(c))
            sym += 1;
    }
    return num > 0 && sym > 0;
}
int main()
{
    string s = "kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kagbcss2th";
    int n = s.size();
    int res = 0;
    for (int len = 8; len <= 16; ++len)
    {
        for (int i = 0; i <= n - len; ++i)
        {
            string sub = s.substr(i, len);
            if (isValid(sub))
            {
                res += 1;
            }
        }
    }
    cout << res << endl;
    return 0;
}

8. 选数概率

解题：数学推理 + 暴力