第一题:简单的字符串分割,相信大家都a了
第二题:主要思想并查集,代码如下:
import java.util.*; public class Main { static int[] parent; static int[] size; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = sc.nextInt(); } while (m-- > 0){ int t = sc.nextInt(); int x = sc.nextInt()-1; int y = sc.nextInt()-1; if(t == 1){ if(!isConnected(x,y)){ System.out.println((find(x)+find(y)+2)^Math.abs(size[find(x)]-size[find(y)])); union(x,y); } }else { if(isConnected(x,y)) System.out.println("YES"); else System.out.println("NO"); } } } public static int find(int p){ while (p != parent[p]){ parent[p] = parent[parent[p]]; p = parent[p]; } return p; } public static boolean isConnected(int p,int q){ return find(p) == find(q); } public static void union(int p,int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; if(pRoot < qRoot){ parent[qRoot] = pRoot; size[pRoot] += size[qRoot]; }else { parent[pRoot] = qRoot; size[qRoot] += size[pRoot]; } } }
全部评论
(2) 回帖