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

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

A - digits 2

题目描述

You are given a positive integer $ n $ which is at most $ 100 $ .

Please find a positive integer satisfying the following conditions:

  1. The sum of all digits of this number is dividable by $ n $ .
  2. This number is also dividable by $ n $ .
  3. This number contains no more than $ 10^4 $ digits.

If such an integer doesn’t exist, output Impossible (without quotation marks).

If there are multiple such integers, please output any one.

输入描述

The first line contains one integer $ T $ indicating that there are $ T $ tests.

Each test consists an integer $ n $ in a single line.

  • $ 1 \le T \le 100 $

  • $ 1 \le n \le 100 $

输出描述

For each query, output one line containing the answer. The number you print cannot have leading zeros. If there are multiple answers, you can print any. If such an integer doesn’t exist, output Impossible (without quotation marks) in a single line.

示例1

输入

1
2
3
4
3
1
9
12

输出

1
2
3
1
666666
888

说明

For the last test, $ 888 $ is dividable by $ 12 $ $ (888 = 12 \times 74) $ and $ 8 + 8 + 8 = 24 $ is also dividable by $ 12 $ $ (24 = 12 \times 2) $ .

题解

题意

给定一个 $ n $ ,要求输出一个数 $ m $ ,满足 $ m $ 是 $ n $ 的倍数,且 $ m $ 的各位数字之和也为 $ n $ 的倍数。

解法

将 $ n $ 输出 $ n $ 次(逃

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
int main() {
int t, n;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) printf("%d", n);
printf("\n");
}
return 0;
}

B - generator 1

题目描述

You are given four positive integers $ x_0, x_1, a, b $ . And you know $ x_i = a \cdot x_{i-1} + b \cdot x_{i-2} $ for all $ i \ge 2 $ .

Given two positive integers $ n $ , and $ MOD $ , please calculate $ x_n $ modulo $ MOD $ .

Does the problem look simple? Surprise! The value of $ n $ may have many many digits!

输入描述

The input contains two lines.

The first line contains four integers $ x_0, x_1, a, b $ $ 1 \le x_0, x_1, a, b \le 10^9 $ .

The second line contains two integers $ n $ , $ MOD $ ( $ 1 \le n < 10^{(10^6)} $ , $ 10^9 < MOD \le 2 \times 10^9 $ , $ n $ has no leading zero).

输出描述

Print one integer representing the answer.

示例1

输入

1
2
1 1 1 1
10 1000000001

输出

1
89

说明

The resulting sequence $ x $ is Fibonacci sequence. The $ 11 $ -th item is $ 89 $ .

题解

题意

给定数列 $ x $ 的第 $ 0 $ 项和第 $ 1 $ 项,以及递推关系式 $ x_i = a \cdot x_{i-1} + b \cdot x_{i-2} $ 中的 $ a $ 和 $ b $ 。

求该数列的第 $ n $ 项。

解法

众所周知这样的递推数列可以用矩阵快速幂做,时间复杂度为 $ \mathcal{O}(\log{n}) $ 。

但是因为 $ n $ 实在过大,所以采用矩阵快速幂套十倍增,时间复杂度为 $ \mathcal{O}(\log_{10}{n}\times \log_2{10}) $ 。

代码

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
char str[1000005];
ll x0, x1, a, b, mod;
ll tmp1[2][2] = {1, 0, 0, 1}, tmp2[2][2],
mat[12][2][2] = {1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1};
void matmul(const ll a[2][2], const ll b[2][2], ll c[2][2]) {
c[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % mod;
c[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % mod;
c[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % mod;
c[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % mod;
}
int main() {
scanf("%lld%lld%lld%lld%s%lld", &x0, &x1, &a, &b, str + 1, &mod);
int len = strlen(str + 1);
mat[8][0][0] = a;
mat[8][0][1] = b;
mat[8][1][0] = 1;
mat[8][1][1] = 0;
for (int i = len; i; i--) {
matmul(mat[2], mat[8], mat[1]);
for (int j = 2; j < 10; j++) matmul(mat[1], mat[j - 1], mat[j]);
matmul(tmp1, mat[str[i] - '0'], tmp2);
memcpy(tmp1, tmp2, sizeof(tmp1));
}
printf("%lld\n", (tmp1[1][0] * x1 + tmp1[1][1] * x0) % mod);
return 0;
}

C - generator 2

题目描述

There is a sequence of length $ n $ : $ x_0, x_1, x_2, \ldots, x_{n-1} $ . Please answer Q queries. Each query consists of one integer v, asking the minimum index $ i $ such that $ x_i = v $ . If the sequence doesn’t have any number with value $ v $ , you only need to output $ -1 $ .

Does the problem look simple? Surprise! The value of n may be as large as $ 10^{18} $ !

Because $ n $ is so large. We will only give you four integers $ x_0, a, b, p $ to generate the sequence. For all $ i>0 $ , the sequence is generated as $ x_i = (a \cdot x_{i-1} + b) \mod p $ .

输入描述

The first line of input contains an integer $ T $ ( $ T \le 4 $ ) denoting there are $ T $ tests in the input.

Each test contains $ Q+2 $ lines.

The first line of each test contains five integers $ n, x_0, a, b, p $ ( $ 1 \le n \le 10^{18}, 0 \le x_p,a,b < p \le 10^9 + 9 $ , $ p $ is a prime number).

The second line contains one integer $ Q $ ( $ Q \le 1000 $ ).

Each of the following $ Q $ lines contains one integer $ v $ ( $ 0 \le v < p $ ).

输出描述

For each query, print one integer as the answer in one line.

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
3
1000000009 1 1 1 1000000009
5
0
1
10
1000000008
1000000007
100000009 1 1 1 1000000009
3
0
10
1000000008
1000000000000000000 1 5 0 1000000007
6
0
1
10
1000000006
12345678
1234567

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1000000008
0
9
1000000007
1000000006
-1
9
-1
-1
0
381838283
500000003
652614354
581802189

说明

For the first test, the sequence looks like $ 1, 2, 3, \dots, 1000000008, 0 $ . So the position of the first occurrence of value $ v $ is $ v - 1 $ except for value $ 0 $ which occurs at $ 1000000008 $ .

示例2

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
2
1000000000000000000 5 2 2 1000000007
4
0
1
2
3
5 1 0 3 950000017
4
0
1
2
3

输出

1
2
3
4
5
6
7
8
115068150
342074
115068151
-1
-1
0
-1
1

题解

题意

已知 $ x_0,a,b,p $ ,现有递推式 $ x_n=(x_{n-1}*a+b)\%p, $ 每次询问一个 $ v $ ,问最小的 $ n $ 使得有 $ x_n=v。 $

解法

首先总结出 $ x_n $ 的通项公式:

那么对于给定的 $ v $ ,有公式:

对于 $ a $ 等于 $ 0 $ 或 $ 1 $ 时特殊处理,其他情况用BSGS求解。

同时需要注意的是不能将大步设定到 $ \sqrt{p} $ ,而要设定到为 $ p^{\frac{2}{3}} $ , 这样小步的复杂度就变为 $ p^{\frac{1}{3}} $ 。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, v;
int x0, a, b, p;
unordered_map<ll, ll> mp;
ll loop, up;
ll Qpow(ll x, ll n, ll mod) {
ll t = 1;
while (n) {
if (n & 1) t = t * x % mod;
x = x * x % mod;
n >>= 1;
}
return t;
}
void pre_BSGS(ll p, ll b) {
mp.clear();
up = ceil(pow(p, 2.0 / 3));
ll t = 1;
for (int i = 0; i <= up; i++) {
if (i == up) loop = t;
mp[t] = i;
t = t * b % p;
}
}
ll BSGS(ll N, ll P) {
ll m = ceil(pow(p, 1.0 / 3));
ll obj = Qpow(N, P - 2, P);
for (ll i = 1; i <= m; i++) {
obj = 1ll * obj * loop % P;
if (mp.count(obj)) {
return 1ll * i * up - mp[obj];
}
}
return -1;
}
int main() {
int t, q;
scanf("%d", &t);
while (t--) {
scanf("%lld%d%d%d%d", &n, &x0, &a, &b, &p);
ll ab_apo = 1ll * b * Qpow(a - 1, p - 2, p) % p;
ll x0ab_apo = (x0 + ab_apo) % p;
ll o_b = Qpow(b, p - 2, p);
pre_BSGS(p, a);
scanf("%d", &q);
while (q--) {
scanf("%lld", &v);
if (a == 1) {
ll ans = ((v - x0) * o_b % p + p) % p;
printf("%lld\n", ans < n ? ans : -1);
} else if (a == 0) {
printf("%d\n", x0 == v ? 0 : b == v ? 1 : -1);
} else {
v = (v + ab_apo) % p;
v = v * Qpow(x0ab_apo, p - 2, p) % p;
ll ans = BSGS(v, p);
printf("%lld\n", ans < n ? ans : -1);
}
}
}
return 0;
}

D - generator 3

题目描述

Here is another simple problem: Given n points in the $ 2 $ -dimensional plane, please calculate the area of the convex hull.

However, as you might already have guessed, the value of $ n $ is very large! So you’ll use the following generator to generate all those points:

You are given nine integers $ x_0, y_0, a_x, a_y, b_x, b_y, p_x, p_y, n $ .

There are two recursive equations: $ x_i= (a_x \times x_{i-1} + b_x) \mod p_x $ and $ y_i= (a_y \times y_{i-1} + b_y) \mod p_y $ for all $ 0 < i < n $ .

The given n points are $ (x_i, y_i) $ for $ 0 \le i < n $ .

输入描述

The input consists of only one line.

This line contains nine integers in the following order: $ x_0, y_0, a_x, a_y, b_x, b_y, p_x, p_y, n $ .

  • $ 0 \le x_0, a_x, b_x < p_x < 2 \times 10^5 $

  • $ 0 \le y_0, a_y, b_y < p_y < 2 \times 10^5 $

  • $ 3 \le n \le 10^{18} $

  • There may be multiple points in the same position

输出描述

Please output one integer denoting the area of the convex hull (of the generated n points) multiplied by $ 2 $ .

It can be proved that two times such area is always an integer.

示例1

输入

1
2 3 4 5 6 7 8 9 10

输出

1
28

示例2

输入

1
123 193 37 59 31 128 195777 193241 12345678

输出

1
75659192744

E - independent set 1

题目描述

Note:For C++ languages, the memory limit is 100 MB. For other languages, the memory limit is 200 MB.

In graph theory, an independent set is a set of nonadjacent vertices in a graph. Moreover, an independent set is maximum if it has the maximum cardinality (in this case, the number of vertices) across all independent sets in a graph.

An induced subgraph $ G’(V’, E’) $ of a graph $ G(V, E) $ is a graph that satisfies:

  • $ V’ \subseteq V $ .
  • edge $ (a,b) \in E’ $ if ans only if $ a \in V’, b \in V’ $ ans edge $ (a, b) \in E $ .

Now, given an undirected unweighted graph consisting of $ n $ vertices and $ m $ edges. This problem is about the cardinality of the maximum independent set of each of the $ 2^n $ possible induced subgraphs of the given graph. Please calculate the sum of the $ 2^n $ such cardinalities.

输入描述

The first line contains two integers $ n $ and $ m $ ( $ 2 \le n \le 26, 0 \le m \le \frac{n \times (n-1)}{2} $ ) —- the number of vertices and the number of edges, respectively. Next m lines describe edges: the i-th line contains two integers $ x_i, y_i $ ( $ 0 \le x_i < y_i < n $ ) —- the indices (numbered from $ 0 $ to $ n - 1 $ ) of vertices connected by the $ i $ -th edge.

The graph does not have any self-loops or multiple edges.

输出描述

Print one line, containing one integer represents the answer.

示例1

输入

1
2
3
3 2
0 1
0 2

输出

1
9

说明

The cardinalities of the maximum independent set of every subset of vertices are: {}: 0, {0}: 1, {1}: 1, {2}: 1, {0, 1}: 1, {0, 2}: 1, {1, 2}: 2, {0, 1, 2}: 2 . So the sum of them are $ 9 $ .

示例2

输入

1
2
3
4
5
6
7 5
0 5
3 4
1 2
2 5
0 2

输出

1
328

题解

题意

给定一张图,求该图所有子图的最大独立集的大小之和。

解法

因为子图虽然很多,但是点数很少,可以考虑枚举点集。使用状压DP即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, a[27];
char f[(1 << 27) + 5];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
a[u] += (1 << v);
a[v] += (1 << u);
}
for (int i = 0; i < n; i++)
for (ll j = 0; j < (1 << i); j++)
f[(1 << i) + j] = max(f[j], (char)(f[j & (~a[i])] + 1));
ll ans = 0;
for (int i = 0; i < (1 << n); i++) ans += f[i];
printf("%lld\n", ans);
return 0;
}

F - maximum clique 1

题目描述

You are given a set $ S $ containing $ n $ distinct positive integers $ a_1, a_2, \ldots, a_n $ .

Please find a subset of $ S $ which has the maximum size while satisfying the following constraint:

The binary representations of any two numbers in this subset must have at least two different bits.

If there are multiple valid subsets, please output any one of them.

输入描述

The input contains only two lines.

The first line contains an integer $ N $ denoting the size of $ S $ .

The second line contains $ N $ positive integers $ a_1, a_2, \ldots, a_N $ denoting the members of set $ S $ .

  • $ 1 \le N \le 5000 $

  • $ 1 \le a_i \le 10^9 $

  • all $ a_i $ are distinct

输出描述

You should output two lines.

The first line contains one integer $ m $ denoting the size of the subset you found.

The second line contains m positive integers denoting the member of this subset.

示例1

输入

1
2
5
3 1 4 2 5

输出

1
2
3
4 1 2

说明

$ 3 (112) $ and $ 1 (012) $ has only $ 1 $ different bit so they can not be in the set together. $ 4 (1002) $ and $ 1 (0012) $ has $ 2 $ different bits so they can be in the set together.

Following unordered pairs are allowed to be in the set together: $ <1, 2>, <1, 4>, <2, 4>, <2, 5>, <3, 4>, <3, 5> $ . Thus the maximum set is of size $ 3 ({1, 2, 4}) $ .

解法

题意

给定一个序列,要求分出一个尽可能大的集合,满足任意两数的二进制位上至少有两个不同。

解法

把每一个数看作为一个点,那么对于任意两数,如果它们二进制位上至少有两个不同则连一条边。

那么问题转化为最大团问题。

最大团转为补图最大独立集. 可以发现补图是二分图, 所以直接dinic即可。

最大独立集相当于 $ n $- 最小割, 最终 $ X $ 部仍与 $ S $ 相连的点和 $ Y $ 部不与 $ S $ 相连的点构成最大独立集。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, S = N - 2, T = N - 1, INF = 0x3f3f3f3f;
int n, a[N], b[N];
struct edge {
int to, w, next;
edge(int to = 0, int w = 0, int next = 0) : to(to), w(w), next(next) {}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt = 1;
queue<int> Q;
int bfs() {
for (int i = 1; i <= n; i++) dep[i] = INF, vis[i] = 0, cur[i] = head[i];
dep[S] = INF, vis[S] = 0, cur[S] = head[S];
dep[T] = INF, vis[T] = 0, cur[T] = head[T];
dep[S] = 0, Q.push(S);
while (Q.size()) {
int u = Q.front();
Q.pop();
for (int i = head[u]; i; i = e[i].next)
if (dep[e[i].to] > dep[u] + 1 && e[i].w) {
dep[e[i].to] = dep[u] + 1;
Q.push(e[i].to);
}
}
return dep[T] != INF;
}
int dfs(int x, int w) {
if (x == T) return w;
int used = 0;
for (int i = cur[x]; i; i = e[i].next) {
cur[x] = i;
if (dep[e[i].to] == dep[x] + 1 && e[i].w) {
int f = dfs(e[i].to, min(w - used, e[i].w));
if (f) used += f, e[i].w -= f, e[i ^ 1].w += f;
if (used == w) break;
}
}
return used;
}
int dinic() {
int ans = 0;
while (bfs()) ans += dfs(S, INF);
return ans;
}
void add(int u, int v, int w) {
e[++cnt] = edge(v, w, head[u]);
head[u] = cnt;
e[++cnt] = edge(u, 0, head[v]);
head[v] = cnt;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
b[i] = __builtin_parity(a[i]);
b[i] ? add(S, i, 1) : add(i, T, 1);
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
int x = a[i] ^ a[j];
if ((x & (x - 1)) == 0) b[i] ? add(i, j, INF) : add(j, i, INF);
}
printf("%d\n", n - dinic());
for (int i = 1; i <= n; i++)
if ((dep[i] == INF) ^ b[i]) printf("%d ", a[i]);
printf("\n");
return 0;
}

G - subsequence 1

题目描述

You are given two strings s and t composed by digits (characters 0 $ \sim$ 9). The length of s is n and the length of t is m. The first character of both s and t aren’t 0.

Please calculate the number of valid subsequences of s that are larger than t if viewed as positive integers. A subsequence is valid if and only if its first character is not 0.

Two subsequences are different if they are composed of different locations in the original string. For example, string 1223 has $ 2 $ different subsequences 23.

Because the answer may be huge, please output the answer modulo 998244353.

输入描述

The first line contains one integer $ T $ , indicating that there are $ T $ tests.

Each test consists of $ 3 $ lines.

The first line of each test contains two integers $ n $ and $ m $ , denoting the length of strings $ s $ and $ t $ .

The second line of each test contains the string $ s $ .

The third line of each test contains the string $ t $ .

  • $ 1 \le m \le n \le 3000 $

  • sum of $ n $ in all tests $ \le 3000 $ .

  • the first character of both $ s $ and $ t $ aren’t 0.

输出描述

For each test, output one integer in a line representing the answer modulo 998244353.

示例1

输入

1
2
3
4
5
6
7
8
9
10
3
4 2
1234
13
4 2
1034
13
4 1
1111
2

输出

1
2
3
9
6
11

说明

For the last test, there are $ 6 $ subsequences 11, $ 4 $ subsequcnes 111 and $ 1 $ subsequence 1111 that are valid, so the answer is 11.

解法

题意

给定两个仅包含数字的字符串,询问串一中有多少不含前导零的子数串比串二大。

解法

DP+排列组合强行推(X

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
#define N 3001
char s[N], t[N];
ll g[N], f[N][N];
void Prepare() {
for (int i = 0; i < N; i++) f[i][0] = f[i][i] = 1;
for (int i = 2; i < N; i++)
for (int j = 1; j < i; j++)
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;
}
int main() {
Prepare();
int T, n, m;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
scanf("%s%s", s + 1, t + 1);
g[0] = 1;
for (int i = 1; i <= m; i++) g[i] = 0;
ll ans = 0;
for (int i = 1; i <= n; i++) {
if (s[i] != '0')
for (int j = m; j <= n - i; j++)
ans = (ans + f[n - i][j]) % mod;
for (int j = 1; j <= min(i, m); j++)
if (s[i] > t[j]) ans = (ans + f[n - i][m - j] * g[j - 1]) % mod;
for (int j = min(i, m); j; j--)
if (s[i] == t[j]) g[j] = (g[j] + g[j - 1]) % mod;
}
printf("%lld\n", ans);
}
return 0;
}

H - subsequence 2

题目描述

There is a hidden string of length $ n $ composed of the first $ m $ lowercase English letters. For any two different English letters, we will tell you a subsequence of the hidden string constructed by removing all other letters from the hidden string.

For example, if the hidden string is apple and the chosen letters are e and p, the resulting subsequence would be ppe; if the chosen letters are a and x, the resulting subsequence would be a.

Now, please recover the hidden string. Output -1 if there are no possible hidden string. Output any one if there are multiple possible hidden strings.

输入描述

The first line contains two integers $ n $ and $ m $ .

Following are $ \dfrac{m \times (m-1)}{2} $ groups of two lines. The first line in each group contains a two-letter string composed of $ c1, c2 $ , and an integer $ LEN $ . The second line contains a string composed of letters $ c1, c2 $ with length $ LEN $ , indicates the resulting subsequence by removing all other letters except $ c1 $ and $ c2 $ from the hidden string.

  • $ 1 \le n \le 10^4 $

  • $ 2 \le m \le 10 $

  • $ 0 \le LEN \le n $

  • all unordered pairs of letters in first m small English letters will occur exactly once.

输出描述

If there is at least one possible hidden string, please output any. Otherwise, output -1.

示例1

输入

1
2
3
4
5
6
7
3 3
ab 2
ab
bc 2
bc
ca 2
ac

输出

1
abc

示例2

输入

1
2
3
4
5
6
7
3 3
ab 2
ab
bc 2
bc
ca 2
ac

输出

1
-1

示例3

输入

1
2
3
4
5
6
7
4 3
ac 4
cccc
ba 0

cb 4
cccc

输出

1
cccc

题解

题意

使用前 $ m $ 个小写字母构造一个长度为 $ n $ 的字符串

有 $ m∗(m−1)/2 $ 个限制条件:

  • $ c1、c2、len $ :表示除去其他非 $ c1、c2 $ 之外的字母剩下的串长度为 $ len $
  • $ s $ :除去其他非 $ c1、c2 $ 之外的字母剩下的字符串,长度为 $ len $

需要我们根据这个限制条件构造出原串,如果不存在输出−1

解法

队友写的,拓扑排序.jpg

代码

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
#include <bits/stdc++.h>
using namespace std;
int n, m;
char p[50][5], s[50][10005];
int len[50], off[15];
set<int> nexts[20005];
int in[20005];
char ans[10005];
int ansi;
queue<int> q;
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i * 2 < m * (m - 1); ++i) {
scanf("%s%d", p[i], len + i);
if (len[i])
scanf("%s", s[i]);
else
s[i][0] = 0;
if (!off[p[i][0] - 'a' + 1])
for (int j = 0; s[i][j]; ++j)
if (s[i][j] == p[i][0]) ++off[p[i][0] - 'a' + 1];
if (!off[p[i][1] - 'a' + 1])
for (int j = 0; s[i][j]; ++j)
if (s[i][j] == p[i][1]) ++off[p[i][1] - 'a' + 1];
}
for (int i = 1; i < m; ++i) off[i] += off[i - 1];
if (off[m - 1] + off[m] != n) {
puts("-1");
return 0;
}
for (int i = 0; i * 2 < m * (m - 1); ++i) {
int mp[256], c[2] = {off[p[i][0] - 'a'], off[p[i][1] - 'a']};
mp[p[i][0]] = 0, mp[p[i][1]] = 1;
for (int j = 1; j < len[i]; ++j) {
int cl = mp[s[i][j - 1]], co = mp[s[i][j]];
int t = c[co] + (s[i][j - 1] == s[i][j]);
if (nexts[c[cl]].find(t) == nexts[c[cl]].end()) {
nexts[c[cl]].insert(t);
++in[t];
}
++c[cl];
}
}
for (int i = 0; i < n; ++i)
if (!in[i]) q.push(i);
while (!q.empty()) {
int t = q.front();
q.pop();
ans[ansi++] = upper_bound(off, off + m, t) - off + 'a' - 1;
for (auto it = nexts[t].begin(); it != nexts[t].end(); ++it)
if (!--in[*it]) q.push(*it);
}
printf("%s\n", ansi == n ? ans : "-1");
return 0;
}

I - three points 1

题目描述

You are given five positive integers $ w, h, a, b, c $ . Please construct $ 3 $ points $ X, Y, Z $ in the $ 2 $ -dimensional plane such that the distance between $ X $ and $ Y $ is $ a $ the distance between $ X $ and $ Z $ is $ b $ , the distance between $ Y $ and $ Z $ is $ c $ . Furthermore, the $ x $ coordinates of all constructed points must be in the range $ [0, w] $ , and the $ y $ coordinates of all constructed points must be in the range $ [0,h] $ .

The value of the constructed coordinates $ X, Y, Z $ can be real numbers. The input guarantees that at least one solution exists.

输入描述

The first line contains an integer $ T $ indicating there are $ T $ tests.

Each test consists of a single line containing five integers: $ w, h, a, b, c $ .

$ 1 \le w, h, a, b, c \le 50 $

$ 1 \le T \le 5 \times 10^4 $

输出描述

For each test, output one line containing six numbers, the first two numbers are the coordinate of $ X $ , the third and fourth numbers are the coordinate of $ Y $ , the last two numbers are the coordinate of $ Z $ . If there are multiple solutions, please output any one.

All absolute error within $ 1e^{-6} $ will be ignored.

示例1

输入

1
2
3
4
3
24 16 20 25 15
1 1 1 1 1
50 50 1 2 3

输出

1
2
3
0.000000000000 0.000000000000 12.000000000000 16.000000000000 24.000000000000 7.000000000000
0.000000000000 0.000000000000 0.500000000000 0.866025403784 1.000000000000 0.000000000000
1.000000000000 0.000000000000 0.000000000000 0.000000000000 3.000000000000 0.000000000000

说明

For the last test, the distance between $ (1, 0) $ and $ (0, 0) $ is $ 1 $ , the distance between $ (1, 0) $ and $ (3, 0) $ is $ 2 $ , and the distance between $ (0, 0) $ and $ (3, 0) $ is $ 3 $ .

题解

题意

给定一个宽度为 $ w $ ,高度为 $ h $ 的矩形。要求在矩形内选取三个点 $ X,Y,Z $ ,使得 $ XY $ 长度为 $ a $ , $ XZ $ 长度为 $ b $ , $ YZ $ 长度为 $ c $ 。

解法

枚举将一个点放在矩形的左下角,然后另一个点放在矩形的边上,求第三个点的所有情况。

尽量避免浮点运算以减小误差。

代码

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
#include <bits/stdc++.h>
using namespace std;
double w, h, l[3];
double x[3], y[3];
double a1, a2;
void putO(int i) {
x[i] = y[i] = 0;
double a = i == 0 ? l[2] : l[0], b = i == 1 ? l[2] : l[1];
a2 = acos((a * a + b * b - l[i] * l[i]) / 2 / a / b);
}
void putA(int i) {
if (l[i] <= w) {
x[i] = l[i];
y[i] = 0;
a1 = 0;
} else {
a1 = acos(w / l[i]);
x[i] = w;
y[i] = sqrt(l[i] * l[i] - w * w);
}
}
bool putT(int i) {
x[i] = l[i] * cos(a1 + a2);
y[i] = l[i] * sin(a1 + a2);
return -1e-7 <= x[i] && x[i] <= w + 1e-7 && -1e-7 <= y[i] &&
y[i] <= h + 1e-7;
}
bool put() {
putO(0);
swap(l[1], l[2]);
if (putA(1), putT(2)) return true;
if (putA(2), putT(1)) return true;
swap(l[1], l[2]);
putO(1);
swap(l[0], l[2]);
if (putA(0), putT(2)) return true;
if (putA(2), putT(0)) return true;
swap(l[0], l[2]);
putO(2);
swap(l[0], l[1]);
if (putA(0), putT(1)) return true;
if (putA(1), putT(0)) return true;
swap(l[0], l[1]);
return false;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%lf%lf%lf%lf%lf", &w, &h, l + 2, l + 1, l);
if (!put()) {
swap(w, h);
put();
for (int i = 0; i < 3; ++i) swap(x[i], y[i]);
}
printf("%.8f %.8f ", x[0], y[0]);
printf("%.8f %.8f ", x[1], y[1]);
printf("%.8f %.8f\n", x[2], y[2]);
}
return 0;
}

J - three points 2

题目描述

Here is an unweighted tree (Graph theorem literature) with $ n $ vertices along with $ Q $ queries. Each query consists of three integers $ a, b, c $ . Please find three vertices $ X, Y, Z $ such that the distance between $ X $ and $ Y $ is $ a $ , the distance between $ X $ and $ Z $ is $ b $ , and the distance between $ Y $ and $ Z $ is $ c $ .

The distance of two vertices is the number of edges in the simple path between them.

输入描述

The first line of input contains an integer n denoting the number of vertices.

The $ i $ -th line of the following $ n-1 $ lines contains two integers $ x_i, y_i $ denoting an edge connecting vertex $ x_i $ and vertex $ y_i $ (vertices are numbered from $ 0 $ to $ n-1 $ ).

The $ (n+1) $ -th line contains an integer $ Q $ denoting the number of queries.

The following $ Q $ lines each contains a query represented by three positive integers $ a, b, c $ .

  • $ 3 \le n, Q \le 2 \times 10^5 $

  • $ 1 \le a,b,c \le n-1 $

输出描述

For each query, if there exist three vertices $ X, Y, Z $ satisfying that the distance between $ X $ and $ Y $ is $ a $ , the distance between $ X $ and $ Z $ is $ b $ , and the distance between $ Y $ and $ Z $ is $ c $ , output one line containing three numbers indicating the index of $ X, Y $ , and $ Z $ . If there is no solution, please output only one integer -1 in a line. If there are multiple solutions, output any one.

示例1

输入

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

输出

1
2
3
4
0 2 3
-1
3 4 2
-1

说明

For the first test, the simple path between $ 0 $ and $ 2 $ is $ 0-1-2 $ , the simple path between $ 0 $ and $ 3 $ is $ 0-1-3 $ , and the simple path between $ 2 $ and $ 3 $ is $ 2-1-3 $ . All of them have a distance of $ 2 $ .