头像

nanotrt


访客:436

离线:17小时前


活动打卡代码 AcWing 282. 石子合并

nanotrt
4小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = in.nextInt();
        }
        in.close();
        System.out.println(minCost(arr));
    }

    private static int minCost(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        int[] preSum = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i - 1] + arr[i - 1];
        }
        for (int l = 1; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l, ans = Integer.MAX_VALUE;
                for (int k = i; k < j; ++k) {
                    ans = Math.min(ans, dp[i][k] + dp[k + 1][j]);
                }
                dp[i][j] = ans + preSum[j + 1] - preSum[i];
            }
        }
        return dp[0][n - 1];
    }
}


活动打卡代码 AcWing 282. 石子合并

nanotrt
4小时前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;

class Main {
    private static int[] preSum;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = in.nextInt();
        }
        in.close();
        int[][] dp = new int[n][n];
        preSum = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i - 1] + arr[i - 1];
        }
        System.out.println(minCost(dp, arr, 0, n - 1));
    }

    private static int minCost(int[][] dp, int[] arr, int i, int j) {
        if (i == j) return 0;
        if (dp[i][j] != 0) return dp[i][j];
        int ans = Integer.MAX_VALUE / 2;
        for (int k = i; k < j; ++k) {
            ans = Math.min(minCost(dp, arr, i, k) + minCost(dp, arr, k + 1, j), ans);
        }
        ans += preSum[j + 1] - preSum[i];
        return dp[i][j] = ans;
    }
}


活动打卡代码 AcWing 154. 滑动窗口

nanotrt
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), k = in.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            arr[i] = in.nextInt();
        }
        in.close();
        solve(arr, n, k);
    }

    private static void solve(int[] arr, int n, int k) {
        Deque<Integer> minQ = new ArrayDeque<>();
        Deque<Integer> maxQ = new ArrayDeque<>();
        StringBuilder minSb = new StringBuilder();
        StringBuilder maxSb = new StringBuilder();
        for (int i = 0; i < k; ++i) {
            while (!minQ.isEmpty() && arr[minQ.peekLast()] > arr[i]) {
                minQ.pollLast();
            }
            while (!maxQ.isEmpty() && arr[maxQ.peekLast()] < arr[i]) {
                maxQ.pollLast();
            }
            minQ.offerLast(i);
            maxQ.offerLast(i);
        }

        for (int i = k; i <= n; ++i) {
            while (!minQ.isEmpty() && minQ.peekFirst() < i - k) {
                minQ.pollFirst();
            }
            while (!maxQ.isEmpty() && maxQ.peekFirst() < i - k) {
                maxQ.pollFirst();
            }
            minSb.append(arr[minQ.peekFirst()]);
            minSb.append(" ");
            maxSb.append(arr[maxQ.peekFirst()]);
            maxSb.append(" ");
            while (!minQ.isEmpty() && arr[minQ.peekLast()] > arr[i]) {
                minQ.pollLast();
            } 
            minQ.offerLast(i);
            while (!maxQ.isEmpty() && arr[maxQ.peekLast()] < arr[i]) {
                maxQ.pollLast();
            }
            maxQ.offerLast(i);
        }
        System.out.println(minSb);
        System.out.println(maxSb);
    }
}

Java太难了,挑战模式有点来不及啊



活动打卡代码 AcWing 152. 城市游戏

nanotrt
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(), n = in.nextInt();
        int[][] arr = new int[m][n + 1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                arr[i][j] = in.next().equals("F") ? 1 : 0;
            }
        }
        in.close();
        System.out.println(3 * maxArea(arr, m, n));
    }

    private static int maxArea(int[][] arr, int m, int n) {
        int[] maxHeight = new int[n + 1];
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j <= n; ++j) {
                maxHeight[j] = arr[i][j] == 0 ? 0 : 1 + maxHeight[j];
                while (!stack.isEmpty() && maxHeight[stack.peek()] >= maxHeight[j]) {
                    int curHeight = maxHeight[stack.poll()];
                    int left = stack.isEmpty() ? -1 : stack.peek();
                    ans = Math.max((j - left - 1) * curHeight, ans);
                }
                stack.push(j);
            }
            stack.pop();
        }
        return ans;
    }
}



nanotrt
5天前

算法

$O(logn)$

斐波那契数列可以用矩阵来表示。
$a_n = a_{n - 1} + a_{n - 2}$
$a_{n - 1} = a_{n - 1}$
所以矩阵就是{1, 1},{1, 0}。可以采用矩阵快速幂,类比于整数的快速幂来求这个矩阵。

代码

blablabla
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        while ((n = in.nextInt()) != -1) {
            System.out.println(fib(n));
        }
        in.close();
    }

    private static int fib(int n) {
        if (n == 0) return 0;
        int[][] A = new int[][]{{1, 1}, {1, 0}};
        int[][] ret = new int[][]{{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = mul(ret, A);
            }
            A = mul(A, A);
            n >>= 1;
        }
        return ret[1][0];
    }

    private static int[][] mul(int[][] A, int[][] B) {
        int n = A.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    ans[i][j] += A[i][k] * B[k][j];
                }
                ans[i][j] %= 10000;
            }
        }
        return ans;
    }
}


活动打卡代码 AcWing 205. 斐波那契

nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        while ((n = in.nextInt()) != -1) {
            System.out.println(fib(n));
        }
        in.close();
    }

    private static int fib(int n) {
        if (n == 0) return 0;
        int[][] A = new int[][]{{1, 1}, {1, 0}};
        int[][] ret = new int[][]{{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = mul(ret, A);
            }
            A = mul(A, A);
            n >>= 1;
        }
        return ret[1][0];
    }

    private static int[][] mul(int[][] A, int[][] B) {
        int n = A.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    ans[i][j] += A[i][k] * B[k][j];
                }
                ans[i][j] %= 10000;
            }
        }
        return ans;
    }
}


活动打卡代码 AcWing 150. 括号画家

nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        System.out.println(maxLen(s));
    }

    private static int maxLen(String s) {
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                stack.push(i);
            } else {
                int j = stack.pop();
                if (j != -1 && (s.charAt(i) == ')' && s.charAt(j) == '(' || s.charAt(i) == ']' && s.charAt(j) == '[' || s.charAt(i) == '}' && s.charAt(j) == '{')) {
                    ans = Math.max(ans, i - stack.peek());
                } else {
                    stack.clear();
                    stack.push(i);
                }
            }
        }
        return ans;
    }
}


活动打卡代码 AcWing 148. 合并果子

nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = in.nextInt();
        }
        in.close();
        System.out.println(minCost(arr));
    }

    private static int minCost(int[] arr) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int a : arr) {
            pq.offer(a);
        }
        int ans = 0;
        while (pq.size() > 1) {
            int a = pq.poll(), b = pq.poll();
            ans += a + b;
            pq.offer(a + b);
        }
        return ans;
    }
}


活动打卡代码 AcWing 146. 序列

nanotrt
5天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;

class Main {
    public static void main(String[] args) {
        int[][] mat = new int[1000][2000];
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int i = 0; i < T; ++i) {
            int m = in.nextInt(), n = in.nextInt();
            for (int j = 0; j < m; ++j) {
                for (int k = 0; k < n; ++k) {
                    mat[j][k] = in.nextInt();
                }
            }
            solve(mat, m, n);
        }
    }

    private static void solve(int[][] mat, int m, int n) {
        int[] prev = mat[0];
        Arrays.sort(prev, 0, n);
        for (int i = 1; i < m; ++i) {
            prev = merge(prev, mat[i], n);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            sb.append(prev[i]);
            sb.append(" ");
        }
        System.out.println(sb);
    }

    private static int[] merge(int[] prev, int[] cur, int n) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(prev[a[0]] + cur[a[1]], prev[b[0]] + cur[b[1]]));
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            pq.offer(new int[]{0, i});
        }
        for (int i = 0; i < n; ++i) {
            int[] temp = pq.poll();
            ans[i] = prev[temp[0]] + cur[temp[1]];
            if (++temp[0] < n) {
                pq.offer(temp);
            }
        }
        return ans;
    }
}


活动打卡代码 AcWing 145. 超市

nanotrt
6天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
import java.util.Scanner;
import java.util.PriorityQueue;
import java.util.Arrays;

class Main {
    public static void main(String[] args) {
        int[][] arr = new int[10001][2];
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            for (int i = 0; i < n; ++i) {
                arr[i][0] = in.nextInt();
                arr[i][1] = in.nextInt();
            }
            System.out.println(maxProfit(arr, n));
        }
        in.close();
    }

    private static int maxProfit(int[][] arr, int n) {
        Arrays.sort(arr, 0, n, (a, b) -> Integer.compare(a[1], b[1]));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            pq.offer(arr[i][0]);
            if (pq.size() > arr[i][1]) {
                pq.poll();
            }
        }
        for (int a : pq) {
            ans += a;
        }
        return ans;
    }
}