博客

第 87 场双周赛

T1 — 模拟

class Solution {
public:
    int q[13] = {0,31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    int get(string s)
    {
        int m = stoi(s.substr(0,2));
        int d = stoi(s.substr(3,2));
        int res = 0;
        
        for(int i = 0; i < m; i ++) res += q[i];
        return res + d;
    }
    
    int countDaysTogether(string a, string b, string c, string d) {
        
        
        int s1 = get(a);
        int s2 = get(b);
        int s3 = get(c);
        int s4 = get(d);
        
        return max(0, min(s2, s4) - max(s3, s1) + 1);
        
        
    }
};

T2 — 贪心

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int res = 0, j = 0;
        for(int i = 0; i < b.size(); i ++)
        {
            if(j >= a.size()) break;
            if(a[j] <= b[i] && j < a.size()) j++, res ++;
        }
        return res;
    }
};

T3 — 位运算贪心 / 线段树 + 二分

位运算贪心

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        int n = nums.size();
        
        vector<int> p(30, n);
        vector<int> res(n);
        for(int i = n - 1; i >= 0; i --)
        {
            int t = i;
            for(int j = 0; j < 30; j ++)
            {
                if(nums[i] >> j & 1) p[j] = i;
                else if(p[j] != n) t = max(t, p[j]); 
            }
            res[i] = t - i + 1;
        }
        return res;
    }
};

线段树 + 二分

class Solution {
public:
    int w[100010];
    
    struct node
    {
        int l,r;
        int sum;
    }tr[400010];

    void pushup(int u)
    {
        tr[u].sum = tr[u << 1].sum | tr[u << 1 | 1].sum;
    }

    void build(int u,int l,int r)
    {
        if(l==r)tr[u]={l,r,w[l]};
        else
        {
            tr[u]={l,r};
            int mid=l+r>>1;
            build(u<<1,l,mid);
            build(u<<1|1,mid+1,r);
            pushup(u);
        }
    }

    int query(int u,int l,int r)
    {
        if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
        else
        {
            int mid=tr[u].l+tr[u].r>>1;
            if(r<=mid)return query(u<<1,l,r);
            else if(l>mid)return query(u<<1|1,l,r);
            else
            {
                int left=query(u<<1,l,r);
                int right=query(u<<1|1,l,r);
                return left | right;
            }
        }
    }

    vector<int> smallestSubarrays(vector<int>& nums) {
        vector<int>res;
        int n = nums.size();
        for(int i = 0; i < nums.size(); i ++)
            w[i + 1] = nums[i];
        
        build(1,1,n);
        
        for(int i = 1; i <= n; i ++)
        {
            int maxv = query(1, i, n);
            //cout << maxv << ' ';
            int l = i, r = n;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(query(1, i, mid) < maxv) l = mid + 1;
                else r = mid;
            }
            res.push_back(r - i + 1);
        }
        return res;
    }
};

T4 — 贪心

class Solution {
public:
    long long minimumMoney(vector<vector<int>>& q) {
        long long res = 0;
        long long sum = 0;
        for(auto &p : q)
        {
            int a = p[0], b = p[1];
            if(a > b) sum += a - b;
        }

        for(auto &p : q)
        {
            int a = p[0], b = p[1];
            long long s = sum;
            if(a > b) s -= a - b;
            res = max(res, s + a);
        }

        return res;
    }
};