• 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 hs=new HashMap();
    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 q=new PriorityQueue((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
    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.

  • 相关阅读:
    第四章redis配置文件的介绍
    服务器推送数据之SSE (server send event)
    一分钟搞定基于Saltstack集群批量安装部署Docker
    SpringMVC
    农业信息学复习资料
    [附源码]Python计算机毕业设计jspm郫县兼职信息系统
    php服装商城网站毕业设计源码241505
    如何查找无物流信息单号
    C# 查找[m,n]范围内的所有素数
    FFmpeg音视频复用器----为啥大多数视频只有一个视频流和一个音频流
  • 原文地址：https://blog.csdn.net/Xing_ke/article/details/136287962