题目链接：第 325 场周赛 – 力扣（LeetCode）

• 最后一题没考虑全痛失AK

到目标字符串的最短距离

class Solution {
public:
    int closetTarget(vector<string>& words, string target, int startIndex) 
    {
        int res=INT_MAX;
        int n=words.size();
        for(int i=0;i<n;i++)
        {
            if(words[i]==target)
            {
                res=min(res, (i-startIndex+n)%n);
                res=min(res, (startIndex-i+n)%n);
            }
        }
        return res==INT_MAX?-1:res;
    }
};

每种字符至少取K个

从头或尾任取一些数字，让abc都至少出现k次。

做法：二分步数（PS：肯定有其他做法，没多想）

class Solution {
public:
    int s1[100010][4], s2[100010][4];
    int k;
    bool check(int len, int n)
    {
        for(int l=0, r=len-l;l<=len;l++, r--)
        {
            int a=(l-1>=0?s1[l-1][0]:0)+s2[n-r][0];
            int b=(l-1>=0?s1[l-1][1]:0)+s2[n-r][1];
            int c=(l-1>=0?s1[l-1][2]:0)+s2[n-r][2];
            if(a>=k && b>=k && c>=k) return true;
        }
        return false;
    }
    int takeCharacters(string s, int k) {
        if(k==0) return 0;
        this->k=k;
        for(int i=0;i<s.size();i++){
            if(i) for(int j=0;j<3;j++) s1[i][j]=s1[i-1][j];
            s1[i][s[i]-'a']++;
        }
        for(int i=s.size()-1;i>=0;i--){
            for(int j=0;j<3;j++) s2[i][j]=s2[i+1][j];
            s2[i][s[i]-'a']++;
        }
        
        int l=1, r=s.size();
        while(l<r)
        {
            int mid=l+r>>1;
            if(check(mid, s.size())) r=mid;
            else l=mid+1;
        }
        if(check(r, s.size())) return r;
        return -1;
    }
};

礼盒的最大甜蜜度

任选k个元素求其之间差最小值，使这个最小值最大。

做法：直接二分甜蜜度

class Solution {
public:
    
    int n, k;
    vector<int> price;
    bool check(int m)
    {
        int r=n-1, l=0;
        if(price[r]-price[l]<m) return false;
        int cnt=2, d=0;
        for(int i=1;i<n-1;i++)
        {
            if(price[i]-price[l]<m) continue;
            if(price[r]-price[i]<m) break;
            cnt++;
            l=i;
        }
        
        return cnt>=k;
    }
    
    int maximumTastiness(vector<int>& price, int k) {
        n=price.size();
        sort(price.begin(), price.end());
        this->price=price;
        this->k=k;
        
        int l=0, r=1e9;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(check(mid)) l=mid;
            else r=mid-1;
        }
        
        return r;
    }
};

好分区的数目

好分区方案数=总方案数-坏分区方案数

• 情况1：$sum>=k\times2$，这种是正常情况，统计一侧分区的方案数再乘以2，就是坏分区方案数

• 情况2：$sum<k\times2$，此时统计一侧分区的方案会重复统计（如[1,2,3], k=5。此时sum=6, 统计一侧方案数时会有：(0, 6), (1, 5), (2, 4), (3, 3), (4, 2)。(3, 3)和(4, 2)都包含重复）但这种情况不会有好分区，特判掉即可

做法：动态规划-01背包

状态表示：$dp[i][j]$ 表示考虑前$i$个数字且总和为$j$的方案数

状态计算：

1. 不考虑第$i$个数字：$dp[i][j]=dp[i-1][j]$
2. 考虑第$i$个数字：$dp[i][j]+=dp[i][j-nums[i]], j>=nums[i]$

结果表示：$res=2\times\sum\limits_{i=0}^{k-1}{dp[n][i]}$

答案表示：$ans=2^n-res$

class Solution {
public:
    int MOD=1e9+7;
    int dp[1010][1010];
    
    int qmi(int a, int b)
    {
        long long res=1;
        while(b)
        {
            if(b&1) res=res*a%MOD;
            a=1ll*a*a%MOD;
            b>>=1;
        }
        return res;
    }
    
    int countPartitions(vector<int>& nums, int k) {
        dp[0][0]=1;
        int n=nums.size();
        long long sum=0;
        for(auto x: nums) sum+=x;
        if(sum<k*2) return 0;
            
        for(int ii=0;ii<n;ii++){
            int i=ii+1;
            for(int j=0;j<k;j++){
                dp[i][j]=dp[i-1][j];//不选
                if(j-nums[ii]>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-nums[ii]])%MOD;
            }
        }
        
        long long res=0;
        for(int i=0;i<k;i++) {
            res=(res+dp[n][i])%MOD;
        }

        res=res*2%MOD;
        
        return (qmi(2, n)-res+MOD)%MOD;
    }
};