首页 > 编程语言 >2023蓝桥杯省赛C/C++组备赛

2023蓝桥杯省赛C/C++组备赛

时间：2023-04-04 09:45:34浏览次数：53  
标签：nums ++ cin 蓝桥 int vector 组备赛 省赛 dp

一、简单计算与模拟

1.成绩统计

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

int n; 

int main()
{
	double point;
	double jige = 0, youxiu = 0;
	cin>>n;
	for (int i = 0; i < n; ++i) {
		cin>>point;
		if (point >= 60) {
			jige++;
			if (point >= 85) youxiu++;	
		}
	}
	double j = jige / n + 0.005;
	double y = youxiu / n + 0.005;
	cout<<(int)(j * 100)<<"%"<<endl;
	cout<<(int)(y * 100)<<"%"<<endl;
    return 0;
}

2.排列字母

// 直接sort

3.成绩统计

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

vector<pair<int, int>> vec(10);
string n;
int main()
{
	vec[0] = {1189, 841};
	for (int i = 1; i <= 9; ++i) {
		int a = vec[i - 1].first, b = vec[i - 1].second;
		vec[i] = {b, a / 2};
	}
	cin>>n;
	int num = n[1] - '0';
	cout<<vec[num].first<<endl;
	cout<<vec[num].second;
    return 0;
}

二、枚举

1.特殊时间

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

int mon[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool checkMonthdate(int num) {
	int a = num / 100;
	int b = num % 100;
	if (a >= 1 && a <= 12 && b >= 1 && b <= mon[a - 1]) return true;
	return false;
}

bool checkTime(int num) {
	int a = num / 100;
	int b = num % 100;
	if (a >= 0 && a <= 23 && b >= 0 && b < 60) return true;
	return false; 
}

int main()
{
	int ans = 0;
	for (int i = 0; i <= 9; ++i) {
		for (int j = 0; j <= 9; ++j) {
			if (i == j) continue;
			int num1 = i * 1000 + i * 100 + i * 10 + j;
			int num2 = i * 1000 + i * 100 + j * 10 + i;
			int num3 = i * 1000 + j * 100 + i * 10 + i;
			int num4 = j * 1000 + i * 100 + i * 10 + i;
			int monNum = 0, timeNum = 0;
			if (checkMonthdate(num1)) monNum++; if (checkMonthdate(num2)) monNum++; if (checkMonthdate(num3)) monNum++; if (checkMonthdate(num4)) monNum++;
			if (checkTime(num1)) timeNum++; if (checkTime(num2)) timeNum++; if (checkTime(num3)) timeNum++; if (checkTime(num4)) timeNum++;
			ans += 4 * monNum * timeNum;
		}
	}
	cout<<ans;
    return 0;
}

2.卡片

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

vector<int> nums(10, 2021);

int main()
{
	int ans = 0;
	bool flag = false;
	for (int i = 1; i <= 20210; ++i) {
		int num = i;
		while (num) {
			int a = num % 10;
			if (nums[a] == 0) {
				flag = true;
				break;
			}
			nums[a]--;
			num /= 10;
		}
		if (flag) {
			cout<<i - 1;
			break;
		}
	}
    return 0;
}

3.约数

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

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

4.美丽的区间

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

int n, s;
int main()
{
	cin>>n>>s;
	int ans = n;
	vector<int> nums(n);
	for (int i = 0; i < n; ++i) {
		cin>>nums[i];
	}
	for (int i = 0; i < n; ++i) {
		int sum = 0;
		for (int j = i; j < n; ++j) {
			sum += nums[j];
			if (sum >= s) {
				ans = min(ans, j - i + 1);
				break;
			}
		}
	}
    cout<<ans;
	return 0;
}

三、递归与递推

1.数的计算

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

int n;

int P(int num) {
	if (num == 1) return 1;
	int sum = 0;
	for (int i = 1; i <= num / 2; ++i) {
		sum += P(i);
	}
	return sum + 1;
}

int main()
{
	cin>>n;
	cout<<P(n);
	return 0;
}


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

int dir[4] = {-2, -1, 1, 2};

struct node{
	string s;
	int d;
	node(){
	}
	node(string ss, int deep) {
		s = ss;
		d = deep;
	}
};


queue<node> qu;
set<string> se;



void BFS() {
	node p, q;
	while (!qu.empty()) {
		p = qu.front();
		int deep = p.d;
		if (p.s == "876543210"){
			cout<<deep<<endl;
			return ;
		}
		qu.pop();
		// 找到0元素索引
		int zero = 0; 
		for(zero; zero < 9; ++zero) {
			if (p.s[zero] == '0') break;
		}
		for (int i = 0; i <4; ++i) {
			string str = p.s;
			swap(str[zero], str[(zero + dir[i] + 9) % 9]);
			if (se.count(str) == 0) {
				se.insert(str);
				q.s = str;
				q.d = deep + 1;
				qu.push(q);
			}
		}
	}
}

int main()
{
	node b;
	b.s = "012345678";
	b.d = 0;
	qu.push(b);
	BFS();
	
	return 0;
}

五、二分查找

1.分巧克力

# include<bits/stdc++.h>

using namespace std; 

int n, k;
vector<pair<int, int>> nums;
//vector<pair<int, int>> nums(1e5 + 5);

// 若返回true，则代表还能增大 
bool check(int m) {
	int sum = 0;
	for (auto it : nums) {
		sum += (it.first / m) * (it.second / m);
	}
	if (sum >= k) return true;
	return false;
}

int main()
{
	cin>>n>>k;
	int h, w;
	for (int i = 0; i < n; ++i) {
		cin>>h>>w;
		nums.push_back({h, w});
	}
	
	int l = 0, r = 1e5;
	int mid;
	while (l < r) {
		mid = (l + r + 1) / 2;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout<<l<<endl;
	return 0;
}

六、贪心

1.翻硬币

# include<bits/stdc++.h>

using namespace std; 

string s, t; 

int main()
{
	cin>>s>>t;
	int n = s.size();
	int ans = 0;
	for (int i = 0; i < n - 1; ++i) {
		if (s[i] != t[i]) {
			if (s[i] == '*') s[i] = 'o';
			else s[i] = '*';
			if (s[i + 1] == '*') s[i + 1] = 'o';
			else s[i + 1] = '*';
			ans++;
		}
		if (s == t) {
			cout<<ans;
			break;
		}
	}
	return 0;
}

2.开心司机

# include<bits/stdc++.h>

using namespace std; 

struct node{
	double w, v, d;
};

bool static cmp(node& a, node& b) {
	return a.d > b.d;
}

int main()
{
	double n, w, d, value = 0;
	cin>>n>>w;
	vector<node> nums(n);
	for (int i = 0; i < n; ++i) {
		cin>>nums[i].w>>nums[i].v;
		nums[i].d = nums[i].v / nums[i].w;		//计算单价 
	}
	sort(nums.begin(), nums.end(), cmp);
	for (auto it : nums) {
		// 如果当前能全装进去 
		if (it.w < w) {
			w -= it.w;
			value += it.v;
		}
		else {
			value += it.d * w;
			break;
		}
	}
	printf("%.1f",value);
	return 0;
}

七、动态规划

1.最长蓝胚子序列

# include<bits/stdc++.h>

using namespace std; 


int main()
{
	string s, t;
	cin>>s>>t;
	string str = "";
	vector<string> ss, tt;
	for (char c : s) {
		if (c >= 'A' && c <='Z') {
			if (str != "") ss.emplace_back(str);
			str = "";
			str += c;
		}
		else str += c;
	}
	ss.emplace_back(str);
	str = "";
	for (char c : t) {
		if (c >= 'A' && c <='Z') {
			if (str != "")tt.emplace_back(str);
			str = "";
			str += c;
		}
		else str += c;
	}
	tt.emplace_back(str);
	int ls = ss.size(), lt = tt.size();
	vector<vector<int>> dp(ls + 1, vector<int>(lt + 1));
	for (int i = 1; i <= ls; ++i) {
		for (int j = 1; j <= lt; ++j) {
			if (ss[i - 1] == tt[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	} 
	cout<<dp[ls][lt];
	return 0;
}

2.合唱队列

# include<bits/stdc++.h>

using namespace std; 


int main()
{
	int n;
	cin>>n;
	vector<int> nums(n);
	vector<int> dp(n, 1);			//dp[i] 代表从第0~第i的最长子序列个数 
	vector<int> dp1(n, 1);
	for (int i = 0; i < n; ++i) {
		cin>>nums[i];
	}
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
		}
	} 
	for (int i = n - 2; i >= 0; --i) {
		for (int j = n - 1; j > i; --j) {
			if (nums[i] > nums[j]) dp1[i] = max(dp1[i], dp1[j] + 1);
		}
	}
	int res = 0;
	for (int i = 0; i < n; ++i) {
		dp[i] = dp[i] + dp1[i] - 1;
		res = max(res, dp[i]);
	}
	cout<<n - res;
	return 0;
}

3.小明的背包1（0-1背包）

#include <bits/stdc++.h>

using namespace std;



int main() {
	int n, v;
	cin>>n>>v;
	vector<int> weight(n), price(n), dp(v + 1);
	for (int i = 0; i < n; ++i) {
		cin>>weight[i]>>price[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = v; j >= weight[i]; j--) {
			dp[j] = max(dp[j], dp[j - weight[i]] + price[i]);
		}
	} 
	cout<<dp[v];
	return 0;
}

4.小明的背包2（完全背包）

#include <bits/stdc++.h>

using namespace std;



int main() {
	int n, v;
	cin>>n>>v;
	vector<int> weight(n), price(n), dp(v + 1);
	for (int i = 0; i < n; ++i) {
		cin>>weight[i]>>price[i];
	}
	//没有顺序要求
	//先遍历物品，再遍历背包 
	for (int i = 0; i < n; i++) {
		for (int j = weight[i]; j <= v; j++) {
			dp[j] = max(dp[j], dp[j - weight[i]] + price[i]);
		}
	} 
	cout<<dp[v];
	return 0;
}

5.最长公共子序列

#include <bits/stdc++.h>

using namespace std;



int main() {
	int n, m;
	cin>>n>>m;
	vector<int> a(n), b(m);
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for (int i = 0; i < n; ++i) cin>>a[i];
	for (int i = 0; i < m; ++i) cin>>b[i];
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
			else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}
	cout<<dp[n][m];
	
	return 0;
}

6.最长上升子序列

#include <bits/stdc++.h>

using namespace std;



int main() {
	int n, ans = 0;
	cin>>n;
	vector<int> nums(n);
	vector<int> dp(n, 1);
	for (int i = 0; i < n; ++i) cin>>nums[i];
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
		}	
		ans = max(ans, dp[i]);
	}
	cout<<ans;
	return 0;
}

十四、前缀和

image.png

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

int n;

int main()
{
	cin>>n;
	vector<long long> nums(n + 1, 0);
	vector<long long> sum(n + 1, 0);
	for (int i = 1; i <= n; ++i) {
		cin>>nums[i];
		sum[i] = sum[i - 1] + nums[i];
	}
	long long ans = 0;
	for (int i = 1; i < n; ++i) {
		ans += nums[i] * (sum[n] - sum[i]);
	}
	cout<<ans;
	return 0;
}

标签：nums,++,cin,蓝桥,int,vector,组备赛,省赛,dp
From： https://www.cnblogs.com/py-blog6/p/17285336.html

相关文章

  • (4.3)数组、对象及类数组对象，set的用法，正则表达式的常用方法，蓝桥杯备赛-(生成数组、数
    1.1数组、对象及类数组对象1.数组：​ 数组是有序的数据集合，其中的索引值从0开始递增，并且数组有length属性，可以获取数组内的元素个数，其中的值可以是任何的数组类型。2.对象：​ 对象是无序的是由一个或多个键值对组成的数据集合，对象没有length属性。3.伪数组(类数组对象)：​ ......
  • [2022年蓝桥杯C/C++ A组]个人做题记录
    碎碎念欸嘿，鸽了小半年去做了一些不喜欢的事情，但兜兜转转，还是acm最香捏求和题意求\(\sum_{i=1}^n\sum_{j=1}^na_i*a_j(i!=j)\)题解感觉是去年的时候笨人唯一做满分的题……经典前缀和，设\(sum[i]=\sum_{j=i}^na[j]\)，答案即为\(\sum_{i=1}^{n-1}a[i]*sum[i+1]\)#definein......
  • [每天例题]蓝桥杯 C语言 单词分析
    蓝桥杯C语言单词分析题目  题目要求1.寻找出现最多的字母和这个字母出现的次数。2.如果有多个字母出现的次数相等，输出字典序最小的那个。思路分析输入方法：方法一：1.可以通过数组来记录该单词，并为单词出现的每一个字母做上标记。2.可以采用for循环将字符串依次输......
  • 2018年第九届蓝桥杯—B组C/C++程序设计省赛解题-2明码
    .明码汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。一个字节可以存储8位信息，用32个字节就可以存一个汉字的字形了。把每个字节转为2进制表示，1表示墨迹，0表示底色。每行2个字节，一共16......
  • 洛谷 P8742 [蓝桥杯 2021 省 AB] 砝码称重
    经典01背包题首先介绍一下01背包，即一种DP问题，以放置物品为模型，每个物品只能放一次。其区分于完全背包（每个物品可以放无限多次），以及多重背包（每个物品有一个固定次数上限）。题中给出了$N$个砝码及每个砝码的质量，要求我们求出可以称出质量的种数。由此想到转化为01背包。......
  • 洛谷 P8762 [蓝桥杯 2021 国 ABC] 123 题解
    为什么可以使用前缀和，这里提供解释：初读题目，我们发现这个数列很迷惑，似乎不能使用数学方法来解。\[1,1,2,1,2,3,1,2,3,4,\cdots\]但是，我们可以想到数形结合的方式，我们将数列看作一个三角形，于是他变成了：\[1\]\[1,2\]\[1,2,3\]\[1,2,3,4\]\[\cdots\cdots\]于是本题变得好思......
  • 2022年第十三届蓝桥杯大赛软件类决赛C/C++大学B组真题
    2022年第十三届蓝桥杯大赛软件类决赛C/C++大学B组真题卡牌constintN=2e5+10;piia[N];intsum;intb[N];intn,m;voidsolve(){ intmx=1e18,ans=0; cin>>n>>m; for(inti=1;i<=n;i++)cin>>a[i].first,a[i].second=i; for(inti=1;i<=n;i++)cin>>b[i......
  • 2021 年蓝桥杯第一次省赛题目全解答
    做题链接：A组B组C组填空题卡片直接模拟。展开代码#include<bits/stdc++.h>usingll=longlong;intmain(){std::cin.tie(nullptr)->sync_with_stdio(f......
  • P8774 [蓝桥杯 2022 省 A] 爬树的甲壳虫（概率DP）
    [蓝桥杯2022省A]爬树的甲壳虫题目描述有一只甲壳虫想要爬上一颗高度为\(n\)的树，它一开始位于树根,高度为\(0\)，当它尝试从高度\(i-1\)爬到高度为\(i\)的位置......
  • 评选最佳品牌（第十届 省赛 T3）
      暴力吗，没什么技术含量。程序：#include<bits/stdc++.h>usingnamespacestd;intn,m;inta[101];strings[1002];intvis[101]={0};intmain(){ios::s......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99