link: https://leetcode.cn/contest/weekly-contest-517/

今天起得挺早的，在学校睡的第一天，正好是周日就打把力扣了。

有点菜了，这把的 D 挺简单的。ABC 都很简单，随便记一下吧。

A

class Solution {
public:
    int countSpecialIntegers(vector<int>& nums) {
        int n = nums.size();
        vector<bool> vis(101), bad(101);
        for(int i = 0; i < n; i++) {
            if(vis[nums[i]] && nums[i - 1] != nums[i])
                bad[nums[i]] = true;
            vis[nums[i]] = true;
        }
        int res = 0;
        for(int i = 1; i <= 100; i++)
            if(!bad[i] && vis[i]) res++;
        return res;
    }
};

B

忘记开 long long 错了一发，没看范围。

class Solution {
    const int mod = 1'000'000'007;
    
public:
    int ksm(long long a, long long b) {
        a %= mod;
        int res = 1;
        while(b) {
            if(b & 1) res = 1LL * res * a % mod;
            a = 1LL * a * a % mod;
            b >>= 1;
        }
        return res;
    }
    
    int sumDecoded(vector<long long>& nums) {
        long long lens[17];
        lens[0] = 1;
        for(int i = 1; i <= 16; i++)
            lens[i] = lens[i - 1] * 10;
        int res = 0;
        for(long long num : nums) {
            long long width = num % 10;
            long long d = num / 10;
            long long len_y = to_string(d).size() - width;
            long long x = d / lens[len_y];
            long long y = d % lens[len_y];
            res = (res + ksm(x, y)) % mod;
        }
        return res;
    }
};

C

这是 easy version，对于先乘后除，那就是直接分开考虑就可以了。

class Solution {
public:
    int minOperations(vector<int>& nums, int sum) {
        vector<int> ok(sum + 1, INT_MAX), cur(sum + 1, INT_MAX);
        ok[0] = 0;
        for(int num : nums) {
            set<int> st;
            for(int x = num, t = 0; x <= sum; x <<=1, t += 1) {
                st.insert(x);
                cur[x] = min(cur[x], t);
            }
            for(int x = num / 2, t = 1; x > 0; x >>= 1, t += 1) {
                if(x > sum) continue;
                st.insert(x);
                // assert(x <= sum);
                cur[x] = min(cur[x], t);
            }
            for(int i = sum; i >= 0; i--) {
                for(auto x : st) {
                    if(i + x > sum) break;
                    if(ok[i] != INT_MAX)
                        ok[i + x] = min(ok[i + x], ok[i] + cur[x]);
                }
            }
            for(auto x : st)
                cur[x] = INT_MAX;
        }
        // for(int i = 0; i <= sum; i++)
        //     cout << ok[i] << " \n"[i == sum];
        if(ok[sum] == INT_MAX) ok[sum] = -1;
        return ok[sum];
    }
};

D

这个其实挺简单的，但就是没想到呢？

刚开始我是想着给每个数字预处理出来看到达每一个数字需要多少步。后面超时了，我以为是无效状态太多，于是还加了个 set。

但是这样复杂度是 $\mathcal{O}(n{V}^2\log V)$，实际上没必要，直接对于每一个 $num$ 计算先除后乘，次数最多也就 ${\log }^{2}V$，综合复杂度 $\mathcal{O}(nV{\log }^{2}V)$。

class Solution {
public:
    int minOperations(vector<int>& nums, int sum) {
        vector<int> dp(sum + 1, INT_MAX);
        dp[0] = 0;
        for(int num : nums) {
            for(int i = sum; i >= 0; i--) {
                if(dp[i] == INT_MAX) continue;
                for(int x = num, t = 0; x > 0; x >>= 1, t += 1) {
                    for(int xx = x, tt = 0; xx + i <= sum; xx <<= 1, tt += 1) {
                        dp[i + xx] = min(dp[i + xx], dp[i] + t + tt);
                    }
                }
            }
        }
        
        return dp[sum] == INT_MAX ? -1 : dp[sum];
    }
};