当前位置:网站首页>Codeforces Round #803 (Div. 2)A~C
Codeforces Round #803 (Div. 2)A~C
2022-07-06 09:28:00 【你好_Ä】
Codeforces Round #803 (Div. 2)A~C
Problem - A - Codeforces
There is an array a with n−1 integers. Let x be the bitwise XOR of all elements of the array. The number x is added to the end of the array a (now it has length n), and then the elements are shuffled.
You are given the newly formed array a. What is x? If there are multiple possible values of x, you can output any of them.
Input
The input consists of multiple test cases. The first line contains an integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer n (2≤n≤100) — the number of integers in the resulting array a.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤127) — the elements of the newly formed array a.
Additional constraint on the input: the array a is made by the process described in the statement; that is, some value of x exists.
Output
For each test case, output a single integer — the value of x, as described in the statement. If there are multiple possible values of x, output any of them.
Example
input
4
4
4 3 2 5
5
6 1 10 7 10
6
6 6 6 6 6 6
3
100 100 0
output
3
7
6
0
问题解析
题目是说有一个长度为n的数组,这数组可以有n-1个数进行xor运算后得到剩下的那一个数,让你找出数组中这个数是那个。
长度只有100,直接枚举数组中全部的数,看其他的数异或运算后能不能得到这个数。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
void solve()
{
int n;
cin >> n;
vector<int>a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
int x = 0;
for (int j = 0; j < n; j++)
{
if (j != i)x ^= a[j];
}
if (x == a[i])
{
cout << a[i] << endl;
return;
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Problem - B - Codeforces
There are n piles of sand where the i-th pile has ai blocks of sand. The i-th pile is called too tall if 1<iai−1+ai+1. That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.)
You are given an integer k. An operation consists of picking k consecutive piles of sand and adding one unit of sand to them all. Formally, pick 1≤l,r≤n such that r−l+1=k. Then for all l≤i≤r, update ai←ai+1.
What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?
Input
The input consists of multiple test cases. The first line contains an integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers n and k (3≤n≤2⋅105; 1≤k≤n) — the number of piles of sand and the size of the operation, respectively.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the sizes of the piles.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
Output
For each test case, output a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.
Example
input
3
5 2
2 9 2 4 1
4 4
1 3 2 1
3 1
1 3 1
output
2
0
1
问题解析
题目是说给你一个数组a,称a[i]>a[i-1]+a[i+1]的元素为山峰,然后有一个操作,每次可以选一个长度为k的区间,把这个区间里的元素都+1,问经过任意次操作后数组中最多能有多少个山峰元素。
如果k等于1,我们可以把任意一个元素变成山峰,但是最多只能有(n-1)/2个山峰,因为每个山峰元素的两边肯定不为山峰元素。
如果k大于1,那么我们是无法把一个非山峰元素变成山峰元素的,因为如果一个元素本身不是山峰元素,说明这个值是不大于两边元素之和的,如果k大于1,那么我们只能增大两个邻居中的一个,或者同时增大邻居和这个元素,这样都无法增大a[i]使得它大于a[i-1]+a[i+1]。所以如果k大于1,那么原数组有几个山峰元素,就是几个山峰元素。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
void solve()
{
int n, k, res = 0;
cin >> n >> k;
vector<int>a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
if (k == 1)
{
cout << (n - 1) / 2 << endl;
return;
}
for (int i = 1; i < n - 1; i++)
{
if (a[i] > a[i - 1] + a[i + 1])res++;
}
cout << res << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
Problem - C - Codeforces
You are given an array a of length n. The array is called 3SUM-closed if for all distinct indices i, j, k, the sum ai+aj+ak is an element of the array. More formally, a is 3SUM-closed if for all integers 1≤i<j<k≤n, there exists some integer 1≤l≤n such that ai+aj+ak=al.
Determine if a is 3SUM-closed.
Input
The first line contains an integer t (1≤t≤1000) — the number of test cases.
The first line of each test case contains an integer n (3≤n≤2⋅105) — the length of the array.
The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109) — the elements of the array.
It is guaranteed that the sum of n across all test cases does not exceed 2⋅105.
Output
For each test case, output “YES” (without quotes) if a is 3SUM-closed and “NO” (without quotes) otherwise.
You can output “YES” and “NO” in any case (for example, strings “yEs”, “yes” and “Yes” will be recognized as a positive response).
Example
input
4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4
output
YES
NO
YES
NO
问题解析
题目是说给你一个长度为n的数组a,只要这个数组的任意三个元素相加起来都能是这个数组的一个元素,这个数组就被称为3sum封闭,问你这个数组是否是3sum封闭的。
当数组全为0,他是满足的。
当数组除了一个数不是0,其它数都是0时,他是满足的。
当数组除了两个数不是0,其它数都是0,且这两个数相加为0时,他是满足的。
当数组没有0时,我们要讨论一下情况:
当数组中有三个正数,那么三个正数相加会得到一个更大的正数,这样就肯定不能满足。
当数组中有三个负数,那么三个负数相加会得到一个更小的负数,这样就肯定不能满足。
所以说,数组中不能有三个正数或三个负数,即数组最多是4个元素时才有可能是对的,超过这个数量就有可能错,为了方便,我们直接用一个三层for循环来判断能否满足条件即可。
其余的都是不满足的。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
void solve()
{
int n;
cin >> n ;
vector<int>v(n),ans;
for (int i = 0; i < n; i++)
{
cin >> v[i];
if (v[i] != 0)
{
ans.push_back(v[i]);
}
}
if (ans.size() <= 1)cout << "YES" << endl;
else if (ans.size() == 2)
{
if (ans[0] + ans[1] == 0)cout << "YES" << endl;
else cout << "NO" << endl;
}
else if (n < 10)
{
map<int, int>mymap;
for (int i = 0; i < n; i++)
{
mymap[v[i]] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
if (i != j && j != k && i != k)
{
if (mymap[v[i] + v[j] + v[k]] == 0)
{
cout << "NO" << endl;
return;
}
}
}
}
}
cout << "YES" << endl;
}
else cout << "NO" << endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
边栏推荐
- The most complete programming language online API document
- Information security - threat detection - detailed design of NAT log access threat detection platform
- X-Forwarded-For详解、如何获取到客户端IP
- Data storage in memory & loading into memory to make the program run
- [exercise-5] (UVA 839) not so mobile (balance)
- Basic Q & A of introductory C language
- 【练习-9】Zombie’s Treasure Chest
- Auto.js入门
- Read and save zarr files
- Frida hook so layer, protobuf data analysis
猜你喜欢
【练习-7】Crossword Answers
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
Information security - Analysis of security orchestration automation and response (soar) technology
[teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
1013. Divide the array into three parts equal to and
D - function (HDU - 6546) girls' competition
[exercise-5] (UVA 839) not so mobile (balance)
Penetration test (4) -- detailed explanation of meterpreter command
(POJ - 3579) median (two points)
随机推荐
Information security - threat detection engine - common rule engine base performance comparison
Essai de pénétration (1) - - outils nécessaires, navigation
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
[exercise-3] (UVA 442) matrix chain multiplication
Pyside6 signal, slot
Opencv learning log 32 edge extraction
QNetworkAccessManager实现ftp功能总结
1903. Maximum odd number in string
Penetration test (4) -- detailed explanation of meterpreter command
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
Vs2019 initial use
Pytorch extract skeleton (differentiable)
Information security - Analysis of security orchestration automation and response (soar) technology
Opencv learning log 19 skin grinding
Radar equipment (greedy)
Opencv learning log 29 -- gamma correction
C language learning notes
Understand what is a programming language in a popular way
树莓派4B安装opencv3.4.0
[exercise-6] (PTA) divide and conquer