zhaoxiaoyun

2.3万

class Solution {
public boolean judgeSquareSum(int c) {
for (long a = 0; a * a <= c; a++) {
double b = Math.sqrt(c - a * a);
if (b == (int) b) {
return true;
}
}
return false;
}
}


import java.util.*;

public class Main {
static int N = 110;
static int[] l = new int[N];
static int[] r = new int[N];
static int[] v = new int[N];
static int[] q = new int[N];
static int n, k;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 0; i < n; i++) {
scanner.nextLine();
l[i] = scanner.nextInt();
r[i] = scanner.nextInt();
}
scanner.nextLine();
for (int i = 0; i < n; i++) {
q[i] = scanner.nextInt();
}
Arrays.sort(q, 0, n);
k = 0;
dfs(0);
bfs();
}

public static void dfs (int t) {
if (t == -1) return;
dfs(l[t]);
v[t] = q[k ++];
dfs(r[t]);
}

public static void bfs() {
queue.offer(0);
while (!queue.isEmpty()) {
int t = queue.poll();
System.out.print(v[t] + " ");
if (l[t] != -1)
queue.offer(l[t]);
if (r[t] != -1)
queue.offer(r[t]);
}
}
}



class Solution {
static int low, high, res;

public int rangeSumBST(TreeNode root, int low, int high) {
Solution.low = low;
Solution.high = high;
res = 0;
dfs(root);
return res;
}

public static void dfs (TreeNode root) {
if (root.val <= high && root.val >= low)
res += root.val;
if (root.left != null)
dfs(root.left);
if (root.right != null)
dfs(root.right);
}
}


import java.util.Scanner;

public class Main {
static int N = 100010;
static int[] w = new int[N];
static int n;
static int m;

static boolean check(double mid) {
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt += w[i] / mid;
}
return cnt >= m;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
scanner.nextLine();
for (int i = 0; i < n; i++) {
w[i] = scanner.nextInt();
}
double l = 0, r = 1e9;
while (r - l > 1e-4) {
double mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
System.out.println(String.format("%.2f", r));
}
}



class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
while (left < right) {
int mid = (left + right) / 2;
int need = 1, cur = 0;
for (int weight : weights) {
if (cur + weight > mid) {
++need;
cur = 0;
}
cur += weight;
}
if (need <= D) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}


class Solution {
static List<List<Integer>> res;
static List<Integer> temp;

public List<List<Integer>> findPath(TreeNode root, int sum) {
if (root == null)
return res;
dfs(root, sum);
return res;
}

public static void dfs (TreeNode root, int sum) {
if (root == null)
return;
if (root.left == null && root.right == null) {
if (sum == root.val) {
}
return;
}
dfs(root.left, sum - root.val);
dfs(root.right, sum - root.val);
temp.remove(temp.size() - 1);
}
}


class Solution {
static TreeNode dummy;
static TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
dummy = new TreeNode();
cur = dummy;
dfs(root);
return dummy.right;
}

public static void dfs (TreeNode root) {
if (root == null)
return;
dfs(root.left);
cur.right = root;
cur = cur.right;
cur.left = null;
dfs(root.right);
}
}


import java.util.*;

public class Main {
static int N = 1000010;
static int[] f = new int[N];
static int mod = (int) 1e9;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
f[0] = 1;
for (int i = 1; i <= n; i *= 2)
for (int j = 1; j <= n; j++)
if (j >= i)
f[j] = (f[j] + f[j - i]) % mod;
System.out.println(f[n]);
}
}


class Solution {
public int combinationSum4(int[] nums, int target) {
int n = nums.length;
int[] f = new int[target + 1];
f[0] = 1;
for (int i = 1; i <= target; i++) {
for (int j = 0; j < n; j++) {
if (nums[j] <= i)
f[i] += f[i - nums[j]];
}
}
return f[target];
}
}


import java.util.*;

public class Main {
static int N = 1010;
static int[] v = new int[N];
static int[] w = new int[N];
static int[][] f = new int[N][N];
static int n, m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i ++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
for (int i = n; i >= 1; i --) {
for (int j = 0; j <= m; j ++) {
f[i][j] = f[i + 1][j];
if (j >= v[i])
f[i][j] = Math.max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
}
int t = m;
for (int i = 1; i <= n; i ++) {
if (v[i] <= t && f[i][t] == f[i + 1][t - v[i]] + w[i]){
System.out.print(i + " ");
t -= v[i];
}
}
}
}