创办网页,短视频seo客短,网站建设的 文献综述,潍坊网站设计公司目录 1、题目描述#xff1a;2、前言#xff1a;3、动态规划#xff08;bug)#xff1a;3、递归 剪枝#xff08;超时#xff09;#xff1a;4、数学#xff08;正解#xff09;#xff1a; 1、题目描述#xff1a; 小蓝有一个长度为 N 的数组 A [A0, A1,…, AN−… 目录 1、题目描述2、前言3、动态规划bug)3、递归 剪枝超时4、数学正解 1、题目描述 小蓝有一个长度为 N 的数组 A [A0, A1,…, AN−1]。现在小蓝想要从 A 对应的数组下标所构成的集合 I {0, 1, 2, . . . , N − 1} 中找出一个子集 R1那么 R1在 I 中的补集为 R2。记 S1∑r∈R1ArS2 ∑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]为例子 动态规划需要通过数组迭代对于元素i无非就是选与不选但当元素nums[i] 0的时候选了与没选是不确定的其无法从初始dp[0][0]迭代过来以有0的[0, 2]为例子 元素无法从dp[0][0]迭代出去形成了不通路。
值得一提的是优化代码错误更多
以[2, 2, 4]为例未优化与优化代码数组迭代过程如下 由于一维数组从后往前遍历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] );}
}好动态规划到此宣布破产 3、递归 剪枝超时
考试的时候就是用递归做的但是太傻比了退出条件不对我早就应该知道递归的每条路径就是一种遍历情况当时以及昨天我却在分枝上找答案太傻逼了答案应该在递归末尾节点找。 太傻比了之前用递归一直是在分支上找答答案跟本没啥意义再加上有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));elseSystem.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;}}超时是意料之内剪一下枝即可
优化代码
用二维数组可能会爆掉用大杀器其map应该就能拿下本题
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Text7 { public static MapString, 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 HashMapString, 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));elseSystem.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;}}看一下成果 我真是热烈的测了好几遍一个样要么测试的地方不行要么map查表和剪纸的部分正负得零反正麻了
算了不重要了最后再说一下为什么递归不会被0影响这从递归图可以看出来 递归每条路径都是一个选择情况即使两个0也可以清楚看出所有情况。 4、数学正解
详细解析在这里 2023年第十四届蓝桥杯JavaB组省赛真题及解析
