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

ABC三题题解。
A:牛牛选物
状态压缩枚举所有情况即可。
最多1<<20 1e6

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) {
        // write code here、
        int n=v.size(),mx=-1;
        for(int i=0;i<(1<<n);i++){
            int tv=0,tg=0;
            for(int j=0;j<n;j++){
                if((i>>j)&1){
                    tv+=v[j];
                    tg+=g[j];
                }
            }
            if(tv==V)mx=max(mx,tg);
        }
        return mx;
    }

};

B：牛牛与字符串2
KMP nxt数组裸题，KMP还是要熟练掌握的呀，基础知识点。

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

C：
最短路+对数优化乘法
路径边权积显然满足动态规划的性质，可以最短路做。
但这一题的瓶颈在于最短路的时候乘***爆ll。
仔细观察题目全是乘法，于是想到可以用对数优化。
log(a * b) = log(a) + log(b);
另外维护一个数组f表示正常取模的最短路,更新用对数优化的实际最短路e，最后输出时用取模的最短路f。
不过这题没必要用堆优化，优化反而最坏情况下多个log。
直接n^2松弛更新即可(但我代码写的dij，懒得改了。。。反正就多个log n = 5)。

注意：刚开始算组合数的时候就会爆ll，在求组合数的时候就要注意维护对数数组进行优化！

typedef long long ll;
const int M = 2e6+7;
const int mod =1e9+7;
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整型
     */

   int head[M],cnt=1;
    void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
    struct EDGE{int to,nxt,w;double e;}ee[M*2];
    void add(int x,int y,int w,double e){ee[++cnt].nxt=head[x],ee[cnt].e=e,ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
    bool vs[M];
    ll fac[1100],f[1100];
    double fae[1100],d[M];
    ll qpow(ll a,ll b){
        ll ans=1;
        while(b){
            if(b&1)ans=ans*a%mod;
            a=a*a%mod;
            b/=2;
        }
        return ans;
    }
    ll C(int n,int m){
        return fac[n]*qpow(fac[n-m],mod-2)%mod*qpow(fac[m],mod-2)%mod;
    }
    ll CE(int n,int m){
        return fae[n]-fae[n-m]-fae[m];
    }
    priority_queue<pair<double,int> ,vector<pair<double,int> >,greater<pair<double,int> > >q;
    ll dij(int s,int t,int n){
        for(int i=1;i<=n;i++)d[i]=2e18+7,f[i]=1;
        memset(vs,0,sizeof(vs));
        d[s]=0;f[s]=1;
        q.push({d[s],s});
        while(!q.empty()){
            pair<double,int>  tp=q.top();q.pop();
            int u=tp.second ;
            if(vs[u])continue;
            vs[u]=1;
            for(int i=head[u];i;i=ee[i].nxt){
                int v=ee[i].to,w=ee[i].w;double e=ee[i].e;
                if(d[v]>d[u]+e)//1经过u再到v的距离小于 1直接到v的距离 则更新距离
                    f[v]=f[u]*w%mod,d[v]=d[u]+e,q.push({d[v],v});
            }
        }
        return f[t];
    }

    int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
        // write code here
        memset(head,0,sizeof(head));memset(f,0,sizeof(f));
        cnt=1;fae[0]=0;fac[0]=1;
        for(int i=1;i<=1000;i++)fac[i]=fac[i-1]*i%mod,fae[i]=fae[i-1]+log(i);
        for(auto x:edge){
            ll w=C(x[2],x[3]);
            double e=CE(x[2],x[3]);
            add(x[0],x[1],w,e);
            add(x[1],x[0],w,e);
        }
        return dij(s,t,n);
    }
};