牛客编程巅峰赛S2第8场 - 钻石&王者

A. 牛牛选物

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
     * @param v int整型一维数组 
     * @param g int整型一维数组 
     * @param V int整型 
     * @return int整型
     */
    int res = -1;
    int n = 0;
    void dfs(int u, int cur, int pro, int[] g, int[] v, int lim){
        if(cur > lim) return;
        if(u == n){
            if(cur == lim){
                res = Math.max(res, pro);
            }
            return;
        }
        if(cur + v[u] <= lim){
            dfs(u+1, cur+v[u], pro+g[u], g, v, lim);
        }
        dfs(u+1, cur, pro, g, v, lim);
    }

    public int Maximumweight(int[] v, int[] g, int V) {
        // write code here
        n = v.length;

        dfs(0, 0, 0, g, v, V);
        return res;
    }
}

B. 牛牛与字符串2

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
     * @param s string字符串 代表题意中的字符串s
     * @return int整型
     */
    public int[] get_next(String p){
        int n = p.length();
        int[] ne = new int[n + 1];

        for(int i=2, j=ne[i-1]; i<=n; i++){
            while(j != 0 && p.charAt(i-1) != p.charAt(j)) j = ne[j];
            if(p.charAt(i-1) == p.charAt(j)) j ++;
            ne[i] = j;
        }

        return ne;
    }

    public int solve (String s) {
        // write code here
        int n = s.length();

        int[] ne = get_next(s);
        int res = ne[n];
        return res == 0? -1:res;
    }
}

C. 牛牛送快递

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 有n个城市
     * @param m int整型 有m条路径
     * @param s int整型 起始城市坐标
     * @param t int整型 终点城市坐标
     * @param edge int整型二维数组 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
     * @return int整型
     */
    int E = 510, N = 1010, INF = 0x3f3f3f3f, MOD = 1000000007;
    int be, ed;
    int[][] C = new int[N][N];
    double[][] g = new double[E][E]; // g[a][b]存储a -> b的C值的对数值
    int[][] rg = new int[E][E]; // rg[a][b]存储a -> b的C值的真实值
    double[] L = new double[N]; // L[i] => 存储i!的对数值
    double[] dist = new double[N]; // 用于存储对数距离
    int[] rdist = new int[N]; // 用于存储真实距离
    boolean[] st = new boolean[N];

    public void getC(int n){
        for(int i=0; i<=n; i++){
            for(int j=0; j<=i; j++){
                if(j == 0) C[i][j] = 1;
                else C[i][j] = (int)(((long)C[i-1][j] + C[i-1][j-1]) % MOD);
            }
        }
    }

    public int Dijkstra(int n){
        Arrays.fill(dist, INF);
        rdist[be] = 1;
        dist[be] = 0;

        for(int i=0; i<n; i++){
            // 找到最短距离的点
            int t = -1;
            for(int j=1; j<=n; j++){
                if(!st[j] && (t == -1 || dist[j] < dist[t])){
                    t = j;
                }
            }

            if(st[t]) continue;
            st[t] = true;

            // 用这个点的距离更新其它节点
            for(int j=1; j<=n; j++){
                if(dist[j] > dist[t] + g[t][j]){
                    dist[j] = dist[t] + g[t][j];
                    rdist[j] = (int)((long)rdist[t] * rg[t][j] % MOD);
                }
            }
        }
        return rdist[ed];
    }

    public int minDist (int n, int m, int s, int t, int[][] edge) {
        // write code here
        be = s; ed = t;
        getC(N - 1);
        // 预处理L数组
        for(int i=1; i<N; i++) L[i] = L[i-1] + Math.log(i);

           for(int i=1; i<=n; i++){
               for(int j=1; j<=n; j++){
                   if(i == j){
                    g[i][j] = 0;
                    rg[i][j] = 1;
                }
                   else {
                    rg[i][j] = 0;
                    g[i][j] = INF;
                }
               }
           }

           // 加边
           for(int[] cur : edge){
               int a = cur[0];
               int b = cur[1];
               int rc = C[cur[2]][cur[3]]; // 获取实际的消耗
               double c = L[cur[2]] - L[cur[3]] - L[cur[2]-cur[3]];
               g[a][b] = g[b][a] = c;
               rg[a][b] = rg[b][a] = rc;
           }
           return Dijkstra(n);
    }
}