备战蓝桥杯 刷题笔记（第一期）

1，进制转换

九进制正整数 (2022)9转换成十进制等于多少？

#include<iostream>
#include<math.h>
using namespace std;
 
int to_ten(int a, int num)//将a进制转换为十进制
{
    int b = 0;//记录转换完成的十进制数
    int t;    //临时保存 i 数位上的数字
    int i = 0;//从零开始递增
    while (num != 0)
    {
        t = num % 10;//取个位数
        num /= 10;//num为int 抹除个位数
        b += t * pow(a, i);//b累加 系数t 乘以a的i次方
        i++;
    }
    return b;//返回答案
}
 
int to_other(int a, int num)//将十进制转换为a进制
{    //转化为 十进制的逆操作
    int t;//临时存储 a进制的一个数位上的数
    int i = 0;
    int b = 0;
    while (num != 0)
    {
        t = num % a;
        num /= a;
        b += t * pow(10, i);//转化
        i++;
    }
    return b;
}
 
int main()
{
    cout << to_other(9, 2022);
    return 0;
}

2，题目描述

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 a 道题目, 周六和周日每天做 b 道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 n 题?

输入格式

输入一行包含三个整数 a,b 和 n.

输出格式

输出一个整数代表天数。

样例输入

10 20 99

样例输出

8

#include<iostream>
using namespace std;
long long a, b, n;
//n的数据范围很大，用long long 防止越界
int main()
{
	cin >> a >> b >> n;
	
	/*由于n的数据范围很大，直接写while循环会超时，
	所以得先计算一下需要几周，在计算还需要几天*/
	long long zhou = n / (a * 5 + b * 2);//做题周数
	long long sheng = n % (a * 5 + b * 2);//剩余天数
	long long tian = zhou * 7;//答案
 
	long long t = 1;//控制一周的循环
	while (sheng > 0)
	{
		if (t % 6 == 0 || t % 7 == 0)//周六 周日
			sheng -= b;
		else
			sheng -= a;
		tian++;
		t++;//星期几 加一
	}
	cout << tian;
}

3，题目描述

小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。

给定 n, 请问小蓝的卡片至少有多少种?

输入格式

输入一行包含一个正整数表示 n 。

输出格式

输出一行包含一个整数, 表示答案。

样例输入

6

样例输出

3

#include<iostream>
using namespace std;
// a[i]表示i种卡牌最多可以不重复的数量
//得到状态转移方程a[i]=a[i-1]+i
int a[100000];
int main()
{
	int n;
	cin >> n;
	a[1] = 1;
	for (int i = 2; i < 100000; i++)
	{
		a[i] = a[i - 1] + i;
		if (a[i] >= n)
		{
			cout << i;
			return 0;
		}
	}
}

4，题目描述

给定一个只包含大写字母的字符串 S, 请你输出其中出现次数最多的字符。

如果有多个字母均出现了最多次, 按字母表顺序依次输出所有这些字母。

输入格式

一个只包含大写字母的字符串 S.

输出格式

若干个大写字母，代表答案。

#include<iostream>
#include<math.h>
int num[26];//大写字母转化为整数 对应位置记录出现次数 
using namespace std;
int main()
{
	string s;
	cin >> s;
	int big = 0;//最大出现次数
 
	for (int i = 0; i < s.length(); i++)
	{
		num[s[i] - 'A']++;//出现一次 相应位置加一
		big = max(big, num[s[i] - 'A']);//更新最大出现次数
	}
 
	for (int i = 0; i < 26; i++)
		if (num[i] == big)//寻找出现最多的
			cout << char(i + 65);//转化为字符输出
}

5，递推

给定 n 个整数 a1​,a2​,⋅⋅⋅,an​ ，求它们两两相乘再相加的和，即：

S=a1​⋅a2​+a1​⋅a3​+⋯+a1​⋅an​+a2​⋅a3​+⋯+an−2​⋅an−1​+an−2​⋅an​+an−1​⋅an​

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 a1​,a2​,⋯,an​。

输出格式

输出一个整数S，表示所求的和。请使用合适的数据类型进行运算

样例输入

4
1 3 6 9

样例输出

117

/*#include<iostream>//暴力法 超时！！
#include<vector>
using namespace std;
vector<int>arr;//输入的数组
int n;//输入的数字数量
long long ans;//保存答案
void fun(int k)
{
	if (k == n-1)
		return;//退出条件
	for (int i = k + 1; i < n; i++)
		ans += arr[i] * arr[k];//和i项后的每项求乘积，再求和
	fun(k + 1);//递归循环
}
int main()
{
	cin >> n;
	int t;
	for (int i = 0; i < n; i++)
	{
		cin >> t;//输入的数组
		arr.push_back(t);
	}
	fun(0);
	cout << ans;
}*/
 
//空间换时间
#include<iostream>
#include<math.h>
#include<vector>
long long a[200005], s[200005], ans;
using namespace std;
int main()
{
		/*当n = 4时
		ans = a1 * a2 + a1 * a3 + a1 * a4 + a2 * a3 + a2 * a4 + a3 * a4
		= a1 * (a2 + a3 + a4) + a2 * (a3 + a4) + a3 * a4
		就是 每个数 乘以 它之后的每个数之和 的和
		至于区间的数之和就是前缀和了*/
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];//传入a[i]
	s[1] = a[1];//赋值s1，便于后续的sn求值
	for (int i = 2; i <= n; i++)
		s[i] = s[i - 1] + a[i];//递推得到sn数组
	for (int i = 1; i <= n; i++)
		ans += a[i] * (s[n] - s[i]);//套入递推公式
	cout << ans;
}

6，二分查找

输入 n 个不超过 10的9次方 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1​,a2​,…,an​，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1。

输入格式

第一行 2 个整数 n 和m，表示数字个数和询问次数。

第二行 n 个整数，表示这些待查询的数字。

第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

输出格式

输出一行，m 个整数，以空格隔开，表示答案。

输入 

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

输出 

1 2 -1 

#include<iostream>//二分法
using namespace std;
 
long long arr[1000005];
long long n, m;
 
long long find(long long x)
{
	long long mid, l = 0, r = n, ans = -1;
	while (l < r)//左边界小于右边界就一直循环
	{
		mid = l + (r - l) / 2;//每次更新mid 防止越界
		if (arr[mid] >= x)
		{
			ans = mid;//ans记录x第一次出现的位置
			r = mid;//坐标值偏大，向左扩展 折半
		}
		else
			l = mid + 1;//坐标值偏小，向右扩展 折半
	}
	if (arr[ans] == x)//找到了
		return ans + 1;//因为数组第一个地址是0，不是1，所以加一
	return -1;//没找到
}
int main()
{
	cin >> n >> m;
	for (long long i = 0; i < n; i++)
		cin >> arr[i];
	int t;//每次要找的数据
	for (long long i = 0; i < m; i++)
	{
		cin >> t;
		cout << find(t) << " ";
	}
}

7，题目描述

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

输入：num = 14
输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

#include<iostream>//递推
#define maxn 1000001//数组最大容量
using namespace std;
int f[maxn];//记录第n项转化为0的次数
int fun(int n)
{
    f[0] = 0;//第一项为0，拿去后面的递推
    for (int i = 1; i <= n; i++)//求出0到目标项的所有项的转化次数
    {
        //f[i]的值只与i-1项或者i/2项相关联，递推求解
        if (i % 2 == 1)
            f[i] = f[i - 1] + 1;
        else
            f[i] = f[i / 2] + 1;
    }
    return f[n];
}
int main()
{
	int n;
	cin >> n;
	cout<<fun(n);
}

 8，零一背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数，N，V，，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

/*#include<iostream>//01背包问题
using namespace std;
int dp[1005][1005];
int v[1005], w[1005];
int main()               //未优化，内存大
{
    int n, m;
    cin >> n >> m;//物品数量和背包容积
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];//体积和价值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (j < v[i])//放不下了 等于上一阶段的（不拿）
                dp[i][j] = dp[i - 1][j];
            else//可以装下 考虑拿不拿
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }
    cout << dp[n][m];
}*/
 
#include<iostream>
using namespace std;
int dp[1000];
int main()        //优化后
{
    int n, m;//物品数量和背包容积
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int v, w;//体积和价值
        cin >> v >> w;//边输入 边处理
        for (int j = m; j >= v; j--)
            dp[j] = max(dp[j], dp[j - v] + w);
    }
    cout << dp[m] << endl;
}

 9，完全背包问题

有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

4 5
1 2
2 4
3 4
4 5
 

输出样例：

10

#include<iostream>//（完全背包）
using namespace std;
int dp[1000];
int main()        
{
    int n, m;//物品数量和背包容积
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int v, w;//体积和价值
        cin >> v >> w;//边输入 边处理
        for (int j = v; j <=m; j++)
            dp[j] = max(dp[j], dp[j - v] + w);
    }
    cout << dp[m] << endl;
}

10，题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。如：3*(5-2)+7 对应的后缀表达式为：3.5.2.-*7.+@。在该式中，`@` 为表达式的结束符号。`.` 为操作数的结束符号。

输入

输入一行一个字符串 s，表示后缀表达式。

输出

输出一个整数，表示表达式的值。

样例输入

3.5.2.-*7.+@

样例输出

16

#include<iostream>
#include<stack>
using namespace std;
stack<int>shu;
int main()
{
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '.')
			continue;
		else if (s[i] == '@')
			break;
 
		else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
		{
			int t1 = shu.top();
			shu.pop();
			int t2 = shu.top();
			shu.pop();
			if (s[i] == '+')
			{
				shu.push(t2 + t1);
			}
			else if (s[i] == '-')
			{
				shu.push(t2 - t1);
			}
			else if (s[i] == '*')
			{
				shu.push(t2 * t1);
			}
			else if (s[i] == '/')
			{
				shu.push(t2 / t1);
			}
		}
		else
			shu.push(s[i] - '0');
 
 
	}
	cout << shu.top();
 
}