1002 Boss Rush

Problem Description

Finally, Little Q gets his weapon at level 105 in the RPG game, now he is trying to beat the boss as soon as possible. The boss has H units of health point (HP), Little Q needs to cause at least H units of damage to beat the boss.

Little Q has learnt n skills, labeled by 1,2,…,n. Each skill can not be used multiple times, because there is not enough time for Little Q to wait for the skill to cool down. Assume Little Q uses the i-th skill at the x-th frame, the actor controlled by him will take ti frames to perform, which means Little Q will not be allowed to use other skills until the (x+ti)-th frame. The length of the damage sequence of the i-th skill is leni, which means the skill will cause di,j (0≤j

The game starts at the 0-th frame. Your task is to help Little Q beat the boss as soon as possible, or determine Little Q can’t beat the boss using all the skills at most once.

Input

The first line contains a single integer T (1≤T≤100), the number of test cases. For each test case:

The first line contains two integers n and H (1≤n≤18, 1≤H≤1018), denoting the number of skills and the HP of the boss.

For each skill, the first line contains two integers ti and leni (1≤ti,leni≤100000), the second line contains leni integers di,0,di,1,…,di,leni−1 (1≤di,j≤109).

It is guaranteed that the sum of all leni is at most 3000000, and there are at most 5 cases such that n>10.

Output

For each test case, output a single line containing an integer, denoting the first frame to beat the boss. If it is impossible to beat the boss, please print ‘’-1’’ instead.

Sample Input

3
1 100
5 3
50 60 70
2 100
2 3
40 40 100
100 2
20 5
1 1000
1 1
999

Sample Output

1
2
-1

Source

2022“杭电杯”中国大学生算法设计超级联赛（3）

小Q在玩RPG游戏，他尝试尽快击败BOSS，BOSS有H单位的血量，小Q有N个技能，每个技能花费$t_i$帧时间，能造成$le{n}_i$秒伤害（类似于燃烧瓶）每秒伤害不同，且$le{n}_i>=t_i$,问最快击败BOSS在哪一帧，起始在第0帧

首先发现n<=18,$2^{18}$为262144，猜想为nlogn的做法，考虑是否能二分，注意因为本题时间比较紧张，所以R应该为所有技能释放的最长时间，而不是INF，否则很容易超时
然后我们考虑如何二分，因为技能对BOSS的伤害是一段区间，所以我们用记忆化搜索得到本次时间内按某一顺序击败BOSS的最短时间
然后因为伤害是连续的，我们可以考虑用前缀和得到该技能施展某一秒时的总伤害，可以优化时间
tags:二分 记忆化搜索

AC代码

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-07-27 15:27:20

 *************************************************************************/

  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

  

using namespace std;

  

#define xx first

#define yy second

#define rep(i, h, t) for (int i = h; i <= t; i++)

#define dep(i, t, h) for (int i = t; i >= h; i--)

#define endl char(10)

#define int long long

//记得%d应该写成%lld

  

typedef pair<int, int> PII;

typedef long long ll;

int n, H;

const int N = 2e5 + 10;

const int M = 20;

int d[M][N], t[M], len[M], f[300010], s[M][N];

int l, r, ans, mid;

int dfs(int x)

{

    if (f[x] != -1)

        return f[x];

    int res = 0;

    int cnt = 0;

    for (int i = 0; i < n; i++)

    {

        if (x >> i & 1)

            res += t[i + 1];

    }

    if (res > mid)

        return f[x] = 0;

  

    for (int i = 0; i < n; i++)

    {

        if (!(x >> i & 1))

            cnt = max(s[i + 1][min(len[i + 1], mid - res)] + dfs(x ^ (1 << i)), cnt);

    }

    return f[x] = cnt;

}

bool check()

{

    for (int i = 0; i < (1 << n); i++)

        f[i] = -1;

    return dfs(0) >= H;

}

signed main()

{

    ios::sync_with_stdio(false);

    int k;

    cin >> k;

    while (k--)

    {

        cin >> n >> H;

        ans = 0;

        rep(i, 1, n)

        {

            cin >> t[i] >> len[i];

            ans += max(t[i], len[i]);

            rep(j, 1, len[i])

            {

                cin >> d[i][j];

                s[i][j] = s[i][j - 1] + d[i][j];

            }

        }

        l = 0, r = ans;

  

        while (l < r)

        {

            mid = l + r >> 1;

            if (check())

                r = mid;

            else

                l = mid + 1;

        }

        if (r >= ans)

            cout << -1 << endl;

        else

            cout << r - 1 << endl;

    }

}
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

1011 Taxi

Problem Description

There are n towns in Byteland, labeled by 1,2,…,n. The i-th town’s location is (xi,yi). Little Q got a taxi VIP card, he can use the VIP card to cut down the taxi fare. Formally, assume Little Q is at (x′,y′), if he calls a taxi to drive him to the k-th town, the VIP card will reduce min(|x′−xk|+|y′−yk|,wk) dollars.

Little Q wants to make full use of his VIP card. He will give you q queries, in each query you will be given his location, and you need to choose a town such that the VIP card will reduce the most taxi fare.

Input

The first line contains a single integer T (1≤T≤100), the number of test cases. For each test case:

The first line contains two integers n and q (1≤n,q≤100000), denoting the number of towns and the number of queries.

Each of the following n lines contains three integers xi, yi and wi (1≤xi,yi,wi≤109), describing a town.

Each of the following q lines contains two integers x′ and y′ (1≤x′,y′≤109), describing a query.

It is guaranteed that the sum of all n is at most 500000, and the sum of all q is at most 500000.

Output

For each query, print a single line containing an integer, denoting the maximum possible reduced taxi fare.

Sample Input

1
3 4
1 5 7
5 1 6
2 3 9
1 5
2 2
4 3
10 10

Sample Output

6
4
5
9

Source

2022“杭电杯”中国大学生算法设计超级联赛（3）

这道题官方讲得更好，这里就直接贴题解了hh

如果没有 w 的限制，那么是经典问题。根据
|x| = max(x, −x)，有
max { |x ′ − xi | + |y ′ − yi | }
= max { max(x ′ − xi , −x ′ + xi) + max(y ′ − yi , −y ′ + yi) }
= max { x ′ − xi + y ′ − yi , −x ′ + xi + y ′ − yi , x′ − xi − y ′ + yi , −x ′ + xi − y ′ + yi) }
= max { (x ′ + y ′ ) + (−xi − yi),(x ′ − y ′ ) + (−xi + yi),(−x ′ + y ′ ) + (xi − yi),(−x ′ − y ′ ) + (xi + yi) }
分别记录 xi + yi、xi − yi、−xi + yi、−xi − yi 的最大值即可在 O(1) 时间内求出所有点到 (x ′ , y′ ) 的曼哈顿距离的最大值。
现在考虑加入 w 的限制。将所有城镇按照 w 从小到大排序，并记录排序后每个后缀的 xi + yi、xi − yi、−xi + yi、−xi − yi 的最大值，用于 O(1) 求给定点 (x ′ , y′ ) 到该后缀中所有点 的距离最大值。
选取按 w 排序后的第 k 个城镇，O(1) 求出给定点 (x ′ , y′ ) 到第 k…n 个城镇的距离最大值 d，有两种情况
• wk < d，那么第 k…n 个城镇对答案的贡献至少为 wk。用 wk 更新答案后，由于第 1…k 个 城镇的 w 值均不超过 wk，因此它们不可能接着更新答案，考虑范围缩小至 [k + 1, n]。
• wk ≥ d，那么第 k…n 个城镇对答案的贡献为 d。用 d 更新答案后，考虑范围缩小至 [1, k − 1]。 容易发现每次考虑的范围都是一个区间，如果每次取 k 为区间的中点，那么迭代 O(log n) 次即可得到最优解。 时间复杂度 O((n + q)log n)。

AC代码

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-07-27 16:59:51

 *************************************************************************/

  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

  

using namespace std;

  

#define xx first

#define yy second

#define rep(i, h, t) for (int i = h; i <= t; i++)

#define dep(i, t, h) for (int i = t; i >= h; i--)

#define endl char(10)

#define int long long

//记得%d应该写成%lld

typedef pair<int, int> PII;

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 1e18;

int n, m;

int a[N], b[N], c[N], d[N];

struct node

{

    int x, y, w;

    bool operator<(const node &t) const

    {

        return w < t.w;

    }

} tr[N];

signed main()

{

    ios::sync_with_stdio(false);

    int t;

    cin >> t;

    while (t--)

    {

        int n, m;

        cin >> n >> m;

        rep(i, 1, n)

        {

            cin >> tr[i].x >> tr[i].y >> tr[i].w;

        }

        sort(tr + 1, tr + 1 + n);

        a[n + 1] = b[n + 1] = c[n + 1] = d[n + 1] = -INF;

        dep(i, n, 1)

        {

            a[i] = max(a[i + 1], -tr[i].x - tr[i].y);

            b[i] = max(b[i + 1], -tr[i].x + tr[i].y);

            c[i] = max(c[i + 1], tr[i].x - tr[i].y);

            d[i] = max(d[i + 1], tr[i].x + tr[i].y);

        }

        while (m--)

        {

            int x, y;

            cin >> x >> y;

            int l = 1, r = n;

            int ans = -INF;

            while (l <= r)

            {

                int res = -INF;

                int mid = l + r >> 1;

                res = max(res, x + y + a[mid]);

                res = max(res, x - y + b[mid]);

                res = max(res, -x + y + c[mid]);

                res = max(res, -x - y + d[mid]);

                if (tr[mid].w < res)

                {

                    l = mid + 1;

                    ans = max(ans, tr[mid].w);

                }

                else

                {

                    r = mid - 1;

                    ans = max(ans, res);

                }

            }

            cout << ans << endl;

        }

    }

}
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

1012 Two Permutations

Problem Description

There are two permutations P1,P2,…,Pn, Q1,Q2,…,Qn and a sequence R. Initially, R is empty. While at least one of P and Q is non-empty, you need to choose a non-empty array (P or Q), pop its leftmost element, and attach it to the right end of R. Finally, you will get a sequence R of length 2n.

You will be given a sequence S of length 2n, please count the number of possible ways to merge P and Q into R such that R=S. Two ways are considered different if and only if you choose the element from different arrays in a step.

Input

The first line contains a single integer T (1≤T≤300), the number of test cases. For each test case:

The first line contains a single integer n (1≤n≤300000), denoting the length of each permutation.

The second line contains n distinct integers P1,P2,…,Pn (1≤Pi≤n).

The third line contains n distinct integers Q1,Q2,…,Qn (1≤Qi≤n).

The fourth line contains 2n integers S1,S2,…,S2n (1≤Si≤n).

It is guaranteed that the sum of all n is at most 2000000.

Output

For each test case, output a single line containing an integer, denoting the number of possible ways. Note that the answer may be extremely large, so please print it modulo 998244353 instead.

Sample Input

2
3
1 2 3
1 2 3
1 2 1 3 2 3
2
1 2
1 2
1 2 2 1

Sample Output

2
0

Source

2022“杭电杯”中国大学生算法设计超级联赛（3）

给你两个n长度的排列p,q，还有一个2* n的排列s，你可以将p或q头部的一个元素取出插到r的尾部，问有多少种情况能凑出s
设$f[x][y]$为p对应s的第x位，q对应s的第y位，但是看数据范围就可以发现我们无法构造这样的数组
所以我们考虑进行优化
我们定义$f[x][0/1]$，表示s中的第x位匹配在p还是q，然后进行记忆化搜索即可

tags:DP 记忆化搜索

AC代码

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-07-27 20:39:33

 *************************************************************************/

  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

  

using namespace std;

  

#define xx first

#define yy second

#define rep(i, h, t) for (int i = h; i <= t; i++)

#define dep(i, t, h) for (int i = t; i >= h; i--)

#define endl char(10)

#define int long long

//记得%d应该写成%lld

  

typedef pair<int, int> PII;

typedef long long ll;

const int N = 3e5 + 10;

int f[N * 2][2], p[N], q[N], s[N * 2];

const int mod = 998244353;

int n;

int dfs(int x, int y, int flag)

{

    if (x > n && y > n)

        return 1;

    if (f[x + y - 1][flag] != -1)

        return f[x + y - 1][flag];

    int res = 0;

    if (p[x] == s[x + y - 1] && x <= n)

    {

        res += dfs(x + 1, y, 0);

        res %= mod;

    }

    if (q[y] == s[x + y - 1] && y <= n)

    {

        res += dfs(x, y + 1, 1);

        res %= mod;

    }

    return f[x + y - 1][flag] = res;

}

signed main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

  

        cin >> n;

        for (int i = 1; i <= n; i++)

            cin >> p[i];

        for (int i = 1; i <= n; i++)

            cin >> q[i];

        for (int i = 1; i <= 2 * n; i++)

            cin >> s[i];

        for (int i = 1; i <= 2 * n; i++)

            f[i][0] = f[i][1] = -1;

        int ans = 0;

        if (p[1] == s[1])

        {

            ans += dfs(2, 1, 0);

            ans %= mod;

        }

        if (q[1] == s[1])

        {

            ans += dfs(1, 2, 1);

            ans %= mod;

        }

        cout << ans << endl;

    }

}
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