首页 > 其他分享 >蓝桥杯历年试题 砝码称重

蓝桥杯历年试题 砝码称重

时间:2024-04-09 19:32:54浏览次数:26  
标签:insert set int 历年试题 重量 蓝桥 循环 砝码 称重

看到这个题,自然而然想到用集合set来做,因为set本身就有去重的效果。

#include<bits/stdc++.h>
using namespace std;
int N;
int w;
set<int> s;
int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> w;
		vector<int> v(s.begin(), s.end());	//这里需要用vector来充当s的大小,因为下一步循环中要确保该次循环size的大小是不变的,循环内部就会增加s中的元素,会陷入死循环 
		for (int i = 0; i < v.size(); i++)	
		{
			s.insert(w + v[i]);
			if( abs(w - v[i])!=0 )	 	//注意取绝对值 
				s.insert(abs(w - v[i]));
		}
		s.insert(w);
	}
	cout << s.size() << endl;	// 集合 s 中装了不同的 “组合重量” 的数量即是答案
	return 0;
}

 这种方法是比较方便的

这个问题主要的两个值就是砝码的个数和能通过加减实现的重量,而前一步可以取到的重量对下一步也有影响,那么又想到用动态规划来解决

设置一个二维数组,第一个维度是指使用了前n个砝码,第二个维度指可以取到的重量,当然并不是所有重量都可以取到,于是设为bool类型,来判断能否取到。能取到的最大重量一定是所有砝码的质量总和,所以循环到其重量之和就可以。

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

int N;
int a[101];
bool ans[101][1000010];

int main()
{
    int count;
	cin >> N;
	int tol = 0;

	for (int i = 1; i <= N; i++)	
	{
		cin >> a[i];
		all += a[i];	//计算所有砝码总质量,用于循环次数
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= all; j++)	
			ans[i][j] = ans[i - 1][j];
//首先将i-1所能得到的j继承给i,因为能取到的质量只会在少一个砝码的情况下增加
		for (int j = 1; j <= all; j++) 
		{
			if (ans[i][j] == false)
			{
				if (a[i] == j)		// 新砝码本身的重量
					ans[i][j] = true;
				else if (ans[i-1][j + a[i]] == true)		
					ans[i][j] = true;
				else if (ans[i-1][abs(j - a[i])] == true)	// dp背包思想
					ans[i][j] = true;
			}
		}
	}
	for (int i = 1; i <= all; i++) 
	{
		if (ans[N][i] == true)		// 计数能取到的质量
			count++;
	}
	cout << count << endl;
	return 0;
}

标签:insert,set,int,历年试题,重量,蓝桥,循环,砝码,称重
From: https://blog.csdn.net/m0_71041937/article/details/137562563

相关文章

  • 【每周例题】蓝桥杯 C++ 多数
    多数元素题目多数元素思路分析一.第一个想法,暴力遍历,然后会发现容易超时,那么更进一步想:哈希表使用哈希表存储每个数出现的次数,即使用哈希映射(HashMap)来存储每个元素以及出现的次数。对于哈希映射中的每个键值对,键表示一个元素,值表示该元素出现的次数加入后,遍历所有键值对,......
  • 蓝桥杯备考随手记: Java 中常用的排序和查找方法
    1.排序方法Arrays.sort():用于对数组进行排序。它使用优化的快速排序算法来对数组进行排序。示例代码:int[]arr={5,2,8,1,6};Arrays.sort(arr);Collections.sort():用于对集合进行排序。它使用优化的归并排序算法来对集合进行排序。示例代码:List<Integer>list......
  • 蓝桥杯备考随手记: BigInteger 和 BigDecimal
    在Java中,BigInteger和BigDecimal是用来处理大整数和高精度浮点数的类,分别属于java.math包。下面分别介绍这两个类的特点、用途和常用方法:BigInteger:特点:BigInteger类表示任意精度的整数,可以处理比long型和int型更大范围的整数。BigInteger是不可变的(immutable)类,一......
  • P8794 [蓝桥杯 2022 国 A] 环境治理
    P8794[蓝桥杯2022国A]环境治理-洛谷|计算机科学教育新生态(luogu.com.cn)#include<iostream>usingnamespacestd;#definelllonglongconstintN=150;constintinf=0x7fffffff;intn,q;intd[N][N],l[N][N];intt[N][N];voidfloyd(){for(intk=......
  • 蓝桥杯学习日记
    目录方法二分+区间合并搜索与图论全排列n皇后问题走迷宫树的重心图中点的层次有向图的拓扑排序数学知识数论质数:在大于1的整数中,如果只包含1和本身这两个约数,就被称为质数,或者素数质数判定-试除法null质因数:将正整数表示为一连串的质因子相乘分解质因数-试除法筛质数约数约数......
  • 蓝桥杯2014国A-排列序数(待续)
    [蓝桥杯2014国A]排列序数题目描述如果用abcd这\(4\)个字母组成一个串,有\(4!=24\)种,如果把它们排个序,每个串都对应一个序号:abcd0abdc1acbd2acdb3adbc4adcb5bacd6badc7bcad8bcda9bdac10bdca11cabd......
  • 【蓝桥·算法双周赛 第 9 场 小白入门赛】字符迁移【算法赛】题解(字符串+模运算+差分)
    思路差分数组是一种特殊的数组,它的第iii个数定义为原数组的第ii......
  • 【蓝桥·算法双周赛 第 4 场 小白入门赛】自助餐【算法赛】题解(分支+字符串)
    思路首先定义一个整型变量n和一个长整型变量ans,其中n用于存放输入的字符串个数,ans则用于累计所有字符串对应的价格。在接收到n之后,进入一个循环,在循环中,每次接收一个字符串s,并根据s的首字母判断该字符串对应的餐盘种类,并将其价格累加到ans中。具体来说,如果......
  • 蓝桥杯2018年A组-付账问题
    0.题目题目描述几个人一起出去吃饭是常有的事。但在结帐的时候,常常会出现一些争执。现在有\(n\)个人出去吃饭,他们总共消费了\(S\)元。其中第\(i\)个人带了\(a_i\)元。幸运的是,所有人带的钱的总数是足够付账的,但现在问题来了:每个人分别要出多少钱呢?为了公平起见,我们希......
  • 第十五届蓝桥杯第三期模拟赛 《台阶问题》
    问题描述小蓝要上一个楼梯,楼梯共有n级台阶(即小蓝总共要走n级)。小蓝每一步可以走a级、b级或c级台阶。请问小蓝总共有多少种方案能正好走到楼梯顶端?输入格式输入的第一行包含一个整数n。第二行包含三个整数a,b,c。输出格式输出一行包含一个整数,表示答案。答......