【赛时 AK】LeetCode 周赛 469 题解

1. 计算十进制表示

class Solution {
public:
    vector<int> decimalRepresentation(int n) {
        vector ret(0,0);
        int cur=1;
        while (n){
            if (n%10){
                ret.push_back(n%10*cur);
            }
            n/=10;
            if (cur<1000000000) cur*=10;
        }
        ranges::reverse(ret);
        return ret;
    }
};

2. 分割数组得到最小绝对差

class Solution {
public:
    long long splitArray(vector<int>& nums) {
        int n=nums.size();
        int l=n-1;
        for (;l>0;l--){
            if (nums[l]>=nums[l-1]){
                l--;
                break;
            }
        }
        long long ans=LLONG_MAX;
        long long cur=0,sum=accumulate(nums.begin(),nums.end(),0ll);
        for (int i=0;i<n;i++){
            if (i and nums[i]<=nums[i-1]){
                break;
            }
            cur+=nums[i];
            if (i>=l){
                ans=min(
                    ans,
                    abs(cur-(sum-cur))
                );
            }
        }
        if (ans==LLONG_MAX) return -1;
        else return ans;
    }
};

3. ZigZag 数组的总数 I

DP

template<typename T = long long, int mod = 998244353>
struct Mint {
    T v;

    Mint(T _v = T{}) {
        v = _v % mod;
        if (v < 0) v += mod;
    }

    explicit operator int() const { return (int)v; }
    explicit operator long long() const { return (long long)v; }

    Mint operator+(const Mint &o) const { return Mint(v + o.v); }
    Mint operator-(const Mint &o) const { return Mint(v - o.v); }
    Mint operator*(const Mint &o) const { return Mint(v * o.v % mod); }

    Mint pow(long long e) const {
        Mint res(1), base(v);
        while (e > 0) {
            if (e & 1) res = res * base;
            base = base * base;
            e >>= 1;
        }
        return res;
    }

    Mint inv() const { return pow(mod - 2); }

    Mint operator/(const Mint &o) const { return *this * o.inv(); }

    Mint& operator+=(const Mint &o) { v += o.v; if (v >= mod) v -= mod; return *this; }
    Mint& operator-=(const Mint &o) { v -= o.v; if (v < 0) v += mod; return *this; }
    Mint& operator*=(const Mint &o) { v = (v * o.v) % mod; return *this; }
    Mint& operator/=(const Mint &o) { return *this *= o.inv(); }

    bool operator==(const Mint &o) const { return v == o.v; }
    bool operator!=(const Mint &o) const { return v != o.v; }

    friend istream& operator>>(istream &is, Mint &m) {
        long long x; is >> x;
        m = Mint(x);
        return is;
    }

    friend ostream& operator<<(ostream &os, const Mint &m) {
        return os << m.v;
    }
};

using Z=Mint<long long,1000000007>;

Z dp[2001][2001][2];

class Solution {
public:
    
    int zigZagArrays(int n, int l, int r) {
        for (int i=l;i<=r;i++){
            dp[1][i][0]=dp[1][i][1]=1;
        }
        for (int i=2;i<=n;i++){
            for (int j=l;j<=r;j++) dp[i][j][0]=dp[i][j][1]=0;
            Z cur=dp[i-1][l][0];
            for (int j=l+1;j<=r;j++){
                dp[i][j][1]+=cur;
                cur+=dp[i-1][j][0];
            }
            cur=dp[i-1][r][1];
            for (int j=r-1;j>=l;j--){
                dp[i][j][0]+=cur;
                cur+=dp[i-1][j][1];
            }
        }
        Z res=0;
        for (int i=l;i<=r;i++)
            res+=dp[n][i][0]+dp[n][i][1];
        return (int)res;
    }
};

4. ZigZag 数组的总数 II

矩阵乘法优化 DP

template <typename T = long long, int p = 1000000007>
struct matrix {
    int n, m;
    std::vector<std::vector<T>> a;
    matrix(int _n = 0, int _m = 0, T x = T{}) : n(_n), m(_m), a(_n, std::vector<T>(_m, 0)) {
        for (int i = 0; i < std::min(n, m); ++i) a[i][i] = x;
    }
    std::vector<T>& operator[](int i) { return a[i]; }
    const std::vector<T>& operator[](int i) const { return a[i]; }

    matrix operator*(const matrix& b) const {
        matrix ret(n, b.m);
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < m; ++k) {
                if (!a[i][k]) continue;
                long long val = a[i][k];
                for (int j = 0; j < b.m; ++j) {
                    ret[i][j] = (ret[i][j] + val * b[k][j]) % p;
                }
            }
        }
        return ret;
    }

    matrix pow(long long b) const {
        matrix base = *this;
        matrix ret(n, n, T{1});
        while (b) {
            if (b & 1LL) ret = ret * base;
            base = base * base;
            b >>= 1LL;
        }
        return ret;
    }
};

class Solution {
public:
    int zigZagArrays(int n, int l, int r) {
        l--,r--;
        matrix b={1,75,0ll};
        for (int i=l;i<=r;i++){
            b[0][i]=1;
        }
        matrix u={75,75,0ll},v={75,75,0ll};
        for (int j=l;j<=r;j++){
            for (int i=l;i<j;i++){
                u[i][j]=1;
            }
            for (int i=j+1;i<=r;i++){
                v[i][j]=1;
            }
        }
        n--;
        matrix w=u*v;
        matrix a=b*w.pow(n/2);
        if (n&1) a=a*u;
        long long ans=0;
        for (int i=l;i<=r;i++) ans=(ans+a[0][i])%1000000007;
        w=v*u;
        a=b*w.pow(n/2);
        if (n&1) a=a*v;
        for (int i=l;i<=r;i++) ans=(ans+a[0][i])%1000000007;
        return ans;
    }
};