当前位置:网站首页>Codeforces Global Round 19
Codeforces Global Round 19
2022-07-06 09:29:00 【狗蛋儿l】
A. Sorting Parts
You have an array a of length n. You can exactly once select an integer len between 1 and n−1 inclusively, and then sort in non-decreasing order the prefix of the array of length len and the suffix of the array of length n−len
For example, if the array is a=[3,1,4,5,2], and you choose len=2, then after that the array will be equal to [1,3,2,4,5].
Could it be that after performing this operation, the array will not be sorted in non-decreasing order?
Input
There are several test cases in the input data. The first line contains a single integer t (1≤t≤100) — the number of test cases. This is followed by the test cases description.
The first line of each test case contains one integer n
(2≤n≤104) — the length of the array.
The second line of the test case contains a sequence of integers a1,a2,…,an (1≤ai≤109) — the array elements.
It is guaranteed that the sum of nover all test cases does not exceed 104.
Output
For each test case of input data, output “YES” (without quotes), if the array may be not sorted in non-decreasing order, output “NO” (without quotes) otherwise. You can output each letter in any case (uppercase or lowercase).
Example
Input
3
3
2 2 1
4
3 1 2 1
5
1 2 2 4 4
Output
YES
YES
NO
Note
In the first test case, it’s possible to select len=1, then after operation, the array will not be sorted in non-decreasing order and will be equal to [2,1,2].
In the second test case, it’s possible to select len=3, then after operation, the array will not be sorted in non-decreasing order and will be equal to [1,2,3,1].
In the third test case, the array will be sorted in non-decreasing order for every possible len.
思路:
大概就是判断这个数组是不是有序,有序就YES,无序就NO
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
vector<int> a(n);
for (auto& u : a)
cin >> u;
if (!is_sorted(a.begin(), a.end()))
cout << "YES\n";
else
cout << "NO\n";
}
}
B. MEX and Array
Let there be an array b1,b2,…,bk. Let there be a partition of this array into segments [l1;r1],[l2;r2],…,[lc;rc], where l1=1, rc=k, and for any 2≤i≤c holds that ri−1+1=li. In other words, each element of the array belongs to exactly one segment.
Let’s define the cost of a partition as c+∑i=1cmex({bli,bli+1,…,bri}),where mex of a set of numbers S is the smallest non-negative integer that does not occur in the set S. In other words, the cost of a partition is the number of segments plus the sum of MEX over all segments. Let’s define the value of an array b1,b2,…,bk as the maximum possible cost over all partitions of this array.You are given an array a of size n. Find the sum of values of all its subsegments.An array x is a subsegment of an array y if x can be obtained from y by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Input
The input contains several test cases. The first line contains one integer t
(1≤t≤30) — the number of test cases.
The first line for each test case contains one integer n
(1≤n≤100) — the length of the array.
The second line contains a sequence of integers a1,a2,…,an
(0≤ai≤109) — the array elements.
It is guaranteed that the sum of the values n
over all test cases does not exceed 100.
Output
For each test case print a single integer — the answer to the problem.
Example
Input
4
2
1 2
3
2 0 1
4
2 0 5 1
5
0 1 1 0 1
Output
4
14
26
48
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
vector<int> a(n);
for (auto& u : a)
cin >> u;
int ans = 0;
for (int i = 0; i < n; i++) {
ans += (i + 1) * (n - i);
if (a[i] == 0)
ans += (i + 1) * (n - i);
}
cout << ans << '\n';
}
}
C. Andrew and Stones
Andrew has n piles with stones. The i-th pile contains ai stones. He wants to make his table clean so he decided to put every stone either to the 1-st or the n-th pile.
Andrew can perform the following operation any number of times: choose 3 indices 1≤i<j<k≤n, such that the j-th pile contains at least 2 stones, then he takes 2 stones from the pile j and puts one stone into pile i and one stone into pile k.
Tell Andrew what is the minimum number of operations needed to move all the stones to piles 1and n, or determine if it’s impossible.
Input
The input contains several test cases. The first line contains one integer t
(1≤t≤10000) — the number of test cases.
The first line for each test case contains one integer n
(3≤n≤105) — the length of the array.
The second line contains a sequence of integers a1,a2,…,an
(1≤ai≤109) — the array elements.
It is guaranteed that the sum of the values n
over all test cases does not exceed 105.
Output
For each test case print the minimum number of operations needed to move stones to piles 1 and n, or print −1 if it’s impossible.
Input
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2
Output
4
-1
1
-1
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
if (*max_element(a.begin() + 1, a.end() - 1) == 1 || (n == 3 && a[1] % 2 == 1)) {
cout << "-1\n";
return;
}
long long answer = 0;
for (int i = 1; i < n - 1; i++)
answer += (a[i] + 1) / 2;
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tests;
cin >> tests;
while (tests--)
solve();
}
边栏推荐
- 解决Intel12代酷睿CPU单线程调度问题(二)
- Problem - 1646C. Factorials and Powers of Two - Codeforces
- It is forbidden to trigger onchange in antd upload beforeupload
- QT实现圆角窗口
- QT simulates mouse events and realizes clicking, double clicking, moving and dragging
- (lightoj - 1369) answering queries (thinking)
- 分享一个在树莓派运行dash应用的实例。
- 去掉input聚焦时的边框
- Problem - 922D、Robot Vacuum Cleaner - Codeforces
- Codeforces Round #798 (Div. 2)A~D
猜你喜欢
Codeforces Round #799 (Div. 4)A~H
pytorch提取骨架(可微)
(POJ - 3685) matrix (two sets and two parts)
1605. Sum the feasible matrix for a given row and column
860. Lemonade change
SF smart logistics Campus Technology Challenge (no T4)
Remove the border when input is focused
969. Pancake sorting
新手必会的静态站点生成器——Gridsome
本地可视化工具连接阿里云centOS服务器的redis
随机推荐
(lightoj - 1236) pairs forming LCM (prime unique decomposition theorem)
第5章 消费者组详解
Useeffect, triggered when function components are mounted and unloaded
Educational Codeforces Round 130 (Rated for Div. 2)A~C
Hbuilder X格式化快捷键设置
969. Pancake sorting
第2章 HFDS的Shell操作
QT realizes window topping, topping state switching, and multi window topping priority relationship
Market trend report, technical innovation and market forecast of double-sided foam tape in China
Research Report on market supply and demand and strategy of Chinese table lamp industry
(lightoj - 1349) Aladdin and the optimal invitation (greed)
QT按钮点击切换QLineEdit焦点(含代码)
< li> dot style list style type
useEffect,函数组件挂载和卸载时触发
Installation and configuration of MariaDB
Codeforces Round #803 (Div. 2)A~C
875. Leetcode, a banana lover
QT simulates mouse events and realizes clicking, double clicking, moving and dragging
Problem - 922D、Robot Vacuum Cleaner - Codeforces
Acwing: Game 58 of the week