当前位置:网站首页>Codeforces Global Round 19 ABC
Codeforces Global Round 19 ABC
2022-07-05 01:37:00 【Vijurria】
The main idea of the topic : Given a length of n Array of a, We can subscript 1~n-1 Select a number from flag So it can be divided into two sections , And for this [1,flag] [flag,n] The values of the two intervals are sorted in non descending order ( Not strictly ascending ).
If the whole sequence is not sorted in ascending order, it will be output YES, Otherwise NO.
input
3 3 2 2 1 4 3 1 2 1 5 1 2 2 4 4output
YES YES NO
It is found that as long as a number exists, it is not in its place , It cannot be transformed into a non descending sequence .( Because its operability is extremely strong , Subscript exists in 1~n-1 In the range of )
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<cstring>
#include<cstdlib>
#include<map>
#include<algorithm>
using namespace std;
int a[200200],b[200200];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(a+1,a+1+n);
bool flag=false;
for(int i=1;i<=n;i++)
{
if(a[i]!=b[i]) flag=true;// Non descending order
}
if(flag==false) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
The main idea of the topic : Given a size of n Array of a, Find the sum of the values of all its sub segments .
Its value is defined as the number of segments + Of all segments MEX The sum of the .(mex: The smallest natural number that has never appeared )
If you can delete a few from the beginning ( Maybe zero or all ) Elements and delete a few from the end ( Maybe zero or all ) Elements come from y get x, The array x It's an array y Subsegment .
input
4 2 1 2 3 2 0 1 4 2 0 5 1 5 0 1 1 0 1output
4 14 26 48
The first one involved in the calculation in the code for loop , Obviously, what is easy to see is the sum of interval lengths ! Such as [1 3 5 4 2], Divided into multiple sub segments, that is, a single length has 5 individual , Double length ones have 4 individual , There are three 3 individual , Four have 2 individual , There are five 1 individual ··· By analogy, the length of other intervals .
If you know the length of the interval, you should find the length of each interval mex 了 . It's amazing , Look at the picture get
In fact, why are you looking for 0 Just do it ? Because if not 0 When the number of , It may not be able to find smaller numbers or need larger numbers to fill in the range it participates in , So it doesn't make much sense , But individually, they are 0, It doesn't matter whether you add it or not . So we just need to see 0 And the number of intervals it participates in .
The number of intervals is equal to the number !!!
【 Why was it the same idea when I wrote last night, but I didn't see these figures 0 How to find the way ???( Autistic )】
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<string>
#include<cstring>
#include<cstdlib>
#include<map>
#include<algorithm>
using namespace std;
int a[200200];
int main()
{
//cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int sum=0;
for(int i=1;i<=n;i++)
sum+=i*(n-i+1);
//cout<<sum<<endl;
for(int i=1;i<=n;i++)
{
if(a[i]==0) sum+=i*(n-i+1);
}
cout<<sum<<endl;
}
return 0;
}
The main idea of the topic : Given a length of n Sequence a, Let's subscript 2~n-1 All the numbers of are moved to the subscript 1 Or subscript n The place of . The rules of moving are :Select(i,j,k): choice 3 An index 1≤i<j<k≤n, Make No j Piles contain at least 2 A stone , Then he started from the pile j Remove from 2 A stone , And put a stone into i In the pile , Put a stone in k In the pile .
Ask us : Move all the stones to the pile 1 And heaps n What is the minimum number of operations required ? Or determine whether it is impossible .
It is impossible to output -1.
input
4 5 1 2 2 3 6 3 1 3 1 3 1 2 1 4 3 1 1 2output
4 -1 1 -1
Quite apart from the a1 and an, see 2~n-1 In order to know the number of operation steps , If it's an even number, just 2, Odd numbers 2 Round up again . Here we can get the minimum number of steps .
that -1 What do you think of the situation ? Even numbers can be divided, so don't think , If the number is odd, the title is given j Must be in >=2 To participate in mobile , So it is certain that when the middle row is all 1 He couldn't move when he was ; From the example given, we can see that when there is n==3 And when the middle is an odd number, it is actually equivalent to having one in the middle 1 He can't move .
The rest of the numbers can be moved to both sides by more or less moving times .
#include<iostream>
#include<cmath>
#include<vector>
#include<string>
#include<cstring>
#include<cstdlib>
#include<map>
#include<algorithm>
using namespace std;
int a[200200];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
long long int t;
cin>>t;
while(t--)
{
long long int n,sum=0;
cin>>n;
for(long long int i=1;i<=n;i++)
{
cin>>a[i];
if(i>=2&&i<=n-1)
{
if(a[i]%2==1) sum+=(a[i]+1)/2;
else sum+=a[i]/2;
}
}
long long int sum1=0;
for(long long int i=2;i<=n-1;i++)
{
if(a[i]==1) sum1++;
}
if((n==3&&a[2]%2==1)||sum1==n-2) cout<<"-1"<<endl;
else cout<<sum<<endl;
}
return 0;
}
There is a hole here that it needs to be opened LL, Otherwise wa hey
————————————
D ah !dp ah , Come back another day ...
边栏推荐
- Package What is the function of JSON file? What do the inside ^ angle brackets and ~ tilde mean?
- Outlook: always prompt for user password
- Discrete mathematics: propositional symbolization of predicate logic
- Win:使用 PowerShell 检查无线信号的强弱
- PHP 约瑟夫环问题
- Roads and routes -- dfs+topsort+dijkstra+ mapping
- C basic knowledge review (Part 3 of 4)
- Complex, complicated and numerous: illustration of seven types of code coupling
- [wave modeling 1] theoretical analysis and MATLAB simulation of wave modeling
- Basic operations of database and table ----- delete index
猜你喜欢
[development of large e-commerce projects] performance pressure test - Optimization - impact of middleware on performance -40
MATLB | multi micro grid and distributed energy trading
Phpstrom setting function annotation description
Yyds dry goods inventory kubernetes management business configuration methods? (08)
One plus six brushes into Kali nethunter
小程序容器技术与物联网 IoT 可以碰撞出什么样的火花
[OpenGL learning notes 8] texture
Redis(1)之Redis简介
微信小程序:独立后台带分销功能月老办事处交友盲盒
Wechat applet: Xingxiu UI v1.5 WordPress system information resources blog download applet wechat QQ dual end source code support WordPress secondary classification loading animation optimization
随机推荐
Change the background color of a pop-up dialog
The perfect car for successful people: BMW X7! Superior performance, excellent comfort and safety
Common bit operation skills of C speech
Nebula importer data import practice
Global and Chinese market of optical densitometers 2022-2028: Research Report on technology, participants, trends, market size and share
Complex, complicated and numerous: illustration of seven types of code coupling
Global and Chinese markets of radiation linear accelerators 2022-2028: Research Report on technology, participants, trends, market size and share
线上故障突突突?如何紧急诊断、排查与恢复
Arbitrum: two-dimensional cost
Armv8-a programming guide MMU (3)
Huawei machine test question: longest continuous subsequence
Kibana installation and configuration
Game 280 of leetcode week
MATLB|多微电网及分布式能源交易
Global and Chinese market of portable CNC cutting machines 2022-2028: Research Report on technology, participants, trends, market size and share
Unified blog writing environment
Database postragesq BSD authentication
[FPGA tutorial case 9] design and implementation of clock manager based on vivado core
ROS command line tool
Win:将一般用户添加到 Local Admins 组中