数组分割(2023省蓝桥杯)n种讨论 JAVA

这篇具有很好参考价值的文章主要介绍了数组分割(2023省蓝桥杯)n种讨论 JAVA。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1、题目描述:

小蓝有一个长度为 N 的数组 A = [A0, A1,…, AN−1]。现在小蓝想要从 A 对应的数组下标所构成的集合 I = {0, 1,
2, . . . , N − 1} 中找出一个子集 R1,那么 R1在 I 中的补集为 R2。记 S1=∑r∈R1Ar,S2
=∑r∈R2Ar,我们要求 S1 和 S2 均为偶数,请问在这种情况下共有多少种不同的 R1。当 R1 或 R2 为空集时我们将 S1 或 S2 视为 0。 输入格式 第一行一个整数 T,表示有 T 组数据。 接下来输入 T 组数据,每组数据包含两行:第一行一个整数 N,表示数组
A 的长度;第二行输入 N 个整数从左至右依次为 A0, A1, . . . , AN−1,相邻元素之间用空格分隔。 输出格式
对于每组数据,输出一行,包含一个整数表示答案,答案可能会很大,你需要将答案对1000000007 进行取模后输出。

样例输入:

2
2
6 6
2
1 6

样例输出:

4
0

[提示]
对于第一组数据,答案为 4。(注意:大括号内的数字表示元素在数组中的下标。)
R1 = {0}, R2 = {1};此时 S1 = A0 = 6 为偶数, S2 = A1 = 6 为偶数。
R1 = {1}, R2 = {0};此时 S1 = A1 = 6 为偶数, S2 = A0 = 6 为偶数。
R1 = {0, 1}, R2 = {};此时 S1 = A0 + A1 = 12 为偶数, S2 = 0 为偶数。
R1 = {}, R2 = {0, 1};此时 S1 = 0 为偶数, S2 = A0 + A1 = 12 为偶数。
对于第二组数据,无论怎么选择,都不满足条件,所以答案为 0。

对于 20% 的评测用例,1 ≤ N ≤ 10。
对于 40% 的评测用例,1 ≤ N ≤ 10^2。
对于 100% 的评测用例,1 ≤ T ≤ 10, 1 ≤ N ≤ 103 , 0 ≤ Ai ≤ 10^9。


2、前言:

这题考完蓝桥杯之后,自闭地看着答案整理过一遍,当时一度认为只能用数学方法做,而且当时也意识到自己见识太少,所以这俩月一直在埋头苦刷暂避锋芒。这不,这两天感觉自己又行了再来回顾本题,看看能否用新的算法做,以下是思考结果:


3、动态规划(bug):

最开始想到的就是用动态规划解决本题,虽然动态规划学的不熟,但是有思路就能写出来,本题还是不建议用动态规划解因为题目给的数据太大,非常容易爆数组。

1、本题与01背包有些许相似所以用01背包思想试解

2、dp[ i ][ j ] = n即:考虑前i个元素挑选出的元素和为j的方案数为n

3、初始化dp[i][0] = 1,考虑前i个元素,和为0的方案数为什么都不选1种

4、对于元素i无非选与不选两种,dp[i][j]=dp[i - 1][j] + dp[i - 1][j - nums[j]],前提是j >= nums[j]

5、最后取所有dp[len][j]且j是偶数的元素即可

错误代码1:

import java.util.*;

public class Text2{//继承父类Jframe,获取父类方法
	public static int mod = 1000000007;
    public static void main(String[] args) {
    	  Scanner sc = new Scanner(System.in);
    	  int n = sc.nextInt();
    	  for(int i = 0; i < n; i ++) {
    		  int len = sc.nextInt();
    		  int nums[] = new int[len + 1];
    		  for(int j = 1; j <= len; j ++) nums[j] = sc.nextInt();
    		   
    		  System.out.println(dfs(nums, len));
    		 
    	  }
    }
    
   public static int dfs(int nums[], int len) {
	  int num = 0;
	  for(int j = 1; j <= len; j ++) num = num + nums[j];
	  if(num % 2 != 0) return 0;
	  int dp[][]  = new int[len + 1][num + 1];
	  for(int i = 0; i <= len; i ++) dp[i][0] = 1;
	  int cnt = 1;
	  for(int i = 1; i <= len; i ++) {
		  for(int j = 1; j <= num; j ++) {
			  
			  dp[i][j] = dp[i - 1][j]; 
			  
			  if(j >= nums[i])
				  dp[i][j] = dp[i][j] + dp[i - 1][j - nums[i]];
			  
			  if(i == len && j % 2 == 0) {
				  cnt = cnt + dp[i][j];
			      System.out.println(i + " " + j + " " + dp[i][j]);
			  }
		  }
	  }
	  return cnt;
   }
    
}

想着用一维数组优化
错误代码1优化版:

import java.util.*;

public class Text1{//继承父类Jframe,获取父类方法
	public static int mod = 1000000007;
    public static void main(String[] args) {
    	  Scanner sc = new Scanner(System.in);
    	  int n = sc.nextInt();
    	  for(int i = 0; i < n; i ++) {
    		  int len = sc.nextInt();
    		  int nums[] = new int[len + 1];
    		  for(int j = 1; j <= len; j ++) nums[j] = sc.nextInt();
    		   
    		  System.out.println(dfs(nums, len));
    		 
    	  }
    }
    
   public static int dfs(int nums[], int len) {
	  int num = 0;
	  for(int j = 1; j <= len; j ++) num = num + nums[j];
	  if(num % 2 != 0) return 0;
	  int dp[]  = new int[num + 1];
	  dp[0] = 1;//考虑前0件元素得到0的方法有1个
	  int cnt = 1;
	  for(int j = 1; j <= len; j ++)//考虑前len个元素
		  for(int z = num; z >= nums[j]; z --)
			  {
			   dp[z] = dp[z] + dp[z - nums[j]];
			   if(j == len && z % 2 == 0 && (num - z) % 2 == 0) cnt = (cnt + dp[z]) % mod;
			  }
	  return cnt;
   }
    
}

解题思路:

为什么看着思路没问题题,但却还是错误代码呢,因为题目的数据含有0!!!

以正常没有0的[2, 4]为例子:

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展

动态规划需要通过数组迭代,对于元素i无非就是选与不选但当元素nums[i] = 0的时候,选了与没选是不确定的其无法从初始dp[0][0]迭代过来以有0的[0, 2]为例子:

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展
元素无法从dp[0][0]迭代出去,形成了不通路。

值得一提的是优化代码错误更多

以[2, 2, 4]为例,未优化与优化代码数组迭代过程如下:

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展

由于一维数组从后往前遍历dp[3][2]虽然符合条件但是无法从dp[2][2]迭代下来(2 < 4)

如果数据范围>0的话动态规划还是能在不爆数组的情况下都对的以下是产生随机数据的代码以及测试结果

代码:

import java.awt.print.Printable;
import java.util.*;

public class Text4{
	public static int mod = 1000000007;
    public static void main(String[] args) { 
    	      for(int i = 0; i < 1000; i ++) {
    	    	Scanner sc = new Scanner(System.in);
    		    int len = new Random().nextInt(1000) + 1;
//    	    	int len = sc.nextInt();
    		    int nums[] = new int[len + 1];
    		    for(int j = 1; j <= len; j ++) 
//    		    	nums[j] = sc.nextInt();
    		    	nums[j] = new Random().nextInt(1000) + 1;
    		    
    		    boolean flag =  (dfs(nums, len) == ddffs(nums, len));
    		    System.out.println(flag);
    		    if(!flag) {
    		    	print(nums, dfs(nums, len), ddffs(nums, len));
    		    	return;
    		    }
    	      }
    }
   public static int dfs(int nums[], int len) {
	   int num = 0;
		  for(int j = 1; j <= len; j ++) num = num + nums[j];
		  if(num % 2 != 0) return 0;
		  int dp[][]  = new int[len + 1][num + 1];
		  for(int i = 0; i <= len; i ++) dp[i][0] = 1;
		  int cnt = 1;
		  for(int i = 1; i <= len; i ++)
			  for(int j = 1; j <= num; j ++) {
				  
				  dp[i][j] = dp[i - 1][j]; 
				  if(j >= nums[i])
					  dp[i][j] = (dp[i][j] + dp[i - 1][j - nums[i]]) % mod;
				  
				  if(i == len && j % 2 == 0) cnt = (cnt + dp[i][j]) % mod;
			  }
		  
		  return cnt;
   }
   public static int ddffs(int a[], int m) {
	     int L = 0, J = 0; 
		 for(int i = 1; i <= m; i ++) 
			 if(a[i] % 2 == 0) L ++;
			 else J ++;
		 
		 if(J % 2 != 0) return 0;
		 else {
			 if(J == 0) J = 1;
			 return (int)(Math.pow(2, L) * Math.pow(2, J - 1) % mod);
		 }
 }
   public static void print(int a[], int b, int c) {
	   System.out.println(a.length - 1 + " " + b + " " + c);
	   for(int i = 1; i < a.length; i ++) System.out.print(a[i] + " ");
   }
}

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展

好动态规划到此宣布破产


3、递归 + 剪枝(超时):

考试的时候就是用递归做的,但是太傻比了,退出条件不对,我早就应该知道递归的每条路径就是一种遍历情况,当时以及昨天我却在分枝上找答案太傻逼了,答案应该在递归末尾节点找。

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展
太傻比了之前用递归一直是在分支上找答答案,跟本没啥意义,再加上有0的出现我一直以为本题不能用常规递归做,用什么分治思想之类的。。。刚在才醒悟过来,把递归图画了以下才醒悟,根本没必要那么复杂直接在递归末尾节点判断就行了

每个元素都是选与不选两种情况,从首节点到任意末尾节点都是一条路径,本题来说是选元素的其中一种选法,只需要判断满不满足题意就行了,太傻比了希望以后不要再犯这种错误了!

代码:

import java.util.Scanner;

public class Text6 {//继承父类Jframe,获取父类方法
	public static int mod = 1000000007;
    public static void main(String[] args) {
    	  Scanner sc = new Scanner(System.in);
    	  int m = sc.nextInt();
    	  for(int j = 0; j < m; j ++) {
    		  long sum = 0;
    	   int n = sc.nextInt();
    	   int nums[] = new int[n];
    	  
    	   for(int i = 0; i < n; i ++) {
    		   nums[i] = sc.nextInt();
    	       sum = sum + nums[i];
    	   }
    	   if(sum % 2 == 0)
    	     System.out.println(dfs(nums, n, 0, 0));
    	   else
    		   System.out.println(0);
    	  }
    }
    
   public static int dfs(int nums[], int len, int i, long sum) {
	    if(i == len) {
	    	if(sum % 2 == 0) return 1;
	    	return 0;
	    }
	    int choosethis = dfs(nums, len, i + 1, sum + nums[i]) % mod;
	    int notchoose = dfs(nums, len, i + 1, sum) % mod;
	    return (choosethis + notchoose) % mod;
   }
    
}

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展
超时是意料之内,剪一下枝即可

优化代码:

用二维数组可能会爆掉,用大杀器其map应该就能拿下本题:

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Text7 { 
	public static Map<String, Integer> map;
	public static int mod = 1000000007;
    public static void main(String[] args) {
    	  Scanner sc = new Scanner(System.in);
    	  int m = sc.nextInt();
    	  for(int j = 0; j < m; j ++) {
    		  map = new HashMap<String, Integer>();
    		  long sum = 0;
    	      int n = sc.nextInt();
    	      int nums[] = new int[n];
    	  
    	      for(int i = 0; i < n; i ++) {
    		     nums[i] = sc.nextInt();
    	         sum = sum + nums[i];
    	     }
    	   if(sum % 2 == 0)
    	     System.out.println(dfs(nums, n, 0, 0));
    	   else
    		   System.out.println(0);
    	  }
    }
    
   public static int dfs(int nums[], int len, int i, long sum) {
	    if(map.containsKey(i + " " + sum)) return map.get(i + " " + sum);
	    if(i == len) {
	    	if(sum % 2 == 0) return 1;
	    	return 0;
	    }
	    
	    int choosethis = dfs(nums, len, i + 1, sum + nums[i]) % mod;
	    int notchoose = dfs(nums, len, i + 1, sum) % mod;
	    map.put(i + " " + sum, (choosethis + notchoose) % mod);
	    return (choosethis + notchoose) % mod;
   }
    
}

看一下成果!

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展
我真是热烈的🐎测了好几遍一个样,要么测试的地方不行,要么map查表和剪纸的部分正负得零,反正麻了

算了不重要了,最后再说一下为什么递归不会被0影响,这从递归图可以看出来

数组分割(2023省蓝桥杯)n种讨论 JAVA,蓝桥杯,java,职场和发展
递归每条路径都是一个选择情况,即使两个0也可以清楚看出所有情况。


4、数学(正解):

详细解析在这里:
2023年第十四届蓝桥杯JavaB组省赛真题及解析文章来源地址https://www.toymoban.com/news/detail-671301.html

到了这里,关于数组分割(2023省蓝桥杯)n种讨论 JAVA的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 2023年第十四届蓝桥杯Java_大学B组真题

    【考生须知】 考试开始后,选手首先下载题目,并使用考场现场公布的解压密码解压试 题。 考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案,被浏览的答案允许拷贝。时间截止后,将无法继续提交或浏览答案。 对同一题目,选手可多次提交答案,以最后一次提

    2023年04月11日
    浏览(42)
  • 2023年第十四届蓝桥杯省赛Java C组题解

    只做出来(ACDFGH),挑几个出来,答案不一定正确,但自己测试通过了 求1~20230408的和 这里就直接套等差数列的求和公式,答案:204634714038436   【问题描述】         有一个长度为n的数组(n是10的倍数),每个数 Ai 都是区间[0,9]中的整数,小明发现数组里每种数出现的次数不太

    2023年04月26日
    浏览(38)
  • 2023第十四届蓝桥杯模拟赛第二期个人题解(Java实现)

    2023第十四届蓝桥杯校内模拟赛第三期个人题解(Java实现) 蓝桥杯真题——单词分析(Java实现) 这篇文章为个人题解,假如我写的解法有误,欢迎大家在评论区指正👏👏!!!希望这篇文章对你有帮助❤❤ 请找到一个大于 2022 的最小数,这个数转换成二进制之后,最低的

    2023年04月23日
    浏览(131)
  • 【华为OD统一考试B卷 | 100分】分割数组的最大差值(C++ Java JavaScript Python)

    在线OJ 已购买本专栏用户,请私信博主开通账号,在线刷题!!! 运行出现 Runtime Error 0Aborted,请忽略 华为OD统一考试A卷+B卷 新题库说明 2023年5月份,华为官方已经将的 2022/0223Q(1/2/3/4)统一修改为OD统一考试(A卷)和OD统一考试(B卷)。 你收到的链接上面会标注A卷还是B卷。

    2024年02月16日
    浏览(93)
  • 2023华为OD机试真题【计算数组中心位置】【Java Python】

    给你一个整数数组nums,请计算数组的中心位置。数组的中心位置是数组的一个下标, 其左侧所有元素相乘的积等于右侧所有元素相乘的积。数组第一个元素的左侧积为1,最后一个元素的右侧积为1。 如果数组有多个中心位置,应该返回最靠近左边的那一个,如果数组不存在

    2024年02月14日
    浏览(47)
  • 【华为OD机试 2023】 数组合并(C++ Java JavaScript Python)

    华为OD统一考试A卷+B卷 新题库说明 2023年5月份,华为官方已经将的 2022/0223Q(1/2/3/4)统一修改为OD统一考试(A卷)和OD统一考试(B卷)。 你收到的链接上面会标注A卷还是B卷。请注意:根据反馈,目前大部分收到的都是B卷。但是仍有概率抽到A卷。 A卷对应2023的新题库(2022Q4 2

    2023年04月12日
    浏览(39)
  • 【华为OD机试 2023】优雅子数组(C++ Java JavaScript Python)

    华为OD统一考试A卷+B卷 新题库说明 2023年5月份,华为官方已经将的 2022/0223Q(1/2/3/4)统一修改为OD统一考试(A卷)和OD统一考试(B卷)。 你收到的链接上面会标注A卷还是B卷。请注意:根据反馈,目前大部分收到的都是B卷。但是仍有概率抽到A卷。 A卷对应2023的新题库(2022Q4 2

    2023年04月12日
    浏览(40)
  • 2023华为OD机试真题【计算数组中心位置】【Java Python C++】

    给你一个整数数组nums,请计算数组的中心位置。数组的中心位置是数组的一个下标, 其左侧所有元素相乘的积等于右侧所有元素相乘的积。数组第一个元素的左侧积为1,最后一个元素的右侧积为1。 如果数组有多个中心位置,应该返回最靠近左边的那一个,如果数组不存在

    2024年02月15日
    浏览(47)
  • 【华为OD机试】分割数组的最大差值【2023 B卷|100分】

    【 华为OD机试】-真题 !!点这里!! 【 华为OD机试】真题考点分类 !!点这里  !! 题目描述 给定一个由若干整数组成的数组nums ,可以在数组内的任意位置进行分割, 将该数组分割成两个非空子数组(即左数组和右数组),分别对子数组求和得到两个值, 计算这两个值的差值,

    2024年02月10日
    浏览(39)
  • [职场] 会计学专业学什么 #其他#知识分享#职场发展

    会计学专业学什么 会计学专业属于工商管理学科下的一个二级学科,本专业培养具备财务、管理、经济、法律等方面的知识和能力,具有分析和解决财务、金融问题的基本能力,能在企、事业单位及政府部门从事会计实务以及教学、科研方面工作的工商管理学科高级专门人才

    2024年02月20日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包