当前位置:网站首页>Daily Practice:Codeforces Round #794 (Div. 2)(A~D)
Daily Practice:Codeforces Round #794 (Div. 2)(A~D)
2022-07-05 07:23:00 【_ dawn°】
VP*n,, Mainly this one cf Time is too dark hhhhh
A. Everything Everywhere All But One
give n Number , choice n-1 Number , And replace each of these numbers with the average of these numbers , Ask whether you can make the numbers in the array equal through several operations .
Ideas : Since you have to choose n-1 Change the number to the average , Then meet this n-1 The average of the number is the average of the entire array , And the unselected number is this average . Pay attention to double Keep accuracy .
A Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=55;
int t,n;
double a[N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
double sum=0;
std::map<double,int>mp;
for(int i=1;i<=n;i++){
std::cin>>a[i];
mp[a[i]]++;
sum+=a[i];
}
std::cout<<(mp[sum/n]?"YES":"NO")<<'\n';
}
return 0;
}
B. Odd Subarrays
Give the array , How to segment an array , Make as many inverse pairs of subarrays as possible odd .
Ideas : greedy , Since it satisfies the inverse order, the pair is odd , As long as there is an inverse pair , Then divide it .
AC Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int t,n;
int a[N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
int ans=0;
for(int i=1;i<n;i++){
if(a[i]>a[i+1]) ans++,i++;
}
std::cout<<ans<<'\n';
}
return 0;
}
os: At first, because the array is smaller T A hair , cause sb. to die of anger QWQ
C. Circular Local MiniMax
Give a sequence of numbers , Whether it can be satisfied by rearranging the elements in the array : End to end , Any element is greater than or less than two adjacent numbers .
Ideas : First , When the number of array elements is odd , It cannot be constructed ; Then sort the array , Divided into two parts , One large and one small are placed crosswise , Finally, it is judged that the conditions are met .
AC Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int t,n;
int a[N],ans[N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>t;
while(t--){
std::cin>>n;
memset(ans,0,sizeof(ans));
int cnt=0;
for(int i=1;i<=n;i++){
std::cin>>a[i];
}
if(n&1){
std::cout<<"NO"<<'\n';
continue;
}
std::sort(a+1,a+1+n);
std::vector<int>vecs,vecl;
for(int i=1;i<=n/2;i++){
vecs.push_back(a[i]);
}
for(int i=n/2+1;i<=n;i++){
vecl.push_back(a[i]);
}
for(int i=0;i<n/2;i++){
ans[++cnt]=vecs[i];
ans[++cnt]=vecl[i];
}
bool flag=true;
ans[0]=ans[cnt];
ans[++cnt]=ans[1];
for(int i=1;i<=n;i++){
if(!(ans[i]>ans[i+1]&&ans[i]>ans[i-1]||ans[i]<ans[i+1]&&ans[i]<ans[i-1])){
flag=false;
break;
}
}
if(!flag){
std::cout<<"NO"<<'\n';
continue;
}
std::cout<<"YES"<<'\n';
for(int i=1;i<=n;i++){
std::cout<<ans[i]<<" \n"[i==n];
}
}
return 0;
}
os: Very unexpected , This time C It's not difficult
D. Linguistics
give A,B,AB,BA The number of four elements , Give the string s, Judge whether the given element can form the string .
Ideas : Study Big guy's idea !( This guy actually fought this scene cf,tqlllllll)
First, if the given element A and B The number of does not match , That must be impossible ; The data range is large , We can't enumerate directly , Then we can adopt this idea : Find the minimum number of elements of each kind , Compare them separately .
Let's use double pointers to intercept something like ABAB,BABA Such substrings that are different from each other . about A and AB, We can work out the minimum required quantity together , and B and BA It's the same calculation .
There are only two kinds of even length substrings , namely ABAB and BABA, about BABA In this way , No need AB Elements , and ABAB By reducing a pair of separate A and B To become BABA Similar to substring . Only if there is no single pair A and B, It needs to len/2 individual AB, Then we can use pairs of separate A and B To minimize AB Dosage , Work out AB Minimum dosage . For odd length substrings , We can reduce A or B Make it into the above two seed strings , Use the same treatment .
AC Code:
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
int T;
int a[6];
std::string s;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>T;
while(T--){
for(int i=1;i<=4;i++){
std::cin>>a[i];
}
std::cin>>s;
int cntA=0,cntB=0;
int len=s.length();
for(int i=0;i<len;i++){
if(s[i]=='A') cntA++;
else cntB++;
}
if(!(cntA==a[1]+a[3]+a[4]&&cntB==a[2]+a[3]+a[4])){
std::cout<<"NO"<<'\n';
continue;
}
int cntab=0,cntba=0;
std::vector<int>ab,ba;
for(int i=0;i<len;i++){
int j=i;
while(j+1<len&&s[j+1]!=s[j]) j++;
if(j-i+1&1){
if(s[i]=='A') a[1]--;
else a[2]--;
}
else{
int t=j-i+1>>1;
if(s[i]=='A') ab.push_back(t),cntab+=t;
else ba.push_back(t),cntba+=t;
}
i=j;
}
if(a[1]<0||a[2]<0){
std::cout<<"NO"<<'\n';
continue;
}
int t=std::min(a[1],a[2]);
std::sort(ab.begin(),ab.end());
while(!ab.empty()&&t){
t--;
cntab-=ab.back();
ab.pop_back();
}
if(cntab>a[3]){
std::cout<<"NO"<<'\n';
continue;
}
t=std::min(a[1],a[2]);
std::sort(ba.begin(),ba.end());
while(!ba.empty()&&t){
t--;
cntba-=ba.back();
ba.pop_back();
}
if(cntba>a[4]){
std::cout<<"NO"<<'\n';
continue;
}
std::cout<<"YES"<<'\n';
}
return 0;
}
os: This D It's still hard to think ,, You have to understand the idea of looking at guys for a long time
If there is any mistake, please advise , thank you !
边栏推荐
- Matrix and TMB package version issues in R
- Word import literature -mendeley
- CADD课程学习(5)-- 构建靶点已知的化合结构(ChemDraw)
- NPM and package common commands
- Matrix keyboard scan (keil5)
- Basic operation of external interrupt (keil5)
- 【Node】npm、yarn、pnpm 区别
- [framework] multi learner
- R language learning notes 1
- 现在有html文件,和用vs制作的mvc(连接了数据库),怎么两个相连?
猜你喜欢
When jupyter notebook is encountered, erroe appears in the name and is not output after running, but an empty line of code is added downward, and [] is empty
IPage can display data normally, but total is always equal to 0
window navicat连接阿里云服务器mysql步骤及常见问题
Rough notes of C language (2) -- constants
PHY drive commissioning --- mdio/mdc interface Clause 22 and 45 (I)
Rough notes of C language (1)
Mipi interface, DVP interface and CSI interface of camera
Delayqueue usage and scenarios of delay queue
Ros2 - function package (VI)
Basic series of SHEL script (III) for while loop
随机推荐
Clickhouse database installation deployment and remote IP access
Basic series of SHEL script (III) for while loop
Netease to B, soft outside, hard in
Simple operation with independent keys (hey, a little fancy) (keil5)
[vscode] search using regular expressions
Typescript get timestamp
Batch convert txt to excel format
[idea] efficient plug-in save actions to improve your work efficiency
Ggplot2 drawing learning notes in R
npm install -g/--save/--save-dev的区别
公安基础知识--fb
Target detection series - detailed explanation of the principle of fast r-cnn
Matrix and TMB package version issues in R
Docker installs MySQL and uses Navicat to connect
Using GEE plug-in in QGIS
Unconventional ending disconnected from the target VM, address: '127.0.0.1:62635', transport: 'socket‘
Database SQL practice 3. Find the current salary details of the current leaders of each department and their corresponding department number Dept_ no
Solve tensorfow GPU modulenotfounderror: no module named 'tensorflow_ core. estimator‘
Implementation of one-dimensional convolutional neural network CNN based on FPGA (VIII) implementation of activation layer
What if the DataGrid cannot see the table after connecting to the database