2023.02.21 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

给定 $k$$k$ 以及序列 $t$$t$ 个数 $a_1,a_2,\cdots a_t$$a_1, a_2, \cdots a_t$，你需要求出最小的 $k$$k$ 的倍数满足其所有数字都不存在 $a_1,a_2,\cdots ,a_t$$a_1, a_2, \cdots, a_t$。

类似的原题是 Vijos-1065 最小数字倍数，该题要求仅存在对应数。

一道很简单但做得很麻烦的题，首先考虑的是 $dp(i,j,k)$$dp(i, j, k)$ 表示前 $i$$i$ 位最后一位为 $j$$j$ 然后第 $i$$i$ 对 $i+1$$i + 1$ 及以后的贡献为 $k$$k$ 对应的数，这样的时空复杂度卡的都很死，然后写转移的时候发现 $j$$j$ 是没有意义的，只转移合法的即可，于是去掉一维但时间复杂度不变。

转移及其复杂，需要考虑很多细节，也不知道我咋想出来的，奇奇怪怪。

Code

xxxxxxxxxx
133
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
/*
24
37 9
25
0 1 2 3 4 5 6 7 9
26

27
233333 8
28
2 3 4 5 6 7 8 9
29
*/
30

31
template < typename T = int >
32
inline T read(void);
33

34
bitset < 10 > exist[20];
35

36
bitset < 10 > ban;
37

38
int K, T;
39

40
// basic_string < int > ends[10];
41
map < int, int > mp;
42
unordered_set < int > vis;
43
unordered_set < int > nums;
44
unordered_set < int > legal;
45
ll dp[20][1100000];
46
ll pow10[20];
47
ll ans(LONG_LONG_MAX);
48

49
int main(){
50
    freopen("digit.in", "r", stdin);
51
    freopen("digit.out", "w", stdout);
52
    pow10[0] = 1;
53
    for(int i = 1; i <= 18; ++i)pow10[i] = pow10[i - 1] * 10;
54
    memset(dp, -1, sizeof dp);
55
    K = read(), T = read();
56
    int digitK(0), tmp = K;
57
    while(tmp)++digitK, tmp /= 10;
58
    for(int i = 1; i <= T; ++i)ban[read()] = true;
59
    if(K == 0)printf("%d\n", ban[0] ? -1 : 0), exit(0);
60
    for(int i = 1; i <= 2 * K; ++i){
61
        int val = i;
62
        bool flag(true);
63
        while(val){
64
            if(ban[val % 10]){flag = false; break;}
65
            val /= 10;
66
        }if(flag)legal.insert(i);
67
    }
68
    for(int j = 1; vis.find(K * j % 10) == vis.end(); ++j){
69
        vis.insert(K * j % 10);
70
        // if(!ban[K * j % 10])nums.insert(K * j % 10), mp[K * j % 10] = K * j;
71
        nums.insert(K * j % 10), mp[K * j % 10] = K * j;
72
    }
73
    // dp[0][0][0] = 0;
74
    for(auto num : nums){
75
        if(ban[mp[num] % 10])continue;
76
        dp[1][mp[num] / 10] = mp[num];
77
        // printf("upd dp[%d][%d] = %d\n", 1, mp[num] / 10, mp[num]);
78
        if(!(mp[num] / 10) || legal.find(mp[num] / 10) != legal.end())ans = min(ans,  dp[1][mp[num] / 10]);
79
    }if(ans != LONG_LONG_MAX)printf("%lld\n", ans), exit(0);
80
    // exit(0);
81
    for(int i = 1; i <= 18 - digitK; ++i){
82
        for(auto j : nums){
83
            for(int k = 0; k <= 1000000; ++k){
84
                if(!~dp[i][k])continue;
85
                if(ban[(j + k % 10) % 10])continue;
86
                if(j + k % 10 <= 9){
87
                    // printf("[%d][%d][%d] => [%d][%d][%d]\n", i, j, k, i + 1, j + k % 10, k / 10 + mp[j] / 10);
88
                    dp[i + 1][k / 10 + mp[j] / 10] = dp[i][k] + (ll)mp[j] * pow10[i];
89
                    if(!(k / 10 + mp[j] / 10) || legal.find(k / 10 + mp[j] / 10) != legal.end())ans = min(ans, dp[i + 1][k / 10 + mp[j] / 10]);
90
                }else{
91
                    // printf("[%d][%d][%d] => [%d][%d][%d]\n", i, j, k, i + 1, (j + k % 10) % 10, k / 10 + mp[j] / 10 + 1);
92
                    dp[i + 1][k / 10 + mp[j] / 10 + 1] = dp[i][k] + (ll)mp[j] * pow10[i];
93
                    if(!(k / 10 + mp[j] / 10 + 1) || legal.find(k / 10 + mp[j] / 10 + 1) != legal.end())ans = min(ans, dp[i + 1][k / 10 + mp[j] / 10 + 1]);
94
                }
95
            }
96
        }
97
        if(ans != LONG_LONG_MAX)printf("%lld\n", ans), exit(0);
98
    }printf("-1\n");
99

100
    // int N = read();
101
    // for(int i = 1; i <= 10000; ++i){
102
    //     ll val = (ll)N * i;
103
    //     int cnt(0);
104
    //     while(val){
105
    //         exist[++cnt][val % 10] = true;
106
    //         val /= 10;
107
    //     }
108
    // }
109
    // for(int i = 1; i <= 10; ++i){
110
    //     printf("digit %d : ", i);
111
    //     for(int j = 0; j <= 9; ++j)if(exist[i][j])printf("%d ", j);
112
    //     printf("\n");
113
    // }
114

115
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
116
    return 0;
117
}
118

119
template < typename T >
120
inline T read(void){
121
    T ret(0);
122
    int flag(1);
123
    char c = getchar();
124
    while(c != '-' && !isdigit(c))c = getchar();
125
    if(c == '-')flag = -1, c = getchar();
126
    while(isdigit(c)){
127
        ret *= 10;
128
        ret += int(c - '0');
129
        c = getchar();
130
    }
131
    ret *= flag;
132
    return ret;
133
}

T2

原题 UVA1422 Processor。

存在 $n$$n$ 个任务，每个任务有有效时间 $[s_i,t_i]$$[s_i, t_i]$，任务量 $w_i$$w_i$，存在一个可变速处理器，其速度为 $v$$v$ 时处理对应任务的时间就是 ${\displaystyle \frac{w_i}{v}}$$\dfrac{w_i}{v}$，你需要最小化最大速度使得所有任务可以在规定时间内完成。

大概想出来贪心了，左端点排序然后右端点排序建堆，但是取元素然后区间覆盖的时候一直没太想好怎么处理，主要的问题是卡在了，建树最大实际上应该是 $t_i$$t_i$ 而不是 $n\times w_i$$n \times w_i$，所以直接建树的话复杂度是正确的，总之就是最后全挂了。。

Code

xxxxxxxxxx
133
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define EPS (1e-9)
24
/*
25
3
26
5
27
1 4 2
28
3 6 3
29
4 5 2
30
4 7 2
31
5 8 1
32
6
33
1 7 25
34
4 8 10
35
7 10 5
36
8 11 5
37
10 13 10
38
11 13 5
39
8
40
15 18 10
41
20 24 16
42
8 15 33
43
11 14 14
44
1 6 16
45
16 19 12
46
3 5 12
47
22 25 10
48
*/
49

50
template < typename T = int >
51
inline T read(void);
52

53
int N;
54

55
struct Task{
56
    ld s, t;
57
    ld w;
58
    friend const bool operator < (const Task &a, const Task &b){
59
        return a.t > b.t;
60
    }
61
}task[21000];
62

63
// class SegTree{
64
// private:
65
//     int tr[21000000 << 2], lz[]
66
// public:
67
//     void Pushup(int p){
68

69
//     }
70
// }
71

72
bool Check(int V){
73
    int curpos(1);
74
    priority_queue < Task > tsk;
75
    ld curT(1.0);
76
    while(true){
77
        if(tsk.empty()){
78
            if(curpos > N)return true;
79
            curT = max(curT, (ld)task[curpos].s);
80
            while(curpos <= N && curT >= (ld)task[curpos].s)tsk.push(task[curpos++]);
81
        }
82
        
83
        auto tp = tsk.top(); tsk.pop();
84
        curT = max(curT, (ld)tp.s);
85
        auto nxt = tsk.empty() ? Task{INT_MAX, INT_MAX, INT_MAX} : tsk.top();
86
        if(curT + (ld)tp.w / (ld)V <= nxt.s){
87
            curT += (ld)tp.w / (ld)V;
88
            if(curT - EPS > (ld)tp.t)return false;
89
        }else{
90
            tsk.push(Task{nxt.s, tp.t, tp.w - (nxt.s - curT) * V});
91
            curT = nxt.s;
92
        }
93
        
94
        // printf("V = %d, curT = %.5Lf,  [%d ~ %d]\n", V, curT, tp.s, tp.t);
95
        
96
        while(curpos <= N && curT >= (ld)task[curpos].s)tsk.push(task[curpos++]);
97
    }
98
}
99

100
int main(){
101
    freopen("cpu.in", "r", stdin);
102
    freopen("cpu.out", "w", stdout);
103
    int T = read();
104
    while(T--){
105
        N = read();
106
        for(int i = 1; i <= N; ++i)task[i].s = read(), task[i].t = read(), task[i].w = read();
107
        sort(task + 1, task + N + 1, [](const Task &a, const Task &b)->bool{return a.s < b.s;});
108
        int l = 0, r = 21000000, ans(-1);
109
        while(l <= r){
110
            int mid = (l + r) >> 1;
111
            if(Check(mid))ans = mid, r = mid - 1;
112
            else l = mid + 1;
113
        }printf("%d\n", ans);
114
    }
115
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
116
    return 0;
117
}
118

119
template < typename T >
120
inline T read(void){
121
    T ret(0);
122
    int flag(1);
123
    char c = getchar();
124
    while(c != '-' && !isdigit(c))c = getchar();
125
    if(c == '-')flag = -1, c = getchar();
126
    while(isdigit(c)){
127
        ret *= 10;
128
        ret += int(c - '0');
129
        c = getchar();
130
    }
131
    ret *= flag;
132
    return ret;
133
}

T3

存在初始全为白色的序列，每次从 $[1,n]$$[1, n]$ 随机一个 $a$$a$ 再随机一个 $b$$b$，以 $min(a,b)$$\min(a, b)$ 作为 $l$$l$，以 $max(a,b)$$\max(a, b)$ 作为 $r$$r$，将区间染黑，求 $k$$k$ 次随机后的期望黑色点个数。

手推了一下次数为 $1$$1$ 的部分分，对了。搓了个假的暴力，过了一点。

Code

xxxxxxxxxx
92
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (998244353ll)
24

25
template < typename T = int >
26
inline T read(void);
27

28
ll N, K;
29

30
ll qpow(ll a, ll b){
31
    ll ret(1), mul(a);
32
    while(b){
33
        if(b & 1)ret = ret * mul % MOD;
34
        b >>= 1;
35
        mul = mul * mul % MOD;
36
    }return ret;
37
}
38

39
ll dp[20][20][20];
40
ll ans(0);
41

42
int main(){
43
    freopen("paint.in", "r", stdin);
44
    freopen("paint.out", "w", stdout);
45
    // printf("%lld\n", 17 * qpow(9, MOD - 2) % MOD);
46
    N = read(), K = read();
47
    if(K == 1){
48
        // ll v = (N + 2) >> 1;
49
        // printf("%lld\n", ((v * ((2 * N + 2) % MOD) % MOD - v * (v + 1) % MOD + (N - v) * ((2 * N + 2) % MOD) % MOD - (N + v + 1) % MOD * (N - v) % MOD) % MOD + MOD) % MOD * qpow(N, MOD - 2) % MOD * qpow(N, MOD - 2) % MOD);
50
        printf("%lld\n", (((N + 1) * (N + 1) % MOD * N % MOD - N * (N + 1) % MOD * ((2 * N + 1) % MOD) % MOD * qpow(3, MOD - 2) % MOD - N) % MOD + MOD) % MOD * qpow(N, MOD - 2) % MOD * qpow(N, MOD - 2) % MOD);
51
        exit(0);
52
    }
53
    ll base = qpow(N, MOD - 2) * qpow(N, MOD - 2) % MOD;
54
    for(int i = 1; i <= N; ++i)
55
        for(int j = 1; j <= N; ++j)
56
            (dp[1][min(i, j)][max(i, j)] += base) %= MOD;
57
    for(int i = 2; i <= K; ++i){
58
        for(int j = 1; j <= N; ++j){
59
            for(int k = 1; k <= N; ++k){
60
                int l = min(j, k), r = max(j, k);
61
                for(int L = 1; L <= N; ++L){
62
                    for(int R = L; R <= N; ++R){
63
                        int rl = min(l, L), rr = max(r, R);
64
                        (dp[i][rl][rr] += dp[i - 1][L][R] * base % MOD) %= MOD;
65
                    }
66
                }
67
            }
68
        }
69
    }
70
    for(int i = 1; i <= N; ++i)
71
        for(int j = i; j <= N; ++j)
72
            (ans += dp[K][i][j] * (j - i + 1) % MOD) %= MOD;
73
    printf("%lld\n", ans);
74
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
75
    return 0;
76
}
77

78
template < typename T >
79
inline T read(void){
80
    T ret(0);
81
    int flag(1);
82
    char c = getchar();
83
    while(c != '-' && !isdigit(c))c = getchar();
84
    if(c == '-')flag = -1, c = getchar();
85
    while(isdigit(c)){
86
        ret *= 10;
87
        ret += int(c - '0');
88
        c = getchar();
89
    }
90
    ret *= flag;
91
    return ret;
92
}

T4

给定序列 $A_n$$A_n$，$q$$q$ 次询问每次给定 $p,l,r$$p, l, r$ 表示其在 $p$$p$ 想要值域在 $[l,r]$$[l, r]$ 中切存在于 $A_n$$A_n$ 中的每一种数各一个，定义贡献为物品的位置与 $p$$p$ 的距离，最小化贡献，对于每次询问输出最小值。

Code

xxxxxxxxxx
97
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
/*
24
5 4
25
1 5 3 3 1
26
3 3 4
27
4 4 5
28
2 1 4
29
5 3 5
30
*/
31

32
template < typename T = int >
33
inline T read(void);
34

35
int N, Q;
36
int A[210000];
37
basic_string < int > pos[1100];
38

39
// class SegTree{
40
// private:
41
//     int tr[210000 << 2];
42
//     #define LS (p << 1)
43
//     #define RS (LS | 1)
44
//     #define MID ((gl + gr) >> 1)
45
// public:
46
//     void Pushup()
47
// }
48

49
int main(){
50
    freopen("magic.in", "r", stdin);
51
    freopen("magic.out", "w", stdout);
52
    N = read(), Q = read();
53
    for(int i = 1; i <= N; ++i)pos[A[i] = read()] += i;
54
    if(N > 5000){
55
        while(Q--){
56
            ll ans(0);
57
            int p = read(), l = read(), r = read();
58
            r = min(r, N);
59
            if(p < l)ans = (ll)(l - p + r - p) * (r - p - (l - p) + 1) / 2;
60
            else if(p > r)ans = (ll)(p - l + p - r) * (p - l - (p - r) + 1) / 2;
61
            else ans = (ll)(p - l + 1) * (p - l) / 2 + (ll)(r - p + 1) * (r - p) / 2;
62
            printf("%lld\n", ans);
63
        }
64
    }
65
    while(Q--){
66
        ll ans(0);
67
        int p = read(), l = read(), r = read();
68
        for(int i = l; i <= r; ++i){
69
            if(pos[i].empty())continue;
70
            int mn(INT_MAX);
71
            auto it = lower_bound(pos[i].begin(), pos[i].end(), p);
72
            if(it != pos[i].end())mn = min(mn, abs(p - *it));
73
            if(it != pos[i].begin())mn = min(mn, abs(p - *prev(it)));
74
            if(it != pos[i].end() && next(it) != pos[i].end())mn = min(mn, abs(p - *next(it)));
75
            ans += mn;
76
        }printf("%lld\n", ans);
77
    }
78

79
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
80
    return 0;
81
}
82

83
template < typename T >
84
inline T read(void){
85
    T ret(0);
86
    int flag(1);
87
    char c = getchar();
88
    while(c != '-' && !isdigit(c))c = getchar();
89
    if(c == '-')flag = -1, c = getchar();
90
    while(isdigit(c)){
91
        ret *= 10;
92
        ret += int(c - '0');
93
        c = getchar();
94
    }
95
    ret *= flag;
96
    return ret;
97
}

正解

T1

考虑 $modk$$\bmod{k}$ 意义下，可以考虑 $dp(i,j)$$dp(i, j)$ 表示前 $i$$i$ 位模 $k$$k$ 意义下值为 $j$$j$ 的数然后进行数位 DP，这样是简单且平凡的。

还有更平凡的做法即进行 bfs，记录前驱以及具体数位值，跑一遍即可。

Code

xxxxxxxxxx
85
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template < typename T = int >
26
inline T read(void);
27

28
int K, T;
29
bitset < 10 > ban;
30
basic_string < int > vals;
31
bitset < 1100000 > vis;
32

33
struct Node{
34
    int p; int val; Node* pre;
35
};
36
void Print(Node* p){
37
    basic_string < int > ans;
38
    for(auto cur = p; ~cur->val; cur = cur->pre)
39
        ans += cur->val;
40
    reverse(ans.begin(), ans.end());
41
    for(auto v : ans)printf("%d", v);
42
    printf("\n");
43
    exit(0);
44
}
45
void bfs(void){
46
    queue < Node* > cur;
47
    cur.push(new Node{0, -1, npt});
48
    while(!cur.empty()){
49
        auto p = cur.front(); cur.pop();
50
        for(auto i : vals){
51
            if(p->p == 0 && i == 0)continue;
52
            int np = (p->p * 10 + i) % K;
53
            auto nod = new Node{np, i, p};
54
            if(!np)return Print(nod);
55
            if(vis[np])continue;
56
            vis[np] = true;
57
            cur.push(nod);
58
        }
59
    }
60
}
61

62
int main(){
63
    K = read(), T = read();
64
    for(int i = 1; i <= T; ++i)vals += read();
65
    bfs();
66
    printf("-1\n");
67
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68
    return 0;
69
}
70

71
template < typename T >
72
inline T read(void){
73
    T ret(0);
74
    int flag(1);
75
    char c = getchar();
76
    while(c != '-' && !isdigit(c))c = getchar();
77
    if(c == '-')flag = -1, c = getchar();
78
    while(isdigit(c)){
79
        ret *= 10;
80
        ret += int(c - '0');
81
        c = getchar();
82
    }
83
    ret *= flag;
84
    return ret;
85
}

T2

问题关键在于转换，即不去枚举事件，而去枚举时间，这样贪心更显然且极好维护。

Code

xxxxxxxxxx
87
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N;
27

28
struct Task{
29
    int s, t;
30
    int w;
31
    friend const bool operator < (const Task &a, const Task &b){
32
        return a.t > b.t;
33
    }
34
}task[21000];
35

36
bool Check(int V){
37
    int curpos(1);
38
    priority_queue < Task > tsk;
39
    for(int i = 1; i <= 20000; ++i){
40
        while(curpos <= N && i >= task[curpos].s)tsk.push(task[curpos++]);
41
        int tot(V);
42
        while(!tsk.empty() && tot){
43
            if(i >= tsk.top().t)return false;
44
            // printf("i = %d, Making [%d, %d]\n", )
45
            if(tot >= tsk.top().w)tot -= tsk.top().w, tsk.pop();
46
            else{
47
                auto tp = tsk.top(); tsk.pop();
48
                tp.w -= tot; tot = 0; tsk.push(tp);
49
                break;
50
            }
51
        }
52
    }if(curpos <= N || !tsk.empty())return false;
53
    return true;
54
}
55

56
int main(){
57
    int T = read();
58
    while(T--){
59
        N = read();
60
        for(int i = 1; i <= N; ++i)task[i].s = read(), task[i].t = read(), task[i].w = read();
61
        sort(task + 1, task + N + 1, [](const Task &a, const Task &b)->bool{return a.s < b.s;});
62
        int l = 0, r = 21000000, ans(-1);
63
        while(l <= r){
64
            int mid = (l + r) >> 1;
65
            if(Check(mid))ans = mid, r = mid - 1;
66
            else l = mid + 1;
67
        }printf("%d\n", ans);
68
    }
69
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
70
    return 0;
71
}
72

73
template < typename T >
74
inline T read(void){
75
    T ret(0);
76
    int flag(1);
77
    char c = getchar();
78
    while(c != '-' && !isdigit(c))c = getchar();
79
    if(c == '-')flag = -1, c = getchar();
80
    while(isdigit(c)){
81
        ret *= 10;
82
        ret += int(c - '0');
83
        c = getchar();
84
    }
85
    ret *= flag;
86
    return ret;
87
}

T3

考虑将问题转化为求每个点被涂黑的期望并利用线性性求和，考虑正难则反，用 $1$$1$ 减去不被涂黑的概率即可，显然 $k$$k$ 次后为：

暴力求解期望 $80\mathtt{\text{pts}}$$80\texttt{pts}$，考虑后者应为最高 $2k+1$$2k + 1$ 项的多项式，于是使用拉格朗日插值即可在 $O(k\log k)$$O(k \log k)$ 或 $O(k^2)$$O(k^2)$ 的复杂度内计算，代码略了。

T4

离线询问差分一下算点的贡献就行，奇怪题。

UPD

update-2023_02_21 初稿