BUPT-2022-summer-5

发表于 | 分类于 |

C(数据结构:区间加减、查询最值线段树)

大致题意:一个人在一个城市旅游，旅程有其开始时间和结束时间，给定n个任务，每个任务有其开始时间和结束时间，任务完成后会有奖励p，每在该城市待一天，都会花费k，现求旅程的开始时间和结束时间，使完成任务的奖励之和-花费之和最大(若最大值小于0则输出0，否则输出达到最大值时的开始、结束时间、所完成的任务的编号)

题解:可以将所有任务抽象成小区间，小区间被完全包含时，对答案有贡献，求小区间贡献和-k*区间长度的最大值

区间问题+数据范围2e5，很明显是枚举区间的R，找到最佳的L，再根据此时区间值判断是否更新答案，而对每个R找L时，往往需要借助线段树等数据结构达到log(并且往往是边枚举R边更新L的值)

首先化简问题，固定L为1，则很明显能预处理出一个前缀和数组RR。

而当L不为1时，则要将1~L-1区间对答案的影响消去(一部分来自k、一部分来自左端点<=L-1，右端点<=R的小区间)。

故先将小区间按右端点从小到大重新排列，设所有任务的右端点最大值为MAX，则枚举R从1到MAX，当枚举到i时，将所有右端点<=i的任务的影响插入线段树，将k的影响插入线段树(k这部分在建立线段树时就可预处理好)，然后在1~i区间内查询最小值,(RR[i]-最小值)则为区间的右端点固定为R时，所能取到的最大值。

升级版:若小区间的端点范围开到1e12，小区间个数仍是2e5，易知最佳区间的R一定是某个任务的右端点，L一定是某个任务的左端点，故我们可以先将小区间的左右端点坐标离散化成4e5的范围，再开个4e5的pos数组记录离散化后的坐标和离散化之前的坐标的对应关系以计算k的影响，其他均与上述做法一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 1e6 + 5;
const ll INF = 0x7fffffff;
ll tmp, T, n, m, k;
struct node
{
    ll l, r, p;
    ll id;
    bool operator<(const node &b)
    {
        return r < b.r;
    }
};
node a[maxn];
ll RR[2 * maxn];
// ll lsh[2 * maxn];
ll num;
struct seg_node
{
    pair<ll, ll> val;
    ll lazy;
} segtree[maxn << 2];
void pushup(ll rt)
{
    segtree[rt].val = min(segtree[rt << 1].val, segtree[rt << 1 | 1].val);
}
void pushdown(ll rt, ll ln, ll rn)
{
    if (segtree[rt].lazy)
    {
        segtree[rt << 1].lazy += segtree[rt].lazy;
        segtree[rt << 1 | 1].lazy += segtree[rt].lazy;
        segtree[rt << 1].val.first += segtree[rt].lazy;
        segtree[rt << 1 | 1].val.first += segtree[rt].lazy;
        segtree[rt].lazy = 0;
    }
}
void build(ll left = 1, ll right = num, ll rt = 1)
{
    segtree[rt].lazy = 0;
    if (left == right)
    {
        segtree[rt].val.first = 0;
        segtree[rt].val.second = left;
        return;
    }
    ll mid = (left + right) >> 1;
    build(left, mid, rt << 1);
    build(mid + 1, right, rt << 1 | 1);
    pushup(rt);
}
pair<ll, ll> part_query(ll l, ll r, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        return segtree[rt].val; //+segtree[rt].lazy;
    }
    if (l > right || r < left)
    {
        return {INF, INF};
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    return min(part_query(l, r, left, mid, rt << 1), part_query(l, r, mid + 1, right, rt << 1 | 1));
}
void part_update(ll l, ll r, ll value, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        segtree[rt].val.first += value;
        segtree[rt].lazy += value;
        return;
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    if (l <= mid)
    {
        part_update(l, r, value, left, mid, rt << 1);
    }
    if (r > mid)
    {
        part_update(l, r, value, mid + 1, right, rt << 1 | 1);
    }
    pushup(rt);
}

int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--)
    {
        cin >> n >> k;
        num = 0;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i].l >> a[i].r >> a[i].p;
            a[i].id = i;
            num = max(num, a[i].r);
        }
        memset(RR, 0, sizeof(RR));
        for (ll i = 1; i <= n; i++)
        {

            RR[a[i].r] += a[i].p;
        }
        for (ll i = 1; i <= num; i++)
        {
            // LL[i] += LL[i - 1];
            RR[i] += RR[i - 1];
        }
        for (ll i = 1; i <= num; i++)
        {
            RR[i] -= k * (i);
            // LL[i] -= k * (pos[i] - 1);
        }
        sort(a + 1, a + 1 + n);
        // pos[0] = 0;
        //  LL[num] = 0x7fffffff;
        // pos[0] = 0;
        // deque<ll> qq;
        ll ans = 0;
        ll ansl = -1, ansr = -1;
        build();
        ll tot = 1;
        pair<ll, ll> tmp;
        for (ll i = 1; i <= num; i++)
        {
            
            while (tot <= n && a[tot].r <= i)
            {
                if (a[tot].l + 1 <= num)
                part_update(a[tot].l + 1, num, a[tot].p);//选取到l时，右端点为l的任务仍能完成，故加入时要写l+1
                tot++;
            }
            if (i > 1)
            {
                part_update(i, num, -k);
            }
            tmp = part_query(1, i);
            //cout << i << " " << tmp.first << " " << tmp.second << "!!!\n";
            if (ans < RR[i] - tmp.first)
            {
                ans = RR[i] - tmp.first;
                ansl = tmp.second;
                ansr = i;
            }
        }
        if (ans == 0)
        {
            cout << ans << "\n";
        }
        else
        {
            cout << ans << " " << ansl << " " << ansr << " ";
            vector<ll> ret;
            for (ll i = 1; i <= n; i++)
            {
                if (a[i].l >= ansl && a[i].r <= ansr)
                {
                    ret.push_back(a[i].id);
                }
            }
            cout << ret.size() << "\n";
            for (auto &e : ret)
            {
                cout << e << " ";
            }
            cout << "\n";
        }
        // cout << ans << " " << ans << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

场后反思:

  1. 场上看错了数据范围，以为要离散化，浪费的时间++
  2. 明明思路想好了，code的时候忘记考虑小区间的R的影响，导致最后没写出来
  3. 再考虑L的影响区间时过于混乱(一部分也是开了离散化的锅)，浪费了太多时间在瞎改code上，在code前就应该明确细节

G(博弈论、尺取法)

大致题意:给出、…，、…

现规定第i轮给两位选手分别加上,，规定谁先达到k谁输，若一同达到k或n轮之后都没达到k，则平局，选手1可在每轮结束后选择是否按下reset，若按下，记按下之前选手1的值为x，选手2的值为y，则按下后选手1的值为max(0,x-y)，选手2的值为max(0,y-x)

求选手1能否获胜，若不能，输出-1，若能，则求选手1最少需要按几次reset才能获胜，并求出按下reset的对应回合

题解:观察reset操作，可看出reset操作后双方分数差值不变，相当于双方都减去双方分数的最小值，而不考虑k的限制时，多次reset操作都可看作在最后按reset的位置按一次reset，故可枚举获胜的位置(由后文贪心思路可知，越靠前所需按reset次数越少)，得出获胜的最靠前位置，和其对应的最后一次按reset的位置，再枚举前面的回合，只有在即将到达k时才按reset，即可贪心得出最少按reset的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 2e5 + 5;
ll tmp, T, n, m, k;
ll a[maxn], prea[maxn], b[maxn], preb[maxn];

int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        prea[0] = preb[0] = 0;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i];
            prea[i] = prea[i - 1] + a[i];
        }
        for (ll i = 1; i <= n; i++)
        {
            cin >> b[i];
            preb[i] = preb[i - 1] + b[i];
        }
        ll tot = 0; //最后一次按reset位置，随获胜回合的位置单增
        ll ans = -1;
        vector<ll> ret;
        for (ll i = 1; i <= n; i++) //枚举获胜回合
        {
            while (tot <= i && prea[i] - min(prea[tot], preb[tot]) >= k)//找到满足a不会输的最小tot下标
            {
                tot++;
            }
            if (tot != i && prea[i] - min(prea[tot], preb[tot]) < k && preb[i] - min(prea[tot], preb[tot]) >= k)//计算b是否会输
            {
                ans = i;
                break; //得到最靠前的获胜回合
            }
        }
        if (ans == -1)
        {
            cout << "-1\n";
            continue;
        }
        else if (tot == 0)
        {
            cout << "0\n\n";
            continue;
        }
        else
        {
            bool flag = 1;
            ll pos = 0; //上次按reset位置
            for (ll i = 1; i < tot; i++)
            {
                if (prea[i + 1] - min(prea[pos], preb[pos]) >= k)
                {
                    pos = i; //在i-1回合结束后必须按
                    ret.push_back(i);
                    if (prea[i + 1] - min(prea[pos], preb[pos]) >= k)//按reset后仍可能失败
                    {
                        flag = 0;
                        break;
                    }
                }
            }
            if (!flag)
            {
                cout << "-1\n";
                continue;
            }
            else
            {
                cout << ret.size() + 1 << "\n";
                for (auto &e : ret)
                {
                    cout << e << " ";
                }
                cout << tot << "\n";
            }
        }
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}