头像

acw_weian




离线:8小时前



acw_weian
8小时前
import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception{
        char[] a = read.readLine().toCharArray(), b = read.readLine().toCharArray();
        int n = a.length;
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(a[i] != b[i]){
                ans++;
                a[i] = b[i];
                a[i+1] = a[i+1] == '*' ? 'o': '*';
            }
        }
        System.out.println(ans);
    }
}




import java.io.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args ) throws Exception{

        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]), k = Integer.valueOf(ss[1]);
        int[][] a = new int[n][2];

        for(int i = 0; i < n; i++){
            ss = read.readLine().split(" ");
            int h = Integer.valueOf(ss[0]), w = Integer.valueOf(ss[1]);
            a[i][0] = h; a[i][1] = w;
        }
        int l = 1, r = 100000;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(check(a, mid, k)) l = mid;
            else r = mid - 1;
        }
        System.out.println(l);
    }

    public static boolean check(int[][] a, int size, int k){
        int ans = 0;
        for(int i = 0; i < a.length; i++){
            int h = a[i][0], w = a[i][1];
            for(int row = 0; row + size <= h; row += size){
                for(int col = 0; col + size <= w; col += size){
                    ans++;
                }
            }
        }
        return ans >= k;
    }
}



acw_weian
1个月前

本题使用一个常用技巧: 前后缀分解
该技巧的常用套路如下:
1. 求前缀数组
2. 求后缀数组
3. 枚举前后缀数组的分界点

对于本题,可以分解为求连续数组前缀和的最大值和, 求连续数组后缀和的最大值
可以定义如下:

dp1[i]: 从1~i从前往后枚举,以数字a[i]结尾的,连续和的最大值
dp2[i]: 从n~i从后往前枚举,以数字a[i]结尾的,连续和的最大值

maxLeft[i]: 从1~i从前往后枚举,前1~i个数字连续和的最大值
maxRight[i]: 从n~i从后往前枚举,后n~i个数字连续和的最大值

状态计算如下:
dp1[i] = max( dp1[i - 1] + a[i], a[i])
maxLeft[i] = max(maxLeft[i - 1], dp1[i])

dp2[i] = max( dp2[i + 1] + a[i], a[i])
maxRight[i] = max(maxRight[i + 1], dp2[i])

最后枚举前后缀数组的分界点

总体时间复杂度: O(N)

import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 50010, INF = 10010;
    static int[] a = new int[N], dp1 = new int[N], dp2 = new int[N], maxLeft = new int[N], maxRight = new int[N];
    public static void main(String[] args) throws Exception{
        int t = Integer.valueOf(read.readLine());
        while(t -- > 0){
            Arrays.fill(dp1, -INF); Arrays.fill(dp2, -INF);
            Arrays.fill(maxLeft, -INF); Arrays.fill(maxRight, -INF);
            int n = Integer.valueOf(read.readLine());
            String[] ss = read.readLine().split(" ");
            for(int i = 1; i <= n; i++) a[i] = Integer.valueOf(ss[i - 1]);  //读取输入数组到a
            for(int i = 1; i <= n; i++){   //处理前缀
                dp1[i] = Math.max(dp1[i - 1] + a[i], a[i]);
                maxLeft[i] = Math.max(maxLeft[i - 1], dp1[i]);
            }

            for(int i = n; i >= 1; i--) {  //处理后缀
                dp2[i] = Math.max(dp2[i + 1] + a[i], a[i]);
                maxRight[i] = Math.max(maxRight[i + 1], dp2[i]);
            }

            int out = -INF;
            //枚举前后缀的分界点
            for(int i = 1; i <= n; i++){
                out = Math.max(maxLeft[i - 1] + maxRight[i], out);
            }

            System.out.println(out);
        }
    }
}



acw_weian
2个月前

欧拉函数: 一个数n, 从1~n-1中与n互质的数的个数(互质:最大公约数为1)
思路: 对n进行质因数分解 n = p1^k1 * p2^k2 * … * pn^kn
答案: n * (1 - 1/p1) * (1 - 1/p2) * … * (1 - 1/pn)
等价: n * (p1 - 1)/p1 * (p2 - 1)/p2 * … * (pn - 1)/pn

一个数n的约数的个数 = (k1 + 1) * (k2 + 1) * … * (kn + 1)
一个数n的约数的和 = (p1^0 + p1^1 + … + p1^k1) * (p2^0 + p2^1 + … + p2^k2) * (pn^0 + pn^1 + … + pn^kn)


import java.io.*;
import java.util.*;
class Main {
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws Exception {
        int t = Integer.valueOf(read.readLine());
        while (t -- > 0){
            int a = Integer.valueOf(read.readLine());
            log.write(getEula(a) + "\n");
        }
        log.flush();
    }


    public static long getEula(int a){
        int t = a;
        Map<Integer, Integer> map = new HashMap();
        for(int i = 2; i <= a / i; i++){
            if(a % i == 0){
                int cnt = 0;
                while (a % i == 0){
                    cnt++;
                    a /= i;
                }
                map.put(i, map.getOrDefault(i, 0) +  cnt);
            }
        }
        if(a > 1) map.put(a, map.getOrDefault(a, 0) + 1);
        long eula = t;
        for(Integer key: map.keySet()){
            eula = eula * (key - 1) / key;
        }
        return eula;
    }

}


活动打卡代码 AcWing 125. 耍杂技的牛

acw_weian
2个月前

按照w + s的和从小到大进行排序,求最大值即可,用反证法证明


import java.io.*;
import java.util.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args)throws Exception{
        int n = Integer.valueOf(read.readLine());
        int[][] e = new int[n][2];
        for(int i = 0; i < n; i++){
            String[] ss = read.readLine().split(" ");
            int w = Integer.valueOf(ss[0]), s = Integer.valueOf(ss[1]);
            e[i][0] = w; e[i][1] = s;
        }
        Arrays.sort(e, (o1, o2) -> o1[0] + o1[1] - o2[0] - o2[1]);
        long sum = 0, ans = Long.MIN_VALUE;
        for(int i = 0; i < n; i++){
            ans = Math.max(ans, sum - e[i][1]);
            sum += e[i][0];
        }
        System.out.println(ans);
    }

}



活动打卡代码 AcWing 104. 货仓选址

acw_weian
2个月前
import java.io.*;
import java.util.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        int[] a = new int[n];
        String[] ss = read.readLine().split(" ");
        for(int i = 0; i < n; i++) a[i] = Integer.valueOf(ss[i]);
        Arrays.sort(a);
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans += Math.abs(a[n / 2] - a[i]);
        }
        System.out.println(ans);
    }
}



活动打卡代码 AcWing 913. 排队打水

acw_weian
2个月前

假设有n个人,每个人花费的时间为:
x1 x2 x3 … xn
那么,总共的花费时间为:
x1(n-1) + x2(n-2) + x3*(n-3) + … + xn-1 (公式1)
PS: 后面的人要等前面的人完成才能开始,最后一个人就要等前面所有的人完成才能开始
观察发现,越排在前面的人,花费时间所占的权重越大

算法思路:
升序排序所有的人,按公式1累加即可得到答案


import java.io.*;
import java.util.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        int[] a = new int[n];
        String[] ss = read.readLine().split(" ");
        for(int i = 0; i < n; i++) a[i] = Integer.valueOf(ss[i]);
        Arrays.sort(a);
        long ans = 0;
        for(int i = 0; i < n - 1; i++){
            ans += a[i] * (n - i - 1);
        }
        System.out.println(ans);
    }
}



acw_weian
2个月前

假设有n个人,每个人花费的时间为:
x1 x2 x3 … xn
那么,总共的花费时间为:
x1(n-1) + x2(n-2) + x3*(n-3) + … + xn-1 (公式1)
PS: 后面的人要等前面的人完成才能开始,最后一个人就要等前面所有的人完成才能开始
观察发现,越排在前面的人,花费时间所占的权重越大

算法思路:
升序排序所有的人,按公式1累加即可得到答案


import java.io.*;
import java.util.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        int[] a = new int[n];
        String[] ss = read.readLine().split(" ");
        for(int i = 0; i < n; i++) a[i] = Integer.valueOf(ss[i]);
        Arrays.sort(a);
        long ans = 0;
        for(int i = 0; i < n - 1; i++){
            ans += a[i] * (n - i - 1);
        }
        System.out.println(ans);
    }
}



acw_weian
2个月前

汉密尔顿最短距离.png

import java.io.*;
import java.util.Arrays;

class Main {
    static int N = 20, M = 1 << N;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

    static int[][] dp = new int[N][M];
    static int[][] w = new int[N][N];
    public static void main(String[] args) throws Exception {
        int n = Integer.valueOf(read.readLine());

        for(int i = 0; i < n; i++){
            String[] ss = read.readLine().split(" ");
            for(int j = 0; j < n; j++){
                w[i][j] = Integer.valueOf(ss[j]);
            }
        }
        for(int i = 0; i < n; i++) Arrays.fill(dp[i], 0x3f3f3f3f);
        dp[0][1] = 0;

        for(int j = 0; j < 1 << n; j++){
            for(int i = 0; i < n; i++){
                if((j & (1 << i)) == 0) continue;
                for(int k = 0; k < n; k++){
                    if((j & (1 << k)) == 0 || k == i) continue;
                    dp[i][j] = Math.min(dp[i][j], dp[k][j - (1 << i)] + w[k][i]);
                }
            }
        }

        System.out.println(dp[n - 1][(1 << n) - 1]);
    }

}



acw_weian
2个月前

完全背包问题


/**
 * 完全背包问题, 数字从1~n,可以选0~k次
 * dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i]] + dp[i - 1][j - 2 * a[i]] + ... + dp[i - 1][j - k * a[i]]
 * dp[i][j - a[i]] = dp[i - 1][j - a[i]] + dp[i - 1][j - 2 * a[i]] + ... + dp[i - 1][j - k * a[i]]
 * dp[i][j] - dp[i][j - a[i]] = dp[i - 1][j]
 * 相减得  dp[i][j] = dp[i - 1][j] + dp[i][j - a[i]]
 * dp[j] = dp[j] + dp[j - a[i]]
 */

import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), mod = (int) 1e9 + 7;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                dp[j] = (dp[j] + dp[j - i]) % mod;
            }
        }
        System.out.println(dp[n]);
    }
}

计数dp

正整数之和.png

import java.util.*;

class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), mod = (int) 1e9 + 7;
        int[][] dp = new int[n + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = (dp[i - 1][j - 1] +dp[i - j][j]) % mod;
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) ans = (ans + dp[n][i]) % mod;
        System.out.println(ans);
    }

}