当前位置:网站首页>Codeforces Round #803 (Div. 2)A~C
Codeforces Round #803 (Div. 2)A~C
2022-07-06 16:16:00 【Hello_ Ä】
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
Problem analysis
The title is that there is a length of n Array of , This array can have n-1 The number goes on xor Get the remaining number after operation , Let you find out which number in the array is .
Length only 100, Directly enumerate all the numbers in the array , See if you can get this number after other number XOR operations .
AC Code
#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
Problem analysis
The title is to give you an array a, call a[i]>a[i-1]+a[i+1] The element of is the mountain , And then there's an operation , You can choose one with a length of k The range of , Put all the elements in this interval +1, Ask how many peak elements can be in the array after any operation .
If k be equal to 1, We can turn any element into a mountain , But at most there can be (n-1)/2 A mountain , Because the two sides of each mountain element are definitely not mountain elements .
If k Greater than 1, Then we can't turn a non peak element into a peak element , Because if an element itself is not a mountain element , It indicates that this value is not greater than the sum of the elements on both sides , If k Greater than 1, Then we can only increase one of the two neighbors , Or increase neighbors and this element at the same time , This will not increase a[i] Make it larger than a[i-1]+a[i+1]. So if k Greater than 1, Then the original array has several mountain elements , Just a few mountain elements .
AC Code
#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
Problem analysis
The title is to give you a length of n Array of a, As long as any three elements of this array add up, it can be an element of this array , This array is called 3sum closed , Ask you if this array is 3sum Closed .
When the array is all 0, He is satisfied .
When an array is not except for a number 0, Other numbers are 0 when , He is satisfied .
When the array except two numbers is not 0, Other numbers are 0, And these two numbers add up to 0 when , He is satisfied .
When the array has no 0 when , We need to discuss the situation :
When there are three positive numbers in the array , Then add three positive numbers together to get a larger positive number , This is definitely not enough .
When there are three negative numbers in the array , Then add the three negative numbers together to get a smaller negative number , This is definitely not enough .
So , There cannot be three positive numbers or three negative numbers in the array , That is, the array is at most 4 Elements can be right , If you exceed this number, you may be wrong , For convenience , We directly use a three-tier for Cycle to judge whether the conditions are met .
The rest are not satisfied .
AC Code
#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;
}
边栏推荐
- 生成随机密码/验证码
- Codeforces Round #798 (Div. 2)A~D
- <li>圆点样式 list-style-type
- Bidirectional linked list - all operations
- The most complete programming language online API document
- Educational Codeforces Round 130 (Rated for Div. 2)A~C
- 渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
- 1529. Minimum number of suffix flips
- [exercise-7] crossover answers
- QWidget代码设置样式表探讨
猜你喜欢
Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
921. Minimum additions to make parentheses valid
Suffix expression (greed + thinking)
Frida hook so layer, protobuf data analysis
TCP's three handshakes and four waves
frida hook so层、protobuf 数据解析
Quick to typescript Guide
b站 实时弹幕和历史弹幕 Protobuf 格式解析
1529. Minimum number of suffix flips
Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
随机推荐
Ball Dropping
[exercise-3] (UVA 442) matrix chain multiplication
Penetration test (4) -- detailed explanation of meterpreter command
Maximum product (greedy)
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
What is the difficulty of programming?
QT实现窗口置顶、置顶状态切换、多窗口置顶优先关系
Penetration test (1) -- necessary tools, navigation
[exercise-6] (UVA 725) division = = violence
Penetration test (3) -- Metasploit framework (MSF)
Codeforces Round #798 (Div. 2)A~D
Advancedinstaller安装包自定义操作打开文件
QT按钮点击切换QLineEdit焦点(含代码)
Penetration test (7) -- vulnerability scanning tool Nessus
QT实现窗口渐变消失QPropertyAnimation+进度条
Determine the Photo Position
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
顺丰科技智慧物流校园技术挑战赛(无t4)
树莓派CSI/USB摄像头使用mjpg实现网页摄像头监控