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

A题：

看到S的长度非常小，考虑暴力+贪心的做法，依次对于每个字符，与所有的字符串作差，显然会优先改变差值小的字符，代码如下：

class Solution {
public:
    /**
     * 
     * @param k int整型 表示最多的操作次数
     * @param s string字符串 表示一个仅包含小写字母的字符串
     * @return int整型
     */
    int f[2010];
    int string2(int k, string s) {
        int len=s.size(),sans=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++)
                f[j]=abs(s[i]-s[j]);
            sort(f,f+len);
            int ans=len,s=0;
            for(int j=0;j<len;j++){
                s=s+f[j];
                if(s>k){
                    ans=j;
                    break;
                }
            }
            sans=max(sans,ans);
        }
        return sans;
    }
};

时间复杂度为O（∣s∣^2 log ∣s∣）
当然也有更快的做法，留给读者考虑。

B题：

看到n和m的数据范围只有1000，考虑dp。
设dp[i][j]为前i个字符，设计了j个重音符的方案数。
分为第i个字符取或不取重音符的两个决策。
当不取重音符的时候 dp[i][j]=dp[i-1][j]
当取重音符的时候又分为j=0，j=1和j>1三种情况
当j=0时，说明不取重音符，方案数不变。
当j=1时，说明在第1~i-1个字符中没有取重音符，无需考虑k，显然方案数+1，所以dp[i][j]=1。
当j>1时，有了k的限制，dp[i][j]就是前i-k-1个字符中取j-1个的方案数,即dp[i][j]=dp[i-k-1][j-1]。
所以，把两种决策汇总，就是dp[i][j]的答案。
最后，别忘了取模。
代码如下：

class Solution {
public:
    /**
     * 
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    int M=1000000007;
    long long dp[1010][1010];
    long long solve_bangbang(int n, int m, int k) {
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=min(i,m);j++){
                dp[i][j]=dp[i-1][j];
                if(j==1)dp[i][j]=(dp[i][j]+1)%M;
                if(j>1&&i-k>=0)dp[i][j]=(dp[i][j]+dp[i-k-1][j-1])%M;
            }
        }
        return dp[n][m];
    }
};

时间复杂度O（nm）
同样也有更快的组合数做法，留给读者考虑。

C题：

这是一道整除分块题。
与模板题唯一不同的是，这道题向上取整。
还不了解整除分块的自行上网查找资料，这里不再赘述，这里只考虑l和r的变化。
设p为当i=l时,⌈n/i⌉的值。
r即为满足⌈n/r⌉=p是的最大值。
即为满足⌊n/r⌋=p-1的最大值。
但是还要考虑当p-1|n时，r应该比原来小1。
这样就把这道题转化成了模板题。
代码如下：

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

时间复杂度O（√n）

#题解#