update

OneCodeMonkey · OneCodeMonkey · commit 22bf26959e40 · 2025-03-02T01:00:46.000+08:00
diff --git a/codeForces/Codeforces_1957A_Stickogon.java b/codeForces/Codeforces_1957A_Stickogon.java
@@ -0,0 +1,26 @@
+// Time: 374 ms 
+// Memory: 900 KB
+// 注意：polygons 是多边形，不是矩形。
+// T:O(sum(ni)), S:O(max(ni))
+// 
+import java.util.HashMap;
+import java.util.Scanner;
+
+public class Codeforces_1957A_Stickogon {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int t = sc.nextInt();
+        for (int i = 0; i < t; i++) {
+            int n = sc.nextInt(), ret = 0;
+            HashMap<Integer, Integer> record = new HashMap<>();
+            for (int j = 0; j < n; j++) {
+                record.merge(sc.nextInt(), 1, Integer::sum);
+            }
+            for (int key : record.keySet()) {
+                ret += record.get(key) / 3;
+            }
+
+            System.out.println(ret);
+        }
+    }
+}
diff --git a/codeForces/Codeforces_2003B_Turtle_and_Piggy_Are_Playing_a_Game_2.java b/codeForces/Codeforces_2003B_Turtle_and_Piggy_Are_Playing_a_Game_2.java
@@ -0,0 +1,24 @@
+// Time: 405 ms 
+// Memory: 1000 KB
+// Game & Greedy: 最优情况下，先手的优先删最小的，后手的优先删最大的，那么最终会剩下中间的。
+// T:O(sum(ni * logni)), S:O(max(ni))
+// 
+import java.util.Arrays;
+import java.util.Scanner;
+
+public class Codeforces_2003B_Turtle_and_Piggy_Are_Playing_a_Game_2 {
+    public static void main(String[] args) {
+        Scanner sc = new Scanner(System.in);
+        int t = sc.nextInt();
+        for (int i = 0; i < t; i++) {
+            int n = sc.nextInt();
+            int[] arr = new int[n];
+            for (int j = 0; j < n; j++) {
+                arr[j] = sc.nextInt();
+            }
+            Arrays.sort(arr);
+
+            System.out.println(arr[n / 2]);
+        }
+    }
+}
diff --git a/leetcode_solved/leetcode_1524_Number_of_Sub-arrays_With_Odd_Sum.java b/leetcode_solved/leetcode_1524_Number_of_Sub-arrays_With_Odd_Sum.java
@@ -0,0 +1,30 @@
+// Runtime 95 ms Beats 5.42% 
+// Memory 79.55 MB Beats 7.16%
+// Prefix sum & DP.
+// 注意：给的参数范围是 length <= 10^5，所以有概率超过 int 上限。
+// T:O(n), S:O(n)
+// 
+class Solution {
+    public int numOfSubarrays(int[] arr) {
+        HashMap<Integer, Long> oddSumCount = new HashMap<>(), evenSumCount = new HashMap<>();
+        evenSumCount.put(0, 1L);
+        oddSumCount.put(0, 0L);
+        int len = arr.length, curSum = 0;
+        long ret = 0;
+        for (int i = 0; i < len; i++) {
+            curSum += arr[i];
+            if (curSum % 2 == 1) {
+                ret += evenSumCount.get(i);
+                oddSumCount.put(i + 1, oddSumCount.get(i) + 1);
+                evenSumCount.put(i + 1, evenSumCount.get(i));
+            } else {
+                ret += oddSumCount.get(i);
+                evenSumCount.put(i + 1, evenSumCount.get(i) + 1);
+                oddSumCount.put(i + 1, oddSumCount.get(i));
+            }
+
+        }
+
+        return (int) (ret % (1000000000 + 7));
+    }
+}
