544

2010
no_one

Mr.wyc
Foraino0267

clumsy
Andy2035

wangyc

Acwer

Enchanter
hyq121
Adam_
Chx

### 题目描述

1.初始化并查集的数组p ，for i in n :p[i] = i;
2.合并2个数，即merge（x,y）
3.查询&压缩路径 find(x)
4.用set保存连同块的数量
5.判断set的大小 等于1说明都连起来了

#### 样例

import java.util.*;
public class Main{
public static int[]p;
public static void main(String[]args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int n = in.nextInt();
p = new int[n+1];
for ( int i = 0; i < n; ++i ) {
p[i+1] = i+1;
}
int m = in.nextInt();
for ( int i = 0; i < m; ++i ) {
int x = in.nextInt();
int y = in.nextInt();
merge(x,y);
}
Set<Integer> set = new HashSet();
for ( int i = 1; i <= n; ++i ) {
set.add(find(i));
}

if ( set.size() == 1 ) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}

public static int find(int x) {
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}

public static void merge(int x ,int y ){
int x_new = find(x);
int y_new = find(y);
p[x_new] = y_new;
}

}



### 题目描述

#### 样例

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
in.nextLine();
String line = in.nextLine();
String[] nums = line.split(" ");
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(nums[i]);
}
int pre = arr[0];
int ans = 1;
int max = 1;
for ( int i = 1; i < n; ++i ) {
if (arr[i] <= 2*pre){
ans++;
}else {
ans = 1;
}
max = Math.max(max,ans);
pre = arr[i];
}

System.out.println(max);
}
}
}


### 题目描述

import java.util.*;

public class Main {
public static List<List<Integer>> edges = new ArrayList();
public static int ans = 0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
for ( int i = 0; i <= n; ++i ) {
edges.add(new ArrayList());
}
in.nextLine();
String line = in.nextLine();
String[] nums = line.split(" ");

for (int i = 0; i < n-1; i++) {
int a = Integer.parseInt(nums[i]);
edges.get(a).add(i+2);
}
int[] brr = new int[n+1];
for (int i = 1; i <= n; i++) {
brr[i] = in.nextInt();
// System.out.println(brr[i]);
}
//return ;
Queue<int[]> q = new ArrayDeque();
q.offer(new int[]{1,0});
while(!q.isEmpty()){
int[]t = q.poll();
int cur = t[0];
int color = t[1];
if (color != brr[cur]) {
ans++;
}
//System.out.println("cur:"+cur);
List<Integer>children = edges.get(cur);
for (int child:children){
int[]tmp =new int[2];
tmp[0] = child;
tmp[1] = brr[cur];
// System.out.println("child:"+child);
q.offer(tmp);
}
//System.out.println(ans);
//return;
}

System.out.println(ans);
}
}

// public static void dfs(int cur,int color,int[]brr) {
//     List<Integer> children = edges.get(cur);
//     if (brr[cur] == color) {
//         for( int child:children) {
//             dfs(child,color,brr);
//         }
//     }else {
//         ans++;
//         for(int child:children){
//             dfs(child,brr[cur],brr);
//         }
//     }
// }
}


Finally return the value of the sum. The result include one decimal place.
The definition of variance: S^2= ∑ (X-a) ^2 / (n-1), where X is the average, a is every number in the set, and n is the size of the set.
For example: There is a set [1,3,1] . We can divide it into [1,1] and [3], Then return the result:0.0
Please simply proof the correctness of your solution.

### 题目描述

#### 样例


import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int m = in.nextInt();
in.nextLine();
String line = in.nextLine();
String[] tmp = line.split(" ");
String line2 = in.nextLine();
String[] tmp2 = line2.split(" ");
int len = tmp.length;
int[] arr = new int[n];
int[] brr = new int[m];
int index = 0;
ArrayDeque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < len; ++i) {
int a = Integer.parseInt(tmp[i]);
int t = Integer.parseInt(tmp2[i]);
if (t == 1) {
deque.offer(a);
} else {
arr[index++] = a;
}
}
index = 0;
int pre = (int) deque.poll();
for (int i = 0; i < n; ++i) {
if (arr[i] < pre) {
brr[index]++;
} else {
// 找到pre
while(!deque.isEmpty()) {
int next = (int)deque.peek();
if (arr[i] > next) {
pre = next;
index++;
deque.poll();
}else {
break;
}
}
if (!deque.isEmpty()) {
int next = (int)deque.peek();
if (Math.abs(arr[i] - pre) <= Math.abs(arr[i] - next)) {
brr[index]++;
} else {
index++;
brr[index]++;
pre = (int) deque.poll();
}
}else {
brr[index]++;
}
}
}

StringBuffer ans = new StringBuffer();
for (int i = 0; i < m; ++i) {
if (i != m - 1) {
ans.append(brr[i] + " ");
} else {
ans.append(brr[i]);
}
}

System.out.println(ans.toString());
}
}
}



### 题目描述

#### 样例

import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner in = new Scanner(System.in);
while( in.hasNext()) {
int T = in.nextInt();
for ( int i = 0; i < T; ++i ) {
int t = in.nextInt();
if( t > 0 && t < 4) {
System.out.println("N");
}else{
int m = t*t -4*t;
double a = (Math.sqrt(m)+t)/2;
double b = (t-Math.sqrt(m))/2;
System.out.println("Y "+String.format("%.10f",a)+" "+String.format("%.10f",b));
}
}

}
}
}


### 题目描述

#### 样例

import java.util.*;
public class Main {
public static void main(String[]args) {
Scanner in = new Scanner(System.in);
while( in.hasNext()) {
int n = in.nextInt();
//int[]arr = new int[n+1];
ArrayDeque<Integer> d = new ArrayDeque();
for ( int i = 1; i <= n; ++i ) {
// arr[i] = in.nextInt();
int t = in.nextInt();
if(t == 0){
d.offer(i);
}
}
StringBuffer ans = new StringBuffer();
int zero = (int)d.poll();
for( int i = 1; i <= n; ++i ) {
int a = Math.abs(i - zero);
if(!d.isEmpty()) {
int sec = (int)d.peek();
a = Math.min(a,Math.abs(sec-i));
if(i== zero) {
zero = sec;
d.poll();
}
}
if(i == n) {
ans.append(a);
}else{
ans.append(a+" ");
}
}

System.out.println(ans.toString());
}
}
}


// package test;

import java.util.*;
public class Main {
public static int[]dx = {-1,0,1,0};
public static int[]dy = {0,-1,0,1};
public static void main(String[]args) {
Scanner in = new Scanner(System.in);
while( in.hasNext()) {
int n = in.nextInt();
int m = in.nextInt();
char[][]arr = new char[n][m];
//int ans = 0;
for ( int i = 0; i < n; ++i ) {
String a = in.next();
for ( int j = 0; j < m; ++j ) {
arr[i][j] = a.charAt(j);
}
}
for(int i = 0; i < n; ++i) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < m;++j ) {
if(arr[i][j] == '.') {
sb.append('.');
}else {
sb.append(find(arr,i,j));
}
}
System.out.println(sb.toString());
}

}
}

public static int find(char[][]arr,int x,int y){
int n = arr.length;
int m = arr[0].length;
ArrayDeque<int[]> d = new ArrayDeque();
d.offer(new int[]{x,y});
int ans = 0;
int[][]visit =  new int[n][m];
visit[x][y] = 1;
while(!d.isEmpty()) {
int[] tmp = d.poll();
// if (x == 2&& y == 1) {
//     System.out.println(Arrays.toString(tmp));
// }

ans++;
// ans %= 10;
for ( int i = 0; i < 4; ++i ) {
int x_new = tmp[0]+dx[i];
int y_new = tmp[1]+dy[i];
if (x_new <0 || y_new < 0 || x_new >=n || y_new>=m) {
continue;
}
if (arr[x_new][y_new] == '*') {
continue;
}
if(visit[x_new][y_new] == 1) {
continue;
}
d.offer(new int[]{x_new,y_new});
visit[x_new][y_new] = 1;
}

}
return ans % 10 ;
}
}



import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int n = in.nextInt();
long []sum = new long[n+1];
for ( int i = 0; i < n; ++i ) {
sum[i+1] = sum[i] + in.nextLong();
}
int l = 0;
int r = n;
long max = 0;
// 寻找1～n范围的区间数据
while ( l <= r) {
long sum1 = sum[l] - sum[0];
long sum3 = sum[n] - sum[r];
if (sum1 == sum3) {
max = Math.max(max,sum1);
l++;
r--;
}else if (sum1 < sum3) {
l++;
}else if (sum1 > sum3) {
r--;
}
}
System.out.println(max);
}
}

}