算法-蓝桥杯模拟题

进制转换相关模板

1.将任意进制转换成十进制

image-20250224124357850

例题：

image-20250224124552134

  • 这里的K是16，因为题目要求我们转换为16进制

Ac_code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
const int N = 10;
using ll = long long;
int a[N];


int main()
{
  string s = "2021ABCD";
  for(int i = 0; i < s.length();i ++)
  {
    if('0' <= s[i] && s[i] <= '9') a[i + 1] = s[i] -'0';
    else a[i + 1] = s[i] - 'A' + 10; 
  }

  ll x = 0;
  for(int i = 1;i <= s.length(); i ++)
  {
     x = x * 16 + a[i];
  }
  cout << x << endl;
  return 0;

}

2.将十进制转换为任意进制

image-20250224124900787

AC_code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
	将（2022）9 ，九进制的2022 转换为十进制
*/
#include <iostream>
using namespace std;
const int N = 6;
using ll = long long;

int a[N];

int main()
{
  string s = "2022";
  for(int i = 1;i <= 4; i ++) a[i] = s[i - 1] - '0';

  ll x = 0;
  for(int i = 1;i <= 4;i ++)x = x * 9 + a[i];
  cout << x << endl;
  return 0;
}

例题

image-20250330211953999

AC_code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
	思路：将N进制转换成10进制，然后将10进制转换成M进制
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 12;
int a[N];

char ch[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E','F'};

void solve()
{
  // 1.将N进制转换为十进制
  int n, m; cin >> n >> m;
  string s;cin >> s;
  int len = s.length();
  s = "#" + s;
  for(int i = 1;i <= len;i ++)
  {
      if('0' <= s[i] && s[i] <= '9')a[i] = s[i] - '0';
      else a[i] = s[i] - 'A' + 10;
  }

  ll x = 0;
  for(int i = 1;i <= len; i ++)x = x * n + a[i];
	// 2.将十进制转换为M进制
  string ans;
  while(x)
  {
    ans += ch[x % m];
    x /= m;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}

int main()
{
  
  int _;cin >> _;
  while(_ --) solve();  
  return 0;
}

string to int / int to string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int s2i(string s)
{
    int res = 0;
    for(const auto &i : s)res = res * 10 + i - '0';
    return res;
}

string i2s(int x, int w) // w表示位数
{
    string res;
    while(x)res += (x % 10) + '0', x /= 10;
    while(res.length() < w) res += '0'; //当位数不够的时候加上前置0
    reverse(res.begin(), res.end());
    return res;
}

蓝桥杯相关题目

image-20250330212015065

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

int ito2(int x)
{
	int res = 0;
	while(x) res += x % 2, x /= 2;
	return res;
}

int ito4(int x)
{
	int res = 0;
	while(x) res += x % 4, x /= 4;
	return res;
}

bool check(int x)
{
	if(ito2(x) == ito4(x)) return true;
	else return false;
}

int main()
{
	int ans = 0;
	for(int i = 1;i <= 2024;i ++)
		if(check(i)) ans ++;
	cout << ans;
	return 0;
}

填空题（2024省赛真题）

image-20250330213756659

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;
const int N = 60;
const int p = 1e9 + 7; // p 是质数即可在qmi中使用
ll fac[N]; // 存阶乘

void init(int n)
{
	fac[0] = 1;
	for(int i = 1;i <= n;i ++) fac[i] = (ll)fac[i - 1] * i % p;
}

int qmi(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1) res = (ll)res * a % p;
		a = (ll)a * a % p;
		b >>= 1;
	}
	return res;
}

// 求逆元
int inv(int x) {return qmi(x, p - 2); }

ll c(int n, int m)
{
	if(m > n || n < 0 || m < 0) return 0;
	// c[n][m] = n! / ((n-m)! * m!)
	return (ll)fac[n] * inv(fac[n - m] * fac[m] % p) % p;	
}

int main()
{
	// 趁着这个问题我们杀鸡用牛刀试一下
	// 组合数模板
	int n = 50;
	init(n);
	cout << (c(50, 2) - c(7, 2) + p) % p;
	return 0;
}

模拟2023国赛真题

image-20250330215708835

  • 写一下思路，主要使用了数学方法求解，我们发现每层的数字为
1
2
3
4
1	3	  6	   10	  15
我们获取一下他们的差分数组
  2    3     4     5
发现数组的一阶差分很有规律可以得到二阶差分全为1

解题思路与数学推导

1. 观察原始序列

给定序列：
$$
a_n: \quad 1, \quad 3, \quad 6, \quad 10, \quad 15
$$

2. 计算差分序列

  • 一阶差分（相邻项的差）：
    $$
    \Delta a_n: \quad 3-1=2, \quad 6-3=3, \quad 10-6=4, \quad 15-10=5
    $$
    即：
    $$
    \Delta a_n: \quad 2, \quad 3, \quad 4, \quad 5
    $$

  • 二阶差分（一阶差分的差）：
    $$
    \Delta^2 a_n: \quad 3-2=1, \quad 4-3=1, \quad 5-4=1
    $$
    二阶差分恒为 1，说明通项是 二次多项式。

3. 假设通项公式

设通项为二次多项式：
$$
a_n = An^2 + Bn + C
$$

4. 列方程组求解系数

利用前几项的值建立方程（通常从 ( n=0 ) 或 ( n=1 ) 开始，此处选择 ( n=1 ) 为起点）：
$$
\begin{cases}
a_1 = A(1)^2 + B(1) + C = 1 \
a_2 = A(2)^2 + B(2) + C = 3 \
a_3 = A(3)^2 + B(3) + C = 6 \
\end{cases}
$$
化简为：
$$
\begin{cases}
A + B + C = 1 \quad \text{(1)} \
4A + 2B + C = 3 \quad \text{(2)} \
9A + 3B + C = 6 \quad \text{(3)} \
\end{cases}
$$

5. 通项公式

解得：
$$
a_n = \frac{1}{2}n^2 + \frac{1}{2}n = \frac{n(n + 1)}{2}
$$

6. 验证

计算前几项：
$$
\begin{align*}
a_1 &= \frac{1 \times 2}{2} = 1 \
a_2 &= \frac{2 \times 3}{2} = 3 \
a_3 &= \frac{3 \times 4}{2} = 6 \
a_4 &= \frac{4 \times 5}{2} = 10 \
\end{align*}
$$
与原始序列一致，验证通过。

总结

  1. 差分法：通过计算差分序列判断多项式次数（二阶差分恒定 → 二次多项式）。
  2. 假设通项：设 ( a_n = An^2 + Bn + C )。
  3. 列方程：利用已知项建立方程组。
  4. 求解系数：消元法解出 ( A, B, C )。
  5. 验证：代入通项公式检查一致性。

最终通项公式

$$
\boxed{a_n = \frac{n(n + 1)}{2}}
$$

最后附上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;
const int N = 60;
const int p = 1e9 + 7; // p 是质数即可在qmi中使用

ll a[2030];
ll prefix[2030];

int main()
{
	// 这个问题，我们从数学角度来考虑
	// 我们知道每一层是多少个弹珠即可，推导过程见上述笔记
	// 因为这哥们有的弹珠比较多，我们开ll来存
	// 假设可以堆2024层算一下需要多少弹珠
	for(int i = 0;i <= 2027;i ++)
	{
		a[i] = i * (i + 1) / 2LL;	
	}
	// 预处理前缀和
	for(int i = 0;i <= 2027;i ++) prefix[i] = prefix[i - 1] + a[i];
	// 此时前缀和表示我们堆 n 层需要的弹珠数
	for(int i = 0;i <= 2024;i ++) 
	{
		if(prefix[i] >= 20230610)
		{
			 cout << i - 1; // 494是答案嗷
			 break;
		}
	}
	return 0;
}

哈希表模板题

image-20250330221822347

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <unordered_map>

using namespace std;
using ll = long long;
const int N = 10;

unordered_map<int, int> mp;

int main()
{
	int q; scanf("%d", &q);
	getchar(); // 吸收换行符
	while(q --)
	{
		char cho; int x;
		scanf("%c%d", &cho, &x);
		getchar(); // 吸收换行符
		if(cho == 'I') mp[x] ++;
		else if(cho == 'Q')
		{
            if(mp.find(x) != mp.end()) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
		}
	}
	return 0;
}

提供一些相关unordered_map的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 插入元素
unordered_map<string, int> mp;
mp["apple"] = 5;       // 直接赋值插入
mp.insert({"banana", 3}); // 使用insert插入

// 查找元素
if (mp.find("apple") != mp.end()) {
    cout << "Found, value: " << mp["apple"] << endl;
} else {
    cout << "Not found" << endl;
}

// 删除元素
mp.erase("apple");  // 删除键为"apple"的元素
mp.clear();         // 清空整个map

// 遍历元素（c++17专有，蓝桥杯不能用！！！！）
for (auto& [key, value] : mp) {  // C++17结构化绑定
    cout << key << ": " << value << endl;
}

// 遍历元素（传统方式）
for (auto it = mp.begin(); it != mp.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
}


// 统计键出现的次数（0或1，因为key唯一）
int count = mp.count("apple"); 

// 判断是否存在（C++20起）
if (mp.contains("apple")) {
    cout << "Exists" << endl;
}
我们在蓝桥杯就使用mp.find(x)即可，找不到返回mp.end();