5月29日 CodeForces 构造题刷题集锦

Problem - 1828A - Codeforces

ranting 800

题面翻译

构造一个长度为 $n$ 的序列 $a$ 满足以下条件。

  • 对于每个元素 $a_i$ 满足 $a_i \le 1000$。
  • 对于每个元素 $a_i$ 满足 $a_i \equiv 0 \pmod i$。即每个元素 $a_i$ 能被 $i$ 整除。
  • 满足 $\sum_{i = 1}^{n} a_i \equiv 0 \pmod n$。即所有元素之和能被 $n$ 整除。

$n \leq 200$。

题目描述

You are given a positive integer $ n $ . Please find an array $ a_1, a_2, \ldots, a_n $ that is perfect.

A perfect array $ a_1, a_2, \ldots, a_n $ satisfies the following criteria:

  • $ 1 \le a_i \le 1000 $ for all $ 1 \le i \le n $ .
  • $ a_i $ is divisible by $ i $ for all $ 1 \le i \le n $ .
  • $ a_1 + a_2 + \ldots + a_n $ is divisible by $ n $ .

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 200 $ ). The description of the test cases follows.

The only line of each test case contains a single positive integer $ n $ ( $ 1 \le n \le 200 $ ) — the length of the array $ a $ .

输出格式

For each test case, output an array $ a_1, a_2, \ldots, a_n $ that is perfect.

We can show that an answer always exists. If there are multiple solutions, print any.

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
4
5
6
7
1
2 4
1 2 3
2 8 6 4
3 4 9 4 5
1 10 18 8 5 36
3 6 21 24 10 6 14

提示

In the third test case:

  • $ a_1 = 1 $ is divisible by $ 1 $ .
  • $ a_2 = 2 $ is divisible by $ 2 $ .
  • $ a_3 = 3 $ is divisible by $ 3 $ .
  • $ a_1 + a_2 + a_3 = 1 + 2 + 3 = 6 $ is divisible by $ 3 $ .

In the fifth test case:

  • $ a_1 = 3 $ is divisible by $ 1 $ .
  • $ a_2 = 4 $ is divisible by $ 2 $ .
  • $ a_3 = 9 $ is divisible by $ 3 $ .
  • $ a_4 = 4 $ is divisible by $ 4 $ .
  • $ a_5 = 5 $ is divisible by $ 5 $ .
  • $ a_1 + a_2 + a_3 + a_4 + a_5 = 3 + 4 + 9 + 4 + 5 = 25 $ is divisible by $ 5 $ .

题解

题目解析

这道题我们需要构造一个数列.关于这个数列的构建方法我确实没有想到.

我们尝试构造一个等差数列,当 $n$ 为奇数时:

显然可以构建成功,那么当 $n$ 为偶数时:

显然构建出来了.

AC代码

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 <iostream>
#include <string>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef long long ll;

int main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		if(n&1){
			for(int i=1;i<=n;i++)
				cout << i << " ";
		}else{
			for(int i=1;i<=n;i++)
				cout << 2*i << " ";
		}
		cout << endl;
	}
	return 0;
}

Problem - 1823A - Codeforces

rating 800

题面翻译

构建一个长度为 $n$ 的数组，数组元素只能为 $1$ 或者 $-1$。

定义数组每满足一对 $a_{i} \cdot a_{j} = 1$ $( 1 \leq i < j \leq n )$ 为有 $1$ 个特征 $A$。求数组是否能构成出满足刚好 $k$ 个特征 $A$。如果能构成该数组输出 YES 并给出构造数组。反之只输出 NO。

题目描述

Consider an array $ a_1, a_2, \dots, a_n $ consisting of numbers $ 1 $ and $ -1 $ . Define $ A $ -characteristic of this array as a number of pairs of indices $ 1 \le i < j \le n $ , such that $ a_i \cdot a_j = 1 $ .

Find any array $ a $ with given length $ n $ with $ A $ -characteristic equal to the given value $ k $ .

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows.

The only line of each test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 100 $ ; $ 0 \le k \le \frac{(n-1) n}{2} $ ) — the length of required array and required $ A $ -characteristic.

输出格式

For each test case, if there is no array $ a $ with given $ A $ -characteristic $ k $ , print NO.

Otherwise, print YES and $ n $ numbers $ 1 $ and $ -1 $ , which form the required array $ a $ . If there are multiple answers, print any of them.

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
YES
1 -1 
YES
1 1 
YES
1 -1 1 
NO
YES
1 1 1 
YES
-1 1 -1 1 1 
NO

提示

In the first test case, there is only one pair of different elements in the array, and their product is $ a_1 \cdot a_2 = -1 \neq 1 $ , hence its $ A $ -characteristic is $ 0 $ .

In the second test case, there is only one pair of different elements in the array, and their product is $ a_1 \cdot a_2 = 1 $ , hence its $ A $ -characteristic is $ 1 $ .

In the third test case, there are three pairs of different elements in the array, and their product are: $ a_1 \cdot a_2 = -1 $ , $ a_1 \cdot a_3 = 1 $ , $ a_2 \cdot a_3 = -1 $ , hence its $ A $ -characteristic is $ 1 $ .

In the fourth test case, we can show, that there is no array with length $ 3 $ , which $ A $ -characteristic is $ 2 $ .

题解

题目解析

没想到构造方法,看了题解.

找规律:当区间内含有 $n$ 个 $1$ 时,根据组合数学的知识,我们可以从 $n$ 个 $1$ 中选出 $2$ 个,也就是 $C^2_n=\frac{n(n-1)}{2}$ ,同理 $-1$ 的情况也是一样的.

那么我们仅需判断 $1$ 在 $n$ 个数列中的个数, $0\sim n-1$ 因为其个数为 $0,n$ 的结果是相同的:

AC代码

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 <iostream>
#include <string>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef long long ll;

int main(){
	int T;
	cin >> T;
	while(T--){
		int n,k,i,j;
		cin >> n >> k;
		for(i=0;i<=n;i++) if(i*(i-1)/2+(n-i)*(n-i-1)/2==k) break;
		if(i >= n) cout << "NO" << endl;
		else{
			cout << "YES" << endl;
			for(int j=1;j<=i;j++) cout << 1 << " ";
			for(int j=i+1;j<=n;j++) cout << -1 << " ";
			cout << endl;
		}
	}
	return 0;
}

Problem - 1818B - Codeforces

rating 900

题面翻译

题目描述

给定一个整数 $n$。

你需要构造一个一个长度为 $n$ 的排列 $A$，使得对于任意一对 $l,r$（$1\le l<r\le n$），都满足 $A_l+A_{l+1}+\dots+A_r$ 不可以被 $r-l+1$ 整除。

输入格式

输入一个 $t(1\le t\le 100)$ 表示数据组数。

每组数据一行一个整数 $n(1\le n\le100)$，即排列的长度。

输出格式

对于每组数据，若所求排列不存在，输出 -1，否则输出任意一个合法的排列。

题目描述

You’re given a positive integer $ n $ .

Find a permutation $ a_1, a_2, \dots, a_n $ such that for any $ 1 \leq l < r \leq n $ , the sum $ a_l + a_{l+1} + \dots + a_r $ is not divisible by $ r-l+1 $ .

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

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). Description of the test cases follows.

The first line of each test case contain a single integer $ n $ ( $ 1 \leq n \leq 100 $ ) — the size of the desired permutation.

输出格式

For each test case, if there is no such permutation print $ -1 $ .

Otherwise, print $ n $ distinct integers $ p_1, p_{2}, \dots, p_n $ ( $ 1 \leq p_i \leq n $ ) — a permutation satisfying the condition described in the statement.

If there are multiple solutions, print any.

样例 #1

样例输入 #1

1
2
3
4
3
1
2
3

样例输出 #1

1
2
3
1
1 2
-1

提示

In the first example, there are no valid pairs of $ l < r $ , meaning that the condition is true for all such pairs.

In the second example, the only valid pair is $ l=1 $ and $ r=2 $ , for which $ a_1 + a_2 = 1+2=3 $ is not divisible by $ r-l+1=2 $ .

in the third example, for $ l=1 $ and $ r=3 $ the sum $ a_1+a_2+a_3 $ is always $ 6 $ , which is divisible by $ 3 $ .

题解

题目解析

一道构造题,题目和A-characteristic有异曲同工之妙.同样的,也是分为个数奇偶讨论.

当 $n(n>1)$ 为奇数时:

显然,这样是无法达到条件的.不过特殊的 $n=1$ 倒是可以.那么我们现在讨论 $n$ 为偶数的情况,我们现在构造 $[2,1,4,3,\cdots,n,n-1]$ 的数列:

  • 当 $l$ 与 $r$ 的奇偶性不相同时:

  • 当 $l$ 与 $r$ 的奇偶性相同时:

    • 当 $l$ 与 $r$ 都为偶数时:

    • 当 $l$ 与 $r$ 都为奇数时:

    无论时哪种情况,我们都可以得到:

AC代码

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
#include <iostream>
#include <string>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef long long ll;

int main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		if(n == 1){
			cout << 1 << endl;
			continue;
		}
		if(n&1){
			cout << -1 << endl;
		}else{
			for(int i=1,j=2;j<=n;i+=2,j+=2){
				cout << j << " " << i << " ";
			}
			cout << endl;
		}
	}
	return 0;
}

Problem - 1806B - Codeforces

rating 900

题面翻译

给定长度为 $n$ 的序列 $a$，规定 $a$ 的权值为 $\text{mex}\{a_1+a_2,a_2+a_3,\cdots,a_{n-1}+a_n\}$（$\text{mex}$ 是指一个非负整数序列中最小的未在序列中出现的整数）。现在 $a$ 可以任意排列，求 $a$ 的最小权值。

Translated by @_JYqwq_

题目描述

You are given an array $ a $ of length $ n $ . The score of $ a $ is the MEX $ ^{\dagger} $ of $ [a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n] $ . Find the minimum score of $ a $ if you are allowed to rearrange elements of $ a $ in any order. Note that you are not required to construct the array $ a $ that achieves the minimum score.

$ ^{\dagger} $ The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

  • The MEX of $ [2,2,1] $ is $ 0 $ , because $ 0 $ does not belong to the array.
  • The MEX of $ [3,1,0,1] $ is $ 2 $ , because $ 0 $ and $ 1 $ belong to the array, but $ 2 $ does not.
  • The MEX of $ [0,3,1,2] $ is $ 4 $ because $ 0 $ , $ 1 $ , $ 2 $ , and $ 3 $ belong to the array, but $ 4 $ does not.

输入格式

The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 2\le n\le 2\cdot10^5 $ ).

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 2\cdot 10^5 $ ).

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

输出格式

For each test case, output the minimum score of $ a $ after rearranging the elements of $ a $ in any order.

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
1
0
1

提示

In the first test case, it is optimal to rearrange $ a $ as $ [0,0] $ , the score of this array is the MEX of $ [0+0]=[0] $ , which is $ 1 $ .

In the second test case, it is optimal to rearrange $ a $ as $ [0,1,0] $ , the score of this array is the MEX of $ [0+1,1+0]=[1,1] $ , which is $ 0 $ .

题解

题目解析

同样也是一道构造体,需要分情况讨论.看一下他给的样例,稍微分析一下可以得到第一个出发点:当答案等于 $0$ 的情况.

  • 当 $0$ 的个数少于等于总个数的一半时,那么通过交错搭配可以得到这个答案.

那么答案除了 $1$ 以外还有其他答案吗?答案是肯定的,其还有一中可能就是 $2$ , $[0,1]$ 搭配肯定为 $2$ 也就是说:

  • 当这个数列中除了数字 $0$ 剩下的都是数字 $1$ 并且不满足上一个条件.那么,我们就可以得到这个答案.
  • 剩下的当然就是 $1$ 了,直接else输出.

AC代码

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
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#define endl "\n"
using namespace std;
typedef long long ll;

int a[200010];

int main(){
	int T;
	cin >> T;
	while(T--){
		int n,cunt0=0,cunt1=0;
		cin >> n;
		for(int i=1;i<=n;i++){
			cin >> a[i];
			if(a[i] == 0)
				cunt0++;
			if(a[i] == 1)
				cunt1++;
		}
		if(cunt0 <= (n+1>>1)){
			cout << 0 << endl;
		}else{
			if(cunt1 == n - cunt0 && cunt1 != 0){
				cout << 2 << endl;
			}else{
				cout << 1 << endl;
			}
		}
	}
	return 0;
}