5.30 学习总

刷题记录(Codeforces Round 947 （Div. 1 + Div. 2）B,C题)和Codeforces Round 948 （Div. 2）B题

一.B. 378QAQ and Mocha's Array

B. 378QAQ and Mocha's Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Mocha likes arrays, so before her departure, 378QAQ gave her an array a𝑎 consisting of n𝑛 positive integers as a gift.

Mocha thinks that a𝑎 is beautiful if there exist two numbers i𝑖 and j𝑗 (1≤i,j≤n1≤𝑖,𝑗≤𝑛, i≠j𝑖≠𝑗) such that for all k𝑘 (1≤k≤n1≤𝑘≤𝑛), ak𝑎𝑘 is divisible†† by either ai𝑎𝑖 or aj𝑎𝑗.

Determine whether a𝑎 is beautiful.

†† x𝑥 is divisible by y𝑦 if there exists an integer z𝑧 such that x=y⋅z𝑥=𝑦⋅𝑧.

Input

Each test contains multiple test cases. The first line contains the number of test cases t𝑡 (1≤t≤5001≤𝑡≤500). The description of the test cases follows.

The first line of each test case contains a single integer n𝑛 (3≤n≤1053≤𝑛≤105) — the length of the array a𝑎.

The second line of each test case contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (1≤ai≤1091≤𝑎𝑖≤109) — the elements of the array a𝑎.

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

Output

For each test case, output "Yes" if array a𝑎 is beautiful, and output "No" otherwise.

You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).

Example

input

Copy

7 3 8

7 1 9 3 5

4 12 2 6 3

7 49 9 3 1000000000

output

Copy

No
Yes
Yes
No

Note

In the first test case, any two numbers in the array are coprime, so the answer is "No".

In the second test case, we can pick i=2𝑖=2 and j=1𝑗=1. Since every number in the array is divisible by ai=1𝑎𝑖=1, the answer is "Yes".

In the third test case, we can pick i=3𝑖=3 and j=5𝑗=5. 22 and 44 is divisible by ai=2𝑎𝑖=2 while 33, 66 and 1212 is divisible by aj=3𝑎𝑗=3, so the answer is "Yes".

题意：题目要求我们找到两个数，使得整个数组的每个数都可以被两个数至少一个整除。

思路：因为是整除关系，小数一定不能被大数整除，所以从最小数下手。

找到的第一个数一定是数组的最小数，第二个数为能被第一个数整除的最小数。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	ll n;
	cin>>n;
	vector<ll>a(n);
	for(ll &i:a)
	{
		cin>>i;
	}
	if(n<=2)
	{
		cout<<"Yes\n";
		return;
	}
	bool ans=true;
	sort(a.begin(),a.end());
	ll b,c;
	b=a[0];
	int f=0,f1=0;
	for(int i=1;i<n;i++){
		if(a[i]!=a[i-1]) 
		{
			f=1;
		}
		if(a[i]%b!=0&&f==1)
		{
			f1=1;
			c=a[i];
			break;
		}
	}
	if(f==0||f1==0)
	{
		cout<<"Yes\n";
		return ;
	}
	for(ll i=2;i<n;i++){
		if(a[i]%b!=0&&a[i]%c!=0) 
		{
			ans=false;
			break;
		}
	}
	cout<<(ans?"Yes\n":"No\n");
}
int main()
{
	int t;
	cin>>t;
	
	while(t--){
		solve();
	}
	return 0;
}

二.C. Chamo and Mocha's Array

C. Chamo and Mocha's Array

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Mocha likes arrays, so before her departure, Chamo gave her an array a𝑎 consisting of n𝑛 positive integers as a gift.

Mocha doesn't like arrays containing different numbers, so Mocha decides to use magic to change the array. Mocha can perform the following three-step operation some (possibly, zero) times:

Choose indices l𝑙 and r𝑟 (1≤l<r≤n1≤𝑙<𝑟≤𝑛)
Let x𝑥 be the median†† of the subarray [al,al+1,…,ar][𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟]
Set all values al,al+1,…,ar𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟 to x𝑥

Suppose a=[1,2,3,4,5]𝑎=[1,2,3,4,5] initially:

If Mocha chooses (l,r)=(3,4)(𝑙,𝑟)=(3,4) in the first operation, then x=3𝑥=3, the array will be changed into a=[1,2,3,3,5]𝑎=[1,2,3,3,5].
If Mocha chooses (l,r)=(1,3)(𝑙,𝑟)=(1,3) in the first operation, then x=2𝑥=2, the array will be changed into a=[2,2,2,4,5]𝑎=[2,2,2,4,5].

Mocha will perform the operation until the array contains only the same number. Mocha wants to know what is the maximum possible value of this number.

†† The median in an array b𝑏 of length m𝑚 is an element that occupies position number ⌊m+12⌋⌊𝑚+12⌋ after we sort the elements in non-decreasing order. For example, the median of [3,1,4,1,5][3,1,4,1,5] is 33 and the median of [5,25,20,24][5,25,20,24] is 2020.

Input

Each test contains multiple test cases. The first line contains the number of test cases t𝑡 (1≤t≤5001≤𝑡≤500). The description of the test cases follows.

The first line of each test case contains a single integer n𝑛 (2≤n≤1052≤𝑛≤105) — the length of the array a𝑎.

The second line of each test case contains n𝑛 integers a1,a2,…,an𝑎1,𝑎2,…,𝑎𝑛 (1≤ai≤1091≤𝑎𝑖≤109) — the elements of the array a𝑎.

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

Output

For each test case, output the maximum value of the number.

Example

input

Copy

1 2

1 2 3 4 5

output

Copy

1
4

Note

In the first test case, a=[1,2]𝑎=[1,2]. Mocha can only choose the interval (l,r)=(1,2)(𝑙,𝑟)=(1,2). The array will be changed to a=[1,1]𝑎=[1,1]. Therefore, the answer is 11.

In the second test case, Mocha can perform the following operations:

Choose the interval (l,r)=(4,5)(𝑙,𝑟)=(4,5), then a=[1,2,3,4,4]𝑎=[1,2,3,4,4].
Choose the interval (l,r)=(3,5)(𝑙,𝑟)=(3,5), then a=[1,2,4,4,4]𝑎=[1,2,4,4,4].
Choose the interval (l,r)=(1,5)(𝑙,𝑟)=(1,5), then a=[4,4,4,4,4]𝑎=[4,4,4,4,4].

The array contains only the same number, which is 44. It can be proven that the maximum value of the final number cannot be greater than 44.

题意：对于整个数组，我们可以选择一个范围（l,r），将这个范围内的数全部变为这个范围内的中位数，可以进行多次操作或者不做操作，求最后的数组的全部元素的最大值。

思路：因为当选择的范围长度是2时，就可以将这个范围的两个数全部变为这两个数的较小值(x)，那么一定存在一个长度为3的范围内的中位数<=x。

如果整个数组的长度为2，输出较小值即可，反之，遍历数组全部长度为3的子数组，找到最大的中位数，然后输出。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
	int n;
	cin>>n;
	vector<int>a(n);
	for(int &i:a)
	cin>>i;
	if(n==2)
	{
		cout<<min(a[0],a[1])<<"\n";
		return;	
	}
	ll ans=-1;
	for(int i=0;i<n-2;i++){
		int p[3];
		p[0]=a[i];
		p[1]=a[i+1];
		p[2]=a[i+2];
		sort(p,p+3);
		ans=max(ans,(ll)p[1]);
	}
	cout<<ans<<"\n";
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		solve();
		
	}
	return 0;
}

三.B. Symmetric Encoding

B. 对称编码

每次测试的时间限制

为 2 秒

每次测试的内存限制

256 兆字节

输入

标准输入

输出

标准输出

Polycarp 有一根绳子s𝑠，由小写的拉丁字母组成。他使用以下算法对此字符串进行编码：

首先，他构造了一个新的辅助弦r𝑟，它由字符串的所有不同字母组成s𝑠，按字母顺序书写;
然后编码如下：字符串中的每个字符s𝑠替换为字符串中的对称字符r𝑟（字符串的第一个字符r𝑟将被最后一个替换，第二个被倒数第二个替换，依此类推）。

例如，对字符串进行编码s𝑠="CodeForces“的发生方式如下：

字符串r𝑟以“cdefors";
第一个字符s1𝑠1='c' 替换为的';
第二个角色s2𝑠2='o' 替换为 'e';
第三个角色s3𝑠3='d' 替换为 'r';
...
最后一个字符s10𝑠10='s“替换为”c“。

$\text{[math]}$

字符串r𝑟和替代品s𝑠="CodeForces“。

因此，对字符串进行编码的结果s𝑠="codeforces“是字符串”serofedsoc“。

编写一个执行解码的程序，即恢复原始字符串s𝑠从编码结果。

输入

第一行包含单个整数t𝑡 (1≤吨≤1041≤𝑡≤104） — 测试用例的数量。

每个测试用例的第一行包含一个整数n𝑛 (1≤N≤2⋅1051≤𝑛≤2⋅105） — 字符串的长度b𝑏.

每个测试用例的第二行都包含一个字符串b𝑏长度n𝑛，由小写拉丁字母组成 — 对原始字符串进行编码的结果s𝑠.

可以保证n𝑛在测试中的所有测试用例不超过2⋅1052⋅105.

输出

对于每个测试用例，输出字符串s𝑠从中获取编码结果b𝑏已获得。

例

输入

复制

serofedsoc

ttf

tlrhgmaoi

hnndledmnhlttin

输出

复制

codeforces
fft
algorithm
w
meetinthemiddle

#include<bits/stdc++.h>
using namespace std;
void solve()
{
	int n;
	cin>>n;
	string s,t,v;
	cin>>s;
	t=s;
	sort(t.begin(),t.end());
	
	for(int i=0;i<n;i++){
		if(t[i]!=t[i+1]) v+=t[i];
	}
	map<char,char>q;
	for(int i=0;i<v.size();i++){
		q[v[i]]=v[v.size()-1-i];
	}
	for(int i=0;i<n;i++){
		
		s[i]=q[s[i]];
	}
	cout<<s<<"\n";
}
int main()
{
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}