菜菜ccEL

用户名：uq_98515084648

访问量：2828

签　名：

等　　级
排　　名	2089
经　　验	2463
参赛次数	0
文章发表	30
年　　龄	0
在职情况	学生
学　　校
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

阶乘计算python
浏览：112

高精度加法-python非要用列表
浏览：180

蓝桥杯基础练习VIP-2n皇后问题-python(递归+回溯)-------------------超详细注释
浏览：144

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

蓝桥杯2022年第十三届省赛真题-选数异或-暴力解法+以空间换时间

　　作者: 菜菜ccEL　　　　发表时间：2023-03-27 18:54:03 浏览：558　|　评论：1　

原题链接：蓝桥杯2022年第十三届省赛真题-选数异或

● 本题如果纯纯直接暴力逐个枚举遍历会超时，只能拿64分，所以可以**将已经判断过的区间保存起来加以利用**，以空间换时间，加快代码执行效率。
● 用两个List将已经枚举得到结果后的区间分别保存起来，分别保存为yesList，noList，分别存储区间中含有/不含有异或值为x的区间；
● 由分析可知：
1. 当**大区间中不存在**异或值等于x的两数，那么该大区间中包含的**小区间肯定不存在**了，此时可以**直接输出no**
2. 当**小区间中存在**异或值等于x的两数，那么包含该小区间的**大区间肯定存在**，此时可以**直接输出yes**

具体代码实现如下：
    
    import java.util.ArrayList;
    import java.util.Scanner;
    public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		
    		int n = sc.nextInt(); //长度为n的数列
    		int m = sc.nextInt(); //m个区间
    		int x = sc.nextInt(); //目标异或值
    		
    		int[] arr = new int[n]; //存储数列
    		for(int i=0;i<n;i++)
    			arr[i] = sc.nextInt();
    		int start,end; //定义输入的区间
    		boolean flag; //定义该区间是否存在
    		ArrayList<int[]> yesList = new ArrayList<>(); //保存满足要求的区间
    		ArrayList<int[]> noList = new ArrayList<>(); //保存不满足要求的区间
    		while(sc.hasNextInt()) { //当输入的没有数字时则停止
    			flag = false; //开始初始化为false
				// 输入区间头尾，对应数组下标所以要-1
    			start = sc.nextInt()-1; 
    			end = sc.nextInt()-1;
    			
				// 看本区间是否包含已经符合要求的小区间
    			for(int i=0;i<yesList.size();i++) {
    				if(start<=yesList.get(i)[0]&&end>=yesList.get(i)[1]) {
    					System.out.println("yes"); //如果包含小区间，直接输出yes
    					flag = true;
    					break;
    				}
    			}
    			if(flag) continue;
				// 看本区间是否被包含于不符合要求的大区间中
    			for(int i=0;i<noList.size();i++){
    				if(start>=noList.get(i)[0]&&end<=noList.get(i)[1]) {
    					System.out.println("no"); //如果是直接输出no
    					flag = true;
    					break;
    				}
    			}
    			if(flag) continue;
    			// 本区间和已经遍历过的区间没有包含关系，通过枚举得到结果
    			for(int i=start;i<end;i++) {
    				for(int j=i+1;j<=end;j++) {
    					if((arr[i]^arr[j])==x) {
    						System.out.println("yes");
    						yesList.add(new int[] {i,j}); // 保存答案
    						flag = true;
    						break;
    					}
    				}
    				if(flag) break;
    			}
    			if(!flag) {
    				System.out.println("no");
    				noList.add(new int[]{start,end}); // 保存答案
    			}
    		}
    	}
    }

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

ihccob3

在蓝桥杯官网只有40分

2023-03-30 23:13:08

菜菜ccEL

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言训练-亲密数（C++代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

蓝桥杯2022年第十三届省赛真题-选数异或-暴力解法+以空间换时间

评论区

精彩推荐

C二级辅导-同因查找（C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

关于float，double变量的几点说明

菜菜ccEL

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

C语言训练-亲密数 （C++代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

蓝桥杯2022年第十三届省赛真题-选数异或-暴力解法+以空间换时间

评论区

精彩推荐

C二级辅导-同因查找 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

关于float，double变量的几点说明

C二级辅导-阶乘数列（C语言代码）

C语言训练-亲密数（C++代码）

　　评论区

C二级辅导-同因查找（C语言代码）