Codeforces Round 953 (Div. 2 ABCDEF题) 视频讲解

2024-06-19 08:20

本文主要是介绍Codeforces Round 953 (Div. 2 ABCDEF题) 视频讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A. Alice and Books

Problem Statement

Alice has n n n books. The 1 1 1-st book contains a 1 a_1 a1 pages, the 2 2 2-nd book contains a 2 a_2 a2 pages, … \ldots , the n n n-th book contains a n a_n an pages. Alice does the following:

  • She divides all the books into two non-empty piles. Thus, each book ends up in exactly one of the two piles.
  • Alice reads one book with the highest number in each pile.

Alice loves reading very much. Help her find the maximum total number of pages she can read by dividing the books into two piles.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 500 1 \le t \le 500 1t500) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n n n ( 2 ≤ n ≤ 100 2 \le n \le 100 2n100) — the number of books Alice has.

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1ai109) — the number of pages in each book.

Output

For each test case, output a single integer — the maximum number of pages Alice can read.

Example

Example

input
5
2
1 1
4
2 3 3 1
5
2 2 3 2 2
2
10 3
3
1 2 3
output
2
4
5
13
5

Note

In the first test case, Alice can put book number 1 1 1 in the first pile, and book number 2 2 2 in the second pile. Then she will read a 1 + a 2 = 1 + 1 = 2 a_1 + a_2 = 1 + 1 = 2 a1+a2=1+1=2 pages.

In the second test case, Alice can put books with numbers 2 2 2 and 3 3 3 in the first pile, and books with numbers 1 1 1 and 4 4 4 in the second pile. Then she will read the book with the highest number 3 3 3 from the first pile, and the book with the highest number 4 4 4 from the second pile. Then she will read a 3 + a 4 = 3 + 1 = 4 a_3 + a_4 = 3 + 1 = 4 a3+a4=3+1=4 pages.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 1e2 + 10;int n;
int a[N];void solve() {cin >> n;int mx = 0;for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i < n; i ++)mx = max(mx, a[i]);cout << mx + a[n] << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

B. New Bakery

Problem Statement

Bob decided to open a bakery. On the opening day, he baked n n n buns that he can sell. The usual price of a bun is a a a coins, but to attract customers, Bob organized the following promotion:

  • Bob chooses some integer k k k ( 0 ≤ k ≤ min ⁡ ( n , b ) 0 \le k \le \min(n, b) 0kmin(n,b)).
  • Bob sells the first k k k buns at a modified price. In this case, the price of the i i i-th ( 1 ≤ i ≤ k 1 \le i \le k 1ik) sold bun is ( b − i + 1 ) (b - i + 1) (bi+1) coins.
  • The remaining ( n − k ) (n - k) (nk) buns are sold at a a a coins each.

Note that k k k can be equal to 0 0 0. In this case, Bob will sell all the buns at a a a coins each.

Help Bob determine the maximum profit he can obtain by selling all n n n buns.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1t104) — the number of test cases. The description of the test cases follows.

The only line of each test case contains three integers n n n, a a a, and b b b ( 1 ≤ n , a , b ≤ 1 0 9 1 \le n, a, b \le 10^9 1n,a,b109) — the number of buns, the usual price of a bun, and the price of the first bun to be sold at a modified price.

Output

For each test case, output a single integer — the maximum profit that Bob can obtain.

Example

Example

input
7
4 4 5
5 5 9
10 10 5
5 5 11
1000000000 1000000000 1000000000
1000000000 1000000000 1
1000 1 1000
output
17
35
100
45
1000000000000000000
1000000000000000000
500500

Note

In the first test case, it is optimal for Bob to choose k = 1 k = 1 k=1. Then he will sell one bun for 5 5 5 coins, and three buns at the usual price for 4 4 4 coins each. Then the profit will be 5 + 4 + 4 + 4 = 17 5 + 4 + 4 + 4 = 17 5+4+4+4=17 coins.

In the second test case, it is optimal for Bob to choose k = 5 k = 5 k=5. Then he will sell all the buns at the modified price and obtain a profit of 9 + 8 + 7 + 6 + 5 = 35 9 + 8 + 7 + 6 + 5 = 35 9+8+7+6+5=35 coins.

In the third test case, it is optimal for Bob to choose k = 0 k = 0 k=0. Then he will sell all the buns at the usual price and obtain a profit of 10 ⋅ 10 = 100 10 \cdot 10 = 100 1010=100 coins.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;void solve() {int n, a, b;cin >> n >> a >> b;int k1 = max(min(b - a, n), 0ll), k2 = max(min(b - a + 1, n), 0ll);cout << max((2 * b - k1 + 1) * k1 / 2 + (n - k1) * a, (2 * b - k2 + 1) * k2 / 2 + (n - k2) * a) << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

C. Manhattan Permutations

Problem Statement

Let’s call the Manhattan value of a permutation † ^{\dagger} p p p the value of the expression ∣ p 1 − 1 ∣ + ∣ p 2 − 2 ∣ + … + ∣ p n − n ∣ |p_1 - 1| + |p_2 - 2| + \ldots + |p_n - n| p11∣+p22∣++pnn.

For example, for the permutation [ 1 , 2 , 3 ] [1, 2, 3] [1,2,3], the Manhattan value is ∣ 1 − 1 ∣ + ∣ 2 − 2 ∣ + ∣ 3 − 3 ∣ = 0 |1 - 1| + |2 - 2| + |3 - 3| = 0 ∣11∣+∣22∣+∣33∣=0, and for the permutation [ 3 , 1 , 2 ] [3, 1, 2] [3,1,2], the Manhattan value is ∣ 3 − 1 ∣ + ∣ 1 − 2 ∣ + ∣ 2 − 3 ∣ = 2 + 1 + 1 = 4 |3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4 ∣31∣+∣12∣+∣23∣=2+1+1=4.

You are given integers n n n and k k k. Find a permutation p p p of length n n n such that its Manhattan value is equal to k k k, or determine that no such permutation exists.

† ^{\dagger} A permutation of length n n n is an array consisting of n n n distinct integers from 1 1 1 to n n n in arbitrary order. For example, [ 2 , 3 , 1 , 5 , 4 ] [2,3,1,5,4] [2,3,1,5,4] is a permutation, but [ 1 , 2 , 2 ] [1,2,2] [1,2,2] is not a permutation ( 2 2 2 appears twice in the array), and [ 1 , 3 , 4 ] [1,3,4] [1,3,4] is also not a permutation ( n = 3 n=3 n=3 but there is 4 4 4 in the array).

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^{4} 1t104) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers n n n and k k k ( 1 ≤ n ≤ 2 ⋅ 1 0 5 , 0 ≤ k ≤ 1 0 12 1 \le n \le 2 \cdot 10^{5}, 0 \le k \le 10^{12} 1n2105,0k1012) — the length of the permutation and the required Manhattan value.

It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^{5} 2105.

Output

For each test case, if there is no suitable permutation, output “No”. Otherwise, in the first line, output “Yes”, and in the second line, output n n n distinct integers p 1 , p 2 , … , p n p_1, p_2, \ldots, p_n p1,p2,,pn ( 1 ≤ p i ≤ n 1 \le p_i \le n 1pin) — a suitable permutation.

If there are multiple solutions, output any of them.

You can output the answer in any case (for example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as a positive answer).

Example

input
8
3 4
4 5
7 0
1 1000000000000
8 14
112 777
5 12
5 2
output
Yes
3 1 2
No
Yes
1 2 3 4 5 6 7
No
Yes
8 2 3 4 5 6 1 7
No
Yes
5 4 3 1 2
Yes
2 1 3 4 5

Note

In the first test case, the permutation [ 3 , 1 , 2 ] [3, 1, 2] [3,1,2] is suitable, its Manhattan value is ∣ 3 − 1 ∣ + ∣ 1 − 2 ∣ + ∣ 2 − 3 ∣ = 2 + 1 + 1 = 4 |3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4 ∣31∣+∣12∣+∣23∣=2+1+1=4.

In the second test case, it can be proven that there is no permutation of length 4 4 4 with a Manhattan value of 5 5 5.

In the third test case, the permutation [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] [1,2,3,4,5,6,7] [1,2,3,4,5,6,7] is suitable, its Manhattan value is ∣ 1 − 1 ∣ + ∣ 2 − 2 ∣ + ∣ 3 − 3 ∣ + ∣ 4 − 4 ∣ + ∣ 5 − 5 ∣ + ∣ 6 − 6 ∣ + ∣ 7 − 7 ∣ = 0 |1-1|+|2-2|+|3-3|+|4-4|+|5-5|+|6-6|+|7-7|=0 ∣11∣+∣22∣+∣33∣+∣44∣+∣55∣+∣66∣+∣77∣=0.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;void solve() {int n, k;cin >> n >> k;if (n * n / 2 < k || k & 1) {cout << "No" << endl;return;}cout << "Yes" << endl;std::vector<int> p(n + 1);int cnt = (n * n / 2 - k) / ((n + 1 >> 1) * 2), pos = ((n * n / 2 - k) % ((n + 1 >> 1) * 2)) / 2;for (int i = 1; i <= cnt; i ++)p[i] = i;for (int i = cnt + 1, j = n / 2 + 1; i <= cnt + (n + 1 >> 1); i ++, j ++)p[i] = j;for (int i = cnt + (n + 1 >> 1) + 1, j = cnt + 1; i <= n; i ++, j ++)p[i] = j;for (int i = cnt + (n + 1 >> 1) + 1, j = pos; j; j --, i --)swap(p[i], p[i - 1]);for (int i = 1; i <= n; i ++)cout << p[i] << " ";cout << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

D. Elections

Problem Statement

Elections are taking place in Berland. There are n n n candidates participating in the elections, numbered from 1 1 1 to n n n. The i i i-th candidate has a i a_i ai fans who will vote for him. Additionally, there are c c c people who are undecided about their favorite candidate, let’s call them undecided. Undecided people will vote for the candidate with the lowest number.

The candidate who receives the maximum number of votes wins the elections, and if multiple candidates receive the same maximum number of votes, the candidate with the lowest number among them wins.

You found these elections too boring and predictable, so you decided to exclude some candidates from them. If you do not allow candidate number i i i to participate in the elections, all a i a_i ai of his fans will become undecided, and will vote for the candidate with the lowest number.

You are curious to find, for each i i i from 1 1 1 to n n n, the minimum number of candidates that need to be excluded from the elections for candidate number i i i to win the elections.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 2 ⋅ 1 0 4 1 \leq t \leq 2 \cdot 10^4 1t2104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n n n and c c c ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1n2105, 0 ≤ c ≤ 1 0 9 0 \le c \le 10^9 0c109) — the number of candidates in the elections and the number of undecided people.

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an ( 0 ≤ a i ≤ 1 0 9 0 \le a_i \le 10^9 0ai109) — the number of fans for each candidate.

It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105.

Output

For each test case, output n n n integers, the i i i-th of which should be equal to the minimum number of candidates that need to be excluded from the elections for candidate number i i i to win.

Example

Example

input
5
3 1
2 0 3
2 3
0 10
5 3
5 4 3 2 1
4 5
3 10 7 1
6 0
2 2 2 3 3 3
output
0 1 2
1 0
0 1 2 3 4
1 0 2 3
1 1 2 0 4 5

Note

In the first test case:

  • If all candidates are allowed, candidate number 1 1 1 will receive 3 3 3 votes ( 1 1 1 undecided person will vote for him), candidate number 2 2 2 will receive 0 0 0 votes, and candidate number 3 3 3 will receive 3 3 3 votes. Therefore, candidate number 1 1 1 wins (he received the same number of votes as candidate 3 3 3, but his number is lower), so the answer for him is 0 0 0.
  • If candidate number 1 1 1 is not allowed, his 2 2 2 fans will become undecided. Then candidate number 2 2 2 will receive 3 3 3 votes ( 3 3 3 undecided people will vote for him) and candidate number 3 3 3 will receive 3 3 3 votes. Therefore, candidate number 2 2 2 wins (he received the same number of votes as candidate 3 3 3, but his number is lower), so the answer for him is 1 1 1.
  • If candidates with numbers 1 1 1 and 2 2 2 are not allowed, candidate number 3 3 3 wins, so the answer for him is 2 2 2.

In the second test case, candidate number 1 1 1 will win if candidate number 2 2 2 is not allowed to participate.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;void solve() {int n, c;cin >> n >> c;std::vector<int> a(n);int mx = 0, p;for (int i = 0; i < n; i ++) {cin >> a[i];if (a[i] > mx) mx = a[i], p = i;}int sum = 0;for (int i = 0; i < n; i ++) {if (p == 0 && i == 0 || i == p && a[0] + c < a[i]) cout << 0 << " ";else if (sum + c + a[i] >= mx) cout << i << " ";else cout << i + 1 << " ";sum += a[i];}cout << endl;
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

E. Computing Machine

Problem Statement

Sasha has two binary strings s s s and t t t of the same length n n n, consisting of the characters 0 and 1.

There is also a computing machine that can perform two types of operations on binary strings a a a and b b b of the same length k k k:

  1. If a i = a i + 2 = a_{i} = a_{i + 2} = ai=ai+2= 0, then you can assign b i + 1 : = b_{i + 1} := bi+1:= 1 ( 1 ≤ i ≤ k − 2 1 \le i \le k - 2 1ik2).
  2. If b i = b i + 2 = b_{i} = b_{i + 2} = bi=bi+2= 1, then you can assign a i + 1 : = a_{i + 1} := ai+1:= 1 ( 1 ≤ i ≤ k − 2 1 \le i \le k - 2 1ik2).

Sasha became interested in the following: if we consider the string a = s l s l + 1 … s r a=s_ls_{l+1}\ldots s_r a=slsl+1sr and the string b = t l t l + 1 … t r b=t_lt_{l+1}\ldots t_r b=tltl+1tr, what is the maximum number of 1 characters in the string a a a that can be obtained using the computing machine. Since Sasha is very curious but lazy, it is up to you to answer this question for several pairs ( l i , r i ) (l_i, r_i) (li,ri) that interest him.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^{4} 1t104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n n n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 1 \le n \le 2 \cdot 10^5 1n2105) — the length of the strings s s s and t t t.

The second line of each test case contains a binary string s s s of length n n n, consisting of the characters 0 and 1.

The third line of each test case contains a binary string t t t of length n n n, consisting of the characters 0 and 1.

The fourth line of each test case contains a single integer q q q ( 1 ≤ q ≤ 2 ⋅ 1 0 5 1 \le q \le 2 \cdot 10^5 1q2105) — the number of queries.

The i i i-th of the following lines contains two integers l i l_{i} li and r i r_{i} ri ( 1 ≤ l i ≤ r i ≤ n 1 \le l_{i} \le r_{i} \le n 1lirin) — the boundaries of the i i i-th pair of substrings that interest Sasha.

It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105 and the sum of q q q over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105.

Output

For each test case, output q q q integers — the answers to all queries.

Example

input
3
4
1111
0000
2
1 2
2 4
4
1010
1101
2
1 3
1 4
6
010101
011010
5
2 3
1 6
2 5
4 4
3 6
output
2
3
2
3
1
4
3
1
2

Note

In the first test case:

  • In the first query, a = a = a= 11, so the maximum number of 1 characters is 2 2 2.
  • In the second query, a = a = a= 111, so the maximum number of 1 characters is 3 3 3.

In the second test case:

  • In the first query, a = a = a= 101 and b = b = b= 110. No operations can be performed, so the maximum number of 1 characters is 2 2 2.
  • In the second query, a = a = a= 1010 and b = b = b= 1101. Since a 2 = a 4 = a_2 = a_4 = a2=a4= 0, we can assign b 3 : = b_3 := b3:= 1. Now b 1 = b 3 = b_1 = b_3 = b1=b3= 1, so we can assign a 2 : = a_2 := a2:= 1. The string a a a becomes 1110, so the maximum number of 1 characters is 3 3 3.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 2e5 + 10;int n, q, cnt;
string a, b, c, d;
int tot[N];int work(int l, int r) {string s = b, t = a;for (int i = l; i <= r - 2; i ++)if (a[i] == a[i + 2] && a[i] == '0') s[i + 1] = '1';for (int i = l; i <= r - 2; i ++)if (s[i] == s[i + 2] && s[i] == '1') t[i + 1] = '1';int res = 0;for (int i = l; i <= r; i ++)res += t[i] == '1';return res;
}void solve() {cin >> n >> a >> b >> q;a = ' ' + a, b = ' ' + b, c = a, d = b;for (int i = 1; i <= n - 2; i ++)if (c[i] == c[i + 2] && c[i] == '0') d[i + 1] = '1';for (int i = 1; i <= n - 2; i ++)if (d[i] == d[i + 2] && d[i] == '1') c[i + 1] = '1';for (int i = 1; i <= n; i ++)tot[i] = tot[i - 1] + (c[i] == '1');while (q -- ) {int l, r;cin >> l >> r, cnt ++;if (r - l + 1 <= 4) {cout << work(l, r) << endl;continue;}int res = tot[r] - tot[l - 1];if (d[l - 1] == d[l + 1] && d[l - 1] == '1' && a[l] == '0') res --;if (l + 1 <= n && a[l - 1] == '0' && a[l + 1] == '0' && b[l] == '0') {if (l + 2 <= n && d[l + 2] == '1') res --;}if (r + 1 <= n && d[r - 1] == d[r + 1] && d[r + 1] == '1' && a[r] == '0') res --;if (r + 1 <= n && a[r - 1] == '0' && a[r + 1] == '0' && b[r] == '0') {if (r - 2 >= 1 && d[r - 2] == '1') res --;}cout << res << endl;}
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int dt;cin >> dt;while (dt --)solve();return 0;
}

F. Large Graph

Problem Statement

Given an array a a a of length n n n. Let’s construct a square matrix b b b of size n × n n \times n n×n, in which the i i i-th row contains the array a a a cyclically shifted to the right by ( i − 1 ) (i - 1) (i1). For example, for the array a = [ 3 , 4 , 5 ] a = [3, 4, 5] a=[3,4,5], the obtained matrix is

b = [ 3 4 5 5 3 4 4 5 3 ] b = \begin{bmatrix} 3 & 4 & 5 \\ 5 & 3 & 4 \\ 4 & 5 & 3 \end{bmatrix} b= 354435543

Let’s construct the following graph:

  • The graph contains n 2 n^2 n2 vertices, each of which corresponds to one of the elements of the matrix. Let’s denote the vertex corresponding to the element b i , j b_{i, j} bi,j as ( i , j ) (i, j) (i,j).
  • We will draw an edge between vertices ( i 1 , j 1 ) (i_1, j_1) (i1,j1) and ( i 2 , j 2 ) (i_2, j_2) (i2,j2) if ∣ i 1 − i 2 ∣ + ∣ j 1 − j 2 ∣ ≤ k |i_1 - i_2| + |j_1 - j_2| \le k i1i2+j1j2k and gcd ⁡ ( b i 1 , j 1 , b i 2 , j 2 ) > 1 \gcd(b_{i_1, j_1}, b_{i_2, j_2}) > 1 gcd(bi1,j1,bi2,j2)>1, where gcd ⁡ ( x , y ) \gcd(x, y) gcd(x,y) denotes the greatest common divisor of integers x x x and y y y.

Your task is to calculate the number of connected components † ^{\dagger} in the obtained graph.

† ^{\dagger} A connected component of a graph is a set of vertices in which any vertex is reachable from any other via edges, and adding any other vertex to the set violates this rule.

Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 5 1 \leq t \leq 10^5 1t105) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n n n and k k k ( 2 ≤ n ≤ 1 0 6 2 \le n \le 10^6 2n106, 2 ≤ k ≤ 2 ⋅ 1 0 6 2 \le k \le 2 \cdot 10^6 2k2106) — the length of the array and the parameter k k k.

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1,a2,,an ( 1 ≤ a i ≤ 1 0 6 1 \le a_i \le 10^6 1ai106) — the elements of the array a a a.

It is guaranteed that the sum of n n n over all test cases does not exceed 1 0 6 10^6 106.

Output

For each test case, output a single integer — the number of connected components in the obtained graph.

Example

input
6
3 3
3 4 5
3 3
3 4 9
3 2
3 4 9
2 2
2 8
5 3
8 27 5 4 3
4 10
2 2 2 2
output
3
2
3
1
4
1

Note

In the first test case, the matrix b b b is given in the statement. The first connected component contains the vertices ( 1 , 1 ) (1, 1) (1,1), ( 2 , 2 ) (2, 2) (2,2), and ( 3 , 3 ) (3, 3) (3,3). The second connected component contains the vertices ( 1 , 2 ) (1, 2) (1,2), ( 2 , 3 ) (2, 3) (2,3), and ( 3 , 1 ) (3, 1) (3,1). The third connected component contains the vertices ( 1 , 3 ) (1, 3) (1,3), ( 2 , 1 ) (2, 1) (2,1), and ( 3 , 2 ) (3, 2) (3,2). Thus, the graph has 3 3 3 connected components.

In the second test case, the following matrix is obtained:

b = [ 3 4 9 9 3 4 4 9 3 ] b = \begin{bmatrix} 3 & 4 & 9 \\ 9 & 3 & 4 \\ 4 & 9 & 3 \end{bmatrix} b= 394439943

The first connected component contains all vertices corresponding to elements with values 3 3 3 and 9 9 9. The second connected component contains all vertices corresponding to elements with the value 4 4 4.

In the fourth test case, all vertices are in one connected component.

Solution

具体见文后视频。


Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int N = 2e6 + 10;int n, m, k;
int a[N], b[N], p[N];
int st[N], prime[N], idx;
std::vector<int> fact[N], pos[N];int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}
void Euler(int lim) {st[1] = 1;for (int i = 2; i <= lim; i ++) {if (!st[i]) prime[ ++ idx] = i;for (int j = 1; prime[j] * i <= lim; j ++) {st[prime[j] * i] = 1;if (i % prime[j] == 0) break;}}
}
void solve() {cin >> n >> k;for (int i = 1; i <= n; i ++)cin >> a[i];m = 0;for (int i = 2; i <= n; i ++) b[ ++ m] = a[i];b[ ++ m] = a[1];for (int i = 2; i <= n; i ++) b[ ++ m] = a[i];int res = m;set<int> avl;for (int i = 1; i <= m; i ++) {p[i] = i, res += (b[i] == 1) * ((m + 1 >> 1) - abs(i - (m + 1 >> 1)) - 1);for (auto v : fact[b[i]])if (!st[v])pos[v].push_back(i), avl.insert(v);}for (auto i : avl)for (int j = 1; j < pos[i].size(); j ++) {if (pos[i][j] - pos[i][j - 1] <= k) {int pa = find(pos[i][j]), pb = find(pos[i][j - 1]);if (pa != pb) {p[pa] = pb;res --;}}}cout << res << endl;for (int i = 1; i <= m; i ++)for (auto v : fact[b[i]])pos[v].clear();
}signed main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);for (int i = 1; i < (N >> 1); i ++)for (int j = i; j < (N >> 1); j += i)fact[j].push_back(i);Euler(N >> 1);int dt;cin >> dt;while (dt --) solve();return 0;
}

视频讲解

Codeforces Round 953 (Div. 2)(A ~ F 题讲解)


最后祝大家早日在这里插入图片描述

这篇关于Codeforces Round 953 (Div. 2 ABCDEF题) 视频讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1074500

相关文章

流媒体平台/视频监控/安防视频汇聚EasyCVR播放暂停后视频画面黑屏是什么原因?

视频智能分析/视频监控/安防监控综合管理系统EasyCVR视频汇聚融合平台,是TSINGSEE青犀视频垂直深耕音视频流媒体技术、AI智能技术领域的杰出成果。该平台以其强大的视频处理、汇聚与融合能力,在构建全栈视频监控系统中展现出了独特的优势。视频监控管理系统EasyCVR平台内置了强大的视频解码、转码、压缩等技术,能够处理多种视频流格式,并以多种格式(RTMP、RTSP、HTTP-FLV、WebS

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

《x86汇编语言:从实模式到保护模式》视频来了

《x86汇编语言:从实模式到保护模式》视频来了 很多朋友留言,说我的专栏《x86汇编语言:从实模式到保护模式》写得很详细,还有的朋友希望我能写得更细,最好是覆盖全书的所有章节。 毕竟我不是作者,只有作者的解读才是最权威的。 当初我学习这本书的时候,只能靠自己摸索,网上搜不到什么好资源。 如果你正在学这本书或者汇编语言,那你有福气了。 本书作者李忠老师,以此书为蓝本,录制了全套视频。 试

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室