蓝桥杯每日N题 (砝码称重)

这篇具有很好参考价值的文章主要介绍了蓝桥杯每日N题 (砝码称重)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

大家好 我是寸铁 希望这篇题解对你有用,麻烦动动手指点个赞或关注,感谢您的关注

不清楚蓝桥杯考什么的点点下方👇

考点秘籍

想背纯享模版的伙伴们点点下方👇

蓝桥杯省一你一定不能错过的模板大全(第一期)

蓝桥杯省一你一定不能错过的模板大全(第二期)

蓝桥杯省一你一定不能错过的模板大全(第三期)

蓝桥杯省一你一定不能错过的模板大全(第四期)!!!

想背注释模版的伙伴们点点下方👇

蓝桥杯必背第一期

蓝桥杯必背第二期

往期精彩回顾

蓝桥杯上岸每日N题 第一期(一)!!!

蓝桥杯上岸每日N题第一期(二)!!!

蓝桥杯上岸每日N题第一期(三)!!!

蓝桥杯上岸每日N题第二期(一)!!!

蓝桥杯上岸每日N题第三期(一)!!!

蓝桥杯上岸每日N题 第四期(最少刷题数)!!!

蓝桥杯上岸每日N题 第五期(山)!!!

蓝桥杯上岸每日N题 第六期(求阶乘)!!!

蓝桥杯上岸每日N题 第七期(小猫爬山)!!!

蓝桥杯上岸每日N题 第八期 (全球变暖)!!!

蓝桥杯每日N题 (消灭老鼠)

蓝桥杯每日N题(杨辉三角形)

操作系统期末题库 第九期(完结)

LeetCode Hot100 刷题(第三期)

idea创建SpringBoot项目报错解决方案

数据库SQL语句(期末冲刺)

想看JavaB组填空题的伙伴们点点下方 👇

填空题

竞赛干货

算法竞赛字符串常用操作大全

蓝桥杯上岸必刷!!!(模拟/枚举专题)

蓝桥杯上岸必背!!! (第三期 DP)

蓝桥杯上岸必背!!!(第四期DFS)

蓝桥杯上岸必背!!!(第五期BFS)

蓝桥杯上岸必背!!!(第六期树与图的遍历)

蓝桥杯上岸必背!!!(第七期 最短路算法)

蓝桥杯上岸必背!!!(第八期 简单数论)

蓝桥杯上岸必刷!!!(进制、数位专题)

蓝桥杯上岸考点清单 (冲刺版)!!!

蓝桥杯上岸必背模板 (纯享版)

分析

有限制的选择问题(背包问题)

观察题目样例解释:
可以将物品放在两边的天平中,可以将物品的重量看作+w-w
把物品分配在天平两边问题可以转换成从背包总容量m的背包中选取重量为+w-w的物品的方案数

状态表示:

集合:所有从前i件物品中选择重量为j的所有方案的集合
属性:集合是否非空(boolean值)

状态划分:

将集合划分为3类
情况1:不选当前第i件物品
情况2: 当前第i件物品且为 +w
情况3:当前第i件物品且为 -w

注意

由于可以选择-w的情况,数组下标会出现负数情况
所以,我们需要给下标加上一个偏移B,使数组下标不越界文章来源地址https://www.toymoban.com/news/detail-670741.html

Accode

import java.util.*;
public class Main{
	static int N=110,M=200010;
	static int a[]=new int[N];
	static boolean f[][]=new boolean[N][M];
	static int B=M/2;
	//考虑到边界,数组下标不能是负数
	//这里加上偏移量,将数组下标变为合法值
	public static void main(String []args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=0;
		for(int i=1;i<=n;i++) {
			a[i]=sc.nextInt();
			m+=a[i];
		}
		
		f[0][B]=true;
		//0件物品一件都不装是一种方案
		//记为true
		
		for(int i=1;i<=n;i++) {
		    //
			for(int j=-m;j<=m;j++) {
				f[i][j+B]=f[i-1][j+B];
				//从前i-1个物品中选,不选第i个物品
		if(j-a[i]>=-m)f[i][j+B]|=f[i-1][j-a[i]+B];
		//从前i-1个物品中选,且选了第i个物品+a[i]
		
	    if(j+a[i]<=m)f[i][j+B]|=f[i-1][j+a[i]+B];
		//从前i-1个物品中选,且选了第i个物品-a[i]	
			    
		//考虑到数组下标越界,数组下标不能是负数。
		//需要加上偏移量B
			}
		}
		
		int res=0;
		
		for(int j=1;j<=m;j++) {
			if(f[n][j+B])res++;
			//j+B是因为砝码总重为1e5
			//负数情况:-1e5+B>=0
			//负数情况也被包含进来,所以直接对f[n][j+B]判断即可。
			//检测所有从1-i个数中体积为j的集合是否非空
			//非空则加上1
			
		}
		
		System.out.println(res);
	}
}

到了这里,关于蓝桥杯每日N题 (砝码称重)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯上岸每日N题 (修剪灌木)

    爱丽丝要完成一项修剪灌木的工作。 有 N 棵灌木整齐的从左到右排成一排。 爱丽丝在每天傍晚会修剪一棵灌木,让灌木的高度变为 0 厘米。 爱丽丝修剪灌木的顺序是从最左侧的灌木开始,每天向右修剪一棵灌木。 当修剪了最右侧的灌木后,她会调转方向,下一天开始向左修

    2024年02月11日
    浏览(37)
  • 蓝桥杯上岸每日N题第一期(二)!!!

    这道题我们可以得出的是二分的结果是满足k块巧克力的最大边长是多少? 题目要求: 1.形状是正方形,边长是整数 2.大小相同 即要求边长均为x 我们就可以确保得到 边长一致的正方形 大小相同即分出的块数为整数, 向下取整!!! 得到能够凑出的整块巧克力 如果分出的块

    2024年02月16日
    浏览(39)
  • 蓝桥杯上岸每日N题 第一期(一)!!!

    2020 年春节期间,有一个特殊的日期引起了大家的注意:2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202,恰好是一个回文数。我们称这样的日期是回文日期。 有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同,因为不到

    2024年02月16日
    浏览(43)
  • 试题 历届真题 砝码称重【第十二届】【省赛】【B组】

    砝码称重 问题描述 你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。 请你计算一共可以称出多少种不同的正整数重量? 注意砝码可以放在天平两边。 输入格式 输入的第一行包含一个整数 N。 第二行包含 N 个整数:W1,W2,W3,⋅⋅⋅,WN。 输出格式 输出一个整数

    2023年04月08日
    浏览(38)
  • 蓝桥杯上岸每日N题 第七期(小猫爬山)!!!

    要尽可能减少花费--递归的分支尽可能少--优先考虑放重猫 优先考虑放重猫 ,需要从 大到小排个序 , 一直往下搜索,答案是唯一的。 放得下猫就 继续往该车往下加 放不下就再 另外开一辆放猫 分两个分支去放 开一辆继续放其他猫的为一个分支 开另一辆单独只放一只猫的为

    2024年02月14日
    浏览(71)
  • 蓝桥杯上岸每日N题 第八期 (全球变暖)!!!

    其中”上下左右”四个方向上 # 连在一起的一片陆地组成一座岛屿。 具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋 . ),它就会被淹没。 注:图中有3个岛屿,上下连续区域。 注:题中有一个岛屿全被淹没 观察一下:岛屿中陆地的数量和海洋的数量是

    2024年02月14日
    浏览(63)
  • Java算法 leetcode简单刷题记录6

    环和杆: https://leetcode.cn/problems/rings-and-rods/ 统计范围内的元音字符串数: https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/ 最长平衡子字符串: https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/ K 个元素的最大和: https://leetcode.cn/problems/maximum-sum-with-exa

    2024年01月24日
    浏览(46)
  • Java算法 leetcode简单刷题记录4

    买卖股票的最佳时机: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 笨办法: 记录当天的值及之后的最大值,相减得到利润; 所有的天都计算下,比较得到利润最大值; 会超时 记录过程中遇到的最低值,每当有利润大于0及大于上一个利润值的情况,赋值; 最小和分割:

    2024年01月23日
    浏览(45)
  • java数据结构与算法刷题-----LeetCode283. 移动零

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 双指针,用right和left两个指针,将非0元素,全部按顺序换到数组前面。left指向左边非0元素应该插入的位置,right找到非

    2024年01月21日
    浏览(49)
  • java数据结构与算法刷题-----LeetCode566. 重塑矩阵

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 代码:时间复杂度O(r*c).除题目要求外,算法本身没有需要额外空间,空间复杂度O(1) 从0开始算,一个3列n行矩阵中,每行就有3个元

    2024年01月21日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包