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

A题：
发现n的范围只有20，所以暴力枚举每一个物品取或者不取，用二进制状态压缩来解决更加方便。
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
     * @param v int整型vector 
     * @param g int整型vector 
     * @param V int整型 
     * @return int整型
     */
    int Maximumweight(vector<int>& v, vector<int>& g, int V) {
        int n=v.size(),ans=-1;
        for(int i=0;i<(1<<n);i++){
            int s=0,t=0;
            for(int j=0;j<n;j++)
                if(i>>j&1){
                    s=s+v[j];
                    t=t+g[j];
                }
            if(s==V)ans=max(ans,t);
        }
        return ans;
    }
};

时间复杂度 O(2^n)

B题：
最大前缀与最大后缀匹配，就是KMP中的next[len]的定义,所以直接套用模板即可。
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
     * @param s string字符串 代表题意中的字符串s
     * @return int整型
     */
    int nxt[1000010];
    int solve(string s) {
        int n=s.size();
        s=" "+s;
        for(int i=2,j=0;i<=n;i++){
            while(j&&s[i]!=s[j+1])j=nxt[j];
            if(s[i]==s[j+1])j++;
            nxt[i]=j;
        }
        if(nxt[n]==0)return -1;
        else return nxt[n];
    }
};

时间复杂度 O(n)

C题：
发现与普通的最短路不同，它的路程是乘起来的，所以中途可能会出现极大的数字但又不能取模。
所以，我们使用对数的一个性质log(a)+log(b)=log(a*b)，讲乘法改为加法。
但是又有一个新的问题，long long的数值太小，无法预处理1000以内的组合数，但是我们有double啊，它的范围几乎刚刚包含1000以内最大的组合数，所以就用double存储，在跑最短路的同时，为了方便我们还可以同时记录最终的答案。
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 有n个城市
     * @param m int整型 有m条路径
     * @param s int整型 起始城市坐标
     * @param t int整型 终点城市坐标
     * @param edge int整型vector<vector<>> 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
     * @return int整型
     */
    long long M=(1e9)+7,f[510][510],g[510][510],jc2[1010][1010],dis[510],dis2[510],vis[510];
    double jc[1010][1010];
    int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
        for(int i=0;i<=1000;i++){
            jc[i][0]=1;
            jc2[i][0]=1;
            for(int j=1;j<=i;j++){
                jc[i][j]=jc[i-1][j]+jc[i-1][j-1];
                jc2[i][j]=(jc2[i-1][j]+jc2[i-1][j-1])%M;
            }
        }
        memset(f,0x3f,sizeof(f));
        for(int i=1;i<=n;i++)f[i][i]=0;
        for(int i=0;i<m;i++){
            int u=edge[i][0],v=edge[i][1],a=edge[i][2],b=edge[i][3];
            f[u][v]=f[v][u]=log(jc[a][b]);
            g[u][v]=g[v][u]=jc2[a][b];
        }
        memset(dis,0x3f,sizeof(dis));
        dis[s]=0;
        dis2[s]=1;
        for(int i=1;i<=n;i++){
            int nw=0;
            for(int j=1;j<=n;j++)
                if(!vis[j]&&dis[j]<dis[nw])nw=j;
            vis[nw]=true;
            if(nw==t)break;
            for(int j=1;j<=n;j++)
                if(!vis[j]&&dis[nw]+f[nw][j]<dis[j]){
                    dis[j]=dis[nw]+f[nw][j];
                    dis2[j]=dis2[nw]*g[nw][j]%M;
                }
        }
        return dis2[t];
    }
};

时间复杂度 O(n^2)