第 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];
        
    }
};