日常题

写在前面

最近不知为何，做题不得劲，进而导致我在写某个题的贪心时，能写一个小时
(唉我是彩笔， 有问题的地方记得在评论区说一下，你的建议是我进步的最大帮助)

T1 重构栈

时间限制： 2 秒 内存限制： 1024 MB

题目描述

有一个初始为空的栈 $S$。现在要依次对它执行若干操作，操作共有三种类型：

• + x：将元素 $x$ 压入栈顶；
• ? x：查询元素 $x$ 是否在栈中。查询有两种可能的结果：
  • T：元素 $x$ 在栈中；
  • F：元素 $x$ 不在栈中；
• -：弹出栈顶元素（保证此时栈非空）。

铃仙记录下了整个过程中所有的 + x、T x、F x 操作，却唯独遗漏了所有的 - 操作。

现在，铃仙想在被记录的操作序列中插入若干个 - 操作，使得：

• 任意时刻，栈中的元素互不相同；
• 所有 ? x 查询的结果都与重构出的操作序列一致。

保证至少存在一种合法的重构方案。

输入格式

本题有多组测试数据。

第一行一个整数 $T$（$1 \le T \le 10^5$），表示测试数据的组数。

接下来依次描述每一组数据。对于每组数据：

• 第一行一个正整数 $n$（$1 \le n \le 10^6$）。
• 接下来 $n$ 行，每行形如 + x、T x 或 F x，表示一条被记录的操作。保证 $1 \le x \le 10^9$。
• 保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组数据，输出一行，为一个仅由字符 +、?、- 构成的字符串，表示你重构出的操作序列：

• 若第 $i$ 个字符为 +，表示重构序列的第 $i$ 个操作将一个元素压入栈中；
• 若第 $i$ 个字符为 ?，表示重构序列的第 $i$ 个操作查询一个元素是否在栈中；
• 若第 $i$ 个字符为 -，表示重构序列的第 $i$ 个操作弹出栈顶元素。

若存在多种合法的原始操作序列，输出任意一种即可。

---

T1 Solution

读完题我们可以发现，这是一个模拟栈进出问题。

于是这时候你(事实上是我)就会想：用一个数组直接记录进出数字的状态，然后直接遍历一遍加模拟栈一下就完了

显然这是不行的

我们可以注意到,每一个+ x的操作都是为了保证能满足在它之后某个T x查询要求。如果一个已经被压入栈的数字没有了查询它的操作，那这个数字就没有存在的必要了。反之亦然。

那么我们可以先使用一个数组来记录每个压入操作的过期时间(这里我们先进行预处理，方便输出)。从前往后遍历一次所有操作并记录：

• + x —>记录x最近一次的压入下标
• T x —>寻找对应的最新一次+ x，并以这个压入操作的过期时间设置为当前查询的下标

然后再一次从前往后遍历所有操作：

• 遇到+时，将下标压入栈，答案加一个+
• 遇到T或F时:答案加一个?
• 每一步操作执行完后，循环检查栈顶。如果栈顶元素的过期时间 ≤ 当前下标（说明它已经没用了），就弹出栈顶，答案加一个-

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

vector<int> al;
struct op{
    char c;
    int x;
};
vector<op> a;

int find(int x){
    int l = 0, r = al.size() - 1;
    int ans = -1;
    while(l <= r){
        int mid =(l + r) >> 1;
        if(al[mid] >= x){
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ans + 1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        al.clear();
        a.clear();
        a.resize(n);
        
        for(int i = 0; i < n; i++){
            char c;
            int x;
            cin >> c >> x;
            al.push_back(x);
            a[i] = {c, x};
        }    
        sort(al.begin(), al.end());
        al.erase(unique(al.begin(), al.end()), al.end());
        int m = al.size();
        
        vector<int> l_push(m + 2, -1);
        vector<int> expire(n, -1);
        for(int i = 0; i < n; i++){
            int fx = find(a[i].x);
            if(a[i].c == '+')l_push[fx] = i;
            else if(a[i].c == 'T')expire[l_push[fx]] = i;  
        }
        
        stack<int> s;
        string ans;
        for(int i = 0; i < n; i++){
            if(a[i].c == '+'){
                s.push(i);
                ans += '+';
            }
            else ans += '?';
            while(!s.empty() && expire[s.top()] <= i){
                ans += '-';
                s.pop();
            }
        }
        cout << ans << endl;
    }
    return 0;
}

T2 收获

题目描述

帝放弃了编程，决定"上道"——来到永远亭，正式开始务农。在劳动中，帝改掉了作息不规律的毛病，每天恰好工作 (m) 个单位时间。

现在到了收获的季节，帝需要收割并加工人间之里种植的 (n) 种作物。对于第 (i) 种作物，处理一单位时间能获得 (w_i) 的收益。为了让每天的工作不至于太单调，对于第 (i) 种作物，帝每天处理它的总时间长度可以是 ([l_i, r_i]) 范围内的整数。

某天，天气预报说明天天气不好，成熟的作物需要马上收割，必须今天抢收。可是人间之里人手不够，帝最多只能集中精力照顾一种作物——具体地说，帝最多选择一种作物，并删除每天处理这种作物的时间范围限制，即删除后处理该作物的总时间长度可以是 ([0, m]) 范围内的任意整数，而处理其他作物的时间范围不变。帝仍然要在这一天恰好工作 (m) 个单位时间。

帝想知道：满足上述条件的情况下，这一天能获得的最大收益是多少。

输入格式

第一行两个整数 (n) 和 (m) ((1 \le n \le 10^5), (1 \le m \le 10^{11}))，分别表示作物种类数和一天工作的时间长度。

接下来 (n) 行，每行三个整数 (w_i)、(l_i)、(r_i) ((1 \le w_i \le 10^6), (1 \le l_i \le r_i \le 10^6))，表示作物的收益和时间长度的限制。

数据保证 (\sum l_i \le m \le \sum r_i)。

输出格式

输出一行一个整数，表示这一天能获得的最大收益。

---

T2 Solution

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct zywoo{//dnys
    ll w, l, r;
};

int n;
ll ans = 0, m;
vector<ll> prel, prer, prew, prelv;
vector<ll> ltime, lv;
vector<int> v;

bool cmp(const zywoo& a, const zywoo& b){
    return a.w > b.w;
}

ll find(int a, ll T){
    int al = 1, ar = a;
    ll nans = ar;
    while(al <= ar){
        int mid = (al + ar) >> 1;
        if(prer[mid] - prel[mid] >= T){
            nans = mid;
            ar = mid - 1;
        }
        else{
            al = mid + 1;
        }
    }
    return nans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    vector<zywoo> k(n + 1);
    for(int i = 1;i <= n;i ++)cin >> k[i].w >> k[i].l >> k[i].r;

    prel.resize(n + 1, 0);
    prer.resize(n + 1, 0);
    prew.resize(n + 1, 0);
    prelv.resize(n + 1, 0);
    ltime.resize(n + 2, 0); 
    lv.resize(n + 2, 0);
    sort(k.begin() + 1, k.end(), cmp);

    for(int i = 1; i <= n;i ++){
        prel[i] = prel[i - 1] + k[i].l;
        prer[i] = prer[i - 1] + k[i].r;
        prew[i] = prew[i - 1] + k[i].w * k[i].r;
        prelv[i] = prelv[i - 1] + k[i].w * k[i].l;
    }
    for(int i = n;i >= 1;i --){
        ltime[i] = ltime[i + 1] + k[i].l;
        lv[i] = lv[i + 1] + k[i].l * k[i].w;
    }

    for(int i = 1;i <= n;i ++){
        ll T = m - ltime[i + 1];
        ll nowsum = lv[i + 1];
        if(T >= prer[i - 1]){
            nowsum += prew[i - 1] + (T - prer[i - 1]) * k[i].w;
        }
        else{
            ll ex = T - prel[i - 1];
            int now = find(i - 1, ex);
            ll t = prer[now - 1] - prel[now - 1]; 
            nowsum += prew[now - 1] + k[now].w * (k[now].l + ex - t) + (prelv[i - 1] - prelv[now]);
        }
        ans = max(ans, nowsum);
    }

    cout << ans << endl;

    return 0;
}

T3 破冰车

题目描述

你是一名运输员，驾驶着至冬国最新型的破冰车，奉命穿越风雪交加的冰原，把一批重要物资运往远方的前哨站。

这辆破冰车由 n 个能源核心供能。第 i 个能源核心的储能为 a_i 单位，每消耗 1 单位能源，破冰车恰好前进 1 公里。破冰车只能前进、不能后退，每一公里所消耗的能源，可以自由选择来自哪一个核心。

出发前，所有能源核心都处于满能量状态。沿途设有 m 个由至冬工程师提前架设的补给站，第 j 个补给站距离起点 x_j 公里，并且只能为第 t_j 个能源核心充电。每个补给站储备的能源无穷无尽，能让对应的核心瞬间充满。

请你计算：这辆破冰车最远能行驶多少公里。

---

输入格式

第一行一个整数 T (1 ≤ T ≤ 10^4)，表示测试数据组数。

对于每组数据：

• 第一行两个整数 n, m (1 ≤ n, m ≤ 10^5)，表示能源核心的个数和补给站的个数。
• 第二行 n 个整数 a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9)，分别表示每个能源核心的储能。
• 接下来 m 行，每行两个整数 x_j, t_j (1 ≤ x_j ≤ 10^9, 1 ≤ t_j ≤ n)，分别表示每个补给站的位置和它能给哪个核心充电。

对于每组测试数据，保证 1 ≤ x_1 < x_2 < … < x_m ≤ 10^9。所有测试数据的 n 之和与 m 之和均不超过 2 × 10^5。

---

输出格式

对于每组数据，输出一行一个整数，表示这辆破冰车最远能行驶多少公里。

---

T3 Solution

Code：

#include<bits/stdc++.h>
using namespace std;
const int M = 2e5 + 2;
typedef long long ll;

vector<ll> pos[M];
pair<int, int> xt[M];
ll idx[M], a[M], rest[M];
ll nowpos, nowsum;

ll check(int i){
    if(idx[i] < pos[i].size())return pos[i][idx[i]];
    return 0x3f3f3f3f;
}

void solve(){
    int n, m;
    cin >> n >> m;
    nowsum = 0;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        rest[i] = a[i];
        nowsum += a[i];
        pos[i].clear();
        idx[i] = 0;
    }
    for(int i = 1;i <= m;i ++){
        cin >> xt[i].first >> xt[i].second;
        pos[xt[i].second].push_back(xt[i].first);
    }
    
    priority_queue<pair<ll,int>, vector< pair<ll,int> >, greater<pair<ll,int> > >pq;
    
    nowpos = 0;

    for (int i = 1; i <= n; i++)pq.push(pair<ll, int>(check(i), i));
    
    for(int i = 1;i <= m;i ++){
        ll x = xt[i].first, t = xt[i].second, need = x - nowpos;
        if(nowsum < need){
            cout << nowpos + nowsum << endl;
            return;
        }

        while(need > 0){
            pair<ll, int> c = pq.top();
            pq.pop();
            ll npos = c.first, id = c.second;

            if(npos != check(id) )continue;

            ll at = min(rest[id], need);
            rest[id] -= at;
            nowsum -= at;
            need -= at;

            if(rest[id] > 0)pq.push(pair<ll, int>(check(id), id));
        }
        if(idx[t] < pos[t].size() && pos[t][idx[t]] == x) idx[t] ++;

        ll add = a[t] - rest[t];
        rest[t] = a[t];      
        nowsum += add;

        pq.push(pair<ll, int>(check(t), t));

        nowpos = x;

    }
        
     cout << nowpos + nowsum << endl;
}

    /*while(total > 0){
        cnt ++;
        if(total - e[p[cnt].second] >= dis[cnt]){
            ans += dis[cnt];
            total -= dis[cnt];
        }
        else continue;
    }

    cout << ans << endl;*/


int main(){
    int T;
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}