Skip to content

Commit 5ba8ac8

Browse files
OneCodeMonkeyOneCodeMonkey
committed
update
1 parent 499a6c7 commit 5ba8ac8

7 files changed

+249
-0
lines changed

‎codeForces/Codeforces_0165A_Supercentral_Point.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
// Time: 654 ms
2+
// Memory: 1100 KB
3+
// Map.
4+
// T:O(n), S:O(n)
5+
//
6+
import java.util.ArrayList;
7+
import java.util.Collections;
8+
import java.util.HashMap;
9+
import java.util.List;
10+
import java.util.Scanner;
11+
12+
public class Codeforces_0165A_Supercentral_Point {
13+
public static void main(String[] args) {
14+
Scanner sc = new Scanner(System.in);
15+
int n = sc.nextInt(), ret = 0;
16+
HashMap<Integer, List<Integer>> xAxios = new HashMap<>(), yAxios = new HashMap<>();
17+
int[][] points = new int[n][2];
18+
for (int i = 0; i < n; i++) {
19+
int x = sc.nextInt(), y = sc.nextInt();
20+
if (!xAxios.containsKey(y)) {
21+
xAxios.put(y, new ArrayList<>());
22+
}
23+
xAxios.get(y).add(x);
24+
if (!yAxios.containsKey(x)) {
25+
yAxios.put(x, new ArrayList<>());
26+
}
27+
yAxios.get(x).add(y);
28+
points[i] = new int[]{x, y};
29+
}
30+
for (int key : xAxios.keySet()) {
31+
Collections.sort(xAxios.get(key));
32+
}
33+
for (int key : yAxios.keySet()) {
34+
Collections.sort(yAxios.get(key));
35+
}
36+
for (int i = 0; i < n; i++) {
37+
int x = points[i][0], y = points[i][1];
38+
List<Integer> yLine = yAxios.get(x), xLine = xAxios.get(y);
39+
boolean y1 = false, y2 = false, x1 = false, x2 = false;
40+
if (yLine.get(0) < y) {
41+
y1 = true;
42+
}
43+
if (yLine.get(yLine.size() - 1) > y) {
44+
y2 = true;
45+
}
46+
if (xLine.get(0) < x) {
47+
x1 = true;
48+
}
49+
if (xLine.get(xLine.size() - 1) > x) {
50+
x2 = true;
51+
}
52+
53+
if (x1 && x2 && y1 && y2) {
54+
ret++;
55+
}
56+
}
57+
58+
System.out.println(ret);
59+
}
60+
}

‎codeForces/Codeforces_0610A_Pasha_and_Stick.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
// Time: 312 ms
2+
// Memory: 1100 KB
3+
// .
4+
// T:O(1), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_0610A_Pasha_and_Stick {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int n = sc.nextInt(), ret = 0;
12+
if (n >= 6 && n % 2 == 0) {
13+
ret = n % 4 == 0 ? (n / 4 - 1) : n / 4;
14+
}
15+
16+
System.out.println(ret);
17+
}
18+
}

‎codeForces/Codeforces_1195C_Basketball_Exercise.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
// Time: 592 ms
2+
// Memory: 800 KB
3+
// DP.
4+
// T:O(n), S:O(n)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1195C_Basketball_Exercise {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int n = sc.nextInt();
12+
int[] arr1 = new int[n], arr2 = new int[n];
13+
for (int i = 0; i < n; i++) {
14+
arr1[i] = sc.nextInt();
15+
}
16+
for (int i = 0; i < n; i++) {
17+
arr2[i] = sc.nextInt();
18+
}
19+
long[] dp1 = new long[n + 1], dp2 = new long[n + 1];
20+
dp1[1] = arr1[0];
21+
dp2[1] = arr2[0];
22+
for (int i = 2; i <= n; i++) {
23+
long max1 = Math.max(dp1[i - 2], dp2[i - 2]);
24+
dp1[i] = Math.max(dp2[i - 1] + arr1[i - 1], max1 + arr1[i - 1]);
25+
dp2[i] = Math.max(dp1[i - 1] + arr2[i - 1], max1 + arr2[i - 1]);
26+
}
27+
28+
System.out.println(Math.max(dp1[n], dp2[n]));
29+
}
30+
}
31+

‎codeForces/Codeforces_1342B_Binary_Period.java‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
// Time: 249 ms
2+
// Memory: 1000 KB
3+
// Notice it is subsequence, so simple construct a 2-period string.
4+
// T:O(sum(ni)), S:O(max(ni))
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1342B_Binary_Period {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
String s = sc.next();
14+
int len = s.length(), countOne = 0;
15+
for (char c : s.toCharArray()) {
16+
if (c == '1') {
17+
countOne++;
18+
}
19+
}
20+
if (countOne == 0 || countOne == len) {
21+
System.out.println(s);
22+
} else {
23+
StringBuilder ret = new StringBuilder();
24+
if (s.charAt(0) == '0') {
25+
ret.append('0').append("10".repeat(len - 1));
26+
} else {
27+
ret.append('1').append("01".repeat(len - 1));
28+
}
29+
System.out.println(ret);
30+
}
31+
}
32+
}
33+
}

‎codeForces/Codeforces_1370B_GCD_Compression.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
// Time: 389 ms
2+
// Memory: 1200 KB
3+
// .
4+
// T:O(sum(ni)), S:O(max(ni))
5+
//
6+
import java.util.ArrayList;
7+
import java.util.List;
8+
import java.util.Scanner;
9+
10+
public class Codeforces_1370B_GCD_Compression {
11+
public static void main(String[] args) {
12+
Scanner sc = new Scanner(System.in);
13+
int t = sc.nextInt();
14+
for (int i = 0; i < t; i++) {
15+
int n = sc.nextInt();
16+
List<Integer> oddIndex = new ArrayList<>(), evenIndex = new ArrayList<>();
17+
for (int j = 0; j < 2 * n; j++) {
18+
int a = sc.nextInt();
19+
if (a % 2 == 0) {
20+
evenIndex.add(j + 1);
21+
} else {
22+
oddIndex.add(j + 1);
23+
}
24+
}
25+
if (oddIndex.size() % 2 == 1) {
26+
for (int j = 0; j < (oddIndex.size() - 1) / 2; j++) {
27+
System.out.println(oddIndex.get(2 * j) + " " + oddIndex.get(2 * j + 1));
28+
}
29+
for (int j = 0; j < (evenIndex.size() - 1) / 2; j++) {
30+
System.out.println(evenIndex.get(2 * j) + " " + evenIndex.get(2 * j + 1));
31+
}
32+
} else {
33+
for (int j = 1; j < oddIndex.size() / 2; j++) {
34+
System.out.println(oddIndex.get(2 * j) + " " + oddIndex.get(2 * j + 1));
35+
}
36+
for (int j = (oddIndex.size() == 0 ? 1 : 0); j < evenIndex.size() / 2; j++) {
37+
System.out.println(evenIndex.get(2 * j) + " " + evenIndex.get(2 * j + 1));
38+
}
39+
}
40+
}
41+
}
42+
}

‎codeForces/Codeforces_1684A_Digit_Minimization.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
// Time: 312 ms
2+
// Memory: 300 KB
3+
// Greedy.
4+
// T:O(sum(logni)), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1684A_Digit_Minimization {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
int n = sc.nextInt();
14+
int maxDigit = 9, firstDigit = -1, exp = 0;
15+
while (n > 0) {
16+
if (firstDigit == -1) {
17+
firstDigit = n % 10;
18+
}
19+
maxDigit = Math.min(maxDigit, n % 10);
20+
n /= 10;
21+
exp++;
22+
}
23+
24+
System.out.println(exp == 2 ? firstDigit : maxDigit);
25+
}
26+
}
27+
}

‎leetcode_solved/leetcode_3411_Maximum_Subarray_With_Equal_Products.java‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
// Runtime 1 ms Beats 100.00%
2+
// Memory 42.53 MB Beats -%
3+
// Math theory: 1. First can prove 2-length array are always ok. 2.The right subarray is that from the
4+
// third items to the last, the items can not have common factor i > 1 to the lcm(n1, n2, .., ni)
5+
// T:O(n^2 * logn), S:O(1)
6+
//
7+
class Solution {
8+
public int maxLength(int[] nums) {
9+
int len = nums.length, ret = 2;
10+
for (int i = 0; i < len - 1; i++) {
11+
int lcm1 = nums[i];
12+
for (int j = i + 1; j < len; j++) {
13+
if (nums[j] > 1 && gcd(lcm1, nums[j]) > 1) {
14+
break;
15+
}
16+
ret = Math.max(ret, j - i + 1);
17+
lcm1 = lcm(lcm1, nums[j]);
18+
// System.out.println("lcm: " + lcm1 + " - ret: " + ret);
19+
}
20+
}
21+
22+
return ret;
23+
}
24+
25+
private int lcm(int a, int b) {
26+
return a * b / gcd(a, b);
27+
}
28+
29+
private int gcd(int a, int b) {
30+
if (a > b) {
31+
return gcd(b, a);
32+
}
33+
if (b % a == 0) {
34+
return a;
35+
}
36+
return gcd(b % a, a);
37+
}
38+
}

0 commit comments

Comments
 (0)