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

A题 数据范围1024 直接暴力做了...

    public int string2(int k, String s) {
        // write code here
        int[] arr = new int[s.length()];
        char[] str = s.toCharArray();
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = str[i] - 'a';
        }

        int res =0;
        for(int i=0;i<26;++i){
            int kk=k;
            int cur =i;

            //都转成cur
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for(int j=0;j<arr.length;++j){
                queue.add(Math.abs(cur-arr[j]));
            }
            int curRes =0;

            while(!queue.isEmpty() && kk>=0 && queue.peek() <= kk){
                curRes++;
                kk-=queue.poll();
            }
            res =Math.max(res,curRes);
        }


        return res;
    }

B题 当时想到排列组合，思路想错了 没走到计算那一步。（计算取模更麻烦）

解法1： 排列组合方式 （使用dp求解组合数）

    int mod =1000000007;
    public long solve_bangbang (int n, int m, int k) {
        int down = n- k*(m-1);
        int up =m;
        if(down <up) return 0;
        //在down中选up个位置放重音。
        //使用性质 C(a,b) =C(a-1,b)+C(a-1,b-1)
        return fun(down,up);
    }

    public long fun(int a,int b){
        int n =Math.max(a,b)+1;
        long[][] dp = new long[n][n];
        for(int i=1;i<n;++i){
            dp[i][0]=1;
            dp[i][i]=1;
            for(int j=1;j<=i/2;++j){
                dp[i][j] = (dp[i-1][j]+dp[i-1][j-1]) % mod;
                dp[i][i-j] = dp[i][j];
            }
        }
        return dp[a][b];
    }

解法2： 排列组合方式（使用乘法逆元+快速幂 ？ 看题解来的）

    int mod=1000000007;
    public long solve_bangbang (int n, int m, int k) {
        long c=(m-1)*k + m;
        if(n<c)return 0;
        int insertNum = n- k*(m-1);
        int insertPos = m;

        return C(insertNum,insertPos);
    }

    public long fastPower2(long base,long power){
        long result = 1;
        while(power>0){
            if( (power&1) ==1 ){
                result = (result*base)%mod;
            }
            power = power/2;
            base = (base*base )%mod;
        }
        return result;
    }

    long C(int n,int m){
        long 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*fastPower2(tp,mod-2)%mod;
    }

解法3： 直接dp

    public long solve_bangbang (int n, int m, int k) {
        int mod =1000000007;

        long[][] dp =new long[1005][1005];
        //[i][j]   i ： 重音数 ；  j：音符数

        //如果没有重音 只有一种情况
        for(int j=0;j<=n;++j){
            dp[0][j]=1;
        }
        //如果只有一个重音， 可以放任意一个位置。 不用考虑间隔k
        for(int j=1;j<=n;++j){
            //对于每个位置 dp[1][j] 根据当前位置放不放重音，分两种情况
            // dp[0][j-1]表示 前面j-1个音符不放重音，重音放在j位置上
            // dp[1][j-1]表示重音放在前j-1个位置， 当前位置不放
            dp[1][j] = (dp[0][j-1]+dp[1][j-1])%mod;
        }

        //如果有两个以上的重音
        for(int i=2; i<=m;++i){
            // 至少得有 j=(i-1)*k+i 个音符，才能放得下这么多重音。
            for(int j=(i-1)*k+i;j<=n;++j){
                //dp[i][j]同样分两种情况， 与上面1个重音的情况不同的是，如果当前位置放重音，那前i-1个重音必须放在前j-k-1个位置上（间隔为k）
                //dp[i][j-1]表示前j-1个位置放了i个重音， 当前位置不放
                //dp[i-1][j-k-1]表示前j-k-1个位置放了i-1个重音，当前位置放一个
                dp[i][j] = (dp[i][j-1]+dp[i-1][j-k-1]) %mod;
            }
        }

//        //打印dp表
//        for(int i=0;i<=m;++i){
//            for(int j=0; j<=n;++j){
//                System.out.print(dp[i][j]+"\t");
//            }
//            System.out.println();
//        }
        return dp[m][n];
    }

C题： 看懂了再填坑....