第 218 场周赛

第 218 场周赛 

5620. 连接连续二进制数字

给你一个整数 

n

 ，请你将 

1

 到 

n

 的二进制表示连接起来，并返回连接结果对应的 十进制 数字对 

109 + 7

 取余的结果。

• 怎么计算，从左往右，还是从右往左，类似于除法，从左往右比较好，方便处理取模运算
• 怎么进位，当i=2^x时，进一位；

const int mod=1e9+7;
    int getFirstOne(int num){
	    bitset<32> bs(num);
	    int i = 31;
	    for (; i >=0; i--) {
		    if (bs[i]==1)
			    break;
	    }
	    return i+1;
    }
    int concatenatedBinary(int n) {
        long long ans=0;
        int cnt=1;
        int rec=2;
        for(int i=1;i<=n;i++){
            if(rec==i){
                cnt++;
                rec*=2;
            }
            ans=(ans<<cnt)+i;
            ans%=mod;
            
        }
        return (int) ans;
        
    }
           

//用python也很简单   
 def concatenatedBinary(self, n: int) -> int:
        ans=0
        mod=10**9+7
        for num in range(1,n+1):
            b=bin(num)[2:];
            cnt=len(b);
            ans=(ans<<cnt)+num;
            ans%=mod

        return ans
           

 5619. 最小不兼容性

给你一个整数数组 nums​​​ 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。

一个子集的 不兼容性 是该子集里面最大值和最小值的差。

请你返回将数组分成 k 个子集后，各子集 不兼容性 的 和 的 最小值 ，如果无法分成分成 k 个子集，返回 -1 。

子集的定义是数组中一些数字的集合，对数字顺序没有要求。

示例 1：

输入：nums = [1,2,1,4], k = 2

输出：4

解释：最优的分配是 [1,2] 和 [1,4] 。

不兼容性和为 (2-1) + (4-1) = 4 。

注意到 [1,1] 和 [2,4] 可以得到更小的和，但是第一个集合有 2 个相同的元素，所以不可行。

示例 2：

输入：nums = [6,3,8,1,3,1,2,2], k = 4

输出：6

解释：最优的子集分配为 [1,2]，[2,3]，[6,8] 和 [1,3] 。

不兼容性和为 (2-1) + (3-2) + (8-6) + (3-1) = 6 。

示例 3：

输入：nums = [5,3,3,6,3,3], k = 3

输出：-1

解释：没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。

提示：

1 <= k <= nums.length <= 16

nums.length 能被 k 整除。

1 <= nums[i] <= nums.length

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/minimum-incompatibility

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思路：使用dfs,但是要注意剪枝

int ans=INT_MAX;
    int k;
    int per;
    void dfs(vector<int> &cur,vector<int> &cnt,int tmp,int step,vector<int> &nums){
        if(tmp>ans)
            return;
        if(step==nums.size()){
            ans=min(ans,tmp);
            return ;

        }
        for(int i=0;i<k;i++){
            if(nums[step]==cur[i]) //当前集合里有相同的数字，不能放
                continue;
            if(cnt[i]<per){  //集合没有满
                int pre=cur[i];  
                cur[i]=nums[step];
                cnt[i]++;
                dfs(cur,cnt,tmp+((pre!=-1)?cur[i]-pre:0),step+1,nums);

                cnt[i]--;
                cur[i]=pre;

                if(cnt[i]==0)  //i以及i之后的集合都是空的，放那个里面都一样
                    break;
            }
        }

        return ;
    }
    int minimumIncompatibility(vector<int>& nums, int k) {
        unordered_map<int,int> dict;
        int n=nums.size();
        for(auto &it:nums){
            dict[it]++;
            if(dict[it]>k)
                return -1;
        }
        sort(nums.begin(),nums.end());
        vector<int> cur(k,-1);
        vector<int> cnt(k,0);
        this->k=k;
        this->per=n/k;
        dfs(cur,cnt,0,0,nums);
        return ans;
    }
           

基本思路：动态规划，先做预备工作，找到所有符合条件的小集合，然后筛选,其中，对于f[mask]，mask表示的是二进制代码中为1的已经分配好集合了，而f[mask]表示的是最小兼容差

• if f[mask]=-1，f[mask]=f[mask^sub]+value[sub] ，表示的是f[mask]可以有sub集合，以及其补集组成
• if f[mask]=-1,f[mask]=min(f[mask],f[mask^sub]+value[sub]);

class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        if(k==nums.size())
            return 0;
        unordered_map<int,int> dict;
        for(auto &it:nums){
            dict[it]++;
            if(dict[it]>k)
                return -1;
        }
        
        int n=nums.size();
        int M=(1<<n);
        vector<int> value(M,-1);  //预备工作，找到所有的分组
        vector<int> frequent(n+1,0);
        for(int i=1;i<M;i++){
            if(__builtin_popcount(i)==n/k){
                for(int j=0;j<n;j++){
                    if(i&(1<<j)){
                        frequent[nums[j]]++;
                    }
                }
                bool flag=true;
                for(int j=1;j<=n;j++){
                    if(frequent[j]>1){
                        flag=false;
                        break;
                    }
                }                
                
                if(flag){
                    int lb=INT_MAX,ub=INT_MIN;
                    for(int j=1;j<=n;j++){
                        if(frequent[j]>0){
                            lb=min(lb,j);
                            ub=max(ub,j);
                        }
                    }
                    value[i]=ub-lb;
                    //cout<<i<<"  "<<value[i]<<endl;
                }
                for(int j=0;j<n;j++){
                    if(i&(1<<j)){
                        --frequent[nums[j]];
                    }
                }                
            }
        }
        
        vector<int> f(M,-1);
        f[0]=0;
        for(int mask=1;mask<M;++mask){
            if(__builtin_popcount(mask)%(n/k)==0){
                for(int sub=mask;sub;sub=(sub-1)&mask){
                    if(value[sub]!=-1&&f[mask^sub]!=-1){
                        if(f[mask]!=-1){
                            f[mask]=min(f[mask],f[mask^sub]+value[sub]);//mask^sub表示的是不含sub的其他集合
                        }
                        else{
                            f[mask]=f[mask^sub]+value[sub];
                        }
                    }
                }
            }
        }
        return f[M-1];
        
    }
};