刷题记录(Codeforces Round 947 （Div. 1 + Div. 2）B,C题)和Codeforces Round 948 （Div. 2）B题
一.B. 378QAQ and Mocha's Array
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????=????⋅????.
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.
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).
No
Yes
Yes
No
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
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.
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.
For each test case, output the maximum value of the number.
1
4
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
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“。
字符串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????已获得。
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();
}
}