devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）

作者：Gausst松鼠会 | 2024-02-29 18:55:49

赞

踩

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区分开）

  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.Arrays;
  4. import java.util.BitSet;
  5. import java.util.HashMap;
  6. import java.util.HashSet;
  7. import java.util.Iterator;
  8. import java.util.LinkedList;
  9. import java.util.PriorityQueue;
  10. import java.util.Queue;
  11. import java.util.Random;
  12. import java.util.Stack;
  13. import java.util.StringTokenizer;
  14. import java.util.Vector;
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22. public class Main{
  23. 	static long md=(long)998244353;
  24. 	static long Linf=Long.MAX_VALUE/2;
  25. 	static int inf=Integer.MAX_VALUE/2;
  26. 	
  27.  
  28. 	
  29. 	public static void main(String[] args) throws IOException{
  30. 		AReader input=new AReader();
  31. 	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  32. 	    
  33. 	    int n=input.nextInt();
  34. 	    int[] a=new int[n+1];
  35. 	    HashMap<Integer, Integer> hs=new HashMap<Integer, Integer>();
  36. 	    long ans=0;
  37. 	    for(int i=1;i<=n;++i) {
  38. 	    	a[i]=input.nextInt();
  39. 	    	if(a[i]==0) {
  40. 	    		continue;
  41. 	    	}
  42. 	    	int t=a[i];
  43. 	    	int y=(int)Math.sqrt(a[i]);
  44. 	    	while(y>0) {
  45. 	    		int z=y*y;
  46. 	    		if(t%z==0) {
  47. 	    			t/=z;
  48. 	    			break;
  49. 	    		}
  50. 	    		y--;
  51. 	    	}
  52. 	    	
  53. 	    	if(hs.get(t)!=null) {
  54. 	    		int p=hs.get(t);
  55. 	    		ans+=p;
  56. 	    		hs.put(t, p+1);
  57. 	    	}else {
  58. 	    		hs.put(t, 1);
  59. 	    	}
  60. 	    }
  61. 	    int zero=0;
  62. 	    for(int i=1;i<=n;++i) {
  63. 	    	if(a[i]==0) {
  64. 	    		ans+=i-1;
  65. 	    		zero++;
  66. 	    	}else {
  67. 	    		ans+=zero;
  68. 	    	}
  69. 	    }
  70. 	    out.print(ans);
  71. 	    
  72.  	    out.flush();
  73. 	    out.close();
  74. 	}
  75. 	//System.out.println();
  76. 	//out.println();
  77. 	//String o="abcdefghijklmnopqrstuvwxyz";
  78. 	//char[] op=o.toCharArray();
  79. 	static
  80. 	class AReader{ 
  81. 	    BufferedReader bf;
  82. 	    StringTokenizer st;
  83. 	    BufferedWriter bw;
  84.  
  85. 	    public AReader(){
  86. 	        bf=new BufferedReader(new InputStreamReader(System.in));
  87. 	        st=new StringTokenizer("");
  88. 	        bw=new BufferedWriter(new OutputStreamWriter(System.out));
  89. 	    }
  90. 	    public String nextLine() throws IOException{
  91. 	        return bf.readLine();
  92. 	    }
  93. 	    public String next() throws IOException{
  94. 	        while(!st.hasMoreTokens()){
  95. 	            st=new StringTokenizer(bf.readLine());
  96. 	        }
  97. 	        return st.nextToken();
  98. 	    }
  99. 	    public char nextChar() throws IOException{
  100. 	        //确定下一个token只有一个字符的时候再用
  101. 	        return next().charAt(0);
  102. 	    }
  103. 	    public int nextInt() throws IOException{
  104. 	        return Integer.parseInt(next());
  105. 	    }
  106. 	    public long nextLong() throws IOException{
  107. 	        return Long.parseLong(next());
  108. 	    }
  109. 	    public double nextDouble() throws IOException{
  110. 	        return Double.parseDouble(next());
  111. 	    }
  112. 	    public float nextFloat() throws IOException{
  113. 	        return Float.parseFloat(next());
  114. 	    }
  115. 	    public byte nextByte() throws IOException{
  116. 	        return Byte.parseByte(next());
  117. 	    }
  118. 	    public short nextShort() throws IOException{
  119. 	        return Short.parseShort(next());
  120. 	    }
  121. 	    public BigInteger nextBigInteger() throws IOException{
  122. 	        return new BigInteger(next());
  123. 	    }
  124. 	    public void println() throws IOException {
  125. 	        bw.newLine();
  126. 	    }
  127. 	    public void println(int[] arr) throws IOException{
  128. 	        for (int value : arr) {
  129. 	            bw.write(value + " ");
  130. 	        }
  131. 	        println();
  132. 	    }
  133. 	    public void println(int l, int r, int[] arr) throws IOException{
  134. 	        for (int i = l; i <= r; i ++) {
  135. 	            bw.write(arr[i] + " ");
  136. 	        }
  137. 	        println();
  138. 	    }
  139. 	    public void println(int a) throws IOException{
  140. 	        bw.write(String.valueOf(a));
  141. 	        bw.newLine();
  142. 	    }
  143. 	    public void print(int a) throws IOException{
  144. 	        bw.write(String.valueOf(a));
  145. 	    }
  146. 	    public void println(String a) throws IOException{
  147. 	        bw.write(a);
  148. 	        bw.newLine();
  149. 	    }
  150. 	    public void print(String a) throws IOException{
  151. 	        bw.write(a);
  152. 	    }
  153. 	    public void println(long a) throws IOException{
  154. 	        bw.write(String.valueOf(a));
  155. 	        bw.newLine();
  156. 	    }
  157. 	    public void print(long a) throws IOException{
  158. 	        bw.write(String.valueOf(a));
  159. 	    }
  160. 	    public void println(double a) throws IOException{
  161. 	        bw.write(String.valueOf(a));
  162. 	        bw.newLine();
  163. 	    }
  164. 	    public void print(double a) throws IOException{
  165. 	        bw.write(String.valueOf(a));
  166. 	    }
  167. 	    public void print(char a) throws IOException{
  168. 	        bw.write(String.valueOf(a));
  169. 	    }
  170. 	    public void println(char a) throws IOException{
  171. 	        bw.write(String.valueOf(a));
  172. 	        bw.newLine();
  173. 	    }
  174. 	}
  175. }
  176.

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的时刻
  • 由于有最晚出发时间的限制，所以不会有走环的情况
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.Arrays;
  4. import java.util.BitSet;
  5. import java.util.HashMap;
  6. import java.util.HashSet;
  7. import java.util.Iterator;
  8. import java.util.LinkedList;
  9. import java.util.PriorityQueue;
  10. import java.util.Queue;
  11. import java.util.Random;
  12. import java.util.Stack;
  13. import java.util.StringTokenizer;
  14. import java.util.Vector;
  15.  
  16.  
  17.  
  18.  
  19.  
  20.  
  21.  
  22. public class Main{
  23. 	static long md=(long)998244353;
  24. 	static long Linf=Long.MAX_VALUE/2;
  25. 	static int inf=Integer.MAX_VALUE/2;
  26. 	
  27. 	static
  28. 	class Edge{
  29. 		int fr,to,nxt;
  30. 		long l,d,k,c;
  31. 		public Edge(int u,int v,long L,long D,long K,long C) {
  32. 			fr=u;
  33. 			to=v;
  34. 			l=L;
  35. 			d=D;
  36. 			c=C;
  37. 			k=K;
  38. 		}
  39. 	}
  40. 	static Edge[] e;
  41. 	static int[] head;
  42. 	static int cnt;
  43. 	static void addEdge(int fr,int to,long l,long d,long k,long c) {
  44. 		cnt++;
  45. 		e[cnt]=new Edge(fr, to, l, d, k, c);
  46. 		e[cnt].nxt=head[fr];
  47. 		head[fr]=cnt;
  48. 	}
  49. 	
  50. 	static 
  51. 	class Node{
  52. 		int x;
  53. 		long dis;
  54. 		public Node(int X,long D) {
  55. 			x=X;
  56. 			dis=D;
  57. 		}
  58. 	}
  59. 	
  60. 	
  61. 	public static void main(String[] args) throws IOException{
  62. 		AReader input=new AReader();
  63. 	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  64. 	    int n=input.nextInt();
  65. 	    int m=input.nextInt();
  66. 	    e=new Edge[m+1];
  67. 	    head=new int[n+1];
  68. 	    cnt=0;
  69. 	    for(int i=1;i<=m;++i) {
  70. 	    	long l=input.nextLong();
  71. 	    	long d=input.nextLong();
  72. 	    	long k=input.nextLong();
  73. 	    	long c=input.nextLong();
  74. 	    	int u=input.nextInt();
  75. 	    	int v=input.nextInt();
  76. 	    	addEdge(v, u, l, d, k, c);
  77. 	    }
  78. 	    PriorityQueue<Node> q=new PriorityQueue<Node>((o1,o2)->{
  79. 	    	if(o2.dis-o1.dis>0)return 1;
  80. 	    	else if(o2.dis-o1.dis<0)return -1;
  81. 	    	else return 0;
  82. 	    });
  83. 	    
  84. 	    long[] dis=new long[n+1];
  85. 	    Arrays.fill(dis, -1);
  86. 	    dis[n]=Linf;
  87. 	    q.add(new Node(n, Linf));
  88. 	    while(!q.isEmpty()) {
  89. 	    	Node now=q.peek();
  90. 	    	q.poll();
  91. 	    	int x=now.x;
  92. 	    	if(x!=n&&dis[x]>=now.dis)continue;
  93. 	    	dis[x]=now.dis;
  94. 	    	for(int i=head[x];i>0;i=e[i].nxt) {
  95. 	    		int v=e[i].to;
  96. 	    		long c=e[i].c;
  97. 	    		long may=dis[x]-c;
  98. 	    		long l=e[i].l;
  99. 	    		long d=e[i].d;
  100. 	    		long k=e[i].k;
  101. 	    		if(may>=l) {
  102. 	    			may=l+Math.min((may-l)/d, k-1)*d;
  103. 	    			q.add(new Node(v, may));
  104. 	    		}
  105. 	    	}
  106. 	    }
  107. 	    for(int i=1;i<n;++i) {
  108. 	    	if(dis[i]==-1) {
  109. 	    		out.println("Unreachable");
  110. 	    	}else out.println(dis[i]);
  111. 	    }
  112. 	    
  113.  	    out.flush();
  114. 	    out.close();
  115. 	}
  116. 	//System.out.println();
  117. 	//out.println();
  118. 	static
  119. 	class AReader{ 
  120. 	    BufferedReader bf;
  121. 	    StringTokenizer st;
  122. 	    BufferedWriter bw;
  123.  
  124. 	    public AReader(){
  125. 	        bf=new BufferedReader(new InputStreamReader(System.in));
  126. 	        st=new StringTokenizer("");
  127. 	        bw=new BufferedWriter(new OutputStreamWriter(System.out));
  128. 	    }
  129. 	    public String nextLine() throws IOException{
  130. 	        return bf.readLine();
  131. 	    }
  132. 	    public String next() throws IOException{
  133. 	        while(!st.hasMoreTokens()){
  134. 	            st=new StringTokenizer(bf.readLine());
  135. 	        }
  136. 	        return st.nextToken();
  137. 	    }
  138. 	    public char nextChar() throws IOException{
  139. 	        //确定下一个token只有一个字符的时候再用
  140. 	        return next().charAt(0);
  141. 	    }
  142. 	    public int nextInt() throws IOException{
  143. 	        return Integer.parseInt(next());
  144. 	    }
  145. 	    public long nextLong() throws IOException{
  146. 	        return Long.parseLong(next());
  147. 	    }
  148. 	    public double nextDouble() throws IOException{
  149. 	        return Double.parseDouble(next());
  150. 	    }
  151. 	    public float nextFloat() throws IOException{
  152. 	        return Float.parseFloat(next());
  153. 	    }
  154. 	    public byte nextByte() throws IOException{
  155. 	        return Byte.parseByte(next());
  156. 	    }
  157. 	    public short nextShort() throws IOException{
  158. 	        return Short.parseShort(next());
  159. 	    }
  160. 	    public BigInteger nextBigInteger() throws IOException{
  161. 	        return new BigInteger(next());
  162. 	    }
  163. 	    public void println() throws IOException {
  164. 	        bw.newLine();
  165. 	    }
  166. 	    public void println(int[] arr) throws IOException{
  167. 	        for (int value : arr) {
  168. 	            bw.write(value + " ");
  169. 	        }
  170. 	        println();
  171. 	    }
  172. 	    public void println(int l, int r, int[] arr) throws IOException{
  173. 	        for (int i = l; i <= r; i ++) {
  174. 	            bw.write(arr[i] + " ");
  175. 	        }
  176. 	        println();
  177. 	    }
  178. 	    public void println(int a) throws IOException{
  179. 	        bw.write(String.valueOf(a));
  180. 	        bw.newLine();
  181. 	    }
  182. 	    public void print(int a) throws IOException{
  183. 	        bw.write(String.valueOf(a));
  184. 	    }
  185. 	    public void println(String a) throws IOException{
  186. 	        bw.write(a);
  187. 	        bw.newLine();
  188. 	    }
  189. 	    public void print(String a) throws IOException{
  190. 	        bw.write(a);
  191. 	    }
  192. 	    public void println(long a) throws IOException{
  193. 	        bw.write(String.valueOf(a));
  194. 	        bw.newLine();
  195. 	    }
  196. 	    public void print(long a) throws IOException{
  197. 	        bw.write(String.valueOf(a));
  198. 	    }
  199. 	    public void println(double a) throws IOException{
  200. 	        bw.write(String.valueOf(a));
  201. 	        bw.newLine();
  202. 	    }
  203. 	    public void print(double a) throws IOException{
  204. 	        bw.write(String.valueOf(a));
  205. 	    }
  206. 	    public void print(char a) throws IOException{
  207. 	        bw.write(String.valueOf(a));
  208. 	    }
  209. 	    public void println(char a) throws IOException{
  210. 	        bw.write(String.valueOf(a));
  211. 	        bw.newLine();
  212. 	    }
  213. 	}
  214. }
  215.  
  216.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/167620
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号