刷題記錄(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();}
}
