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

A：String II
枚举最后子序列是什么字符，然后暴力处理结果即可。

public:
    /**
     * 
     * @param k int整型 表示最多的操作次数
     * @param s string字符串 表示一个仅包含小写字母的字符串
     * @return int整型
     */
    int a[1100];
    int string2(int k, string s) {
        // write code here
        int n =s.length(),mx=0;
        for(int c=0;c<26;c++){
            memset(a,0,sizeof(a));
            for(int i=0;i<n;i++){
                a[i]=abs(s[i]-'a'-c);
            }
            sort(a,a+n);
            int tp=0,nm=0;
            for(int i=0;i<n;i++){
                if(tp+a[i]<=k){
                    tp+=a[i];nm++;
                }else{
                    break;
                }

            }
            mx=max(mx,nm);
        }
        return mx;
    }
};

B：Bang! Bang!
很经典的组合数学问题。

要选出m个重音，每个重音中间隔k个音符，则最少需要m+(m-1)*k个音符才能有方案。

我们先删除这(m-1)*k 个隔离的字符，然后在剩下的音符中选m个，

选完后在他们之间插入之间删去的字符,刚好是满足条件的（在剩下的音符中选出m个后，在每两个重音之间插入k个音符，这与在原来n个音符选m个且符合条件的方案一一对应）。

所以：方案数为：C(n-(m-1)*k,m);

typedef long long ll;
const int mod = 1e9+7;

class Solution {
public:
    /**
     * 
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    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){
        ll ans=1,tp=1;
        for(int i=1;i<=n;i++)ans=ans*i%mod;
        for(int i=1;i<=m;i++)tp=tp*i%mod;
        for(int i=1;i<=n-m;i++)tp=tp*i%mod;
        return ans*qpow(tp,mod-2)%mod;
    }
    long long solve_bangbang(int n, int m, int k) {
        // write code here
        ll c=(m-1)*k + m;
        if(n<c)return 0;
        n-=(m-1)*k;
       return C(n,m);
    }
};

C：天花板

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