笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

codeforces每日5题(均1500)-第二十一天_codeforces题目有中文吗

作者：笔触狂放9 | 2024-02-09 18:00:17

踩

codeforces题目有中文吗

Walking Robot

题面翻译

Description

在一个数轴上，有一个机器人要从 $x = 0$ 处移动到 $x = n$ 处。机器人身上有两种电池，第一种是普通电池，第二种是太阳能可充电电池，普通电池的容量上限为 $b$ 点电量，太阳能电池的容量上限为 $a$ 点电量。

定义数轴上的第 $i$ 段线段代表左端点为 $x = i - 1$ ，右端点为 $x = i$ 的线段。

这 $n$ 条线段中，有一些线段可以被太阳照射到。

当机器人向右移动一个单位时，它会消耗一点电量。

当机器人走到一个可以被太阳照射到的线段上时，如果他是使用普通电池走到这条线段的并且太阳能电池的电量不满，则可以增加一点电量。这里的线段特指长度为 $1$ 的线段。即如果它从一条被照射到的线段上走到另一条被照射的线段上，依然有可能增加电量。

机器人总电量为 $0$ 或到达终点时会停下。现在请你求出机器人最远可以走多远。

Input

第一行三个整数代表 $n, b, a$

下面一行 $n$ 个整数，第 $i$ 个整数 $s_i$ 描述第 $i$ 条线段是否被阳光照射，如果被照射则为 $1$ ，否则为 $0$ 。

Output

一行一个整数，代表答案。

Limitation

$1~\leq~n,~b,~a~\leq~2~\times~10^5$

$\forall~i~\in~[1,~n],~0~\leq~s_i~\leq~1$

题目描述

There is a robot staying at $X = 0$ on the $O x$ axis.

He has to walk to $X = n$ .

You are controlling this robot and controlling how he goes.

The robot has a battery and an accumulator with a solar panel.

The $i$ -th segment of the path (from $X = i - 1$ to $X = i$ ) can be exposed to sunlight or not.

The array $s$ denotes which segments are exposed to sunlight: if segment $i$ is exposed, then $s_i = 1$ , otherwise $s_i = 0$ .

The robot has one battery of capacity $b$ and one accumulator of capacity $a$ .

For each segment, you should choose which type of energy storage robot will use to go to the next point (it can be either battery or accumulator).

If the robot goes using the battery, the current charge of the battery is decreased by one (the robot can’t use the battery if its charge is zero).

And if the robot goes using the accumulator, the current charge of the accumulator is decreased by one (and the robot also can’t use the accumulator if its charge is zero).

If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can’t become higher than it’s maximum capacity).

If accumulator is used to pass some segment, its charge decreases by 1 no matter if the segment is exposed or not.

You understand that it is not always possible to walk to $X = n$ .

You want your robot to go as far as possible.

Find the maximum number of segments of distance the robot can pass if you control him optimally.

输入格式

The first line of the input contains three integers $n, b, a$ ( $\le n, b, a \le 2 \cdot 10^5$ ) — the robot’s destination point, the battery capacity and the accumulator capacity, respectively.

The second line of the input contains $n$ integers $s_1, s_2, \dots, s_n$ ( $\le s_i \le 1$ ), where $s_i$ is $1$ if the $i$ -th segment of distance is exposed to sunlight, and $0$ otherwise.

输出格式

Print one integer — the maximum number of segments the robot can pass if you control him optimally.

样例 #1

样例输入 #1

样例输出 #1

5
1

样例 #2

样例输入 #2

6 2 1
1 0 0 1 0 1
1
2

样例输出 #2

3
1

提示

In the first example the robot can go through the first segment using the accumulator, and charge levels become $b = 2$ and $a = 0$ .

The second segment can be passed using the battery, and charge levels become $b = 1$ and $a = 1$ .

The third segment can be passed using the accumulator, and charge levels become $b = 1$ and $a = 0$ .

The fourth segment can be passed using the battery, and charge levels become $b = 0$ and $a = 1$ .

And the fifth segment can be passed using the accumulator.

In the second example the robot can go through the maximum number of segments using battery two times and accumulator one time in any order.

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
int n,a,b,s[N];
map<int,int>p;
int main(){
	cin>>n>>b>>a;
	for(int i=1;i<=n;i++){
		scanf("%d",&s[i]);
	}
	int i=0;
	int b1=b,a1=a;
	while((a1||b1)&&i++<=n){
		if(s[i]==0){
			if(a1) a1--;
			else b1--;
		}
		else if(s[i]==1){
			if(b1&&a1<a) b1--,a1++;
			else a1--;
		}
		if(i==n) break;
	}
	cout<<i<<endl;
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Photo of The Sky

题面翻译

有n个打乱的点的x,y轴坐标（坐标点x,y都被打乱）现在告诉你这2*n个值，问最小的矩形面积能覆盖住n个点且矩形长和宽分别与x,y轴平行。

题目描述

Pavel made a photo of his favourite stars in the sky.

His camera takes a photo of all points of the sky that belong to some rectangle with sides parallel to the coordinate axes.

Strictly speaking, it makes a photo of all points with coordinates $(x, y)$ , such that $x_1 \leq x \leq x_2$ and $y_1 \leq y \leq y_2$ , where $x_1, y_1)$ and $x_2, y_2)$ are coordinates of the left bottom and the right top corners of the rectangle being photographed.

The area of this rectangle can be zero.

After taking the photo, Pavel wrote down coordinates of $n$ of his favourite stars which appeared in the photo.

These points are not necessarily distinct, there can be multiple stars in the same point of the sky.

Pavel has lost his camera recently and wants to buy a similar one.

Specifically, he wants to know the dimensions of the photo he took earlier.

Unfortunately, the photo is also lost.

His notes are also of not much help; numbers are written in random order all over his notepad, so it’s impossible to tell which numbers specify coordinates of which points.

Pavel asked you to help him to determine what are the possible dimensions of the photo according to his notes.

As there are multiple possible answers, find the dimensions with the minimal possible area of the rectangle.

输入格式

The first line of the input contains an only integer $n$ ( $\leq n \leq 100\,000$ ), the number of points in Pavel’s records.

The second line contains $\cdot n$ integers $a_1$ , $a_2$ , …, $a_{2 \cdot n}$ ( $\leq a_i \leq 10^9$ ), coordinates, written by Pavel in some order.

输出格式

Print the only integer, the minimal area of the rectangle which could have contained all points from Pavel’s records.

样例 #1

样例输入 #1

4
4 1 3 2 3 2 1 3
1
2

样例输出 #1

1
1

样例 #2

样例输入 #2

3
5 8 5 5 7 5
1
2

样例输出 #2

0
1

提示

In the first sample stars in Pavel’s records can be $(1, 3)$ , $(1, 3)$ , $(2, 3)$ , $(2, 4)$ .

In this case, the minimal area of the rectangle, which contains all these points is $1$ (rectangle with corners at $(1, 3)$ and $(2, 4)$ ).

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
typedef long long ll;
ll n,a[N],k;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=2*n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+1+n+n);
	k=(a[n]-a[1])*(a[2*n]-a[n+1]);
	for(int i=2;i<=n+1;i++){
		k=min(k,(a[2*n]-a[1])*(a[i+n-1]-a[i]));
	}
	cout<<k<<endl;
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

The Fair Nut and String

题面翻译

给出一个只包含小写字母的串 $s$ ，询问满足以下条件的子序列的个数：

1、这个子序列中的所有字符都是小写字母 $a$ 。

2、如果这个子序列的长度大于 $1$ ，那么这个子序列中的每两个字母之间一定要包含一个小写字母 $b$ 。

答案模 $10^9 + 7$ 。

$\leq 10^5$ 。

题目描述

The Fair Nut found a string $s$ .

The string consists of lowercase Latin letters.

The Nut is a curious guy, so he wants to find the number of strictly increasing sequences $p_1, p_2, \ldots, p_k$ , such that:

For each $i$ ( $\leq i \leq k$ ), $s_{p_i} =$ ‘a’.
For each $i$ ( $\leq i < k$ ), there is such $j$ that $p_i < j < p_{i + 1}$ and $s_j =$ ‘b’.

The Nut is upset because he doesn’t know how to find the number. Help him.

This number should be calculated modulo $10^9 + 7$ .

输入格式

The first line contains the string $s$ ( $1\leq |s| \leq 10^5$ ) consisting of lowercase Latin letters.

输出格式

In a single line print the answer to the problem — the number of such sequences $p_1, p_2, \ldots, p_k$ modulo $10^9 + 7$ .

样例 #1

样例输入 #1

abbaa
1

样例输出 #1

5
1

样例 #2

样例输入 #2

baaaa
1

样例输出 #2

4
1

样例 #3

样例输入 #3

agaa
1

样例输出 #3

3
1

提示

In the first example, there are $5$ possible sequences. $[1]$ , $[4]$ , $[5]$ , $[1, 4]$ , $[1, 5]$ .

In the second example, there are $4$ possible sequences. $[2]$ , $[3]$ , $[4]$ , $[5]$ .

In the third example, there are $3$ possible sequences. $[1]$ , $[3]$ , $[4]$

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
string a;
int s,x;
int main(){
	cin>>a;
	for(int i=0;i<a.size();i++){
		if(a[i]=='a') s=(s+x+1)%1000000007;
		if(a[i]=='b') x=s;
	}
	cout<<s<<endl;
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Yet Another Array Partitioning Task

题面翻译

定义一个序列的“美丽度”为这个序列前 $m$ 大的数的和。现在有一个长度为 $n$ 的序列，你需要把它分成 $k$ 个长度至少为 $m$ 的连续子序列，每个元素不重不漏，使得这些子串的“美丽度”之和最大。而且要求输出划分方案。

$1\le n\le 2\times 10^5,m\ge 1,k\ge 2,m\times k\le n$ 。

题目描述

An array $b$ is called to be a subarray of $a$ if it forms a continuous subsequence of $a$ , that is, if it is equal to $a_l$ , $a_{l + 1}$ , $\ldots$ , $a_r$ for some $l, r$ .

Suppose $m$ is some known constant.

For any array, having $m$ or more elements, let’s define it’s beauty as the sum of $m$ largest elements of that array.

For example:

For array $x = [4, 3, 1, 5, 2]$ and $m = 3$ , the $3$ largest elements of $x$ are $5$ , $4$ and $3$ , so the beauty of $x$ is $5 + 4 + 3 = 12$ .
For array $x = [10, 10, 10]$ and $m = 2$ , the beauty of $x$ is $10 + 10 = 20$ .

You are given an array $a_1, a_2, \ldots, a_n$ , the value of the said constant $m$ and an integer $k$ . Your need to split the array $a$ into exactly $k$ subarrays such that:

Each element from $a$ belongs to exactly one subarray.
Each subarray has at least $m$ elements.
The sum of all beauties of $k$ subarrays is maximum possible.

输入格式

The first line contains three integers $n$ , $m$ and $k$ ( $\le n \le 2 \cdot 10^5$ , $\le m$ , $\le k$ , $\cdot k \le n$ ) — the number of elements in $a$ , the constant $m$ in the definition of beauty and the number of subarrays to split to.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $-10^9 \le a_i \le 10^9$ ).

输出格式

In the first line, print the maximum possible sum of the beauties of the subarrays in the optimal partition.

In the second line, print $k - 1$ integers $p_1, p_2, \ldots, p_{k-1}$ ( $\le p_1 < p_2 < \ldots < p_{k-1} < n$ ) representing the partition of the array, in which:

All elements with indices from $1$ to $p_1$ belong to the first subarray.
All elements with indices from $p_1 + 1$ to $p_2$ belong to the second subarray.
$\ldots$ .
All elements with indices from $p_{k-1} + 1$ to $n$ belong to the last, $k$ -th subarray.

If there are several optimal partitions, print any of them.

样例 #1

样例输入 #1

9 2 3
5 2 5 2 4 1 1 3 2
1
2

样例输出 #1

样例 #2

样例输入 #2

6 1 4
4 1 3 2 2 3
1
2

样例输出 #2

样例 #3

样例输入 #3

2 1 2
-1000000000 1000000000
1
2

样例输出 #3

提示

In the first example, one of the optimal partitions is $[5, 2, 5]$ , $[2, 4]$ , $[1, 1, 3, 2]$ .

The beauty of the subarray $[5, 2, 5]$ is $5 + 5 = 10$ .
The beauty of the subarray $[2, 4]$ is $2 + 4 = 6$ .
The beauty of the subarray $[1, 1, 3, 2]$ is $3 + 2 = 5$ .

The sum of their beauties is $10 + 6 + 5 = 21$ .

In the second example, one optimal partition is $[4]$ , $[1, 3]$ , $[2, 2]$ , $[3]$ .

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
int n,a[N],m,k,b[N];
map<int,int>p;
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	ll s=0;
	for(int i=n,j=1;j<=(k*m);i--,j++){
		p[b[i]]++;
		s+=b[i];
	}
	cout<<s<<endl;
	for(int i=1,now=0,q=0;i<=n;i++){
		if(p[a[i]]){
			now++;
			p[a[i]]--;
		}
		if(now>=m){
			printf("%d ",i);
			q++;
			now=0;
		}
		if(q==k-1){
			return 0;
		}
	}
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Heaters

题面翻译

题意描述：

$V o v a$ 先生的家可以看作一个 $\times 1$ 的矩形，寒冷的冬天来了， $V o v a$ 先生想让他的家里变得暖和起来。现在我们给你 $V o v a$ 先生家的平面图，其中 $1$ 表示这个地方是加热炉，0表示这个地方什么也没有。所有加热器都有一个加热半径 $r$ ,一个位于 $a_i$ 加热器可以加热[ $a_i-r+1,a_i+r-1$ ]的范围。现在， $V o v a$ 先生想让他的整个家都变得暖和，一开始所有的加热器都是关闭的，请你求出 $V o v a$ 先生最少要开几个加热器才能使整个家变得暖和

输入输出格式：

输入格式：

第一行:两个整数 $n, r (1 \leq n, r \leq 1000)$ ,含义如上

第二行，n个整数，表示 $V o v a$ 家的地图

输出格式：

一个整数，表示 $V o v a$ 先生至少要打开几个加热器

题目描述

Vova’s house is an array consisting of $n$ elements (yeah, this is the first problem, I think, where someone lives in the array).

There are heaters in some positions of the array.

The $i$ -th element of the array is $1$ if there is a heater in the position $i$ , otherwise the $i$ -th element of the array is $0$ .

Each heater has a value $r$ ( $r$ is the same for all heaters).

This value means that the heater at the position $p os$ can warm up all the elements in range $[p os - r + 1; p os + r - 1]$ .

Vova likes to walk through his house while he thinks, and he hates cold positions of his house.

Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater.

Vova’s target is to warm up the whole house (all the elements of the array), i.e.

if $n = 6$ , $r = 2$ and heaters are at positions $2$ and $5$ , then Vova can warm up the whole house if he switches all the heaters in the house on (then the first $3$ elements will be warmed up by the first heater and the last $3$ elements will be warmed up by the second heater).

Initially, all the heaters are off.

But from the other hand, Vova didn’t like to pay much for the electricity.

So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater.

Your task is to find this number of heaters or say that it is impossible to warm up the whole house.

输入格式

The first line of the input contains two integers $n$ and $r$ ( $\le n, r \le 1000$ ) — the number of elements in the array and the value of heaters.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $\le a_i \le 1$ ) — the Vova’s house description.

输出格式

Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.

样例 #1

样例输入 #1

6 2
0 1 1 0 0 1
1
2

样例输出 #1

3
1

样例 #2

样例输入 #2

样例输出 #2

2
1

样例 #3

样例输入 #3

样例输出 #3

-1
1

样例 #4

样例输入 #4

10 3
0 0 1 1 0 1 0 0 0 1
1
2

样例输出 #4

3
1

提示

In the first example the heater at the position $2$ warms up elements $[1; 3]$ , the heater at the position $3$ warms up elements $[2, 4]$ and the heater at the position $6$ warms up elements $[5; 6]$ so the answer is $3$ .

In the second example the heater at the position $1$ warms up elements $[1; 3]$ and the heater at the position $5$ warms up elements $[3; 5]$ so the answer is $2$ .

In the third example there are no heaters so the answer is -1.

In the fourth example the heater at the position $3$ warms up elements $[1; 5]$ , the heater at the position $6$ warms up elements $[4; 8]$ and the heater at the position $10$ warms up elements $[8; 10]$ so the answer is $3$ .

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,a[N],k,r;
int main(){
	scanf("%d%d",&n,&r);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]) a[i]=i;
		else a[i]=a[i-1];
	}
	for(int i=n+1;i<=n+r;i++){
		a[i]=a[i-1];
	}
	int x=a[r]+r-1,k=1;
	while(x<n&&k<N) k++,x=a[x+r]+r-1;
	if(a[r]==0||k==N){
		puts("-1");
		return 0;
	}
	cout<<k<<endl;
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/72525