第12届蓝桥杯java A组做题记录

A题：相乘

请添加图片描述

package JAVA12l蓝桥杯;
//求2021的逆元


public class 相乘 {
	static int mod = (int)1e9 + 7;
	public static long qmi(long a,int k,int p)
	{
		long res = 1;
		while(k > 0)
		{
			if(k % 2 == 1) res = res * a % p;
			a = a * a % p;
			k >>= 1;
		}
		return res;
	}
	public static void main(String[] args)
	{
		
		long ans = 999999999 * qmi(2021, mod - 2, mod) % mod;
		System.out.print(ans);
	}
}

B题：直线请添加图片描述

package JAVA12l蓝桥杯;
import java.util.*;
//直线：枚举斜率k和截距b，两者有一个不同的即不同
//如果 k = (y2 - y1)/(x2 - x1)
/// b = (x2 * y1 - x1 *x2)/(x2 - x1)
public class 直线 {
	static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    public static void main(String[] args) {
        Set<String> Set= new TreeSet<>();
        
        for (int x1 = 0; x1 < 20; x1++)
            for (int y1 = 0; y1 < 21; y1++)
                for (int x2 = 0; x2 < 20; x2++)
                    for (int y2 = 0; y2 < 21; y2++)
                        if (x1 != x2) {
                        	int a = y2 - y1;
                            int b = x1 - x2;
                            int c = x2 * y1 - x1 * y2;
                            int gcdn = gcd(a,gcd(b, c));
                            Set.add(a / gcdn +","+b / gcdn +"," + c/gcdn);
                        }

        System.out.println(Set.size() + 20);
    }
}

C题 货物摆放

请添加图片描述

package JAVA12l蓝桥杯;
//枚举因子,写该代码之前计算过了 因子数量130左右
//
public class 货物摆放 {
	static int N = 200,cnt  = 0;
	static long[] factor = new long[N];
	public static void main(String[] args)
	{
		long n = Long.parseLong("2021041820210418");
		for(int i = 1;i <= n / i;i++)
		{
			if(n % i == 0)
			{
				factor[++cnt] = i;
				if(i * i != n) factor[++cnt] = n /i;
				
			}
		}
		long res = 0;
		for(int i = 1;i <= cnt;i++)
			for(int j = 1;j <= cnt; j++)
				if(n % (factor[i] * factor[j]) == 0) res++;
		System.out.print(res);
	}
}

D题 路径

请添加图片描述

package JAVA12l蓝桥杯;

import java.util.*;

// 图的边初始化可以如果小于等于21 i* j /gcd（i，j) else  2e9；
// 最短路问题，用dijkstra 邻接矩阵版
// 最短路每次选一个当前为更新且距离源点最短的点
public class 路径 {
	static int N = 2030,dis[] = new int[N];
	static int[][] g = new int[N][N];
	static boolean[] st = new boolean[N];
	static int dijkstra(int n)
	{
		Arrays.fill(dis,(int) 2e9);
		dis[1] = 0;
		for(int i = 1;i <= n;i++)
		{
			int t = -1;
			for(int j = 1;j <= n;j++)
				if(!st[j] && (t == -1 || dis[t] > dis[j]))
					t = j;
		
			if(t == -1) break;
			st[t] = true;
			for(int j = 1;j <= n;j++)
				if(dis[j] > dis[t] + g[t][j])
					dis[j] = dis[t] + g[t][j];
		}
		return dis[n];
	}
	static int gcd(int a,int b)
	{
		if(b == 0) return a;
		else return gcd(b, a % b);
	}
	
	public static void main(String[] args)
	{
	
		for(int i = 1;i <= 2021;i++)
			for(int j = i + 1;j <= 2021;j++)
				if(j - i <= 21)
					g[i][j] = g[j][i] = i * j / gcd(i, j);
				else g[i][j] = g[j][i] =(int) 2e9;
		
		
		System.out.print(dijkstra(2021));
	}
}

E题 回路计算

请添加图片描述

package JAVA12l蓝桥杯;
import java.util.*;
// dp[i][j] 代表在i号教学楼，访问教学楼状态为j的不同方案
// 包括不包括 i？包括
// dp[i | 1 << k][j] = dp[i][j] += dp[i & ~(1 << (j - 1))][k];
// 最后将所有能dp[1 << 21) - 1]加起来，
public class 回路计算 {
    public static boolean[][] canGo = new boolean[22][22];
    public static long[][] dp = new long[1 << 21][22];
    
    public static void main(String[] args) {
        // 先填表判断哪些楼之间有路
        for (int i = 1; i <= 21; i++) {
            for (int j = 1; j <= 21; j++) {
                if (gcd(i, j) == 1) {
                    canGo[i][j] = true;
                }
            }
        }
        
        dp[1][1] = 1;
        for (int i = 1; i < (1 << 21); i++) {
            for (int j = 1; j <= 21; j++) {
                // j楼在i这种状态里 -- i的第j位是1
                if ((i & (1 << (j - 1))) > 0) {
                    // dp[i][j] += dp[状态i中的j去掉][从那些楼可以到j]
                    // dp[i][j] = 没有走j之前的状态能够走到j的所有可能的和
                    for (int k = 1; k <= 21; k++) {
                        if (canGo[k][j]) {
                            dp[i][j] += dp[i & ~(1 << (j - 1))][k];
                        }
                    }
                }
            }
        }
        
        long res = 0;
        for (int i = 1; i <= 21; i++) {
            res += dp[(1 << 21) - 1][i];
        }
        
        System.out.println(res);
    }
    
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

F题 最小砝码

请添加图片描述

package JAVA12l蓝桥杯;
// 找规律题 1个砝码表示最多的权重为1 两个最多表示的权重 1 3 
//3个最多表示的权重 为 1 3 9  
//4个最多表示的权重为 1 3 9 27
//可以看出来砝码权重分别为3^i ，用循环求出最少砝码
//3 ，4个如何找，可写程序砝码可表示的数
// 分别用三层循环和四层循环加一个check（)函数，枚举当前砝码最多表示的权重为多少选最大的参数

// 这题本质是考三进制，在有减，不取，加的操作下，n 个数位能表示 0～1+3 + 9 +3^n - 1的数
// 二进制在有不取，加的操作下最多能表表示0 ～ 2 ^n - 1的数
import java.util.Scanner;

public class 最小砝码 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        
        int sum = 0;
        
        for (int i = 0; ; i++) {
            int a = (int) Math.pow(3, i);
            sum += a;
            if (sum >= n) {
                System.out.println(i + 1);
                break;
            }
        }
    }
}

G题 左孩子右兄弟

请添加图片描述

package JAVA12l蓝桥杯;


import java.util.*; 
// dp[u] 代表本子树节点的最大高度 d[u] 代表儿子
// dp[u] = max(dp[son]) + d[u]
// 这里我们可以在dfs 中维护dp[u]
//这里的dp是不是多余的？
//是的，因为每个叶节点只被访问一次

public class 左孩子右兄弟 {
    static int N = (int)1e5 + 10,dp[] = new int[N];
    static int[] h = new int[N], ne = new int[N], e = new int[N], d = new int[N];
    static int idx = 0, ret = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Arrays.fill(h, -1);Arrays.fill(dp, -1);
        int n = sc.nextInt();
        for(int i = 2; i <= n; ++i) {
          int x = sc.nextInt();
          add(x, i); d[x]++;
        }

        System.out.println(dfs(1));
        sc.close();
    }

    public static void add(int a, int b) {
      e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
    }

    public static int dfs(int u) {
      if(dp[u] != -1) return dp[u];
      int ret = 0;
      for(int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        ret = Math.max(ret, dfs(j));
      }
      return dp[u] = ret + d[u];
    } 
}

试题H：异或数列

请添加图片描述

package JAVA12l蓝桥杯;

//从最高位考虑开始开始考虑
//1.若cnt为偶数，则该位所有数亦或的结果为0
//2.若当cnt为奇数时，最后一个1谁拿谁获胜
//2.1若0的个数为偶数（总数为奇数），a先手拿1必胜
//2.2若0的个数位奇数（总数为偶数），a先手拿1则b拿0，a先手拿0则b拿1b后手必胜！
//2.3特别的,需要特判cnt为1的情况先手必胜！
//3.若每一位的1个数都为偶数则平手
// 这里推荐俩题关于异或的 ：
// https://www.acwing.com/problem/content/145/ 
// https://atcoder.jp/contests/abc347/tasks/abc347_d

import java.util.Scanner;
public class 异或数列 {
	
	    static final int N = 2_000_005;
	    static int mod = 1_000_000_007;
	    static int n, m, k, S, T;
	    static int[] a = new int[N];

	    public static void main(String[] args) {
	        int tt = sc.nextInt();
	        while (tt-- > 0)
	            solve();
	        sc.close();
	    }

	    static void solve() {
	        n = sc.nextInt();
	        for (int i = 1; i <= n; ++i)
	            a[i] = sc.nextInt();
	        for (int i = 20; i >= 0; --i) {
	            int cnt = 0;
	            for (int j = 1; j <= n; ++j)
	                if (((a[j] >> i) & 1) == 1)
	                    cnt++;
	            if (cnt % 2 == 0)
	                continue;
	            if (n % 2 == 1 || cnt == 1) {
	                System.out.println(1);
	                return;
	            } else {
	                System.out.println(-1);
	                return;
	            }
	        }
	        System.out.println(0);
	    }

	    static Scanner sc = new Scanner(System.in);
}

请添加图片描述
60% 我的评价是见好就收


import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {//这么短的，可惜超时了4个用例
    Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        Integer[] arr=new Integer[n];
        for(int i=1;i<=n;i++) {
            arr[i-1]=i;
        }
        int [][] arr1=new int[m][2];
        for(int i=0;i<m;i++) {
          arr1[i][0]=sc.nextInt();
            arr1[i][1]=sc.nextInt();
        }
        sc.close();
        for(int i=0;i<m;i++) {
            if(arr1[i][0]==0) {
                Arrays.sort(arr,0,arr1[i][1],(a,b)->b-a);//降序
            }else{
                Arrays.sort(arr,arr1[i][1]-1,n);//升序
            }
        }
        for(int i=0;i<n;i++) {
            System.out.print(arr[i]+" ");
        }
        
    }
}

100% 这是写一小时调俩多小时的，考场最好见好就收，目前码力不足以在考场上解决此问题

package JAVA12l蓝桥杯;
import java.util.*;

public class 双向排序 {
    static final int N = 100005;
    static int n, m;
    static int[] sum0 = new int[N << 3];
    static int[] sum1 = new int[N << 3];
    static boolean[] all0 = new boolean[N << 3];
    static boolean[] all1 = new boolean[N << 3];
    static int[] a = new int[N];
    static int pos = 0;

    static void init(int l, int r, int p) {
        if (l == r) {
            sum0[p] = 0;
            sum1[p] = 1;
        } else {
            int mid = (l + r) >> 1, ps = p << 1;
            init(l, mid, ps);
            init(mid + 1, r, ps | 1);
            sum0[p] = sum0[ps] + sum0[ps | 1];
            sum1[p] = sum1[ps] + sum1[ps | 1];
        }
    }

    static void pd(int p) {
        if (all0[p]) {
            sum0[p] += sum1[p];
            sum1[p] = 0;
            all0[p] = false;
            all0[p << 1] = all0[p << 1 | 1] = true;
            all1[p << 1] = all1[p << 1 | 1] = false;
        } else if (all1[p]) {
            sum1[p] += sum0[p];
            sum0[p] = 0;
            all1[p] = false;
            all1[p << 1] = all1[p << 1 | 1] = true;
            all0[p << 1] = all0[p << 1 | 1] = false;
        }
    }

    static int chg1(int num, int l, int r, int p) {
        if (num == 0) return 0;
        pd(p);
        if (num >= sum1[p]) {
            all0[p] = true;
            return num - sum1[p];
        }
        sum1[p] -= num;
        sum0[p] += num;
        int mid = (l + r) >> 1, ps = p << 1;
        return chg1(chg1(num, l, mid, ps), mid + 1, r, ps | 1);
    }

    static int chg2(int num, int l, int r, int p) {
        if (num == 0) return 0;
        pd(p);
        if (num >= sum0[p]) {
            all1[p] = true;
            return num - sum0[p];
        }
        sum0[p] -= num;
        sum1[p] += num;
        int mid = (l + r) >> 1, ps = p << 1;
        return chg2(chg2(num, l, mid, ps), mid + 1, r, ps | 1);
    }

    static void upd(int l, int r, int p) {
        pd(p);
        if (l == r) {
            a[++pos] = sum1[p];
            return;
        }
        int mid = (l + r) >> 1, ps = p << 1;
        upd(l, mid, ps);
        upd(mid + 1, r, ps | 1);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        init(1, n, 1);
        int mid = 1;
        while (m-- > 0) {
            int p = scanner.nextInt();
            int q = scanner.nextInt();
            if (p == 0) {
                if (q >= mid) {
                    chg1(q - mid + 1, 1, n, 1);
                    mid = q + 1;
                }
            } else {
                if (q < mid) {
                    chg2(mid - q, 1, n, 1);
                    mid = q;
                }
            }
        }
        upd(1, n, 1);
        for (int i = n; i >= 1; --i) {
            if (a[i] == 0) System.out.print(i + " ");
        }
        for (int i = 1; i <= n; ++i) {
            if (a[i] != 0) System.out.print(i + " ");
        }
    }
}

请添加图片描述

占位

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/545986.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【黑马头条】-day09用户行为-点赞收藏关注阅读不喜欢-数据回显-精度丢失解决

【黑马头条】-day09用户行为-点赞收藏关注阅读不喜欢-数据回显-精度丢失解决

文章目录 1 long类型精度丢失问题1.1 解决1.2 导入jackson序列化工具1.3 自定义注解1.4 原理1.5 测试 2 用户行为要求3 创建微服务behavior3.1 微服务创建3.2 添加启动类3.3 创建bootstrap.yml3.4 在nacos中配置redis3.5 引入redis依赖3.6 更新minio 4 点赞4.1 实体类LikesBeha…
阅读更多...
机器人方向控制中应用的磁阻角度传感芯片

机器人方向控制中应用的磁阻角度传感芯片

磁阻传感器提供的输出信号几乎不受磁场变动、磁温度系数、磁传感器距离与位置变动影响&#xff0c;可以达到高准确度与高效能&#xff0c;因此相当适合各种要求严格的车用电子与工业控制的应用。所以它远比采用其它传感方法的器件更具有优势。 机器人的应用日渐广泛&#xff0…
阅读更多...
ChatGPT们写高考作文会发生什么？

ChatGPT们写高考作文会发生什么？

2023年的高考结束了&#xff0c;今年共有1291万考生参加了高考了&#xff0c;再次创造了历史参考人数之最。在高考中&#xff0c;要说什么最引人讨论&#xff0c;那高考作文当仁不让啊。今年随着ChatGPT的爆火&#xff0c;可谓是给文字工作者带来一大助力&#xff0c;如果让AI来…
阅读更多...
2024腾讯一道笔试题--大小写字母移动

2024腾讯一道笔试题--大小写字母移动

题目&#x1f357; 有一个字符数组,其中只有大写字母和小写字母,将小写字母移到前面, 大写字符移到后面,保持小写字母本身的顺序不变,大写字母本身的顺序不变, 注意,不要分配新的数组.(如:wCelOlME,变为wellCOME). 思路分析&#x1f357; 类似于冒泡排序&#xff0c;两两比较…
阅读更多...
将本地项目上传到Github

将本地项目上传到Github

首先安装git、创建github账号 1、创建一个新的仓库 2、创建SSH KEY。先看一下你C盘用户目录下有没有.ssh目录&#xff0c;有的话看下里面有没有id_rsa和id_rsa.pub这两个文件&#xff0c;有就跳到下一步&#xff0c;没有就通过下面命令创建。 ssh-keygen -t rsa -C "you…
阅读更多...
做测试，不会接口测试怎么能行？

做测试，不会接口测试怎么能行？

接口测试的测试点 功能测试&#xff1a;单接口功能、业务场景功能 性能测试&#xff1a;响应时长、错误率、吞吐量、服务器资源使用率 安全测试&#xff1a;敏感数据是否加密、SQL注入、其他 本篇文章以接口功能测试为主。 接口用例设计方法&#xff1a; 单接口测试用例设…
阅读更多...
如何通过Linux pciehp sysfs接口控制PCIe Slot电源状态？-3

如何通过Linux pciehp sysfs接口控制PCIe Slot电源状态？-3

pciehp sysfs接口电源控制与NVME驱动卸载的区别 从NVMe SSD设计本身而言&#xff0c;当通过pciehp sysfs接口对PCIe插槽执行Power Off操作时&#xff0c;由于NVMe SSD作为PCIe设备&#xff0c;其电源供应是直接依赖于所连接的PCIe插槽提供的。当插槽电源被关闭时&#xff0c;会…
阅读更多...
天工期刊投稿发表论文

天工期刊投稿发表论文

《天工》杂志是由国家新闻出版总署批准&#xff0c;山西省科学技术协会主管、山西科技新闻出版传媒有限责任公司主办的工艺美术类专业期刊。杂志以“宣传中华工艺美术技艺&#xff0c;传播前沿工艺美术新成果&#xff0c;挖掘工艺美术人才&#xff0c;助推工美品牌打造”为办刊…
阅读更多...
SpringCloudAlibaba之nacos的服务注册与发现

SpringCloudAlibaba之nacos的服务注册与发现

Nacos的服务注册与发现 照例放个妹子 本章节讲解nacos的服务注册与发现的简单使用 如图所示&#xff1a;按照图示搭建一个nacos作为服务注册中心的简单应用 创建provider服务提供者 创建nacos-discovery-provider模块引入依赖 <dependencies><dependency><…
阅读更多...
vue3从精通到入门4：diff算法的实现

vue3从精通到入门4：diff算法的实现

Vue 3 的 diff 算法相较于 Vue 2 有了一些改进和优化&#xff0c;主要是为了应对更复杂的组件结构和更高的性能需求。 以下是 Vue 3 diff 算法在处理列表更新时的大致步骤&#xff1a; 头头比较&#xff1a;首先&#xff0c;比较新旧列表的头节点&#xff08;即第一个节点&…
阅读更多...
聚观早报 | 哪吒L上市定档；iPhone 16最新高清渲染图

聚观早报 | 哪吒L上市定档；iPhone 16最新高清渲染图

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 4月10日消息 哪吒L上市定档 iPhone 16最新渲染图 华为太空表与问界M9联动 蔚来万里长城加电风景线正式贯通 Red…
阅读更多...
transformer架构详细详解

transformer架构详细详解

一、transformer的贡献 transformer架构的贡献&#xff1a;该架构只使用自注意力机制&#xff0c;没有使用RNN或卷积网络。且可以实现并行计算&#xff0c;加快模型训练速度。 &#xff08;将所有的循环层全部换成&#xff1a;multi-headed self-attention&#xff09; 二、t…
阅读更多...
leetcode刷题日记之全排列

leetcode刷题日记之全排列

题目描述 题目解释 这个题类似于之前做的某一道题&#xff0c;其实算法还是要追踪到树的深度遍历&#xff0c;相当于便利叶子节点的路径记录。不过递归的过程就相当于件数根据树进行遍历了。 代码如下 class Solution:def permute(self, nums: List[int]) -> List[List[i…
阅读更多...
fiddler常用操作汇总

fiddler常用操作汇总

1、过滤 2、查看数据包内容 3、弱网测试 弱网测试其实就是提前设置好一个值&#xff0c;在这个环境下进行测试就行了。 &#xff08;1&#xff09;进入定制规则页面&#xff1a; (2) 点击CtrlF调起搜索&#xff0c;在Find what 中输入300进行查找&#xff0c;更改上行、下行网…
阅读更多...
（四）C++自制植物大战僵尸游戏启动流程

（四）C++自制植物大战僵尸游戏启动流程

植物大战僵尸游戏开发教程专栏地址http://t.csdnimg.cn/ErelL 一、启动方式 鼠标左键单机VS2022上方工具栏中绿色三角按钮&#xff08;本地Windows调试器&#xff09;进行项目启动。第一次启动项目需要编译项目中所有代码文件&#xff0c;编译生成需要一定的时间。不同性能的电…
阅读更多...
LPRNet车牌识别模型训练及CCPD数据集预处理

LPRNet车牌识别模型训练及CCPD数据集预处理

LPRNet车牌识别模型训练及CCPD数据集预处理 1 LPRNet车牌识别模型训练 1.1 源码：LPRNet_Pytorch-master 源码官网：GitHub - sirius-ai/LPRNet_Pytorch: Pytorch Implementation For LPRNet, A High Performance And Lightweight License Plate Recognition Framework. 链…
阅读更多...
内网渗透-cobaltstrike之cs上线获取shell

内网渗透-cobaltstrike之cs上线获取shell

cobaltstrike之cs上线获取shell 文章目录 cobaltstrike之cs上线获取shell前言一、什么是cobaltstrike二、cs上线获取shell 1.环境搭建 CS安装windows连接 2. cs上线获取shell 总结 前言 一、什么是cobaltstrike CobaltStrike是一款渗透测试神器&#xff0c;被业界人称为CS神器…
阅读更多...
U盘有很多空间不见，看这篇能不能帮你解决

U盘有很多空间不见，看这篇能不能帮你解决

文章目录 概要整体架构流程 概要 我本来想在u盘上&#xff0c;安装一个ubuntu系统&#xff0c;结果一直安装失败&#xff0c;最后u盘空间还有好多没有了就是显示不出来了 整体架构流程 按住winx&#xff0c;会弹出以下界面 选择磁盘管理 然后会看到 这个就是你的u盘&…
阅读更多...
工业物联网网关

工业物联网网关

在数字化浪潮席卷全球的今天&#xff0c;工业物联网&#xff08;IIoT&#xff09;作为连接物理世界与数字世界的桥梁&#xff0c;正在逐渐改变传统工业的面貌。而作为IIoT的核心枢纽&#xff0c;工业物联网网关发挥着至关重要的作用。今天&#xff0c;我们就来深入了解一下工业…
阅读更多...
OpenHarmony实战开发-Axios获取解析网络数据。

OpenHarmony实战开发-Axios获取解析网络数据。

介绍 本示例介绍使用第三方库的Axios获取GBK格式的网络数据时&#xff0c;通过util实现GBK转换UTF-8格式。该场景多用于需要转换编码格式的应用。 效果图预览 使用说明 直接进入页面就可获取GBK格式的用户名信息并进行解码操作。 实现思路 1.使用第三方库Axios获取网络数据…
阅读更多...
最新文章

Copyright @ 2022~2023