比赛大图来源:pixiv_id=70066287
出题人:MarisaMagic
题意简述
给定一个长度为 n n n 的 01 01 01 序列,求一个长度最小的连续区间 [ l , r ] [l, r] [ l , r ] 包含所有的 1 1 1 。
解题思路 (模拟)
去除开头和结尾连续的 0 0 0 得到的子区间即包含所有 1 1 1 的长度最小的连续区间。时间复杂度 O ( n ) \mathcal{O}(n) O ( n ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;#define fastio ios::sync_with_stdio(false), cin.tie(0) void marisa () { int n; cin >> n; vector<int > a (n + 1 ) ; for (int i = 1 ; i <= n; i ++ ) cin >> a[i]; int l = 1 ; while (l <= n && !a[l]) l ++ ; int r = n; while (r >= l && !a[r]) r -- ; cout << r - l + 1 << "\n" ; }int main () { fastio; int T = 1 ; while (T -- ) marisa (); return 0 ; }
C++
出题人:MarisaMagic
题意简述
给定数字 n n n 和 m m m ,第一次最多可以减去 m m m ,第二次最多可以减去 x 1 = ⌈ m 2 ⌉ x_1 = \left \lceil \frac{m}{2} \right \rceil x 1 = ⌈ 2 m ⌉ ,第三次最多可以减去 x 2 = ⌈ x 1 2 ⌉ x_2 = \left \lceil \frac{x_1}{2} \right \rceil x 2 = ⌈ 2 x 1 ⌉ ,依次类推。求最少需要多少次使得 n n n 减为 0 0 0 。
解题思路 (模拟)
可以发现 m m m 经过 log 2 m \log_2 m log 2 m 级别次数操作后会变为 1 1 1 ,且之后一直都是 1 1 1 。故可以先暴力模拟直至 m m m 变为 1 1 1 ,或者在 m m m 变为 1 1 1 之前 n n n 即可减为 0 0 0 。最后 n n n 若还有剩余,答案加上 n n n 即可。时间复杂度 O ( log m ) \mathcal{O}(\log m) O ( log m ) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;#define fastio ios::sync_with_stdio(false), cin.tie(0) void marisa () { int n, m; cin >> n >> m; int ans = 0 ; while (n > 0 && m != 1 ){ n -= m; ans ++ ; m = (m + 1 ) / 2 ; } cout << ans + (n <= 0 ? 0 : n) << "\n" ; }int main () { fastio; int T = 1 ; while (T -- ) marisa (); return 0 ; }
C++
出题人:MarisaMagic
题意简述
给定数字 a a a 和 b b b ,每次进行如下两种操作之一:
花费 x x x 代价,使得 a a a 减去 2 2 2 或者 b b b 减去 2 2 2 。(前提 a a a 至少为 2 2 2 或 b b b 至少为 2 2 2 );
花费 y y y 代价,使得 a a a 减去 1 1 1 并且 b b b 减去 1 1 1 。(前提 a a a 至少为 1 1 1 或 b b b 至少为 1 1 1 )。
求使得 a a a 或 b b b 减为 0 0 0 所需的最少次数。
解题思路 (数学)
当 x > 2 × y x > 2 \times y x > 2 × y 。显然一个一个减去所需的次数更少,此时对 a a a 和 b b b 中的较小值一个一个减去即可。故此时答案为 min ( a , b ) × y \min (a, b) \times y min ( a , b ) × y 。
当 x ≤ 2 × y x \le 2 \times y x ≤ 2 × y 。显然两个两个减去的效率更高,此时考虑先将 a a a 和 b b b 其中一个值优先两个两个减,最后可能还余 1 1 1 。故此时答案为 min ( ⌊ a 2 ⌋ × x + a m o d 2 × y , ⌊ b 2 ⌋ × x + b m o d 2 × y ) \min(\left \lfloor \frac{a}{2} \right \rfloor \times x + a \bmod 2 \times y, \left \lfloor \frac{b}{2} \right \rfloor \times x + b \bmod 2 \times y) min ( ⌊ 2 a ⌋ × x + a mod 2 × y , ⌊ 2 b ⌋ × x + b mod 2 × y ) 。
由于可能 x > y x > y x > y 且 a , b a, b a , b 分别所需的操作次数相同,所以并不是 a a a 和 b b b 哪个更小就对哪个进行操作,故最后需要取一下最小值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std;#define fastio ios::sync_with_stdio(false), cin.tie(0) using ll = long long ;void marisa () { ll a, b, x, y; cin >> a >> b >> x >> y; if (x > 2 * y){ cout << min (a, b) * y << "\n" ; return ; } cout << min (a / 2 * x + (a % 2 ) * y, b / 2 * x + (b % 2 ) * y) << "\n" ; }int main () { fastio; int T = 1 ; cin >> T; while (T -- ) marisa (); return 0 ; }
C++
出题人:MarisaMagic
题意简述
有一个长度为 n n n 的环形数组 a a a ,找到一个长度不超过 n n n 的非空子数组使得子数组总和最大。
解题思路 1 (DP,最大最小子数组和)
考虑不跨环的情况。直接 DP 求数组 a a a 的最大子数组和即可。
考虑跨环的情况。相当于用整个数组的和减去一个子数组的和,故此时可以先 DP 求数组 a a a 的最小子数组和,然后再用整个数组 a a a 的和减去这个最小子数组和。
最终答案为两种情况的较大值。特别的,如果数组 a a a 的元素均为负数,由于要找的子数组非空,不满足上述跨环的情况,故此时答案为 a a a 的最大子数组和。时间复杂度 O ( n ) \mathcal{O}(n) O ( n ) 。
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 #include <bits/stdc++.h> using namespace std;#define fastio ios::sync_with_stdio(false), cin.tie(0) using ll = long long ;void marisa () { int n; cin >> n; vector<int > a (n + 1 ) ; bool all_minus = true ; for (int i = 1 ; i <= n; i ++ ){ cin >> a[i]; if (a[i] >= 0 ) all_minus = false ; } ll sum = 0 ; ll mx = -1e18 ; for (int i = 1 ; i <= n; i ++ ){ sum = max (0ll , sum) + a[i]; mx = max (mx, sum); } sum = 0 ; ll mn = 1e18 ; for (int i = 1 ; i <= n; i ++ ){ sum = min (0ll , sum) + a[i]; mn = min (mn, sum); } sum = 0 ; for (int i = 1 ; i <= n; i ++ ) sum += a[i]; if (!all_minus) cout << max (mx, sum - mn) << "\n" ; else cout << mx << "\n" ; }int main () { fastio; int T = 1 ; while (T -- ) marisa (); return 0 ; }
C++
解题思路 2 (前缀和,单调队列)
复制一遍数组 a a a ,预处理前缀和 s s s 。对于每个位置 i i i ,最优的答案为 s i − max max ( 0 , i − n ) ≤ j < i s j s_i - \max_{\max(0, i - n) \le j < i} s_{j} s i − max m a x ( 0 , i − n ) ≤ j < i s j 。
可以用单调队列维护前面位置最小前缀和的下标,对于每个位置 i i i 更新答案。注意开始时需要放入初始状态 0 0 0 。时间复杂度 O ( n ) \mathcal{O}(n) O ( n ) 。
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 #include <bits/stdc++.h> using namespace std;#define fastio ios::sync_with_stdio(false), cin.tie(0) using ll = long long ;void marisa () { int n; cin >> n; vector<int > a (2 * n + 1 ) ; for (int i = 1 ; i <= n; i ++ ){ cin >> a[i]; a[n + i] = a[i]; } using pii = pair<int , ll>; ll mx = -1e18 , sum = 0 ; deque<pii> q; q.emplace_back (0 , 0 ); for (int i = 1 ; i <= 2 * n; i ++ ){ sum += a[i]; while (q.size () && i - q.front ().first > n){ q.pop_front (); } mx = max (mx, sum - q.front ().second); while (q.size () && q.back ().second > sum){ q.pop_back (); } q.emplace_back (i, sum); } cout << mx << "\n" ; }int main () { fastio; int T = 1 ; while (T -- ) marisa (); return 0 ; }
C++
出题人:MarisaMagic
题意简述
给定一个数组 a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a 1 , a 2 , … , a n ,求有多少个不同的区间 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1 ≤ l ≤ r ≤ n 满足 ∑ i = l r a i ≥ x \sum_{i=l}^{r} a_i \ge x ∑ i = l r a i ≥ x 。
解题思路 (离散化,树状数组)
一个区间 [ l , r ] [l, r] [ l , r ] 满足 ∑ i = l r a i ≥ x \sum_{i=l}^{r} a_i \ge x ∑ i = l r a i ≥ x 即前缀和 s r − s l − 1 ≥ x s_r - s_{l - 1} \ge x s r − s l − 1 ≥ x ,相当于 s l − 1 ≤ s r − x s_{l-1} \le s_r - x s l − 1 ≤ s r − x 。
对于每个位置 i i i ,需要求出在 0 ≤ j < i 0 \le j < i 0 ≤ j < i 中有多少个 j j j 满足 s j ≤ s i − x s_{j} \le s_i - x s j ≤ s i − x ,答案就是每个位置 i i i 前面满足条件 j j j 的个数。
我们可以在顺序遍历数组 a a a 的过程中,累计前缀和,并用 树状数组 维护 s i s_i s i 出现的次数。因此,对于每个位置 i i i ,对答案的贡献为之前树状数组中小于等于 s i − x s_i - x s i − x 的数出现的总次数。
由于 − 1 0 9 ≤ x ≤ 1 0 9 -10^9 \le x \le 10^9 − 1 0 9 ≤ x ≤ 1 0 9 ,− 1 0 9 ≤ a i ≤ 1 0 9 -10^9 \le a_i \le 10^9 − 1 0 9 ≤ a i ≤ 1 0 9 ,无法直接存储到树状数组中。但不同的前缀和个数不会超过 n n n ,再加上不同 s i − x s_i - x s i − x 的个数,不同的数总共不会超过 2 n 2n 2 n 。故可以将 s i s_i s i 和 s i − x s_i - x s i − x 进行离散化,再用树状数组维护即可。时间复杂度 O ( n log n ) \mathcal{O}(n\log n) O ( n log n ) 。
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 #include <bits/stdc++.h> using namespace std;#define fastio ios::sync_with_stdio(false), cin.tie(0) using ll = long long ;const int N = 4e5 + 10 ;int tr[N];void add (int x, int c) { for (int i = x; i < N; i += i & -i){ tr[i] += c; } }int query (int x) { int res = 0 ; for (int i = x; i; i -= i & -i){ res += tr[i]; } return res; }void marisa () { int n, x; cin >> n >> x; vector<ll> s (n + 1 ) ; for (int i = 1 ; i <= n; i ++ ){ cin >> s[i]; s[i] += s[i - 1 ]; } vector<ll> v; for (int i = 0 ; i <= n; i ++ ){ v.emplace_back (s[i]); v.emplace_back (s[i] - x); } sort (begin (v), end (v)); v.erase (unique (begin (v), end (v)), end (v)); auto get_id = [&](ll x){ return lower_bound (begin (v), end (v), x) - begin (v) + 1 ; }; ll ans = 0 ; add (get_id (0 ), 1 ); for (int i = 1 ; i <= n; i ++ ){ ans += query (get_id (s[i] - x)); add (get_id (s[i]), 1 ); } cout << ans << '\n' ; }int main () { fastio; int T = 1 ; while (T -- ) marisa (); return 0 ; }
C++
出题人:AveMujica
题意简述
给定两个升序序列 A , B A, B A , B ,长度分别为 n , m n, m n , m ,相邻元素固定且严格为 1 1 1 或 2 2 2 。从序列 A A A 和 B B B 中分别取一个元素相加并去重排序得到一个集合 C C C 。每次询问集合 C C C 中第 q q q 个元素的值。
解题思路 (分类讨论,数学,思维)
本题实质上就是要求我们从公差为 1 或者 2 的集合 A A A 和集合 B B B 中任取一个数 a i a_i a i (1 ≤ i ≤ n 1 \leq i \leq n 1 ≤ i ≤ n ) 和 b j b_j b j (1 ≤ j ≤ m 1 \leq j \leq m 1 ≤ j ≤ m ),构造集合 C C C ,满足集合 C C C 的元素 c k = a i + b j c_k = a_i + b_j c k = a i + b j ,且 c k ≠ c k + 1 c_k \neq c_{k + 1} c k = c k + 1 (1 ≤ k < len ( C ) 1 \leq k < \text{len}(C) 1 ≤ k < len ( C ) ),c k < c k + 1 c_k < c_{k + 1} c k < c k + 1 (1 ≤ k < len ( C ) 1 \leq k < \text{len}(C) 1 ≤ k < len ( C ) )。
如果用暴力算法来求解 c k c_k c k ,并用集合 s e t set se t 去重的话,解法的时间复杂度为 O ( n m log n ) O(nm\log n) O ( nm log n ) ,在 1 ≤ n , m ≤ 1 0 5 1 \leq n, m \leq 10^5 1 ≤ n , m ≤ 1 0 5 的数据限制下显然无法通过本题。考虑通过某些性质来优化求解方案。集合 A A A 和 B B B 的公差都被限制为 1 或者 2,我们从公差切入,不难发现 A A A 表和 B B B 表只可能有 4 种情况:
(1) $ A$ 表和 B B B 表的公差都为 1,A A A 表和 B B B 表长度都大于等于2;
(2) A A A 表和 B B B 表的公差都为 2,A A A 表和 B B B 表长度都大于等于2;
(3) A A A 表和 B B B 表的公差一个为 1,一个为 2,A A A 表和 B B B 表长度都大于等于2;
(4) A A A 表和 B B B 表其中一个长度为1,或长度都为 1。
情况 (4) 很好求解,实质上就是其中一个集合,其每个元素都加上了长度为1的集合中的元素值 x x x 。
对于情况 (1) 和情况 (2),我们可以统一理解为 A A A 表和 B B B 表的公差相同。我们可以证明,公差相同的连续数列 A A A 和 B B B ,任取两数相加后得到的新数列 C C C ,经升序排序和去重后,公差不变,且首项为 min ( a ) + min ( b ) \min(a) + \min(b) min ( a ) + min ( b ) ,末项为 max ( a ) + max ( b ) \max(a) + \max(b) max ( a ) + max ( b ) 。这里给出公差为 2 的证明,公差为 1 的同理可证。
设数列 a a a 为 a 1 , a 1 + 2 , a 1 + 4 , … , a 1 + 2 ( n − 1 ) a_1, a_1 + 2, a_1 + 4, \dots, a_1 + 2(n-1) a 1 , a 1 + 2 , a 1 + 4 , … , a 1 + 2 ( n − 1 ) ,数列 b b b 为 b 1 , b 1 + 2 , b 1 + 4 , … , b 1 + 2 ( m − 1 ) b_1, b_1 + 2, b_1 + 4, \dots, b_1 + 2(m-1) b 1 , b 1 + 2 , b 1 + 4 , … , b 1 + 2 ( m − 1 ) 。两数列的最小项分别为 a 1 a_1 a 1 和 b 1 b_1 b 1 ,最大项分别为 a 1 + 2 ( n − 1 ) a_1 + 2(n - 1) a 1 + 2 ( n − 1 ) 和 b 1 + 2 ( m − 1 ) b_1 + 2(m - 1) b 1 + 2 ( m − 1 ) 。
两数列中任取两数相加,和为:
s = ( a 1 + 2 i ) + ( b 1 + 2 j ) = ( a 1 + b 1 ) + 2 ( i + j ) , s = (a_1 + 2i) + (b_1 + 2j) = (a_1 + b_1) + 2(i + j),
s = ( a 1 + 2 i ) + ( b 1 + 2 j ) = ( a 1 + b 1 ) + 2 ( i + j ) ,
其中 i ∈ [ 0 , n − 1 ] i \in [0, n-1] i ∈ [ 0 , n − 1 ] ,j ∈ [ 0 , m − 1 ] j \in [0, m-1] j ∈ [ 0 , m − 1 ] 。
所有可能的和为 S = a 1 + b 1 + 2 k S = a_1 + b_1 + 2k S = a 1 + b 1 + 2 k ,其中 k = i + j k = i + j k = i + j ,k k k 的取值范围为 0 ≤ k ≤ ( n − 1 ) + ( m − 1 ) = n + m − 2 0 \leq k \leq (n - 1) + (m - 1) = n + m - 2 0 ≤ k ≤ ( n − 1 ) + ( m − 1 ) = n + m − 2 。
因此,S S S 的值为公差 2 的等差数列,覆盖从 a 1 + b 1 a_1 + b_1 a 1 + b 1 到 a 1 + b 1 + 2 ( n + m − 2 ) a_1 + b_1 + 2(n + m - 2) a 1 + b 1 + 2 ( n + m − 2 ) ,首项为 a 1 + b 1 a_1 + b_1 a 1 + b 1 ,末项为 a 1 + b 1 + 2 ( n + m − 2 ) = max ( a ) + max ( b ) a_1 + b_1 + 2(n + m - 2) = \max(a) + \max(b) a 1 + b 1 + 2 ( n + m − 2 ) = max ( a ) + max ( b ) ,公差为 2,命题得证。
由此我们解决了以公差相同的 A A A 表和 B B B 表构造 C C C 表的难题,只需要求出 A A A 表和 B B B 表的最小值 min ( a ) + min ( b ) \min(a) + \min(b) min ( a ) + min ( b ) 和最大值 max ( a ) + max ( b ) \max(a) + \max(b) max ( a ) + max ( b ) ,从最小值以 2 或 1 为步长即可构造出集合内的任一元素 c k c_k c k 。
现在考虑情况 (3),情况 (3) 中 A A A 表和 B B B 表的公差不同,且一个为 1,一个为 2,我们可以证明以下命题:
设数列 a a a 是公差为 1 且长度 n ≥ 2 n \geq 2 n ≥ 2 的连续数列,数列 b b b 是公差为 2 的连续数列(长度 m ≥ 1 m \geq 1 m ≥ 1 )。从 a a a 和 b b b 中各任取一个数相加,组成的新数列 c c c 经升序和去重后,公差为 1,且首项为 min ( a ) + min ( b ) \min(a) + \min(b) min ( a ) + min ( b ) ,末项为 max ( a ) + max ( b ) \max(a) + \max(b) max ( a ) + max ( b ) 。证明如下:
设数列 a a a 的首项为 a 1 a_1 a 1 ,公差为 1,长度为 n n n ,则:
a = { a 1 , a 1 + 1 , a 1 + 2 , … , a 1 + ( n − 1 ) } . a = \{ a_1, a_1 + 1, a_1 + 2, \dots, a_1 + (n - 1) \}.
a = { a 1 , a 1 + 1 , a 1 + 2 , … , a 1 + ( n − 1 )} .
数列 b b b 的首项为 b 1 b_1 b 1 ,公差为 2,长度为 m m m ,则:
b = { b 1 , b 1 + 2 , b 1 + 4 , … , b 1 + 2 ( m − 1 ) } . b = \{ b_1, b_1 + 2, b_1 + 4, \dots, b_1 + 2(m - 1) \}.
b = { b 1 , b 1 + 2 , b 1 + 4 , … , b 1 + 2 ( m − 1 )} .
两数列的最小项分别为 a 1 a_1 a 1 和 b 1 b_1 b 1 ,最大项分别为 a 1 + ( n − 1 ) a_1 + (n - 1) a 1 + ( n − 1 ) 和 b 1 + 2 ( m − 1 ) b_1 + 2(m - 1) b 1 + 2 ( m − 1 ) 。
任取 a i ∈ a a_i \in a a i ∈ a 和 b j ∈ b b_j \in b b j ∈ b ,其和为:
s = a i + b j = ( a 1 + ( i − 1 ) ) + ( b 1 + 2 ( j − 1 ) ) = a 1 + b 1 + ( i − 1 ) + 2 ( j − 1 ) , s = a_i + b_j = (a_1 + (i - 1)) + (b_1 + 2(j - 1)) = a_1 + b_1 + (i - 1) + 2(j - 1),
s = a i + b j = ( a 1 + ( i − 1 )) + ( b 1 + 2 ( j − 1 )) = a 1 + b 1 + ( i − 1 ) + 2 ( j − 1 ) ,
即 s = a 1 + b 1 + k s = a_1 + b_1 + k s = a 1 + b 1 + k ,其中 k = ( i − 1 ) + 2 ( j − 1 ) k = (i - 1) + 2(j - 1) k = ( i − 1 ) + 2 ( j − 1 ) ,则和为:
s = a 1 + b 1 + k . s = a_1 + b_1 + k.
s = a 1 + b 1 + k .
对任意 k ∈ [ 0 , n + 2 m − 3 ] k \in [0, n + 2m - 3] k ∈ [ 0 , n + 2 m − 3 ] ,取:
j = ⌊ k 2 ⌋ + 1 , i = k − 2 ( j − 1 ) + 1. j = \left\lfloor \frac{k}{2} \right\rfloor + 1, \quad i = k - 2(j - 1) + 1.
j = ⌊ 2 k ⌋ + 1 , i = k − 2 ( j − 1 ) + 1.
当 k k k 为偶数时,
j = k 2 + 1 , 2 ( j − 1 ) = k , 此时 i = 1. j = \frac{k}{2} + 1, \quad 2(j - 1) = k, \quad \text{此时} \, i = 1.
j = 2 k + 1 , 2 ( j − 1 ) = k , 此时 i = 1.
当 k k k 为奇数时,
j = k − 1 2 + 1 , 2 ( j − 1 ) = k − 1 , 此时 i = 2. j = \frac{k - 1}{2} + 1, \quad 2(j - 1) = k - 1, \quad \text{此时} \, i = 2.
j = 2 k − 1 + 1 , 2 ( j − 1 ) = k − 1 , 此时 i = 2.
由于 n ≥ 2 n \geq 2 n ≥ 2 ,无论 k k k 奇偶,i ≤ 2 ≤ n i \leq 2 \leq n i ≤ 2 ≤ n ,且 j ≤ ⌊ n + 2 m − 3 2 ⌋ + 1 ≤ m j \leq \left\lfloor \frac{n + 2m - 3}{2} \right\rfloor + 1 \leq m j ≤ ⌊ 2 n + 2 m − 3 ⌋ + 1 ≤ m 。
因此,所有 k k k 均被覆盖,和数列 c c c 为公差 1 的等差数列,覆盖从 a 1 + b 1 a_1 + b_1 a 1 + b 1 到 a 1 + b 1 + n + 2 m − 3 a_1 + b_1 + n + 2m - 3 a 1 + b 1 + n + 2 m − 3 。
由此,我们解决了公差为 1 和公差为 2 的数列的组合难题,对于长度大于等于 2 的公差为 1 的数列 A A A / B B B 和公差为 2 的数列 A A A / B B B ,我们只需要知道 min ( a ) + min ( b ) \min(a) + \min(b) min ( a ) + min ( b ) 和 max ( a ) + max ( b ) \max(a) + \max(b) max ( a ) + max ( b ) ,即可构造出集合 C C C 中的任一元素 c k c_k c k 。
综上,所有情况讨论完毕,对于任一询问,我们都能以 O ( 1 ) O(1) O ( 1 ) 的时间复杂度输出答案,总的时间复杂度为 O ( T ) O(T) O ( T ) 。
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 #include <bits/stdc++.h> using namespace std;using i64 = long long ;void solve () { int n, m; cin >> n >> m; vector<i64> A (n + 1 ) , B (m + 1 ) ; for (int i = 1 ; i <= n; i++) cin >> A[i]; for (int i = 1 ; i <= m; i++) cin >> B[i]; int diffA = 0 , diffB = 0 ; if (n > 1 ) diffA = A[2 ] - A[1 ]; if (m > 1 ) diffB = B[2 ] - B[1 ]; bool flag = (n > 1 && m > 1 ) ? (diffA == diffB) : false ; int t; cin >> t; while (t--) { i64 q; cin >> q; i64 len, diff; i64 c_min = A[1 ] + B[1 ]; i64 c_max = A[n] + B[m]; if (flag) { if (diffA == 1 ) { len = c_max - c_min + 1 ; diff = 1 ; } else { len = (c_max - c_min + 2 ) / 2 ; diff = 2 ; } } else { if (n == 1 && m == 1 ) { len = 1 ; diff = 0 ; } else if (m == 1 ) { len = n; diff = diffA; } else if (n == 1 ) { len = m; diff = diffB; } else { len = c_max - c_min + 1 ; diff = 1 ; } } if (q > len) { cout << -1 << "\n" ; } else { cout << c_min + (q - 1 ) * diff << "\n" ; } } }int main () { ios::sync_with_stdio (false ); cin.tie (nullptr ); solve (); return 0 ; }
C++