头像

hxzz




离线:2天前


活动打卡代码 AcWing 90. 64位整数乘法

hxzz
1个月前
/*

    a*b mod p = a*b - a*b/p
    p <= 10^18
*/

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        long a = cin.nextLong();
        long b = cin.nextLong();
        long p = cin.nextLong();
        long c = ksm(a, b, p);
        System.out.println(c);
    }

    static long ksm(long a, long b, long p) {
        long ans = 0;
        while (b != 0) {
            if ((b & 1) == 1)ans = (ans + a) % p;
            a = (a + a) % p;
            b = (b >> 1);
        }
        return ans;
    }
}




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

hxzz
1个月前
import java.util.*;

public class Main {
    static int[] s = new int[305];
    static int[] a = new int[305];
    static int[][] f = new int[305][305];

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        for (int i = 1; i <= n; ++ i) {
            a[i] = cin.nextInt();
            s[i] += s[i - 1] + a[i];
        }

        for (int len = 2; len <= n; ++ len) {
            for (int l = 1; l + len - 1 <= n; ++ l) {
                int r = len + l - 1;

                f[l][r] = 0x3f3f3f3f;
                for (int k = l; k <= r; ++ k)
                    f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }
        System.out.println(f[1][n]);
    }
}


活动打卡代码 AcWing 899. 编辑距离

hxzz
1个月前
import java.util.*;

public class Main {
    static int[][] f = new int[1010][1010];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int n = cin.nextInt();
        int m = cin.nextInt();
        String[] s = new String[n + 5];

        for (int i = 1; i <= n; ++ i) s[i] = new String(cin.next());

        while (m -- > 0) {
            String a = cin.next();
            int ans = 0;
            int k = cin.nextInt();

            for (int i = 1; i <= n; ++ i) {
                if (minDistance(a, s[i]) <= k)
                    ans ++;
            }

            System.out.println(ans);
        }
    }

    public static int minDistance(String a, String b) {
        int n = a.length();
        int m = b.length();

        a = ' ' + a;
        b = ' ' + b;

        for (int i = 1; i <= n; ++ i) f[i][0] = i;
        for (int i = 1; i <= m; ++ i) f[0][i] = i;

        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j) {
                f[i][j] = Math.min(f[i][j - 1], f[i - 1][j]) + 1; // 添加和删除操作
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + (a.charAt(i) != b.charAt(j) ? 1 : 0)); // 替换和不变操作
            }
       return f[n][m];
    }
}


活动打卡代码 AcWing 902. 最短编辑距离

hxzz
1个月前
import java.util.*;

public class Main {
    static int[][] f = new int[1010][1010];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int n = cin.nextInt();
        String a = cin.next();
        int m = cin.nextInt();
        String b = cin.next();

        a = ' ' + a;
        b = ' ' + b;

        for (int i = 1; i <= n; ++ i) f[i][0] = i;
        for (int i = 1; i <= m; ++ i) f[0][i] = i;

        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j) {
                f[i][j] = Math.min(f[i][j - 1], f[i - 1][j]) + 1; // 添加和删除操作
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + (a.charAt(i) != b.charAt(j) ? 1 : 0)); // 替换和不变操作
            }

        System.out.println(f[n][m]);
    }
}



hxzz
1个月前
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int n, m;
        n = cin.nextInt();
        m = cin.nextInt();

        String a = cin.next();
        a = ' ' + a;
        String b = cin.next();
        b = ' ' + b;
        int[][] f = new int[n + 1][m + 1]; // f[i][j] 表示字符串从 1 ~ i, 和字符串从 1 ~ j 中最大匹配。
        for (int i = 0; i < n + 1; ++ i)
            for (int j = 0; j < m + 1; ++ j) f[i][j] = 0;

        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= m; ++ j) {
                if (a.charAt(i) == b.charAt(j))
                    f[i][j] = f[i - 1][j - 1] + 1;
                else
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
            }

        System.out.println(f[n][m]);
    }
}



hxzz
1个月前

import java.util.*;
public class Main{

    public static void main(String [] args){
        Scanner cin = new Scanner(System.in);

        int n = cin.nextInt();
        int[] f = new int[n + 5];
        Arrays.fill(f, 0x3f3f3f3f);
        for (int i = 0; i < n; ++ i) {
            int k = cin.nextInt();
            int idx = lower_bound(f, 0, n + 1, k);
            f[idx] = k;
        }
        System.out.println(lower_bound(f, 0, n + 1, 0x3f3f3f3f));

    }
    public static int lower_bound(int a[], int l, int r, int x) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }

}




hxzz
1个月前
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int n = cin.nextInt();
        int[] f = new int[n + 5];
        int[] num = new int[n + 5];
        int ans = 0;
        // 用f[i]表示以i结尾的字符串的最大长度,然后通过累加得到答案
        for (int i = 1; i <= n; ++ i) {
            num[i] = cin.nextInt();
            f[i] = 1;
            for (int j = 1; j < i; ++ j) {
                if (num[j] < num[i])
                    f[i] = Math.max(f[i], f[j]+1);
            }
            ans = Math.max(f[i], ans);
        }
        System.out.println(ans);
    }
}


活动打卡代码 AcWing 898. 数字三角形

hxzz
1个月前
import java.util.*;

public class Main {
    static int[][] f = new int[505][505];
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int n = cin.nextInt();
        for (int i = 1; i <= n; ++ i) 
            for (int j = 1; j <= i; ++ j)
                f[i][j] = cin.nextInt();
        // 从倒数第二排依次累加上去
        for (int i = n - 1; i >= 1; -- i) {
            for (int j = 1; j <= i; ++ j) {
                f[i][j] += Math.max(f[i + 1][j], f[i + 1][j + 1]);
            }
        }

        System.out.println(f[1][1]);

    }
}


活动打卡代码 AcWing 9. 分组背包问题

hxzz
1个月前
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int N, V;
        N = cin.nextInt();
        V = cin.nextInt();

        int[] f = new int[V + 5];
        int[] w = new int[110];
        int[] v = new int[110];

        Arrays.fill(f, 0);
        for (int i = 1; i <= N; ++ i) {
            int n = cin.nextInt();
            for (int k = 0; k < n; ++ k) {
                v[k] = cin.nextInt();
                w[k] = cin.nextInt();
            }
            for (int j = V; j >= 0; -- j) {
                for (int k = 0; k < n; ++ k){
                    if(j < v[k]) continue;
                    f[j] = Math.max(f[j], f[j - v[k]] + w[k]);
                }
            }
        }
        System.out.println(f[V]);
    }
}


活动打卡代码 AcWing 9. 分组背包问题

hxzz
1个月前
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int N, V;
        N = cin.nextInt();
        V = cin.nextInt();

        int[][] f = new int[N + 5][V + 5];
        for (int i = 0; i < N + 5; ++ i)
            for (int j = 0; j < V + 5; ++ j)
                f[i][j] = 0;

        for (int i = 1; i <= N; ++ i) {
            int n = cin.nextInt();
            for (int k = 0; k < n; ++ k) {
                int v, w;
                v = cin.nextInt();
                w = cin.nextInt();
                // 这里必须从零开始,这样才能保证,前边的值能向下传递
                for (int j = 0; j <= V; ++ j) {

                    if (f[i][j] == 0) f[i][j] = f[i - 1][j];
                    if (j - v < 0) continue;
                    f[i][j] = Math.max(f[i][j], f[i-1][j - v] + w);
                }
            }
        }

        System.out.println(f[N][V]);
    }
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        int N, V;
        N = cin.nextInt();
        V = cin.nextInt();

        int[][] f = new int[N + 5][V + 5];
        for (int i = 0; i < N + 5; ++ i)
            for (int j = 0; j < V + 5; ++ j)
                f[i][j] = 0;

        for (int i = 1; i <= N; ++ i) {
            int n = cin.nextInt();
            for (int k = 0; k < n; ++ k) {
                int v, w;
                v = cin.nextInt();
                w = cin.nextInt();
                // 这里必须从零开始,这样才能保证,前边的值能向下传递
                for (int j = 0; j <= V; ++ j) {

                    if (f[i][j] == 0) f[i][j] = f[i - 1][j];
                    if (j - v < 0) continue;
                    f[i][j] = Math.max(f[i][j], f[i-1][j - v] + w);
                }

            }


        }


        System.out.println(f[N][V]);
    }
}