头像

SoonMachine




在线 


最近来访(1)
用户头像
yfwen2000

活动打卡代码 AcWing 785. 快速排序

SoonMachine
1小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;


int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int x = q[l + r >> 1], i = l - 1, j = r + 1;

    while(i < j){
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }

    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] q = new int[1000000];
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());
        String[] in = reader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            q[i] = Integer.parseInt(in[i]);
        }

        quickSort(0, n - 1);

        for (int i = 0; i < n; i++) {
            System.out.print(q[i] + " ");
        }
    }

    private static void quickSort(int l, int r) {
        if (l >= r) {
            return;
        }
        int x = q[l + r >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            do {
                i++;
            } while (q[i] < x);
            do {
                j--;
            } while (q[j] > x);
            if (i < j) {
                swap(i,j);
            }
        }

        quickSort(l, j);
        quickSort(j + 1, r);
    }

    private static void swap(int i, int j) {
        int temp = q[i];
        q[i] = q[j];
        q[j] = temp;
    }
}



class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next= node ->next->next;
    }
};



SoonMachine
2个月前
class Solution {
public:
    stack<int> stk;
    void eval(string s){
        int b = stk.top();
        stk.pop();
        int a = stk.top();
        stk.pop();
        if(s == "+") stk.push(a + b);
        else if(s == "-") stk.push(a - b);
        else if(s == "*") stk.push(a * b);
        else stk.push(a / b);
    }
    int evalRPN(vector<string>& tokens) {
        //后缀表达式其实是表达式树的后序遍历
        //遍历完两个子树后马上遍历运算符(根节点)
        unordered_set<string> S{"+","-","*","/"};
        for(auto& s : tokens){
            if(S.count(s)) eval(s);
            else stk.push(stoi(s));
        }
        return stk.top();
    }
};


活动打卡代码 AcWing 826. 单链表

SoonMachine
3个月前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author sunam
 */
public class Main {
    static final int N = 100010;
    static int head;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    /**
     * 存储当前用到了那个点
     */
    static int idx;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    /**
     * 初始化数组
     */
    static void init() {
        head = -1;
        idx = 0;
    }

    static void addToHead(int val) {
        e[idx] = val;
        ne[idx] = head;
        head = idx;
        idx++;
    }

    static void remove(int k) {
        ne[k] = ne[ne[k]];
    }

    static void insert(int k, int val) {
        e[idx] = val;
        ne[idx] = ne[k];
        ne[k] = idx;
        idx++;

    }

    public static void main(String[] args) throws IOException {
        int m = Integer.parseInt(reader.readLine().trim());
        init();
        for (int i = 0; i < m; i++) {
            String[] str = reader.readLine().split(" ");
            switch (str[0]) {
                case "H": {
                    int val = Integer.parseInt(str[1]);
                    addToHead(val);
                    break;
                }
                case "I": {
                    int k = Integer.parseInt(str[1]);
                    int val = Integer.parseInt(str[2]);
                    insert(k - 1, val);
                    break;
                }
                default: {
                    int k = Integer.parseInt(str[1]);
                    if (k == 0) {
                        head = ne[head];
                    } else {
                        remove(k - 1);
                    }
                    break;
                }
            }
        }
        for (int i = head; i != -1; i = ne[i]) {
            System.out.print(e[i] + " ");
        }
    }
}


活动打卡代码 AcWing 1248. 灵能传输

SoonMachine
3个月前
/**
 * @author SoonMachine
 * @apiNote 感冒了脑子有点晕
 */
import java.io.*;
import java.util.Arrays;


public class Main {
    static final int N = 300010;
    static int t;
    static int n;
    static long[] a = new long[N];
    static long[] s = new long[N];
    static boolean[] st = new boolean[N];
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        t = Integer.parseInt(input.readLine().trim());
        for (int r = 0; r < t; r++) {
            Arrays.fill(a, 0);
            Arrays.fill(s, 0);
            n = Integer.parseInt(input.readLine());
            String[] str = input.readLine().split(" ");
            for (int i = 1; i <= n; i++) {
                a[i] = Integer.parseInt(str[i - 1]);
                s[i] = s[i - 1] + a[i];
            }
            long s0 = s[0], sn = s[n];
            if (sn < s0) {
              s0 = s[n];
              sn = s[0];
            }
            Arrays.sort(s, 0, n + 1);
            for (int i = 0; i <= n; i++) {
                if (s[i] == s0) {
                    s0 = i;
                    break;
                }
            }
            for (int i = n; i >= 0; i--) {
                if (s[i] == sn) {
                    sn = i;
                    break;
                }
            }
            Arrays.fill(st, false);
            int left = 0, right = n;
            for (int i = (int) s0; i >= 0; i -= 2) {
                a[left ++] = s[i];
                st[i] = true;
            }
            for (int i = (int) sn; i <= n; i += 2) {
                a[right --] = s[i];
                st[i] = true;
            }
            for (int i = 0; i <= n; i++) {
                if (!st[i]) {
                    a[left ++] = s[i];
                }
            }
            long res = 0;
            for (int i = 1; i <= n; i++) {
                res = Math.max(res, Math.abs(a[i] - a[i - 1]));
            }
            System.out.println(res);
        }
    }
}


活动打卡代码 AcWing 1220. 生命之树

SoonMachine
3个月前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * @author SoonMachine
 */
public class Main {
    static int N = 100010, M = N * 2;
    static int n;
    static int[] w = new int[N];
    static long[] f = new long[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(reader.readLine().trim());
        String[] str = reader.readLine().split(" ");
        for (int i = 1; i <= str.length; i++) {
            w[i] = Integer.parseInt(str[i - 1]);
        }
        Arrays.fill(h, -1);
        for (int i = 0; i < n - 1; i++) {
            str = reader.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            add(a, b);
            add(b, a);
        }
        dfs(1, -1);
        long res = f[1];
        for (int i = 2; i <= n; i++) {
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }

    private static void dfs(int u, int father) {
        f[u] = w[u];

        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (j == father) {
                continue;
            }
            dfs(j, u);
            f[u] += Math.max(f[j], 0);
        }
    }

    private static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}


活动打卡代码 AcWing 1222. 密码脱落

SoonMachine
3个月前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static int[][] dp = new int[1010][1010];
    public static void main(String[] args) throws IOException {
        String s = reader.readLine();
        int n = s.length();
        for(int length = 1; length <= n; length++){
            for (int i = 0; i + length  - 1 < n; i++) {
                int j = i + length - 1;
                if (length == 1) {
                    dp[i][j] = 1;
                }else {
                    dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = Math.max(dp[i][j],dp[i + 1][j - 1] + 2);
                    }
                }
            }
        }
        System.out.println(n - dp[0][n - 1]);
    }
}



活动打卡代码 AcWing 1047. 糖果

SoonMachine
3个月前
import java.util.*;

public class Main {
    static Scanner in = new Scanner(System.in);
    static int[][] dp = new int[110][110];

    public static void main(String[] args) {
        int n = in.nextInt(), k = in.nextInt();
        for (int i = 0; i <= n; i++)
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            int v = in.nextInt();
            for (int j = 0; j < k; j++) dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][Math.floorMod((j - v), k)] + v);
        }
        System.out.println(dp[n][0]);
    }
}



活动打卡代码 AcWing 2066. 解码

SoonMachine
3个月前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String s = reader.readLine();
        StringBuilder res = new StringBuilder("");
        for (int i = 0; i < s.length() - 1; i++) {
            if (isLetter(s.charAt(i)) && isNumber(s.charAt(i + 1))){
                for (int j = 0; j < s.charAt(i + 1) - '0'; j++) {
                    res.append(s.charAt(i));
                }
                i ++;
            }else if (isLetter(s.charAt(i)) && !isNumber(s.charAt(i + 1))){
                res.append(s.charAt(i));
            }
        }
        if (isLetter(s.charAt(s.length() - 1)))res.append(s.charAt(s.length() - 1));
        System.out.println(res);
    }

    private static boolean isNumber(char c) {
        return c >= '1' && c <= '9';
    }

    private static boolean isLetter(char c) {
        return c >= 'A' && c <= 'z';
    }
}


活动打卡代码 AcWing 2065. 整除序列

SoonMachine
3个月前

还是py好写啊

n = input();
while (n > 1):
    print n,;
    n /= 2;
print(1);