HUAWEI Programming Contest 2024(AtCoder Beginner Contest 342)

D - Square Pair

题目大意

  • 给一长为n的数组a,问有多少对A_i,A_j(1\leq i< j\leq n),两者相乘为非负整数完全平方数

解题思路

  • 一个数除以其能整除的最大的完全平方数,看前面有多少个与其余数相同的数,两者乘积满足条件(已经是完全平方数的部分无用)
  • 对于0,特判(与%=0区分开)

import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();int[] a=new int[n+1];HashMap<Integer, Integer> hs=new HashMap<Integer, Integer>();long ans=0;for(int i=1;i<=n;++i) {a[i]=input.nextInt();if(a[i]==0) {continue;}int t=a[i];int y=(int)Math.sqrt(a[i]);while(y>0) {int z=y*y;if(t%z==0) {t/=z;break;}y--;}if(hs.get(t)!=null) {int p=hs.get(t);ans+=p;hs.put(t, p+1);}else {hs.put(t, 1);}}int zero=0;for(int i=1;i<=n;++i) {if(a[i]==0) {ans+=i-1;zero++;}else {ans+=zero;}}out.print(ans);out.flush();out.close();}//System.out.println();//out.println();//String o="abcdefghijklmnopqrstuvwxyz";//char[] op=o.toCharArray();staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}

E - Last Train

题目大意

  • n个点m条边,每条边有信息l,d,k,c

  • 表示l,l+d,l+2*d,\cdots ,l+(k-1)*d时刻有代价为c的路径

  • 1\rightarrow n-1每个点到n的最长距离

解题思路

  •  单一汇点,多源点,反向建图
  • 若当前时间为tim,则到下一个点的时间为may=tim-c
  • 则下一点最晚出发的时间为其等差数列中最大的小于may的时刻
  • 由于有最晚出发时间的限制,所以不会有走环的情况
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;public class Main{static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;staticclass Edge{int fr,to,nxt;long l,d,k,c;public Edge(int u,int v,long L,long D,long K,long C) {fr=u;to=v;l=L;d=D;c=C;k=K;}}static Edge[] e;static int[] head;static int cnt;static void addEdge(int fr,int to,long l,long d,long k,long c) {cnt++;e[cnt]=new Edge(fr, to, l, d, k, c);e[cnt].nxt=head[fr];head[fr]=cnt;}static class Node{int x;long dis;public Node(int X,long D) {x=X;dis=D;}}public static void main(String[] args) throws IOException{AReader input=new AReader();PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));int n=input.nextInt();int m=input.nextInt();e=new Edge[m+1];head=new int[n+1];cnt=0;for(int i=1;i<=m;++i) {long l=input.nextLong();long d=input.nextLong();long k=input.nextLong();long c=input.nextLong();int u=input.nextInt();int v=input.nextInt();addEdge(v, u, l, d, k, c);}PriorityQueue<Node> q=new PriorityQueue<Node>((o1,o2)->{if(o2.dis-o1.dis>0)return 1;else if(o2.dis-o1.dis<0)return -1;else return 0;});long[] dis=new long[n+1];Arrays.fill(dis, -1);dis[n]=Linf;q.add(new Node(n, Linf));while(!q.isEmpty()) {Node now=q.peek();q.poll();int x=now.x;if(x!=n&&dis[x]>=now.dis)continue;dis[x]=now.dis;for(int i=head[x];i>0;i=e[i].nxt) {int v=e[i].to;long c=e[i].c;long may=dis[x]-c;long l=e[i].l;long d=e[i].d;long k=e[i].k;if(may>=l) {may=l+Math.min((may-l)/d, k-1)*d;q.add(new Node(v, may));}}}for(int i=1;i<n;++i) {if(dis[i]==-1) {out.println("Unreachable");}else out.println(dis[i]);}out.flush();out.close();}//System.out.println();//out.println();staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

暂时的停更

最近因学业紧张&#xff0c;暂时停更&#xff0c;但还是会上线 我的专栏&#xff1a;C教程 感谢大家的支持

ChatGPT调教指南 | 咒语指南 | Prompts提示词教程(二)

在我们开始探索人工智能的世界时,了解如何与之有效沉浸交流是至关重要的。想象一下,你手中有一把钥匙,可以解锁与OpenAI的GPT模型沟通的无限可能。这把钥匙就是——正确的提示词(prompts)。无论你是AI领域的新手,还是希望优化与大型语言模型交流的老手,掌握如何精确使用…

SpringBoot3整合Swagger3,访问出现404错误问题(未解决)

秉承着能用就用新的的理念&#xff0c;在JDK、SpringBoot、SpringCloud版本的兼容性下&#xff0c;选择了Java17、SpringBoot3.0.2整合Swagger3。 代码编译一切正常&#xff0c;Swagger的Bean也能加载&#xff0c;到了最后访问前端页面swagger-ui的时候出现404。 根据网上资料…

【Git】Git命令的学习与总结

本文实践于 Learn Git Branching 这个有趣的 Git 学习网站。在该网站&#xff0c;可以使用 show command 命令展示所有可用命令。你也可以直接访问网站的sandbox&#xff0c;自由发挥。 一、本地篇 基础篇 git commit git commit将暂存区&#xff08;staging area&#xff…

【Flink精讲】Flink任务调度机制

Graph 的概念 Flink 中的执行图可以分成四层&#xff1a; StreamGraph -> JobGraph -> ExecutionGraph -> 物理执 行图。 StreamGraph&#xff1a;是根据用户通过 Stream API 编写的代码生成的最初的图。用来表示程序的拓扑结构。JobGraph&#xff1a; StreamGraph …

国家电网相关信息收集

国家电网有限公司招聘平台--首页 (sgcc.com.cn) 这是官方唯一招聘网站平台 国家电网最新组织机构&#xff08;总部、分部、27家省公司、40家直属单位&#xff09; - 知乎 (zhihu.com) 总部招聘&#xff1a; 我的评价&#xff1a;总部在北京&#xff0c;而且只招几个&#xff…

HTTP/HTTPS协议

什么是HTTP协议 HTTP被称为超文本传输协议(里面不仅仅可以是字符串,还可以是图片,特殊字符等),这是一种应用非常广泛的应用层协议. HTTP协议诞生于1991年,现在是最主流使用的一种应用层协议.它从诞生到现在为止迭代了多个版本. 但目前最主流使用的还是HTTP1.1和HTTP2.0. HTTP协…

产品渲染3D效果图一张多少钱,哪个平台更有性价比?

产品渲染3D效果图的价格受到多方面因素的影响&#xff0c;包括但不限于产品类型、渲染难度以及输出尺寸等。如果效果图需要后期处理&#xff0c;还有可能增加其他费用。接下来&#xff0c;我们来了解一下产品渲染效果图的费用情况。 1.产品渲染3D效果图一张多少钱&#xff1f; …

Fiddler工具 — 19.Fiddler抓包HTTPS请求(二)

5、查看证书是否安装成功 方式一&#xff1a; 点击Tools菜单 —> Options... —> HTTPS —> Actions 选择第三项&#xff1a;Open Windows Certificate Manager打开Windows证书管理器。 打开Windows证书管理器&#xff0c;选择操作—>查看证书&#xff0c;在搜索…

MySQL——基础内容

目录 第01章_数据库概述 关系型数据库(RDBMS)——表、关系模型 非关系型数据库(非RDBMS) 表、记录、字段 表的关联关系 一对一关联 一对多关系 多对多 自我引用 第02章_MySQL环境搭建 登录命令 常用命令 show databases; create database use 数据库名 show tables 第03章…

大概了解一下G1收集器

在上一篇文章中&#xff08;链接&#xff1a;大概了解一下CMS收集器&#xff09;我们提到&#xff0c;CMS是一种主要针对旧生代对象进行回收的收集器。与CMS不同&#xff0c;G1号称“全功能的垃圾收集器”&#xff0c;对初生代内存和旧生代内存均进行管理。鉴于此&#xff0c;这…

【Java程序设计】【C00291】基于Springboot的网上图书商城(有论文)

基于Springboot的网上图书商城&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的网上图书商城 本系统分为系统功能模块、管理员功能模块以及卖家功能模块。 系统功能模块&#xff1a;在系统首页可以查看首页、图书…

c++:vector的相关oj题(136. 只出现一次的数字、118. 杨辉三角、26. 删除有序数组中的重复项、JZ39 数组中出现次数超过一半的数字)

文章目录 1. 136. 只出现一次的数字题目详情代码(直接来异或&#xff09;思路 2. 118. 杨辉三角题目详情代码1思路代码2思路2 3. 26. 删除有序数组中的重复项题目详情代码思路 4. JZ39 数组中出现次数超过一半的数字题目详情代码1&#xff08;暴力&#xff09;思路1代码2&#…

Unity发布webgl获取浏览器的URL

Unity发布webgl获取浏览器的URL Unity发布webgl之后获取浏览器的url 在unity中创建文件夹Plugins&#xff0c;然后添加添加文件UnityGetBrowserURL.jslib var GetUrlFunc {//获取地址栏的URLStringReturnValueFunction: function () {var returnStr window.top.location.hre…

【Java程序员面试专栏 数据结构】三 高频面试算法题:栈和队列

一轮的算法训练完成后,对相关的题目有了一个初步理解了,接下来进行专题训练,以下这些题目就是汇总的高频题目,因为栈和队列这两哥们结构特性比较向对应,所以放到一篇Blog中集中练习 题目题干直接给出对应博客链接,这里只给出简单思路、代码实现、复杂度分析 题目关键字…

Less预处理器教程

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/frontlearningNotes 觉得有帮助的同学&#xff0c;可以点心心支持一下哈 一、Less介绍 less官方文档 lesscss.org/ less中文文档 less.bootcss.com/ less是一种css预处理器&#xff0c;它扩展了css语言&#xff0c…

OpenCV开发笔记(七十五):相机标定矫正中使用remap重映射进行畸变矫正

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://blog.csdn.net/qq21497936/article/details/136293833 各位读者&#xff0c;知识无穷而人力有穷&#xff0c;要么改需求&#xff0c;要么找专业人士&#xff0c;要么自己研究 红胖子(红模仿…

Day15-集合-迭代器-课后练习-参考答案

文章目录 Day15_课后练习泛型练习题第1题第2题第3题第4题第5题 集合练习题第1题第2题 Day15_课后练习 泛型练习题 第1题 案例&#xff1a;有如下四个学生的成绩&#xff1a; &#xff08;1&#xff09;用Comparable接口对下列四位同学的成绩做降序排序&#xff0c;如果成绩一…

SQL Server 开发环境配置教程(SSMS+SQL Prompt)

背景 记录一下 SQL Server 常用开发软件 体验了各种数据库IDE(DBeaver、Navicat、DataGrip)之后综合下来还是感觉 SSMSSQL Prompt 对于 SQL Server 最好用&#xff0c;所以在此记录一下配置过程 数据库可视化管理工具SSMS 官方下载地址&#xff1a; https://learn.microsoft…

【Simulink系列】——动态系统仿真 之 混合系统

声明&#xff1a;本系列博客参考有关专业书籍&#xff0c;截图均为自己实操&#xff0c;仅供交流学习&#xff01; 一、混合系统概述 由不同类型系统共同构成的系统称为混合系统&#xff01;仿真时必须考虑连续信号和离散信号的采样匹配问题&#xff0c;一般使用变步长连续求…