当前位置:网站首页>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 !
边栏推荐
- 苏打粉是什么?
- Idea push project to code cloud
- Raspberry pie 4B arm platform aarch64 PIP installation pytorch
- iNFTnews | 喝茶送虚拟股票?浅析奈雪的茶“发币”
- What if the DataGrid cannot see the table after connecting to the database
- [node] differences among NPM, yarn and pnpm
- 二分查找(折半查找)
- arcpy. SpatialJoin_ Analysis spatial connection analysis
- The problem of configuring opencv in qt5.13.2 is solved in detail
- And let's play dynamic proxy (extreme depth version)
猜你喜欢
剑指 Offer 56 数组中数字出现的次数(异或)
611. 有效三角形的个数
Docker installs MySQL and uses Navicat to connect
Intelligent target detection 59 -- detailed explanation of pytoch focal loss and its implementation in yolov4
并查集理论讲解和代码实现
What if the DataGrid cannot see the table after connecting to the database
Powermanagerservice (I) - initialization
C learning notes
Matrix and TMB package version issues in R
(tool use) how to make the system automatically match and associate to database fields by importing MySQL from idea and writing SQL statements
随机推荐
Altimeter data knowledge point 2
Basic series of SHEL script (I) variables
Do you choose pandas or SQL for the top 1 of data analysis in your mind?
【无标题】
Negative number storage and type conversion in programs
Reading literature sorting 20220104
What if the DataGrid cannot see the table after connecting to the database
What is sodium hydroxide?
docker安装mysql并使用navicat连接
Graduation thesis project local deployment practice
Unity UGUI不同的UI面板或者UI之间如何进行坐标匹配和变换
golang定时器使用踩的坑:定时器每天执行一次
[vscode] prohibit the pylance plug-in from automatically adding import
list. files: List the Files in a Directory/Folder
And let's play dynamic proxy (extreme depth version)
Microservice registry Nacos introduction
Jenkins reported an error. Illegal character: '\ufeff'. Class, interface or enum are required
Course learning accumulation ppt
【idea】Could not autowire. No beans of xxx type found
氫氧化鈉是什麼?