codeforces round 655 div2

Codeforces Round #655 (Div. 2)

A. Omkar and Completion

A题
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You have been blessed as a child of Omkar. To express your gratitude, please solve this problem for Omkar!

An array 𝑎 of length 𝑛 is called complete if all elements are positive and don’t exceed 1000, and for all indices 𝑥,𝑦,𝑧 (1≤𝑥,𝑦,𝑧≤𝑛), 𝑎𝑥+𝑎𝑦≠𝑎𝑧 (not necessarily distinct).

You are given one integer 𝑛. Please find any complete array of length 𝑛. It is guaranteed that under given constraints such array exists.

Input
Each test contains multiple test cases. The first line contains 𝑡 (1≤𝑡≤1000) — the number of test cases. Description of the test cases follows.

The only line of each test case contains one integer 𝑛 (1≤𝑛≤1000).

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 1000.

Output
For each test case, print a complete array on a single line. All elements have to be integers between 1 and 1000 and for all indices 𝑥,𝑦,𝑧 (1≤𝑥,𝑦,𝑧≤𝑛) (not necessarily distinct), 𝑎𝑥+𝑎𝑦≠𝑎𝑧 must hold.

If multiple solutions exist, you may print any.

Example
inputCopy
2
5
4
outputCopy
1 5 3 77 12
384 384 44 44
Note
It can be shown that the outputs above are valid for each test case. For example, 44+44≠384.

Below are some examples of arrays that are NOT complete for the 1st test case:

[1,2,3,4,5]

Notice that 𝑎1+𝑎2=𝑎3.

[1,3000,1,300,1]

Notice that 𝑎2=3000>1000.

题意:给你给t组测试数据,一个数组长度为n使得任意两个数的和不会在数组中出现。

题解:显然数组元素都相同就可以了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main()
{
int n,t;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cout<<1<<" ";
cout<<endl;

}
return 0;
}

B. Omkar and Last Class of Math

B题
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
In Omkar’s last class of math, he learned about the least common multiple, or 𝐿𝐶𝑀. 𝐿𝐶𝑀(𝑎,𝑏) is the smallest positive integer 𝑥 which is divisible by both 𝑎 and 𝑏.

Omkar, having a laudably curious mind, immediately thought of a problem involving the 𝐿𝐶𝑀 operation: given an integer 𝑛, find positive integers 𝑎 and 𝑏 such that 𝑎+𝑏=𝑛 and 𝐿𝐶𝑀(𝑎,𝑏) is the minimum value possible.

Can you help Omkar solve his ludicrously challenging math problem?

Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤10). Description of the test cases follows.

Each test case consists of a single integer 𝑛 (2≤𝑛≤109).

Output
For each test case, output two positive integers 𝑎 and 𝑏, such that 𝑎+𝑏=𝑛 and 𝐿𝐶𝑀(𝑎,𝑏) is the minimum possible.

Example
inputCopy
3
4
6
9
outputCopy
2 2
3 3
3 6
Note
For the first test case, the numbers we can choose are 1,3 or 2,2. 𝐿𝐶𝑀(1,3)=3 and 𝐿𝐶𝑀(2,2)=2, so we output 2 2.

For the second test case, the numbers we can choose are 1,5, 2,4, or 3,3. 𝐿𝐶𝑀(1,5)=5, 𝐿𝐶𝑀(2,4)=4, and 𝐿𝐶𝑀(3,3)=3, so we output 3 3.

For the third test case, 𝐿𝐶𝑀(3,6)=6. It can be shown that there are no other pairs of numbers which sum to 9 that have a lower 𝐿𝐶𝑀.

题意:给你t组测试数据,给你个数n,你需要输出满足a+b=n,且a和b的最大公约数最小。输出a和b

题解:
计算n的约数,从2开始,如果存在,输出n/i,n-n/i;即可,如果不存在,说明为质数输出1和n-1即可。特判2.

代码:

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
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int flag=0;
if(n==2)
{
cout<<"1 1"<<endl;
continue;
}
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
flag=1;
int ans1=n/i;
int ans2=n-n/i;
cout<<ans1<<" "<<ans2<<endl;
break;
}
}
if(!flag)
cout<<1<<" "<<n-1<<endl;
}
return 0;
}

C. Omkar and Baseball

C题
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across 𝑛 sessions follow the identity permutation (ie. in the first game he scores 1 point, in the second game he scores 2 points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up!

Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on [1,2,3] can yield [3,1,2] but it cannot yield [3,2,1] since the 2 is in the same position.

Given a permutation of 𝑛 integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn’t exceed 1018.

An array 𝑎 is a subarray of an array 𝑏 if 𝑎 can be obtained from 𝑏 by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤100). Description of the test cases follows.

The first line of each test case contains integer 𝑛 (1≤𝑛≤2⋅105) — the length of the given permutation.

The second line of each test case contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛) — the initial permutation.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 2⋅105.

Output
For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.

Example
inputCopy
2
5
1 2 3 4 5
7
3 2 4 5 1 6 7
outputCopy
0
2
Note
In the first permutation, it is already sorted so no exchanges are needed.

It can be shown that you need at least 2 exchanges to sort the second permutation.

[3,2,4,5,1,6,7]
Perform special exchange on range (1,5)

[4,1,2,3,5,6,7]
Perform special exchange on range (1,4)

[1,2,3,4,5,6,7]

题意:给你个序列,每次你可以选择一段子序列,里面元素互换。使得顺序为从小到大。

题解:最小需要几次互换。顺序好了的0次,当前后顺序好了,中间顺序为全为乱,不含已经相同的值时,1次。当所有都不含相同值是也是一次。当有相同值,中间,也有不同值时,两次。

代码:

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<iostream>
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
int flag1=0,flag2=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
/* if(a[i]==i)
{
flag1=1;
}
else if(a[i]!=i)
{
flag2=1;
}*/
}
int pos1=1;
int pos2=n;
for(int i=1;i<=n;i++)
{
if(a[i]==i)
{
pos1=i;
}
else
break;
}
for(int i=n;i>=1;i--)
{
if(a[i]==i)
{
pos2=i;
}
else
break;
}
for(int i=pos1+1;i<=pos2-1;i++)
{
if(a[i]==i)
{
flag1=1;
}
else if(a[i]!=i)
{
flag2=1;
}
}
if(flag1==1 && flag2==1)
{
cout<<2<<endl;
}
else if((flag1==1 && flag2==0) || pos1>pos2)
{
cout<<0<<endl;
}
else
cout<<1<<endl;
}
return 0;
}
-------------本文结束感谢您这么好看还看我的文章-------------