牛客编程巅峰赛S2第8场 - 青铜&白银&黄金

第一题

没啥好说的，就动一动脑子想一想，奇数就可以拆 (n - 1) / 2 种方案，偶数的话就是 n / 2 - 1

代码的话用一点点位运算的知识即可一行实现.

class Solution {
public:
    int solve(int n) {
        return n / 2 - (n & 1 ^ 1);
    }
};

第二题.

显然不是背包啦，n 给的那么小,v给的那么大，给的还是5s时间限制，直接无脑爆搜即可？

class Solution {
public:
    int n,Va;
    int b[210505];
    int val[10005],w[10005],Ans = -1;
    void DFS(int l,int now ,int W)
    {
        if(now == Va) {Ans = max(Ans,W);return ;}
        for(int i = l ; i <= n ; i ++)
        {
            if(now + val[i] > Va)continue;
            if(b[i] == 1)continue;
            b[i] = 1;
            DFS(i + 1 , now + val[i], W + w[i]);
            b[i] = 0;
        }
        return ;
    }
    int Maximumweight(vector<int>& v, vector<int>& g, int V) {
        int len = v.size();
        Va = V;
        n = len;
        for(int i = 0 ; i < len ; i ++)val[i + 1] = v[i];
        len = g.size();
        for(int i = 0 ; i < len ; i ++)w[i + 1] = g[i];
        DFS(1,0,0);
        return Ans;
    }
};

第三题

就是KMP模板？

class Solution {
public:
    int Next[1000050];
    int solve(string s) {
        int len = s.length();
        int j = - 1;
        Next[0] = -1;
        for(int i = 1 ; i < len ; i ++)
        {
            if(s[j + 1] != s[i] && j != -1)j = Next[j];
            if(s[j + 1] == s[i]) j ++;
            Next[i] = j;
        }
        if(Next[len - 1] != -1)
        return Next[len - 1] + 1;
        return -1;
    }
};

这场比赛相当的水......