当前位置:网站首页>Codeforces Global Round 19(A~D)
Codeforces Global Round 19(A~D)
2022-07-06 07:39:00 【Woodenman Du】
The ten thousand year supplementary question is strange ~
A. https://codeforces.com/contest/1637/problem/A
The question :
Given a length of n Array of numbers , from 1 To n-1 Choose any number as len
Then check before len Is the sequence of elements and the subsequent sequence of elements in ascending order , If not, sort them separately
Now ask if you can sort the given array
analysis : In fact, it is to check whether the array is in ascending order
AC Code:
#include <iostream>
using namespace std;
int t,n;
int main()
{
cin >>t;
while(t--)
{
cin >>n;
int temp = -1,x,ans = 1;
for(int i = 1; i <= n; i++){
cin >>x;
if(temp > x) ans = 0;
temp = x;
}
if(ans) cout <<"NO" <<endl;
else cout <<"YES" <<endl;
}
return 0;
}
B. https://codeforces.com/contest/1637
The question :
Given length is n Array of
Definition : Each subsequence is divided into k paragraph , Then the value of this subsequence is k+MEX( Subsequence elements ).
Find the maximum value of the sum of the values of all subsequences
analysis :
Last time cf Of MEX The problem made me choke , It took me a long time to understand this question , Can't understand English ...
First :
To be the most valuable , It is best to divide each element into a segment
So if an element is 0, The value of contribution is 1 +MEX0 = 2;
If it's other elements , The value of contribution is 1 + 0 = 1
Then think about the code :
My last step requires the sum of the values of all subsequences , That's many times 1 and 2 Add up , To avoid double counting , You can directly input a[i] Change to the value it can contribute .
As for the final optimization :
Since it is all subsequences , Then the number of occurrences of each element has a fixed relationship with its position , According to the conclusion, it is not impossible to sum directly when inputting , That is to say sum += Contribution value * Number of occurrences , This will eliminate n^3 Subsequence traversal
The code will not write ~
C. https://codeforces.com/contest/1637/problem/C
The question :
Given a length of n Array of , To operate : selected i<j<k, a[j]>=2, a[j] reduce 2,a[i] and a[k] Add one
ask : At least how many times such operations can turn all array elements except the beginning and end into 0, If it cannot be achieved, output -1
analysis :
First think about the simplest
There is an even number in the middle , Then I can i,k Point to a[1] and a[n], And then pass by a[j]/2 This operation will a[j] Turn into 0
If it's an odd number , Then I'll use it as i perhaps k, Make it even first .
in other words , Remove the leading and trailing elements , The number of times each element contributes is : Odd number ,(a[i]+1)/2; even numbers a[i]/2;
After derivation, we can get res = (sum + cnt) /2; sum For elements other than the first and last elements and ,cnt It is an odd number
A special case
All the numbers in the middle are 1, Unable to operate , Output -1
Only 3 Elements , The element in the middle is an odd number , No matter how you operate odd numbers or odd numbers , Output -1
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,cnt,sum;
int a[100010];
int main(){
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >>t;
while(t--){
sum = cnt = 0;
cin >>n;
bool ans = true;
for(int i=1;i<=n;++i) cin >>a[i];
//3 Number and the middle number is odd
if( n==3 && (a[2]&1) ){
cout <<-1 <<endl; continue;
}
for(int i=2;i<n;++i){
sum += a[i];
if(a[i]&1) cnt++;
if(a[i]>1) ans = false;
}
// The middle numbers are all 1
if(ans) { cout <<-1 <<endl; continue; }
cout <<(sum + cnt)/2 <<endl;
}
return 0;
}
D. https://codeforces.com/contest/1637/problem/D
The question :
Two lengths are given n Array of , You can perform any number of exchanges ai and bi The operation of , Finally, we should minimize the result of the formula given by the topic , Output minimum result
analysis :
Observe the given formula :
In other words, the problem becomes : After exchanging elements , Minimize the sum of the squares of the respective elements of the two arrays
So you need to list all the elements and possible values , Then find the minimum , Equivalent to a knapsack problem , I write recursion and it explodes directly
Stone or not ?
Problems like this can't be written normally at my level , Membrane guy ~
AC Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,res,res1,sum;
//sum Record the overall elements and
//res Record the final result ,res1 Record (n-2)... Value
int a[101],b[101];
int main(void)
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >>t;
while(t--)
{
res = 1e9,sum = 0,res1 = 0;
//cin
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
res1 += a[i]*a[i]*(n-2);
sum += a[i];
}
for(int i = 1; i <= n; i++){
cin >>b[i];
res1 += b[i]*b[i]*(n-2);
sum += b[i];
}
bool dp[n+1][sum+1];
memset(dp,false,sizeof(dp));
dp[0][0] = true;
// Enumerate all possible elements and
for(int i = 1; i <= n; i++){
for(int j = 1; j <= sum; j++){
if(j >= a[i] & dp[i-1][ j-a[i] ]) dp[i][j] = true;
if(j >= b[i] & dp[i-1][ j-b[i] ]) dp[i][j] = true;
}
}
// Find the formula 2 minimum value
for(int i = 1; i <= sum; i++){
if(dp[n][i]) res = min(res, i*i + (sum-i)*(sum-i));
}
cout <<res + res1 <<endl;
}
return 0;
}
边栏推荐
- [MySQL learning notes 32] mvcc
- TypeScript 可索引类型
- Summary of Digital IC design written examination questions (I)
- Basics of reptile - Scratch reptile
- Ali's redis interview question is too difficult, isn't it? I was pressed on the ground and rubbed
- edge浏览器 路径获得
- Select all the lines with a symbol in word and change them to titles
- Three treasures of leeks and Chinese men's football team
- If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
- Ble of Jerry [chapter]
猜你喜欢
The way to learn go (I) the basic introduction of go to the first HelloWorld
Solution: intelligent site intelligent inspection scheme video monitoring system
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
链表面试题(图文详解)
Opencv learning notes 8 -- answer sheet recognition
Basics of reptile - Scratch reptile
How Navicat imports MySQL scripts
合规、高效,加快药企数字化转型,全新打造药企文档资源中心
解决方案:智慧工地智能巡检方案视频监控系统
TS 类型体操 之 extends,Equal,Alike 使用场景和实现对比
随机推荐
octomap averageNodeColor函数说明
If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
Three no resumes in the software testing industry. What does the enterprise use to recruit you? Shichendahai's resume
Transformer principle and code elaboration
The way to learn go (II) basic types, variables and constants
HTTP cache, forced cache, negotiated cache
Pre knowledge reserve of TS type gymnastics to become an excellent TS gymnastics master
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Generator Foundation
http缓存,强制缓存,协商缓存
OpenJudge NOI 2.1 1661:Bomb Game
Bit operation XOR
Opencv learning notes 8 -- answer sheet recognition
继电反馈PID控制器参数自整定
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
洛谷P4127 [AHOI2009]同类分布 题解
Fundamentals of C language 9: Functions
[MySQL learning notes 29] trigger
CF1036C Classy Numbers 题解
[1. Delphi foundation] 1 Introduction to Delphi Programming