当前位置:网站首页>Codeforces Round #800 (Div. 2)AC
Codeforces Round #800 (Div. 2)AC
2022-07-06 16:15:00 【Hello_ Ä】
Codeforces Round #800 (Div. 2)A~C
Problem - A - Codeforces
Define the score of some binary string TT as the absolute difference between the number of zeroes and ones in it. (for example, T=T= 010001 contains 44 zeroes and 22 ones, so the score of TT is |4−2|=2|4−2|=2).
Define the creepiness of some binary string SS as the maximum score among all of its prefixes (for example, the creepiness of S=S= 01001 is equal to 22 because the score of the prefix S[1…4]S[1…4] is 22 and the rest of the prefixes have a score of 22 or less).
Given two integers aa and bb, construct a binary string consisting of aa zeroes and bb ones with the minimum possible creepiness.
Input
The first line contains a single integer tt (1≤t≤1000)(1≤t≤1000) — the number of test cases. The description of the test cases follows.
The only line of each test case contains two integers aa and bb (1≤a,b≤1001≤a,b≤100) — the numbers of zeroes and ones correspondingly.
Output
For each test case, print a binary string consisting of aa zeroes and bb ones with the minimum possible creepiness. If there are multiple answers, print any of them.
Example
input
5
1 1
1 2
5 2
4 5
3 7
output
10
011
0011000
101010101
0001111111
Problem analysis
The question is , A string consists only of 01 form , The score of this string is 0 The number of and 1 The difference in the number of , The threat degree of this string is the maximum score of all its substrings , Here you are. a individual 0 and b individual 1, Make a string , Keep his threat to a minimum .
Just put 01 Output alternately , Put the extra at the end of the output .
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;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int a, b;
cin >> a >> b;
if (a > b)
{
for (int i = 0; i < b; i++)cout << "01";
for (int i = 0; i < a - b; i++)cout << 0;
}
else
{
for (int i = 0; i < a; i++)cout << "10";
for (int i = 0; i < b - a; i++)cout << 1;
}
cout << endl;
}
return 0;
}
Problem - B - Codeforces
Let’s call a binary string T of length m indexed from 1 to m paranoid if we can obtain a string of length 1 by performing the following two kinds of operations m−1 times in any order :
Select any substring of T that is equal to 01, and then replace it with 1.
Select any substring of T that is equal to 10, and then replace it with 0.
For example, if T= 001, we can select the substring [T2T3] and perform the first operation. So we obtain T= 01.
You are given a binary string S of length n indexed from 1 to n. Find the number of pairs of integers (l,r) 1≤l≤r≤n such that S[l…r] (the substring of S from l to r) is a paranoid string.
Input
The first line contains an integer t (1≤t≤1000) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer n (1≤n≤2⋅105) — the size of S.
The second line of each test case contains a binary string S of n characters S1S2…Sn. (Si= 0 or Si= 1 for each 1≤i≤n)
It is guaranteed that the sum of n over all test cases doesn’t exceed 2⋅105.
Output
For each test case, output the number of pairs of integers (l,r) 1≤l≤r≤n such that S[l…r] (the substring of S from l to r) is a paranoid string.
Example
input
5
1
1
2
01
3
100
4
1001
5
11111
output
1
3
4
8
5
Problem analysis
The hint is to give you a string , Only by 0 and 1 form , There are two operations , You can put a substring “01” become “1”,“10” become “0”, Ask how many substrings of this string can be changed into one character through these two operations .
It can be seen that , As long as the end is “11” or “00” It is impossible for a string to become a character . We just need to find the substring that ends with these two , Then subtract the special number of substrings from all the substrings .
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;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n;
string s;
cin >> n >> s;
int res = 0;
for (int i = 0; i < n - 1; i++)
{
if (s[i] == '0' && s[i + 1] == '0')res += i+1;
if (s[i] == '1' && s[i + 1] == '1')res += i+1;
}
cout << n * (n + 1) / 2 - res << endl;
}
return 0;
}
Problem - C - Codeforces
We have an array of length n. Initially, each element is equal to 0 and there is a pointer located on the first element.
We can do the following two kinds of operations any number of times (possibly zero) in any order:
If the pointer is not on the last element, increase the element the pointer is currently on by 1. Then move it to the next element.
If the pointer is not on the first element, decrease the element the pointer is currently on by 1. Then move it to the previous element.
But there is one additional rule. After we are done, the pointer has to be on the first element.
You are given an array a. Determine whether it’s possible to obtain a after some operations or not.
Input
The first line contains a single 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 a single integer n (1≤n≤2⋅105) — the size of array a.
The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109) — elements of the array.
It is guaranteed that the sum of n over all test cases doesn’t exceed 2⋅105.
Output
For each test case, print “Yes” (without quotes) if it’s possible to obtain a after some operations, 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
7
2
1 0
4
2 -1 -1 0
4
1 -4 3 0
4
1 -1 1 -1
5
1 2 3 4 -10
7
2 -1 1 -2 0 0 0
1
0
output
No
Yes
No
No
Yes
Yes
Yes
Problem analysis
The title is that there is a length of n Array of , At first, the elements were all 0, Then there are two operations , If the current pointer is not in the last element , Then you can make this element +1 Move back to the back , If not in the first element , You can make this element -1 Move backward and forward . Give you an array a, Ask if you can change this initial array into a, And then the pointer should point to the first element .
First of all, we can know , The last one is not 0 Elements must be negative , Because you have to subtract 1, And want to add 1 You need to go back , But the last one is not 0 The element is obviously not going backwards , Only forward , Then it can't be negative ; Similarly, you can know that the first element can only be a positive number .
Then we can also know , If a number goes forward , It must be the following number -1 了 , If a number wants to increase, the corresponding subsequent number must decrease , And because the pointer finally stops in the first place , It is equivalent to that the number of times to go left and right is the same , That is, the sum of the entire array should be 0, If it is expressed as a prefix and, it is from the beginning to the last non 0 The prefix sum of numbers is 0, The prefix sum of other positions cannot be less than or equal to 0, If it is less than 0, Then this position can't go back to the first position . If it is equal to 0, Then he can't walk backwards .
So the conclusion is : The first element of the array must be a positive number , The last number is not 0 Number must be negative , Prefix and except to the last non 0 The prefix sum of the number position is 0, The prefix sum of the previous position must be greater than 0.
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;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n, res = 0;
cin >> n;
vector<int>v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i];
}
while (!v.empty() && v.back() == 0)v.pop_back();
n = v.size();
bool flag = true;
for (int i = 0; i < n; i++)
{
res += v[i];
if (i != n - 1 && res <= 0)
{
flag = false;
break;
}
}
if (res != 0)
{
flag = false;
}
if (!flag)cout << "No" << endl;
else cout << "Yes" << endl;
}
return 0;
}
边栏推荐
- “鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
- Find 3-friendly Integers
- B - Code Party (girls' competition)
- The concept of C language array
- 浏览器打印边距,默认/无边距,占满1页A4
- [exercise-8] (UVA 246) 10-20-30== simulation
- Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
- (POJ - 2739) sum of constructive prime numbers (ruler or two points)
- Classic application of stack -- bracket matching problem
- Truck History
猜你喜欢
Share an example of running dash application in raspberry pie.
Penetration test (8) -- official document of burp Suite Pro
Pyside6 signal, slot
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
快速转 TypeScript 指南
Frida hook so layer, protobuf data analysis
渗透测试 ( 1 ) --- 必备 工具、导航
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
window11 conda安装pytorch过程中遇到的一些问题
807. Maintain the urban skyline
随机推荐
921. Minimum additions to make parentheses valid
QT实现窗口置顶、置顶状态切换、多窗口置顶优先关系
useEffect,函数组件挂载和卸载时触发
B - Code Party (girls' competition)
input 只能输入数字,限定输入
树莓派CSI/USB摄像头使用mjpg实现网页摄像头监控
It is forbidden to trigger onchange in antd upload beforeupload
图图的学习笔记-进程
C language learning notes
Flag framework configures loguru logstore
D - function (HDU - 6546) girls' competition
2027. Minimum number of operations to convert strings
指定格式时间,月份天数前补零
Opencv learning log 28 -- detect the red cup cover
Web based photo digital printing website
Specify the format time, and fill in zero before the month and days
The most complete programming language online API document
Pyside6 signal, slot
AcWing——第55场周赛
1323. Maximum number of 6 and 9