一月无训老年选手险被第一题直接防下,自信膨胀妄图冲击国服前 100 不料写错下标狠狠 WA遗憾离场

---

3345. 最小可整除数位乘积 I

数据范围很小,暴力

class Solution {
public:
    int smallestNumber(int n, int t) {
        for(int i=n;i<=100;i++){
            int cnt=1,p=i;
            while(p){
                cnt*=(p%10);
                p/=10;
            }
            if(cnt%t==0)return i;
        }
        return -1;
    }
};

3346. 执行操作后元素的最高频率 I

区间加减,不难想到差分

然后在值域上统计即可

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> a(1e5+5);
        vector<int> b(1e5+5);
        for(int i=0;i<n;i++){
            b[nums[i]]++;
            int l=max(0,nums[i]-k);
            int r=min((int)1e5+1,nums[i]+k);
            a[l]++;
            a[r+1]--;
        }
        int ans=-1;
        for(int i=0;i<1e5+4;i++){
            a[i+1]+=a[i];
            a[i]=min(a[i],b[i]+numOperations);
            // cout<<i<<' '<<a[i]<<endl;;
            ans=max(ans,a[i]);
        }
        return ans;
    }
};

3347. 执行操作后元素的最高频率 II

数据范围改为 1e9,第二题加个离散化即可

记得现在数据范围要翻三倍

template <typename T> void print(const T &t) { std::cout << t << endl; }
template <typename T, typename... Args> void print(const T &t, const Args... args)
{
    std::cout << t << ' ';
    print(args...);
}

template <typename T>
struct Discrete{
    vector<T> arr;
    Discrete(){}
    Discrete(vector<T> &arr){
        init(arr);
    }
    void init(vector<T> &arr){
        this->arr=arr;
        // clear();
    }
    void add(T val){
        arr.push_back(val);
    }
    void clear(){
        sort(arr.begin(),arr.end());
        arr.erase(unique(arr.begin(),arr.end()),arr.end());
    }
    T get(T v){
        return lower_bound(arr.begin(),arr.end(),v)-arr.begin();
    }
};


class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        Discrete<int> d(nums);
        for(auto i: nums){
            d.add(i+k);
            d.add(i-k);
        }
        d.clear();
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> a(3e5+5);
        vector<int> b(3e5+5);
        for(int i=0;i<n;i++){
            int x=d.get(nums[i]);
            b[x]++;
            int aa=d.get(nums[i]-k);
            int bb=d.get(nums[i]+k);
            int l=max(0,aa);
            int r=min((int)3e5+4,bb);
            a[l]++;
            a[r+1]--;
        }
        int ans=-1;
        for(int i=0;i<3e5+4;i++){
            a[i+1]+=a[i];
            a[i]=min(a[i],b[i]+numOperations);
            ans=max(ans,a[i]);
        }
        return ans;
    }
};

3348. 最小可整除数位乘积 II

待补