牛客巅峰赛S2

第三场

https://ac.nowcoder.com/acm/contest/9246

简单的公式：快速幂

class Solution {
public:
    /**
     * 返回c[n]%1000000007的值
     * @param n long长整型 即题目中的n
     * @return int整型
     */
    const long long mod = 1000000007;
    long long qpow(long long a,long long b){
        long long res = 1;
        while(b){
            if(b&1) res = res*a%mod;
            b >>= 1;
            a = a*a%mod;
        }
        return res%mod;
    }
    int Answerforcn(long long n) {
        // write code here
        long long q1,q2;
        q1 = qpow(3,n-1);
        q2 = qpow(5,n-1);
        return (2*q1%mod*7*q2%mod)%mod;
    }
};

TREE VI：bfs/dfs

class Solution {
public:
    /**
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Dfs遍历序列的结点编号
     * @return long长整型
     */
    long long sum = 0;
    vector<int> aa;
    long long k1,n,cnt = 1;
    void dfs(int d,int num){
        for(int i = 1; i <= k1; i++){
            if(d*k1+i < n){
                cnt++;
                sum += aa[cnt-1]^aa[num-1];
                dfs(d*k1+i,cnt);
            }
            else return;
        }
    }
    
    long long tree6(int k, vector<int>& a) {
        // write code here
        k1 = k;
        n = a.size();
        aa = a;
        dfs(0,1);
        return sum;
    }
};

第四场

https://ac.nowcoder.com/acm/contest/9475

A-牛牛掷硬币：思维+字符串

思路：n次全为正面的概率，1/2^n, n次全为方面的概率，1/2^n，所有总概率就是1/2^n*2 = 1/2^(n-2). 下面就是要如何将答案转化成字符串型。

方法一：

class Solution {
public:
    /**
     * 返回一个严格四舍五入保留两位小数的字符串
     * @param n int整型 n
     * @return string字符串
     */
    string Probability(int n) {
        // write code here
        char s[10][55] = {" ","1.00","0.50","0.25","0.13","0.06","0.03","0.02","0.01","0.00"};
        string str;
        if(n >= 9) str += "0.00";
        else str = string(s[n]);
        return str;
    }
};

方法二：

B-牛牛摆玩偶：二分+贪心

思路：

1）将最小值最大化，很容易联想到二分，那如何来验证答案的是否正确呢？接下来就是贪心的来放玩偶了。

2）假设验证的答案是x，首先将第一个玩偶放在第一个区间的最左端，然后在这个区间内每个长度x放一个玩偶，又因为区间外不能放玩偶，所有我们要去判断当前区间的右端点距离下一个区间的左端点的长度加上当前区间最后一个玩偶的距离这个区间的右端点的长度是否超过了x，如果超过，那么下一个玩偶的位置就放在下一个区间的左端点，否则就放在距离该区间最后一个玩偶x的位置。

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    typedef long long ll ;
    vector<Interval>a;
    bool check(int n,int m,ll x){
        ll st = 1ll*a[0].start;
        ll len,num=0,ys;
        for(int i = 0; i < m; i++){
            if(st > 1ll*a[i].end) continue;
            /*len = 1ll*a[i].end - st;
            num = len/x;
            ys = len%x;
            n -= (num+1);
            if(n <= 0) return true;
            if(i == m-1) continue;
            if(1ll*a[i].end-ys+x > 1ll*a[i+1].start) st = 1ll*a[i].end-ys+x;
            else st = a[i+1].start;*/
            st = max(st,1ll*a[i].start);
            ll nums = (1ll*a[i].end-st)/x + 1;
            num += nums;
            st += nums*x;
        }
        if(n <= num) return true;
        /*
        if(st <= 1ll*a[m-1].end) {
            len = 1ll*a[m-1].end - st;
            num = len/x;
            ys = len%x;
            n -= num+1;
            if(n <= 0) return true;
        }*/
        return false;
    }

    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        sort(intervals.begin(), intervals.end(), [&](Interval& a, Interval& b) -> bool {
        return a.start < b.start;
    });
        a = intervals;
        ll l = 0,r = INT_MAX;
        ll ans = 0;
        while(l <= r){
            ll mid = (l+r) >> 1;
            if(check(n,m,mid)){
                ans = mid;
                l = mid+1;
            }
            else {
                r = mid-1;
            }
        }
        return ans;
    }
};

C-交叉乘：前缀和+规律

思路：

找规律，先画出一个九九乘法表，每个数对应数组的下标，图中圈住的地方是求[1,4]的答案，根据题目给的公式其实就是求 1*2+1*3+1*4+2*3+2*4+3*4,从图中可看出就是求圈中的矩形下半部分的和，不包括对角线，再看每一行，1*(1+2+3+4)+2*(1+2+3+4)+3*(1+2+3+4)+4*(1+2+3+4) = (1+2+3+4)*(1+2+3+4), 这样我们就可以求出整个矩阵的和，而这个矩阵又是一个对称矩阵，那么我们先将和减去对角线上的和再除以2就是答案了。这些和先用前缀和维护出来。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 多次求交叉乘
     * @param a int整型vector a1,a2,...,an
     * @param query int整型vector l1,r1,l2,r2,...,lq,rq
     * @return int整型vector
     */
    typedef long long ll;
    const int mod = 1e9+7;
    ll pre[100005],pre1[100005];
    void sum_pre(vector<int> &a){
        pre[0] = a[0]%mod;
        pre1[0] = 1ll*a[0]*1ll*a[0]%mod;
        for(int i = 1; i < a.size(); i++){
            pre[i] = (pre[i-1]+1ll*a[i])%mod;
            pre1[i] = (pre1[i-1]+1ll*a[i]*1ll*a[i]%mod)%mod;
        }
    }
    vector<int> getSum(vector<int>& a, vector<int>& query) {
        // write code here
        vector<int>ans;
        sum_pre(a);
        for(int i = 0; i < query.size(); i += 2){
            int l = query[i];
            int r = query[i+1];
            ll sum,pfh;
            if(l != 1){
                sum = (pre[r-1]-pre[l-2])*(pre[r-1]-pre[l-2])%mod;
                pfh = pre1[r-1]-pre1[l-2];
            }
            else{
                sum = (pre[r-1])*(pre[r-1])%mod;
                pfh = pre1[r-1];
            }
            sum = (sum-pfh+mod)%mod;
            sum = sum*500000004%mod;
            ans.push_back(sum);
        }
        return ans;
    }
};

第六场

A-String II

思路：先算出串中所有字母全都转化成26个英文字母中的一个的操作次数，然后按次数从小到大排序，然后优先取次数小的，且取完后总次数不能超过k。对于这26个字母得到的答案取最大值即可。

class Solution {
public:
    /**
     * 
     * @param k int整型 表示最多的操作次数
     * @param s string字符串 表示一个仅包含小写字母的字符串
     * @return int整型
     */
    int string2(int k, string s) {
        // write code here
        int ans = 0;
        for(char i = 'a'; i <= 'z'; i++){
            int a[10005];
            for(int j = 0; j < s.size(); j++){
                char s1 = s[j];
                a[j] = abs(s1-i);
            }
            sort(a,a+s.size());
            int sum = k,cnt = 0;
            for(int j = 0; j < s.size(); j++){
                if(a[j] <= sum){
                    cnt++;
                    sum -= a[j];
                }
                else break;
            }
            ans = max(ans,cnt);
        }
        return ans;
    }
};

B-Bang! Bang!：组合数学（插板法）

思路：

1）首先将（m-1)*k 个音符去掉，然后从剩下的音符中找m个重音符。

2）然后插入这（m-1）* k个音符

class Solution {
public:
    /**
     * 
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    typedef long long ll;
    const int mod = 1e9+7; 
    ll inv(ll a,ll b){
        ll res = 1;
        while(b){
            if(b&1) res = res*a%mod;
            a = a*a%mod;
            b >>= 1;
        }
        return res%mod;
    }
    
    ll cal(int a,int b){
        ll fz = 1,fm = 1;
        for(int i = 1; i <= a; i++){
            fz = fz*1ll*i%mod;
        }
        for(int i = 1; i <= a-b; i++){
            fm = fm*1ll*i%mod;
        }
        for(int i = 1; i <= b; i++){
            fm = fm*1ll*i%mod;
        }
        fm = inv(1ll*fm,1ll*(mod-2));
        return fz*fm%mod;
    }
    
    long long solve_bangbang(int n, int m, int k) {
        // write code here
        int cnt = (m-1)*k;
        if((n-cnt) < m) return 0;
        return cal(n-cnt,m);
    }
};

C-天花板：数论(整除)分块+二分

思路：

n/i 向上取整 = 下取整 (n+i-1)/i = 下取整 (n-1)/i+1

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */
    typedef long long ll;
    long long Sum(int n) {
        // write code here
        ll temp = n,l,r,ans = 0;
        for(l = 1; l <= n; l = r+1){
            if((temp-1)/l) r = (temp-1)/((temp-1)/l);
            else r = n;
            r = min(r,temp);
            ans += (r-l+1)*((temp-1)/l+1);
        }
        return ans;
    }
};

第八场

https://ac.nowcoder.com/acm/contest/9887

A-牛牛选物：dfs/容斥原理

思路：对于每个数，我们选完之后它前面的数我们是不用再去选的，因为对于每个数，我们取完之后都往后取，那么它前面的数被取后往后取的时候已经把这个数取过了，这样就可以不用重复操作，算是一个剪枝了，如果不这样的话会超时。

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

B-牛牛与字符串2：KMP

思路：kmp中的next数组的含义是：next[i] 表示以i结尾的后缀与能前缀匹配的最大下标。

有了这个next数组后，我们还要特判一下如果next[n-1] = 0等情况，如果s[0] == s[n-1] 那么ans = 1,否则ans=-1，比如ABC next[2] = 1,但答案是-1，因为‘A’ != 'C'.

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