Theme NexT works best with JavaScript enabled

2019 牛客暑期多校训练营第一场题解

本文包括 2019 牛客暑期多校训练营第一场的题面与题解。

A - Equivalent Prefixes

题目描述

Two arrays $ u $ and $ v $ each with m distinct elements are called equivalent if and only if $ \mathrm{RMQ}(u, l, r) = \mathrm{RMQ}(v, l, r) $ for all $ 1 \leq l \leq r \leq m $

where $ \mathrm{RMQ}(w, l, r) $ denotes the index of the minimum element among $ w_l, w_{l + 1}, \dots, w_{r} $ .

Since the array contains distinct elements, the definition of minimum is unambiguous.

Bobo has two arrays a and b each with n distinct elements. Find the maximum number $ p \leq n $ where $ \{a_1, a_2, \dots, a_p\} $ and $ \{b_1, b_2, \dots, b_p\} $ are equivalent.

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.

The second line contains n integers $ a_1, a_2, \dots, a_n $ .

The third line contains n integers $ b_1, b_2, \dots, b_n $ .

  • $ 1 \leq n \leq 10^5 $
  • $ 1 \leq a_i, b_i \leq n $
  • $ \{a_1, a_2, \dots, a_n\} $ are distinct.
  • $ \{b_1, b_2, \dots, b_n\} $ are distinct.
  • The sum of n does not exceed $ 5 \times 10^5 $ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

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

输出

1
2
3
1
3
4

题解

题意

定义两个序列“等价”的条件为:任取两序列的子区间 $ [l,r] $ 都满足区间最小值的下标相同。

现给定两长度为N的子序列,询问这两序列的“等价”最长前缀子序列的长度。

解法

用单调栈预处理出每个元素作为最小值时的区间最左端点,分别记录为 $ a_{i} $ 和 $ b_{i} $ ,找出最大的 $ k $ 使得 $ a_{i} $ 和 $ b_{i} $ 前 $ 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
#include <bits/stdc++.h>
using namespace std;
#define N 100001
int a[N], b[N], s[N];
int main() {
int n;
while (~scanf("%d", &n)) {
int topa = 0, topb = 0;
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
while (topa > 0 && x <= s[topa]) topa--;
s[++topa] = x;
a[i] = topa;
}
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
while (topb > 0 && x <= s[topb]) topb--;
s[++topb] = x;
b[i] = topb;
}
int add = 1;
while (add <= n && a[add] == b[add]) add++;
printf("%d\n", add - 1);
}
return 0;
}

B - Integration

题目描述

Bobo knows that $ \displaystyle\int_{0}^{\infty} \dfrac{1}{1 + x^2}\ \mathrm{d}x = \frac{\pi}{2} $ .

Given n distinct positive integers $ a_1, a_2, \dots, a_n $ , find the value of $ \displaystyle\frac{1}{\pi} \int_{0}^{\infty} \frac{1}{\prod_{i = 1}^n(a_i^2 + x^2)}\ \mathrm{d}x $ .

It can be proved that the value is a rational number $ \dfrac{p}{q} $ .
Print the result as $ (p \cdot q^{-1}) \bmod (10^9+7) $ .

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer $ n $ .
The second line contains n integers $ a_1, a_2, \dots, a_n $ .

  • $ 1 \leq n \leq 10^3 $
  • $ 1 \leq a_i \leq 10^9 $
  • $ \{a_1, a_2, \dots, a_n\} $ are distinct.
  • The sum of $ n^2 $ does not exceed $ 10^7 $ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

1
2
3
4
5
6
1
1
1
2
2
1 2

输出

1
2
3
500000004
250000002
83333334

题解

题意

给定公式,求解该式

解法

  • 令 $ \displaystyle c_{i} = \dfrac{1}{\prod_{j \neq j}(a_{j}^2-a_{i}^2)} $
  • 则 $ \displaystyle\dfrac{1}{\prod_{j \neq j}(a_{i}^2 + x) } = \sum \dfrac{c_{i}}{a_{i}^2+x} $
  • 所以 $ \displaystyle\int_{0}^{\infty} \dfrac{c_{i}}{a_{i}^2+x} dx = \dfrac{c_{i}}{2 \times a_{i}} \times \pi $
  • 所以 $ \displaystyle\frac{1}{\pi} \int_{0}^{\infty} \frac{1}{\prod_{i = 1}^n(a_i^2 + x^2)}\ \mathrm{d}x = \sum\dfrac{c_{i}}{2 \times a_{i}} $

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 1001
ll Qpow(ll x, ll n) {
ll t = 1;
while (n) {
if (n & 1) t = t * x % mod;
x = x * x % mod, n >>= 1;
}
return t;
}
ll a[N];
int main() {
int n;
while (~scanf("%d", &n)) {
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
ll ans = 0;
for (int i = 1; i <= n; i++) {
ll s = 1;
for (int j = 1; j <= n; j++)
if (i != j) s = s * (Qpow(a[j], 2) - Qpow(a[i], 2) + mod) % mod;
ans = (ans + Qpow(s, mod - 2) * Qpow(2 * a[i], mod - 2)) % mod;
}
printf("%lld\n", ans);
}
return 0;
}

C - Euclidean Distance

题目描述

Bobo has a point $ A $ in the $ n $ dimension real space $ \mathbb{R}^n $ , whose coodinate is $ (a_1 / m, a_2 / m, \dots, a_n / m) $ where $ a_i $ and $ m $ are both integers. He wants to find another point $ P = (p_1, p_2, \dots, p_n) $ meeting the following requirements.

  • $ p_1, p_2, \dots, p_n \in \mathbb{R} $ . That is, they are real numbers.
  • $ p_1, p_2, \dots, p_n \geq 0 $
  • $ p_1 + p_2 + \dots + p_n = 1 $
  • The (squared) Euclidean distance between P and A, which is $ |A - P|_2^2 = \sum_{i = 1}^n (a_i / m - p_i)^2 $ , is minimized.

It can be proved the minimum is always a rational number. Print the squared distance in fraction. Note to print an integer $ n $ as n instead of n/1.

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains two integers $ n $ and $ m $ .
The second line contains n integers $ a_1, a_2, \dots, a_n $ .

  • $ 1 \leq n \leq 10^4 $
  • $ 1 \leq m \leq 10^3 $
  • $ -m \leq a_i \leq m $
  • The sum of n does not exceed $ 5 \times 10^5 $ .

输出描述

For each test case, print a fraction which denotes the result.

示例1

输入

1
2
3
4
5
6
1 1
0
2 3
1 2
3 10
1 -2 3

输出

1
2
3
1
0
16/75

题解

题意

给定 $ n $ 维空间中的一个点 $ A ( \dfrac{a_1}{m},\dfrac{a_2}{m} \dots \dfrac{a_n}{m} ) $ , $ a_i $ 和 $ m $ 都是整数。要求确定一个点 $ P = (p_1,p_2 \dots p_n ) $ 满足:

  • $ p_1,p_2 \dots p_n $ 都是实数
  • $ p_i\geq 0 $
  • $ p_1+p_2+\dots +p_n=1 $
  • $ \displaystyle \sum\limits_{i=1}^{n}(\frac{a_i}{m}-p_i)^2 $ 尽可能小

解法

令 $ P_i=m \times p_i $ 则问题转化为求 $ \displaystyle \sum\limits_{i=1}^{n}(a_i-P_i)^2 $ 的最小值。因为 $ P_i\geq 0 $ ,所以 $ (a_i-P_i)^2 $ 只会随着 $ P_i $ 的增大而减小。

首先将 $ a_i $ 按降序排列,对于每个 $ i $ ,使 $ a_j - P_j = a_{i+1},j \in [1,i] $ ,且 $ \displaystyle m-\sum\limits_{j=1}^iP_j\geq 0 $ ,使较大的值降下。

可以找到一个点 $ id $ ,其之前的 $ a_i $ 都被降到了值 $ a_{id} $ 。之后的 $ P_i = 0 $ ,即后面的 $ a_i $ 值不变。如果还有剩下的部分,可以将其平均分配到前 $ id $ 项,记这个部分是 $ res $ 。那么最终的结果为 $ \displaystyle \frac{id*(a_{id}-\frac{res}{id})^2+\sum\limits_{i=id+1}^{n}a_i^2}{m^2} $ 。

主要思想是 $ P $ 只会使得 $ a $ 减小,所以优先使最大值降低是最优策略。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 10001
int a[N], n, m;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
int main() {
while (~scanf("%d%d", &n, &m)) {
for (int i = 1, x; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + 1 + n, greater<int>());
int res = m, id = 1;
for (id = 1; id < n; id++) {
if (id * abs(a[id + 1] - a[id]) > res) break;
res -= id * abs(a[id + 1] - a[id]);
}
ll s = 0;
for (int i = id + 1; i <= n; i++) s += a[i] * a[i];
ll c = a[id] * id - res, x = c * c + id * s, y = m * m * id,
g = gcd(x, y);
x /= g, y /= g;
if (y == 1)
printf("%lld\n", x);
else
printf("%lld/%lld\n", x, y);
}
return 0;
}

D - Parity of Tuples

题目描述

Bobo has n m-tuple $ v_1, v_2, \dots, v_n $ , where $ v_i = (a_{i, 1}, a_{i, 2}, \dots, a_{i, m}) $ . He wants to find $ \mathrm{count}(x) $ which is the number of $ v_i $ where $ a_{i, j} \wedge x $ has odd number of ones in its binary notation for all $ j $ . Note that $ \wedge $ denotes the bitwise-and.

Print $ \bigoplus_{x = 0}^{2^k - 1} \left(\mathrm{count}(x) \cdot 3^x \bmod (10^9+7)\right) $ for given $ k $ , where $ \oplus $ denotes bitwise-xor.

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains three integers $ n $ , $ m $ and $ k $ .
The ith of the following $ n $ lines contains $ m $ integers $ a_{i, 1}, a_{i, 2}, \dots, a_{i, m} $ .

  • $ 1 \leq n \leq 10^5 $
  • $ 1 \leq m \leq 10 $
  • $ 1 \leq k \leq 20 $
  • $ 0 \leq a_{i, j} < 2^k $
  • There is exactly one test case with $ n = 10^5 $ , $ m = 10 $ and $ k = 20 $ . The other $ 300 $ test cases have $ n \leq 10^3 $ , $ m \leq 4 $ and $ k \leq 10 $ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

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

输出

1
2
3
10
3
1102106

E - ABBA

题目描述

Bobo has a string of length $ 2(n + m) $ which consists of characters A and B. The string also has a fascinating property it can be decomposed into $ (n + m) $ subsequences of length $ 2 $ , and among the $ (n + m) $ subsequences $ n $ of them are AB while other m of them are BA.

Given n and m, find the number of possible strings modulo $ (10^9+7) $ .

输入描述

The input consists of several test cases and is terminated by end-of-file.

Each test case contains two integers n and m.

  • $ 0 \leq n, m \leq 10^3 $
  • There are at most $ 2019 $ test cases, and at most $ 20 $ of them has $ \max\{n, m\} > 50 $ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

1
2
3
1 2
1000 1000
0 0

输出

1
2
3
13
436240410
1

题解

题意

给定 $ n $ 和 $ m $ ,询问你有多少种长度为 $ 2 \times ( n + m ) $ 的仅由字符 $ A $ 和 $ B $ 构成的字符串,能够拆成 $ n $ 个 $ AB $ 序列和 $ m $ 个 $ BA $ 序列。

解法

从贪心的角度考虑,我们将序列中前 $ n $ 个 $ A $ 作为 $ n $ 个 $ AB $ 序列的一部分, 将序列中后 $ m $ 个 $ B $ 作为 $ m $ 个 $ BA $ 序列的一部分。这样不会影响答案正确性。

因此我们对于 $ A $ ,只要放的 $ A $ 的数量小于 $ n + \mathrm{min}(j, m) $ ,其中 $ j $ 为放的 $ B $ 的数量, $ m $ 为 $ BA $ 中的 $ B $ 的数量, $ n $ 为 $ AB $ 中 $ A $ 的数量,那我们可以直接相加方法数当成状态的转移,对于放 $ B $ 的情况也同理。

$ dp $ 的边界是我们在前 $ n $ 个位置可以直接放 $ A $ ,也可以在前 $ m $ 个位置直接放 $ B $ 。

那么我们令 $ f_{i,j} $ 表示前 $ i + j $ 个位置放置了 $ i $ 个 $ A $ 和 $ j $ 个 $ B $ 的方案数,详细状态转移方程见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define N 2001
int f[N << 1][N << 1], n, m;
int main() {
while (~scanf("%d%d", &n, &m)) {
for (int i = 0; i <= n + m; i++)
for (int j = 0; j <= n + m; j++) f[i][j] = 0;
for (int i = 0; i <= n; i++) f[i][0] = 1;
for (int i = 0; i <= m; i++) f[0][i] = 1;
for (int i = 1; i <= n + m; i++)
for (int j = 1; j <= n + m; j++) {
if (i <= n + min(j, m))
f[i][j] = (f[i][j] % mod + f[i - 1][j] % mod) % mod;
if (j <= m + min(i, n))
f[i][j] = (f[i][j] % mod + f[i][j - 1] % mod) % mod;
}
printf("%d\n", f[n + m][n + m] % mod);
}
return 0;
}

F - Random Point in Triangle

题目描述

Bobo has a triangle ABC with $ A(x_1, y_1), B(x_2, y_2) $ and $ C(x_3, y_3) $ . Picking a point $ P $ uniformly in triangle $ ABC $ , he wants to know the expectation value $ E = \max\{S_{PAB}, S_{PBC}, S_{PCA}\} $ where $ S_{XYZ} $ denotes the area of triangle $ XYZ $ .

Print the value of $ 36 \times E $ . It can be proved that it is always an integer.

输入描述

The input consists of several test cases and is terminated by end-of-file.

Each test case contains six integers $ x_1, y_1, x_2, y_2, x_3, y_3 $ .

  • $ |x_1|, |y_1|, |x_2|, |y_2|, |x_3|, |y_3| \leq 10^8 $
  • There are at most $ 10^5 $ test cases.

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

1
2
3
0 0 1 1 2 2
0 0 0 0 1 1
0 0 0 0 0 0

输出

1
2
3
0
0
0

题解

题意

给定一个三角形 $ ABC $ 的三个顶点,现在在该三角形中任选一点 $ P $ ,定义价值 $ E = \max\{S_{PAB}, S_{PBC}, S_{PCA}\} $

询问你 $ 36 \times E $ 的期望值。

解法

对 $ S_{PAB}, S_{PBC}, S_{PCA} $ 分别作为最大值时的情况做讨论,分三个部分做定积分,可求得 $ 36 \times E $ 的期望值等于 $ 11 $ 倍的三角形 $ ABC $ 的面积。

代码

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll a, b, c, d, e, f;
while (~scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &e, &f))
printf("%lld\n", abs(a * (d - f) + c * (f - b) + e * (b - d)) * 11);
return 0;
}

G - Substrings 2

题目描述

Two strings $ u_1 u_2 \dots u_k $ and $ v_1 v_2 \dots v_l $ are isomorphic if and only if $ k = l $ and there exists a injection $ \phi $ such that $ u_i = \phi(v_i) $ for all $ i \in \{1, 2, \dots, k\} $ .
Note that a function f is injection if and only if $ f(x) \neq f(y) $ for all $ x \neq y $ .

Bobo would like to choose some strings from all $ \dfrac{n(n + 1)}{2} $ substrings of the given string $ s_1 s_2 \dots s_n $ .
Find out the maximum number of strings he may choose so that no two chosen strings are isomorphic.

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains a string $ s_1, s_2, \dots, s_n $ .

  • $ 1 \leq n \leq 5\times 10^4 $
  • $ 1 \leq s_i \leq n $
  • There are at most $ 10^3 $ test cases, and at most $ 5 $ of them have $ n > 50 $ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

1
2
3
4
5
6
3
1 2 3
3
1 2 2
5
1 3 1 2 5

输出

1
2
3
3
4
7

H - XOR

题目描述

Bobo has a set A of n integers $ a_1, a_2, \dots, a_n $ .

He wants to know the sum of sizes for all subsets of A whose xor sum is zero modulo $ (10^9+7) $ .

Formally, find $ \displaystyle\left( \displaystyle\sum{S \subseteq A, \oplus_{x \in S} x = 0} |S| \right) \bmod (10^9+7) $ . Note that $ \oplus $ denotes the exclusive-or (XOR).

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers $ a_1, a_2, \dots, a_n $ ​.

  • $ 1 \leq n \leq 10^5 $
  • $ 0 \leq a_i \leq 10^{18} $
  • The number of test cases does not exceed $ 100 $ .
  • The sum of n does not exceed $ 2 \times 10^6 $ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

1
2
3
4
5
6
1
0
3
1 2 3
2
1000000000000000000 1000000000000000000

输出

1
2
3
1
3
2

题解

题意

求 $ n $ 个数中子集内所有数异或为 $ 0 $ 的子集大小之和。

解法

枚举子集必然会超时,那么考虑枚举元素。考察每个元素对答案的贡献,即每个元素各自出现在几个异或和为 $ 0 $ 的子集中。

此时可以利用线性基的特性。

  • 首先计算一次线性基 $ R $ 。

    • 对于每一个不在基底中的元素,它对答案的贡献为 $ \displaystyle 2^{n-|R|-1} $ 。因为我们可以任取每一个不在基底中的元素组成一个数,线性基的特性保证基底中的数唯一的方案来表示这个数。而任取其他不在基底中的数的方案数有 $ \displaystyle 2^{n-|R|-1} $ 种。
    • 对于每一个在基底中的元素,首先把其余的 $ n-1 $ 个元素重新生成一个基底 $ D $ ,如果该元素还是可以插入到基底 $ D $ 中,那么就说明该元素对答案贡献为0,否则贡献为 $ \displaystyle 2^{ n-|D|-1} $ 。
  • 优化

    • 每次生成 $ D $ 的时间复杂度是 $ \mathcal{O}(n) $ ,生成 $ n $ 次的时间复杂度是 $ \mathcal{O}(n^2) $ 。因此考虑优化时间复杂度,对于每个不在基底中的元素,建立一个基 $ B $ ,每次将扔掉一个元素的基 $ R $ 与基 $ B $ 合并。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define N 100001
ll a[N];
ll R[110], B[110], D[110];
bool v[N];
ll que[N];
bool Insert(ll x, ll y[]) {
for (int i = 63; i >= 0; i--)
if ((ll)1 << i & x) {
if (!y[i]) {
y[i] = x;
++y[64];
return true;
}
x ^= y[i];
}
return false;
}
bool Check(ll x, ll y[]) {
for (int i = 63; i >= 0; i--)
if ((ll)1 << i & x) x ^= y[i];
return !x;
}
ll Qpow(ll x, int n) {
ll t = 1;
while (n) {
if (n & 1) t = (t * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return t;
}
int main() {
int n;
while (~scanf("%d", &n)) {
memset(R, 0, sizeof(R));
memset(B, 0, sizeof(B));
for (int i = 1; i <= n; i++) v[i] = false;
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
ll ans = 0, num = 0;
for (int i = 1; i <= n; i++) {
v[i] = Insert(a[i], R);
if (v[i]) que[++num] = a[i];
}
if (R[64] != n) {
ans = (n - R[64]) * Qpow(2, n - R[64] - 1) % mod;
for (int i = 1; i <= n; i++)
if (!v[i]) Insert(a[i], B);
for (int k = 1; k <= num; k++) {
memset(D, 0, sizeof(D));
for (int i = 1; i <= num; i++)
if (i != k) Insert(que[i], D);
for (int i = 0; i <= 63; i++)
if (B[i]) Insert(B[i], D);
if (Check(que[k], D))
ans = (ans + Qpow(2, n - D[64] - 1)) % mod;
}
}
printf("%lld\n", ans);
}
return 0;
}

I - Points Division

题目描述

Bobo has a set P of n distinct points $ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n) $ .

The i-th point has two weights $ a_i $ ​ and $ b_i $ ​.

He wants to partition the points into two sets $ A $ and $ B $ (That is, $ A \cup B = P $ and $ A \cap B = \emptyset $ .

A partition (A, B) is valid if and only if there exists no $ \in A $ and $ j \in B $ where $ x_i \geq x_j $ ​ and $ y_i \leq y_j $ ​.

Find the maximum of $ \left(\sum_{i \in A} a_i \right) + \left(\sum_{j \in B} b_j\right) $ among all valid partitions $ (A, B) $ .

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test cases contains an integer $ n $ .

The i-th of the following $ n $ lines contains four integers $ x_i, y_i, a_i, b_i $ .

  • $ 1 \leq n \leq 10^5 $
  • $ 1 \leq x_i, y_i, a_i, b_i \leq 10^9 $
  • $ (x_i, y_i) \neq (x_j, y_j) $ for all $ i \neq j $
  • The sum of n does not exceed $ 5 \times 10^5 $ .

输出描述

For each test case, print an integer which denotes the result.

示例1

输入

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

输出

1
2
3
10
3
26

题解

题意

给定二维平面上的一些带权点,每个点有两种权值 $ a_{i} $ 和 $ b_{i} $ 。现在要求在该平面上划一条从左到右非下降的折线,将这些点分为左右两个集合。左上角集合中的点计算权值为 $ a $ ,右下角集合中的点计算权值为 $ b $ 。现在询问你权值最大值。

解法

左向右枚举这条线上的折点,并用线段树维护当前横坐标前所有纵坐标的最大的划分,则可以得出最大答案。当存在横坐标相等时从上向下枚举则可以避免重复枚举。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define ll long long
#define inf (0x3fffffff)
#define N 100001
struct Point {
int x, y, id, a, b;
friend bool operator<(Point j, Point k) {
if (j.x == k.x) return j.y > k.y;
return j.x < k.x;
}
Point() {}
Point(int x, int y, int a, int b) : x(x), y(y), a(a), b(b) {}
} p[N];
struct node {
ll mx, tag;
node() : mx(0), tag(0) {}
node(ll mx, ll tag) : mx(mx), tag(tag) {}
} tree[N << 2];
vector<int> vec;
void Build(int id, int l, int r) {
tree[id] = node();
if (l == r) return;
int mid = (l + r) >> 1;
Build(lson(id), l, mid);
Build(rson(id), mid + 1, r);
}
void UpDown(int id) {
if (tree[id].tag == 0) return;
tree[lson(id)].mx = tree[lson(id)].mx + tree[id].tag;
tree[lson(id)].tag = tree[lson(id)].tag + tree[id].tag;
tree[rson(id)].mx = tree[rson(id)].mx + tree[id].tag;
tree[rson(id)].tag = tree[rson(id)].tag + tree[id].tag;
tree[id].tag = 0;
}
void Update1(int id, int l, int r, int ql, int qr, ll val) {
if (l >= ql && r <= qr) {
tree[id].mx += val;
tree[id].tag += val;
return;
}
UpDown(id);
int mid = (l + r) >> 1;
if (ql <= mid) Update1(lson(id), l, mid, ql, qr, val);
if (mid < qr) Update1(rson(id), mid + 1, r, ql, qr, val);
tree[id].mx = max(tree[lson(id)].mx, tree[rson(id)].mx);
}
void Update2(int id, int l, int r, int loc, ll val) {
if (l == r) {
tree[id].mx = max(tree[id].mx, val);
return;
}
UpDown(id);
int mid = (l + r) >> 1;
if (mid >= loc) Update2(lson(id), l, mid, loc, val);
if (mid < loc) Update2(rson(id), mid + 1, r, loc, val);
tree[id].mx = max(tree[lson(id)].mx, tree[rson(id)].mx);
}
ll Query(int id, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr) {
return tree[id].mx;
}
int mid = (l + r) >> 1;
UpDown(id);
ll ans = 0;
if (mid >= ql) ans = max(ans, Query(lson(id), l, mid, ql, qr));
if (mid < qr) ans = max(ans, Query(rson(id), mid + 1, r, ql, qr));
return ans;
}
int main() {
int n;
while (~scanf("%d", &n)) {
vec.clear();
for (int i = 1, x, y, a, b; i <= n; i++) {
scanf("%d%d%d%d", &x, &y, &a, &b);
p[i] = Point(x, y, a, b);
vec.push_back(y);
}
sort(p + 1, p + 1 + n);
vec.push_back(-inf);
vec.push_back(inf);
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (int i = 1; i <= n; i++)
p[i].id =
lower_bound(vec.begin(), vec.end(), p[i].y) - vec.begin() + 1;
int ns = vec.size();
Build(1, 1, ns);
for (int i = 1; i <= n; i++) {
ll g = Query(1, 1, ns, 1, p[i].id);
Update2(1, 1, ns, p[i].id, g + p[i].b);
Update1(1, 1, ns, p[i].id + 1, ns, p[i].b);
Update1(1, 1, ns, 1, p[i].id - 1, p[i].a);
}
printf("%lld\n", tree[1].mx);
}
return 0;
}

J - Fraction Comparision

题目描述

Bobo has two fractions $ \frac{x}{a} $ and $ \frac{y}{b} $ . He wants to compare them. Find the result.

输入描述

The input consists of several test cases and is terminated by end-of-file.

Each test case contains four integers $ x, a, y, b $ .

  • $ 0 \leq x, y \leq 10^{18} $
  • $ 1 \leq a, b \leq 10^9 $
  • There are at most $ 10^5 $ test cases.

输出描述

For each test case, print = if $ \dfrac{x}{a} = \dfrac{y}{b} $ . Print < if $ \dfrac{x}{a} < \dfrac{y}{b} $ . Print > otherwise.

示例1

输入

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

输出

1
2
3
<
>
=

题解

题意

给定两个分数 $ \dfrac{x}{a} $ 和 $ \dfrac{y}{b} $ ,要求比较这两个分数的大小。

解法

不难想到交叉相乘,但是受制于数据范围,我们可以把 $ \dfrac{x}{a} $ 拆成 $ \displaystyle \lfloor \frac{x}{a} \rfloor+\frac{x \bmod a}{a} $ ,把 $ \displaystyle\frac{y}{b} $ 拆成 $ \displaystyle \lfloor \frac{y}{b} \rfloor+\frac{y \bmod b}{b} $ ,如此一来就只需要整数与整数比,分数与分数比较了,分数部分取模以后可以使用交叉乘法而不必担心溢出问题。

但是为什么不试试优秀的__int128呢

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll x, y, a, b;
while (~scanf("%lld%lld%lld%lld", &x, &a, &y, &b)) {
ll x1 = x / a, x2 = x % a * b, y1 = y / b, y2 = y % b * a;
if (x1 == y1)
printf("%c\n", x2 == y2 ? '=' : x2 < y2 ? '<' : '>');
else
printf("%c\n", x1 < y1 ? '<' : '>');
}
return 0;
}