头像

热的干面




离线:1小时前


最近来访(2)
用户头像
种花家的市长
用户头像
dushucheng0901

活动打卡代码 AcWing 4728. 乘方

package lanqiao_day01;

import java.io.*;
import java.math.BigDecimal;
import java.time.Year;
import java.util.*;
import java.util.function.IntPredicate;

import javax.lang.model.type.IntersectionType;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static String nextLine() throws Exception {
        return br.readLine();
    }

    static int N = (int) 1000000000;
    static int n, m;

    public static void main(String[] args) throws Exception {
        n = nextInt();
        m = nextInt();
        long res = 1;
        while (m > 0) {
            if ((m & 1) == 1) {
                res *= n;
            }
            if (res > N || n > N || res < 0 || n < 0) {
                System.out.println(-1);
                return;
            }
            n *= n;
            m /= 2;
        }
        System.out.println(res);
    }
}


活动打卡代码 AcWing 4699. 如此编码

import java.io.*;
import java.math.BigDecimal;
import java.time.Year;
import java.util.*;
import java.util.function.IntPredicate;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }
    static int n,m;
    static int N = 25;
    static int[] a = new int[N];
    static int[] c = new int[N];
    public static void main(String[] args) throws Exception {
        n = nextInt();
        m = nextInt();
        c[0] = 1;
        for(int i =1;i<=n;i++) {
            a[i] = nextInt();
            c[i] = c[i-1]*a[i];
        }
        for(int i=1;i<=n;i++) {
            int res = (m%c[i]-m%c[i-1])/c[i-1];
            System.out.print(res+" ");
        }
    }
}



题目描述

Hecy 又接了个新任务:BE 处理。

BE 中有一类被称为 GBE。

以下是 GBE 的定义:

空表达式是 GBE
如果表达式 A 是 GBE,则 [A] 与 (A) 都是 GBE
如果 A 与 B 都是 GBE,那么 AB 是 GBE
下面给出一个 BE,求至少添加多少字符能使这个 BE 成为 GBE。

注意:BE 是一个仅由(、)、[、]四种字符中的若干种构成的字符串。

输入格式
输入仅一行,为字符串 BE。

输出格式
输出仅一个整数,表示增加的最少字符数。

数据范围
对于所有输入字符串,其长度小于100。

输入样例:
[])
输出样例:
1

思路

这题与密码脱落的思路类似,我还是从集合的最大值分析,而不是跟y总一样分析最小值。

image-20230127141407836.png

import java.io.*;
import java.math.BigDecimal;
import java.time.Year;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static boolean check(char a ,char b) {
        if(a=='['&&b==']') return true;
        else if (a=='('&&b==')') {
            return true;
        }else {
            return false;
        }
    }
    static int N = 110;
    static char[] s;
    static int[][] dp = new int[N][N];
    public static void main(String[] args) throws Exception {
        s = nextLine().toCharArray();
        int n = s.length;
        //长度从2开始,这样不用处理边界L-1 越界问题,长度为1的话匹配括号数量只能为0
        for (int len = 2; len <= n; len++) {
            for (int l = 0; l <= n - len; l++) {
                int r = l + len - 1;
                dp[l][r] = Math.max(dp[l+1][r], dp[l][r-1]);
                if(check(s[l], s[r])) {
                    dp[l][r] = Math.max(dp[l][r], dp[l+1][r-1]+2);
                }
                for(int k = l;k<=r-1;k++) {
                    dp[l][r] = Math.max(dp[l][k]+dp[k+1][r], dp[l][r]);
                }
            }
        }
        System.out.println(n-dp[0][n-1]);
    }
}


活动打卡代码 AcWing 4509. 归一化处理

import java.io.*;

public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception{
        in.nextToken();
        return (int) in.nval;
    }
    public static double nextDouble() throws Exception{
        in.nextToken();
        return in.nval;
    }
    static int N = 1010;
    static int n;
    static double[] a = new double[N];
    public static void main(String[] args)throws Exception{
        n = nextInt();
        double sum = 0;
        for(int i=0;i<n;i++){
            a[i] = nextDouble();
            sum+=a[i];
        }
        double avg = sum/n;
        double s = 0;
        for(int i=0;i<n;i++){
            s+=(a[i]-avg)*(a[i]-avg);
        } 
        double d = s/n;
        for(int i=0;i<n;i++){
            out.println((a[i]-avg)/Math.pow(d,0.5));
        } 
        out.close();
    }
}



Snipaste_2023-01-26_14-49-29.png


import java.io.*;
import java.math.BigDecimal;
import java.time.Year;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static double nextDouble() throws Exception {
        in.nextToken();
        return in.nval;
    }

    public static long nextLong() throws Exception {
        in.nextToken();
        return (long) in.nval;
    }

    public static String nextStr() throws Exception {
        in.nextToken();
        return in.sval;
    }

    public static String nextLine() throws Exception {
        return br.readLine();
    }
    static int N = 1010;
    static int[][] dp = new int[N][N];
    public static void main(String[] args) throws Exception {
        char[] s = nextLine().toCharArray();
        int n = s.length;
        for (int len = 1; len <= n; len++) {
            for (int l = 0; l <= n - len; l++) {
                int r = len + l - 1;
                if(l==r) dp[l][r] = 1;
                else {
                    dp[l][r] = Math.max(dp[l+1][r], dp[l][r-1]);
                    if(s[l]==s[r]) {
                        dp[l][r] = Math.max(dp[l][r], dp[l+1][r-1]+2);
                    }
                }
            }
        }
        System.out.println(n-dp[0][n-1]);
    }

}


活动打卡代码 AcWing 4454. 未初始化警告



import java.io.*;
import java.math.BigDecimal;
import java.time.Year;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static double nextDouble() throws Exception {
        in.nextToken();
        return in.nval;
    }

    public static long nextLong() throws Exception {
        in.nextToken();
        return (long) in.nval;
    }

    public static String nextStr() throws Exception {
        in.nextToken();
        return in.sval;
    }

    public static String nextLine() throws Exception {
        return br.readLine();
    }

    static int n;
    static int k;
    static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws Exception {
        n = nextInt();
        k = nextInt();
        int ans = 0;
        for (int i = 0; i < k; i++) {
            int l = nextInt();
            int r = nextInt();
            if(!map.containsKey(r)&&r!=0) {
                ans++;
            }
            map.put(l, 1);
        }
        System.out.println(ans);
    }

}



package lanqiao_day01;

import java.io.*;
import java.math.BigDecimal;
import java.time.Year;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static double nextDouble() throws Exception {
        in.nextToken();
        return in.nval;
    }

    public static long nextLong() throws Exception {
        in.nextToken();
        return (long) in.nval;
    }

    public static String nextStr() throws Exception {
        in.nextToken();
        return in.sval;
    }

    public static String nextLine() throws Exception {
        return br.readLine();
    }

    static int n, m, k;
    static int N = 110;
    static int M = 1 << 20;
    static int[] log2 = new int[M];
    //使用set去重,优化速度
    static Set[] col = new HashSet[21];
    public static void main(String[] args) throws Exception {
        n = nextInt();
        m = nextInt();
        k = nextInt();

        for (int i = 0; i < m; i++) {
            col[i] = new HashSet<Integer>();
            //获取log2数组,方便之后根据数值得出二进制上哪一位是1
            log2[1 << i] = i;
        }
        //读取n个糖果
        for (int i = 0; i < n; i++) {
            //使用二进制数表示当前这包糖果有哪些糖
            int state = 0;
            for (int j = 0; j < k; j++) {
                int c = nextInt();
                //或运算,例如c=5,1左移四位之后对state进行或运算,state的第五个数会变为1
                state |= 1 << c - 1;
            }
            //当前这包糖果已经全部读完,将其添加到对应的糖果种类数组里
            for (int k = state; k > 0; k -= lowbit(k)) {//lowbit返回最后一个1的数值,例如10010会返回10
                int c = log2[lowbit(k)];//获取对应哪一种糖果
                col[c].add(state);
            }
        }
        //迭代加深,不断去扩大depth的值
        int depth = 1;
        while (depth <= m && !dfs(depth, 0)) {
            depth++;
        }
        //不满足对应的要求,depth最多取m个,如果大于m个就代表没有结果
        if (depth > m)
            depth = -1;
        System.out.println(depth);
    }
    //递归过程
    private static boolean dfs(int depth, int state) {
        //糖果已经拿完或者最少要拿多少包糖果大于当前剩余的数量
        if (depth <= 0 || h(state) > depth)
            return state == (1 << m) - 1;

        int t = -1;
        // 找到选择性最小的一列,就是说包含该糖果种类的糖果包数量最少
        //(1 << m) - 1 -state代表当前还有那些种类没有选择
        for (int i = (1 << m) - 1 -state; i > 0; i -= lowbit(i)) {
            int c = log2[lowbit(i)];
            //比较长度
            if (t == -1 || col[t].size() > col[c].size()) {
                t = c;
            }
        }
        // 枚举选哪行
        Set<Integer> set = col[t];
        for(int row : set) {
            if (dfs(depth - 1, state | row)) {
                return true;
            }
        }
        return false;
    }

    // 求一下最少需要再选几包糖果
    private static int h(int state) {
        int res = 0;
        for (int i = (1 << m) - 1 - state; i > 0;) {
            int c = log2[lowbit(i)];
            res++;
            Set<Integer> set = col[c];
            for(int row : set) {
                i &= ~row;
                //将row这包糖果对应的糖果种类中的1全部变成0,~取反,在配上&能实现对应的效果
            }
        }
        return res;
    }
    private static int lowbit(int i) {
        return i & -i;
    }

}


活动打卡代码 AcWing 4655. 重新排序

思路:

这道题的思路就是我们要求m个区间的最大值,那么这些区间内被覆盖到次数最多的元素在重新排序之后要放最大的值。我们先对n个数字进行输入,输入完毕之后求一下m个区间的前缀和。之后利用差分修改每个区间的覆盖次数,再对差分数组求前缀和得出每个元素的覆盖次数,利用覆盖次数对进行排序,在把原数组根据覆盖次数获得一个新数组,最后求前缀和得出m个区间的总和。

方法是有点绕的,但是总体思路还是很清晰的。

package lanqiao_day01;

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigDecimal;
import java.time.Year;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static double nextDouble() throws Exception {
        in.nextToken();
        return in.nval;
    }

    public static long nextLong() throws Exception {
        in.nextToken();
        return (long) in.nval;
    }

    public static String nextStr() throws Exception {
        in.nextToken();
        return in.sval;
    }

    public static String nextLine() throws Exception {
        return br.readLine();
    }

    public static class num implements Comparable<num> {
        public int n;
        public int c;

        public num(int n, int c) {
            this.c = c;
            this.n = n;
        }

        @Override
        public int compareTo(num o) {
            return this.c - o.c;
        }
    }

    public static void insert(int l, int r, int c) {
        b[l] += c;
        b[r + 1] -= c;
    }

    static int N = 100010;
    static int n;
    static int m;
    static int[] c;
    static int[] l = new int[N];
    static int[] r = new int[N];

    static long[] s = new long[N];
    static num[] a = new num[N];
    static int[] b = new int[N];
    static int[] d = new int[N];
    public static void main(String[] args) throws Exception {
        n = nextInt();
        c = new int[n];
        for (int i = 1; i <= n; i++) {
            c[i-1] = nextInt();
            s[i] += s[i - 1] + c[i-1];
        }
        Arrays.sort(c);
        m = nextInt();
        long pre = 0;
        for (int i = 0; i < m; i++) {
            l[i] = nextInt();
            r[i] = nextInt();
            pre += s[r[i]] - s[l[i] - 1];
            insert(l[i], r[i], 1);
        }
        for (int i = 1; i <= n; i++) {
            b[i] += b[i - 1];
            a[i] = new num(i,b[i]);
        }
        long sum  = 0;
        int u =n-1;
        Arrays.sort(a,1,n+1);
        for(int i=n;i>=1;i--) {
            d[a[i].n] = c[i-1];
        }
        for(int i =1;i<=n;i++) {
            s[i] = s[i-1]+d[i];
        }
        for (int i = 0; i < m; i++) {
            sum+=s[r[i]] - s[l[i] - 1];
        }
        System.out.println(sum-pre);
    }
}



思路:

这道题的思路就是我们要求m个区间的最大值,那么这些区间内被覆盖到次数最多的元素在重新排序之后要放最大的值。我们先对n个数字进行输入,输入完毕之后求一下m个区间的前缀和。之后利用差分修改每个区间的覆盖次数,再对差分数组求前缀和得出每个元素的覆盖次数,利用覆盖次数对进行排序,在把原数组根据覆盖次数获得一个新数组,最后求前缀和得出m个区间的总和。

方法是有点绕的,但是总体思路还是很清晰的。

package lanqiao_day01;

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigDecimal;
import java.time.Year;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static double nextDouble() throws Exception {
        in.nextToken();
        return in.nval;
    }

    public static long nextLong() throws Exception {
        in.nextToken();
        return (long) in.nval;
    }

    public static String nextStr() throws Exception {
        in.nextToken();
        return in.sval;
    }

    public static String nextLine() throws Exception {
        return br.readLine();
    }

    public static class num implements Comparable<num> {
        public int n;
        public int c;

        public num(int n, int c) {
            this.c = c;
            this.n = n;
        }

        @Override
        public int compareTo(num o) {
            return this.c - o.c;
        }
    }

    public static void insert(int l, int r, int c) {
        b[l] += c;
        b[r + 1] -= c;
    }

    static int N = 100010;
    static int n;
    static int m;
    static int[] c;
    static int[] l = new int[N];
    static int[] r = new int[N];

    static long[] s = new long[N];
    static num[] a = new num[N];
    static int[] b = new int[N];
    static int[] d = new int[N];
    public static void main(String[] args) throws Exception {
        n = nextInt();
        c = new int[n];
        for (int i = 1; i <= n; i++) {
            c[i-1] = nextInt();
            s[i] += s[i - 1] + c[i-1];
        }
        Arrays.sort(c);
        m = nextInt();
        long pre = 0;
        for (int i = 0; i < m; i++) {
            l[i] = nextInt();
            r[i] = nextInt();
            pre += s[r[i]] - s[l[i] - 1];
            insert(l[i], r[i], 1);
        }
        for (int i = 1; i <= n; i++) {
            b[i] += b[i - 1];
            a[i] = new num(i,b[i]);
        }
        long sum  = 0;
        int u =n-1;
        Arrays.sort(a,1,n+1);
        for(int i=n;i>=1;i--) {
            d[a[i].n] = c[i-1];
        }
        for(int i =1;i<=n;i++) {
            s[i] = s[i-1]+d[i];
        }
        for (int i = 0; i < m; i++) {
            sum+=s[r[i]] - s[l[i] - 1];
        }
        System.out.println(sum-pre);
    }
}


活动打卡代码 AcWing 4653. 数位排序



import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigDecimal;
import java.time.Year;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer in = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    public static double nextDouble() throws Exception {
        in.nextToken();
        return in.nval;
    }

    public static long nextLong() throws Exception {
        in.nextToken();
        return (long) in.nval;
    }

    public static String nextStr() throws Exception {
        in.nextToken();
        return in.sval;
    }

    public static String nextLine() throws Exception {
        return br.readLine();
    }
    public static class num implements Comparable<num>{
        public int s;
        public int n;
        public num(int s,int n) {
            this.s = s;
            this.n = n;
        }
        @Override
        public int compareTo(num o) {
            if(this.s<o.s) {
                return -1;
            }else if(this.s>o.s){
                return 1;
            }else {
                return this.n-o.n;
            }
        }
    }
    public static int getSum(int n) {
        int sum = 0;
        while(n>0) {
            sum+=n%10;
            n/=10;
        }
        return sum;
    }
    static int N = 1000010;
    static int n;
    static int m;
    static num nums[];
    public static void main(String[] args) throws Exception {
        n = nextInt();
        m = nextInt();
        nums = new num[n];
        for(int i = 1;i<=n;i++) {
            nums[i-1] = new num(getSum(i), i); 
        }
        Arrays.sort(nums);
        System.out.println(nums[m-1].n);
    }
}