头像

星丶空




离线:1个月前


最近来访(129)
用户头像
Tequila
用户头像
郁闷小豪仔
用户头像
SanJiClover
用户头像
小白菜qaq
用户头像
星星.
用户头像
安贵
用户头像
宏_19
用户头像
KepGooo
用户头像
我铁好人
用户头像
K423
用户头像
东方既白
用户头像
小飞机
用户头像
烤冷面
用户头像
不高兴就喝水
用户头像
FrankBlue
用户头像
Acheer
用户头像
曹务迪
用户头像
酬勤
用户头像
xiayutao
用户头像
dafangtou

活动打卡代码 AcWing 787. 归并排序

星丶空
2021-06-03 22:56
package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_787归并排序 {
    static Scanner in = new Scanner(System.in);

    static int N = 100010;
    static int n;
    static int[] a = new int[N];
    static int[] t = new int[N];

    public static void main(String[] args) {
        n = in.nextInt();
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();
        mergeSort(0, n - 1);
        for (int i = 0; i < n; i ++) System.out.print(a[i] + " ");
    }

    public static void mergeSort(int l, int r) {
        if (l >= r) return ;
        int mid = l + r >> 1;
        mergeSort(l, mid);
        mergeSort(mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) t[k ++] = a[i] <= a[j] ? a[i ++] : a[j ++];
        while (i <= mid) t[k ++] = a[i ++];
        while (j <= r) t[k ++] = a[j ++];
        for (k = 0, i = l; i <= r; k ++, i ++) a[i] = t[k];
    }
}



活动打卡代码 AcWing 466. 回文日期

星丶空
2021-06-03 22:43
package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_466回文日期 {
    /**
     *  枚举
     *  如果前4位已经确定,那么后4位也确定了,所以枚举前4位。
     *  思路:1、枚举前4位回文数。
     *       2、判断日期是否在规定范围内。
     *       3、判断日期是否合法。
     */
    static Scanner in = new Scanner(System.in);

    static int date1, date2;
    static int[] days = new int[] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    // 检查当前时间是否合法
    public static boolean check(int date) {
        int y = date / 10000;           // 年
        int m = date % 10000 / 100;     // 月
        int d = date % 100;             // 日

        if (m < 1 || m > 12) return false;
        if (m != 2) {                   // 不是2月
            return d <= days[m];
        } else {                        // 是2月
            // 四年一闰,百年不闰,四百年又一闰。
            boolean flag = ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0);
            if (flag) return d <= days[m] + 1;
            else return d <= days[m];
        }
    }

    public static void main(String[] args) {
        date1 = in.nextInt();
        date2 = in.nextInt();

        int ans = 0;
        for (int i = 1000; i < 10000; i ++) {
            int x = i;
            int date = i;
            for (int j = 0; j < 4; j ++) {
                date = date * 10 + (x % 10);
                x /= 10;
            }

            if (date1 <= date && date <= date2 && check(date)) ans ++;
        }
        System.out.println(ans);
    }
}



活动打卡代码 AcWing 1204. 错误票据

星丶空
2021-06-02 21:23
package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_1204错误票据 {
    static Scanner in = new Scanner(System.in);

    static int N = 100010;
    static int n;
    static int[] cnt = new int[N];

    public static void main(String[] args) {
        // min记录开始值,max记录结束值
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int n = in.nextInt();
        while (in.hasNextInt()) {
            int t = in.nextInt();
            cnt[t] ++;
            min = Math.min(min, t);
            max = Math.max(max, t);
        }

        int ans1 = 0, ans2 = 0;
        for (int i = min; i <= max; i ++) {
            if (cnt[i] == 0) ans1 = i;
            if (cnt[i] == 2) ans2 = i;
        }
        System.out.println(ans1 + " " + ans2);
    }
}



活动打卡代码 AcWing 1245. 特别数的和

星丶空
2021-06-02 20:55
package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_1245特别数的和 {
    // 模拟,如果数位中有2019就加上
    static Scanner in = new Scanner(System.in);

    static int n;

    public static void main(String[] args) {
        n = in.nextInt();
        long ans = 0;
        for (int i = 1; i <= n; i ++) {
            int x = i;
            while (x != 0) {
                int t = x % 10;
                x /= 10;
                if (t == 2 || t == 0 || t == 1 || t == 9) {
                    ans += i;
                    break;
                }
            }
        }
        System.out.println(ans);
    }
}



活动打卡代码 AcWing 1236. 递增三元组

星丶空
2021-06-02 20:31
package 第4讲枚举模拟与排序;

import java.util.Arrays;
import java.util.Scanner;

public class 例题_1236递增三元组 {
    /**
     *  数据范围在10^5,时间复杂度在O(nlogn)以内,所以最多只能枚举1个数组。
     *  而AC两个数组在两端,枚举A时,只能限制B,但不能限制C,所以我们枚举B数组。
     * 
     *  主要思想:枚举B数组,再分别求出A数组中小于当前Bi和C数组中大于当前Bi的个数,相乘累加即是答案。
     *  求个数有两种方法:1、前缀和
     *                  2、二分
     *  (这里用二分吧,简单一些,hh,注意边界问题0或者n-1时个数可能不存在)
     */
    static Scanner in = new Scanner(System.in);

    static int N = 10010;
    static int n;

    public static void main(String[] args) {
        int n = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();       
        for (int i = 0; i < n; i ++) b[i] = in.nextInt();       
        for (int i = 0; i < n; i ++) c[i] = in.nextInt();       
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);

        long ans = 0;
        for (int i = 0; i < n; i ++) {
            // 二分A数组中比Bi小的个数
            int al = 0;
            int ar = n - 1;
            while (al < ar) {
                int mid = al + ar + 1 >> 1;
                if (a[mid] < b[i]) al = mid;
                else ar = mid - 1;
            }
            long cnta;
            if (al == 0 && a[al] >= b[i]) cnta = 0; // 个数不存
            else cnta = (al - 0) + 1;

            // 二分C数组中比Bi大的数
            int cl = 0;
            int cr = n - 1;
            while (cl < cr) {
                int mid = cl + cr >> 1;
                if (c[mid] > b[i]) cr = mid;
                else cl = mid + 1;
            }
            long cntc;
            if (cl == n - 1 && c[cl] <= b[i]) cntc = 0; //个数不存在
            else cntc = ((n - 1) - cl) + 1;

            ans += cnta * cntc;
        }
        System.out.println(ans);
    }
}


活动打卡代码 AcWing 1210. 连号区间数

星丶空
2021-06-02 09:28
package 第4讲枚举模拟与排序;

import java.util.Scanner;

public class 例题_1210连号区间数 {
    /** 
     *  注意给出的数据就包含1~n的所有数,并且每个数字只出现一次。
     *  两重循环,第一重循环固定左端点,第二重循环固定右端点
     *  思路:在区间l~r中找到最大值max和最小值min,如果max - min == r - l,
     *                                      说明当前区间是递增且连续的
     *  例如:一个区间[4,6,7,5] max = 7, min = 4, 7 - 4 == 3 - 0, 所以是连续的
     *       一个区间[5,3,2,6] max = 6, min = 2, 6 - 2 != 3 - 0, 所以不是连续的
     */
    static Scanner in = new Scanner(System.in);

    static int N = 10010;
    static int n;
    static int[] a = new int[N];

    public static void main(String[] args) {
        n = in.nextInt();
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();

        int ans = 0;
        for (int i = 0; i < n; i ++) {
            // 由于区间不断一直变大,max和min只会不断变大和变小
            // 所以不需要对每一个新区间都遍历一次
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for (int j = i; j < n; j ++) {
                min = Math.min(min, a[j]);
                max = Math.max(max, a[j]);
                if (max - min == j - i) ans ++;
            }
        }
        System.out.println(ans);
    }
}


活动打卡代码 AcWing 3578. 最大中位数

星丶空
2021-05-30 18:11
package acwing.race;

import java.util.Arrays;
import java.util.Scanner;

public class 最大中位数3578 {
    /**
     *  这居然是一个二分!!!
     *  二分最大中位数答案,再将中位数右边的数补齐至当前中位数,判断操作次数是否小于k。
     */
    static Scanner in = new Scanner(System.in);

    static int n, k;

    public static void main(String[] args) {
        n = in.nextInt();
        k = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i ++) a[i] = in.nextInt();
        Arrays.sort(a);

        long l = 0, r = Integer.MAX_VALUE;
        while (l < r) {
            long mid = l + r + 1 >> 1;
            if (check(a, mid)) l = mid;
            else r = mid - 1;
        }
        System.out.println(l);
    }

    // 检查当前中位数为x时,操作次数是否足够
    public static boolean check(int[] a, long x) {
        long sum = 0;
        for (int i = n / 2; i < n; i ++) {
            if (x > a[i]) sum += x - a[i];
        }
        return sum <= k;
    }
}



活动打卡代码 AcWing 3579. 数字移动

星丶空
2021-05-30 18:10
package acwing.race;

import java.util.Scanner;

public class 数字移动3579 {
    /**
     *  这题首要任务就是把题目看懂!!!
     *  把题目看懂了,分析题目就明白是用并查集求连通块大小
     */
    static Scanner in = new Scanner(System.in);

    static int N = 200010;
    static int[] p = new int[N];
    static int[] s = new int[N];

    public static void main(String[] args) {
        int t = in.nextInt();
        while (t -- > 0) {
            int n = in.nextInt();
            for (int i = 1; i <= n; i ++) {
                p[i] = i;
                s[i] = 1;
            }
            for (int i = 1; i <= n; i ++) {
                int j = in.nextInt();
                if (find(i) != find(j)) {
                    s[find(i)] += s[find(j)];
                    p[find(j)] = find(i);
                }
            }

            for (int i = 1; i <= n; i ++) System.out.print(s[find(i)] + " ");
            System.out.println();
        }
    }

    public static int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}




星丶空
2021-05-24 00:07
package acwing.lanqiaobei;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 最长非递减子序列3549 {
    /**
     *  y总思想题解,新数字序列a的最长非递减子序列,翻转之前状态肯定是
     *      有4段:111...222...111...222,其中中间的两段是需要翻转,且每段长度允许为0。
     * 
     *  这个是y总的简单化代码,非常简洁。
     */
    static In in = new In(System.in);

    public static void main(String[] args) throws Exception {
        int n = in.nextInt();

        // 注意:s1是前1段最大长度,s2是前2段的最大长度,以此类推!!
        int s1 = 0, s2 = 0, s3 = 0, s4 = 0; 
        while (n -- > 0) {
            int x = in.nextInt();
            if (x == 1) {                   
                s1 = s1 + 1;                    // 直接加在第1段后面。
                s3 = Math.max(s2 + 1, s3 + 1);  // 接在第2段后面或者在第3段后面加。
            } else {
                s2 = Math.max(s1 + 1, s2 + 1);  // 接在第1段后面或者在第2段后面加。
                s4 = Math.max(s3 + 1, s4 + 1);  // 接在第3段后面或者在第3段后面加。
            }
        }

        // 输出最长的一段,1中s3最长,2中s4最长
        System.out.println(Math.max(s3, s4));
    }
}

class In{
    BufferedReader reader;
    StringTokenizer tokenizer;

    In(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() throws Exception {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(next());
    }
}


活动打卡代码 AcWing 3548. 双端队列

星丶空
2021-05-24 00:06
package acwing.lanqiaobei;

import java.util.Scanner;

public class 双端队列3548 {
    /**
     *  注意数据范围在2×10^5,而且队列中一定不会存在重复数字
     *  
     *  直接用一个数组记录数字所在的下标,每次查询输出距离左右端点的最小值即可。
     *      y总的方法甚至不需要保存数据,只保存下标。
     */
    static Scanner in = new Scanner(System.in);

    static int N = 200010;
    static int q, x;
    static int[] a = new int[N];    // 模拟队列(该数组可以直接删除)
    static int[] sign = new int[N]; // 纪录下标

    public static void main(String[] args) {
        q = in.nextInt();
        int l = N / 2, r = N / 2 + 1;
        while (q -- > 0) {
            String s = in.next();
            x = in.nextInt();
            if (s.equals("L")) {
                a[l] = x;
                sign[x] = l;
                l --;
            } else if (s.equals("R")) {
                a[r] = x;
                sign[x] = r;
                r ++;
            } else {
                int ans = Math.min(sign[x] - (l + 1), (r - 1) - sign[x]);
                System.out.println(ans);
            }
        }
    }
}