头像

摆烂且抽风

小号 抽风且摆烂 周赛




在线 


最近来访(21)
用户头像
yxᴄ
用户头像
yxc的小迷妹
用户头像
唐の月
用户头像
抽风且摆烂
用户头像
White55kai
用户头像
种花家的市长
用户头像
仿生陈冠希不会梦到电子张柏芝
用户头像
花俊ぃ夜醉舞
用户头像
小郑同学
用户头像
zwling
用户头像
萌新_9
用户头像
miraitowazzr
用户头像
SugarT
用户头像
X-7D1C11010
用户头像
呆@_9
用户头像
Olivia_
用户头像
刘十三の美叨


给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

示例 1:

输入:nums = [2,1,4,3], left = 2, right = 3
输出:3
解释:满足条件的三个子数组:[2], [2, 1], [3]

一个点的贡献值为其作为最大值的左边界和右边界 对应的所有子数组的乘积

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        模拟 确实妙
        // int n = nums.size();
        // int ans = 0, m0 = -1, m1 = -1;
        // for(int i = 0; i < n; i ++){
        //     if(nums[i] > right) m0 = i;
        //     if(nums[i] >= left) m1 = i;
        //     ans += m1 - m0;
        // }
        // return ans;
        stack<int> stk;
        int n = nums.size();
        vector<int> l(n, -1), r(n, n);
        for(int i = 0; i < n; i ++){
            while(stk.size() && nums[stk.top()] <= nums[i]) stk.pop();
            if(stk.size()) l[i] = stk.top();
            stk.push(i);
         }
         while(stk.size()) stk.pop();
         for(int i = n - 1; i >= 0; i --){
             while(stk.size() && nums[stk.top()] < nums[i]) stk.pop();
             if(stk.size()) r[i] = stk.top();
             stk.push(i);
         }
         int ans = 0;
         for(int i = 0; i < n; i ++){
             if(nums[i] >= left && nums[i] <= right)
                ans += (i - l[i]) * (r[i] - i);
         }
         return ans;
    }
};


活动打卡代码 AcWing 903. 昂贵的聘礼

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int w[N][N];
int m, n;
int dis[N];
int level[N];
bool st[N];

int D(int down, int up){
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);
    dis[0] = 0;
    for(int i = 1; i <= n + 1; i ++){
        int t = -1;
        for(int j = 0; j <= n; j ++){
            if(!st[j] && (t == -1 || dis[t] > dis[j]))
                t = j;
        }
        st[t] = true;
        for(int j = 0; j <= n; j ++){
            if(!st[j] && level[j] >= down && level[j] <= up)
                dis[j] = min(dis[j], dis[t] + w[t][j]);
        }
    }
    return dis[1];
}
int main (){
    scanf("%d%d", &m, &n);
    memset(w, 0x3f, sizeof w);
    for(int i = 0; i <= n; i ++) w[i][i] = 0;
    for(int i = 1; i <= n; i ++){
        int price, lev, cnt;
        scanf("%d%d%d", &price, &lev, &cnt);
        level[i] = lev;
        w[0][i] = min(w[0][i], price);
        while(cnt --){
            int id, cost;
            scanf("%d%d", &id, &cost);
            w[id][i] = min(w[id][i], cost);
        }
    }
    int res = 0x3f3f3f3f;
    for(int i = level[1] - m; i <= level[1]; i ++) res = min(res, D(i, i + m));

    cout << res << endl;
    return 0;
}



一个正整数如果能被 a 或 b 整除,那么它是神奇的。

给定三个整数 n , a , b ,返回第 n 个神奇的数字。因为答案可能很大,所以返回答案 对 109 + 7 取模 后的值。

示例 1:

输入:n = 1, a = 2, b = 3
输出:2
示例 2:

输入:n = 4, a = 2, b = 3
输出:6

提示:

1 <= n <= 10^9
2 <= a, b <= 4 * 10 ^ 4

对于n 能整除a的个数为 n / a, 同理整除b的个数为 n / b;

其中能整除 a 和 b 的个数可能发生重复计算 需要去除的个数为 n / lcm(a, b);

class Solution {
public:
    int gcd(int a, int b){
        return b ? gcd(b, a % b) : a;
    }
    int nthMagicalNumber(int n, int a, int b) {
        long long l = min(a, b), r = (long long)min(a, b) * n;
        int mod = 1e9 + 7;
        int lcm = a * b / gcd(a, b);
        while(l < r)
        {
            long long mid =  (l + r) / 2;
            if(mid / a + mid / b - mid / lcm >= n ) r = mid;
            else l = mid + 1;
        }
        return l % mod;
    }
};



给你一棵 n 个节点的树(一个无向、连通、无环图),每个节点表示一个城市,编号从 0 到 n - 1 ,且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ,其中 roads[i] = [ai, bi] ,表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表,他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车,或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

示例 1:

输入:roads = [[0,1],[0,2],[0,3]], seats = 5
输出:3
解释:
- 代表 1 直接到达首都,消耗 1 升汽油。
- 代表 2 直接到达首都,消耗 1 升汽油。
- 代表 3 直接到达首都,消耗 1 升汽油。
最少消耗 3 升汽油。
网页捕获_21-11-2022_112424_leetcode.cn.jpeg

class Solution {
public:
    long long ans;
    int h[100010], ne[200010], e[200010], idx;
    int d;
    void add(int a, int b){
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
    }
    int dfs(int u, int fa){
        int s = 1;
        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            if(j == fa) continue;
            int t = dfs(j, u);
            ans += (t + d - 1) / d; // 向下取整
            s += t;
        }
        return s;
    }
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        d = seats;
        memset(h, -1, sizeof h);    
        for(auto x : roads){
            add(x[0], x[1]),  add(x[1], x[0]);
        }
        dfs(0, -1);
        return ans;
    }
};



4721 排队

n 个小朋友排成一排,从左到右依次编号为 1∼n。

第 i 个小朋友的身高为 hi。

虽然队伍已经排好,但是小朋友们对此并不完全满意。

对于一个小朋友来说,如果存在其他小朋友身高比他更矮,却站在他右侧的情况,该小朋友就会感到不满。

每个小朋友的不满程度都可以量化计算,具体来说,对于第 i 个小朋友:

如果存在比他更矮且在他右侧的小朋友,那么他的不满值等于其中最靠右的那个小朋友与他之间的小朋友数量。
如果不存在比他更矮且在他右侧的小朋友,那么他的不满值为 −1。
请你计算并输出每个小朋友的不满值。

注意,第 1 个小朋友和第 2 个小朋友之间的小朋友数量为 0,第 1 个小朋友和第 4 个小朋友之间的小朋友数量为 2。

输入格式
第一行包含整数 n。

第二行包含 n 个整数 h1,h2,…,hn。

输出格式
共一行,输出 n 个整数,第 i 个整数为第 i 个小朋友的不满值。

数据范围
前 5 个测试点满足 2≤n≤5。
所有测试点满足 2≤n≤105,1≤hi≤109。

输入样例1:
6
10 8 5 3 50 45

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
typedef long long LL;
typedef pair<int,int> PII;

const int N = 100010;
int f[N], h[N];

int main ()
{   
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> h[i];

    f[n + 1] = 2e9;
    for(int i = n; i >= 1; i --) f[i] = min(f[i + 1], h[i]);

    for(int i = 1; i <= n; i ++){
        int l = i, r = n;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(h[i] > f[mid]) l = mid;
            else r = mid - 1;
        }
        printf("%d ", r - i - 1);
    }
    return 0;
}
//树状数组 + 离散化
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
vector<int> alls;
int w[N];
int n;
int ans[N];
int tr[N];

int find(int x){
    int l = 0, r = alls.size() - 1;
    while(l < r){
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}
void update(int x, int c){
    for(int i = x; i <= alls.size(); i += i & -i)  tr[i] = max(tr[i], c);
}
int query(int x){
    int mx= 0;
    for(int i = x; i >= 1; i -= i & -i) mx = max(tr[i], mx);

    return mx;
}
int main (){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        scanf("%d", &w[i]);
        alls.push_back(w[i]);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    for(int i = n; i >= 1; i --){
        int x = find(w[i]);
        update(x, i);
        x = query(x - 1);
        if(x < i) ans[i] = -1;
        else ans[i] = x - i - 1;
    }    
    for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';

    return 0;
}

//stack
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int w[N];
int n;
int stk[N];
int ans[N];

int main (){
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> w[i];

    int top = 0;
    for(int i = n; i >= 1; i --){
        if(!top || w[i] <= w[stk[top]]) ans[i] = -1;

        else{
            int l = 1, r = top;
            while(l < r){
                int mid = l + r >> 1;
                if(w[stk[mid]] < w[i]) r = mid;
                else l = mid + 1;
            }
            ans[i] = stk[l] - i - 1;
        }
        if(!top || w[i] < w[stk[top]]) stk[++top] = i;
    }
    for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';

    return 0;
}


活动打卡代码 AcWing 920. 最优乘车

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
typedef long long LL;
typedef pair<int,int> PII;

const int N = 510;
bool g[N][N];
int dis[N];
int q[N];
int m, n;
int stop[N];

void bfs(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    int hh = 0, tt = -1;
    q[++tt] = 1;
    while(hh <= tt){
        int t = q[hh ++];
        for(int i = 1; i <= n; i ++){
            if(g[t][i] && dis[i] > dis[t] + 1){
                dis[i] = dis[t] + 1;
                q[++tt] = i;
            }
        }
    }
}
int main ()
{   
    cin >> m >> n;
    string s;
    getline(cin, s);
    while(m --){
        getline(cin, s);
        stringstream ssin;
        ssin << s;
        int cnt = 0, p;
        while(ssin >> p) stop[cnt ++] = p;
        for(int i = 0; i < cnt; i ++){
            for(int j = i + 1; j < cnt; j ++){
                g[stop[i]][stop[j]] = true;
            }
        }
    }    
    bfs();
    if(dis[n] == 0x3f3f3f3f) puts("NO");
    else cout << max(dis[n] - 1, 0) << endl;
    return 0;
}


活动打卡代码 AcWing 1090. 绿色通道

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010;
int n, t;
int w[N];
int f[N];
int q[N];

bool check(int mid){
    int hh = 0, tt = 0;
    memset(f, 0, sizeof f);
    memset(q, 0, sizeof q);
    for(int i = 1; i <= n; i ++){
        if(hh <= tt && i - mid  > q[hh]) hh ++;
        f[i] = f[q[hh]] + w[i];
        while(hh <= tt && f[q[tt]] >= f[i]) tt --;
        q[++tt] = i;
    }
    int res = 2e9;
    for(int i = n - mid + 1; i <= n; i ++) res = min(res, f[i]);
    return res <= t;
}
int main (){
    cin >> n >> t;
    for(int i = 1; i <= n; i ++) cin >> w[i];

    int l = 0, r = n;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid + 1)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}


活动打卡代码 AcWing 1089. 烽火传递

/*
f[i] = min(f[j]) + w[i],    i - k  <= j <= i - 1    区间长度为 k
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;
int n, k;
int w[N];
int f[N];
int q[N];

int main (){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
    }
    int hh = 0, tt = 0;
    for(int i = 1; i <= n; i ++){
        if(i - k > q[hh]) hh ++;
        f[i] = f[q[hh]] + w[i];
        while(hh <= tt && f[q[tt]] >= f[i]) tt --;
        q[++tt] = i;
    }
    int res = 2e9;
    for(int i = n - k + 1; i <= n; i ++) res = min(res, f[i]);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 1087. 修剪草坪

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;
LL f[N];
LL s[N];
int q[N];
int n, m;

LL g(int x){
    if(x == 0) return 0;
    return f[x - 1] - s[x];
}
int main (){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> s[i];
        s[i] += s[i - 1];
    }
    int hh = 0, tt = 0;
    for(int i = 1; i <= n; i ++){
        if(i - m > q[hh]) hh ++;
        f[i] = max(f[i - 1], g(q[hh]) + s[i]);
        while(hh <= tt && g(q[tt]) <= g(i)) tt --;
        q[++tt] = i;
    }
    cout << f[n] << endl;
    return 0;
}



一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。

给你一个整数数组 nums ,返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大,请返回对 109 + 7 取余 后的结果。

子序列 定义为从一个数组里删除一些(或者不删除)元素,但不改变剩下元素的顺序得到的数组。例如,[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。

示例 1:

输入:nums = [2,1,3]
输出:6
解释:子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。

若序列为 1 2 3 4 5

对于3的贡献值为最小值和最大值

作为最大值的贡献值为3 13 23 123 4种

最为最小值的贡献值为3 34 35 345 4种

class Solution {
public:
    const int mod = 1e9 + 7;
    long long qmi(long long a, int b){
        long long res = 1;
        while(b){
            if(b & 1) res = (res * a) % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return res;
    }
    int sumSubseqWidths(vector<int>& nums) {
        int n = nums.size();
        long long res = 0;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i ++){
            res = (res + qmi(2, i) * nums[i] - qmi(2, n - i - 1) * nums[i]);
        }
        return (res % mod + mod) % mod;
    }
};