codeforces每日5题(均1700)-第七天

Multicolored Cars

题面翻译

【题目描述】

定义$cn{t}_x(i)$表示到$i$时刻$x$出现过的个数。

现在给出$n$个数$a_1,a_2\dots \dots a_n$,$a_i$表示时刻$i$出现的数。$Alice$选择了一个数$m$，请帮助$Bob$选择一个数$k$，使得对任意时刻$i$，都有$cn{t}_k(i)>=cn{t}_m(i)$。若不存在这样的$k$请输出$-1$。

【输入格式】

第一行两个整数$n$,$m$,表示有$n$个数，$Alice$选择了的数$m$。

第二行$n$个整数$a_1,a_2\dots \dots a_n$，$a_i$表示时刻$i$出现的数。

【输出格式】

存在这样的$k$请输出任意一个可行解，若不存在这样的$k$请输出$-1$。

【数据范围】

所有数不超过$10^6$

题目描述

Alice and Bob got very bored during a long car trip so they decided to play a game.

From the window they can see cars of different colors running past them. Cars are going one after another.

The game rules are like this.

Firstly Alice chooses some color $A$ , then Bob chooses some color $B$ ( $A\ne B$ ).

After each car they update the number of cars of their chosen color that have run past them.

Let’s define this numbers after $i$ -th car $cn{t}_A(i)$ and $cn{t}_B(i)$ .

• If KaTeX parse error: Expected 'EOF', got '&' at position 11: cnt_{A}(i)&̲gt;cnt_{B}(i) for every $i$ then the winner is Alice.
• If $cn{t}_B(i)>=cn{t}_A(i)$ for every $i$ then the winner is Bob.
• Otherwise it’s a draw.

Bob knows all the colors of cars that they will encounter and order of their appearance.

Alice have already chosen her color $A$ and Bob now wants to choose such color $B$ that he will win the game (draw is not a win).

Help him find this color.

If there are multiple solutions, print any of them.

If there is no such color then print -1.

输入格式

The first line contains two integer numbers $n$ and $A$ ( $1<=n<=10^5,1<=A<=10^6$ ) – number of cars and the color chosen by Alice.

The second line contains $n$ integer numbers $c_1,c_2,...,c_n$ ( $1<=c_i<=10^6$ ) — colors of the cars that Alice and Bob will encounter in the order of their appearance.

输出格式

Output such color $B$ ( $1<=B<=10^6$ ) that if Bob chooses it then he will win the game.

If there are multiple solutions, print any of them.

If there is no such color then print -1.

It is guaranteed that if there exists any solution then there exists solution with ( $1<=B<=10^6$ ).

样例 #1

样例输入 #1

4 1
2 1 4 2

样例输出 #1

2

样例 #2

样例输入 #2

5 2
2 2 4 5 3

样例输出 #2

-1

样例 #3

样例输入 #3

3 10
1 2 3

样例输出 #3

4

提示

Let’s consider availability of colors in the first example:

• $cn{t}_2(i)>=cn{t}_1(i)$ for every $i$ , and color $2$ can be the answer.
• KaTeX parse error: Expected 'EOF', got '&' at position 11: cnt_{4}(2)&̲lt;cnt_{1}(2) , so color $4$ isn’t the winning one for Bob.
• All the other colors also have KaTeX parse error: Expected 'EOF', got '&' at position 11: cnt_{j}(2)&̲lt;cnt_{1}(2) , thus they are not available.

In the third example every color is acceptable except for $10$ .

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
int n,m,k,a[1000005],mmax,signm=0;
int main(){
    
	cin>>n>>m;
	for(int i=1;i<=n;i++){
    
		scanf("%d",&k);
		mmax=max(mmax,k);
		if(k==m){
    
			signm++;
		}
		else if(a[k]>=signm){
    
			a[k]++;
		}
	}
	for(int i=1;i<=mmax;i++){
    
		if(a[i]>=signm&&m!=i){
    
			cout<<i;
			return 0;
		}
	}
	puts("-1");
	return 0;
}

Remove Extra One

题面翻译

给一个长度为n的排列p，找一个元素，使得从排列中取出这个元素以后排列的“records”最多。
一个"record"是一个元素$a_i$满足：对于每个正整数 $1\le j<i$ , $a_i>a_j$.

题目描述

You are given a permutation $p$ of length $n$ .

Remove one element from permutation to make the number of records the maximum possible.

We remind that in a sequence of numbers $a_1,a_2,...,a_k$ the element $a_i$ is a record if for every integer $j$ ( KaTeX parse error: Expected 'EOF', got '&' at position 5: 1<=j&̲lt;i ) the following holds: KaTeX parse error: Expected 'EOF', got '&' at position 6: a_{j}&̲lt;a_{i} .

输入格式

The first line contains the only integer $n$ ( $1<=n<=10^5$ ) — the length of the permutation.

The second line contains $n$ integers $p_1,p_2,...,p_n$ ( $1<=p_i<=n$ ) — the permutation.

All the integers are distinct.

输出格式

Print the only integer — the element that should be removed to make the number of records the maximum possible.

If there are multiple such elements, print the smallest one.

样例 #1

样例输入 #1

1
1

样例输出 #1

1

样例 #2

样例输入 #2

5
5 1 2 3 4

样例输出 #2

5

提示

In the first example the only element can be removed.

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,a[N],sign[N],x=0,y=0,k;
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
    
		if(a[i]>a[y]){
    
			x=y;
			y=i;
			sign[i]--;
		}
		else if(a[i]>a[x]){
    
			x=i;
			sign[y]++;
		}
	}
	k=1;
	for(int i=2;i<=n;i++){
    
		if(sign[i]>sign[k]||(sign[i]==sign[k]&&a[i]<a[k])){
    
			k=i;
		}
	}
	cout<<a[k]<<endl;
	return 0;
}

The Meaningless Game

题面翻译

Slastyona和她的忠实狗狗普什克正在玩一个毫无意义但是很有趣的游戏。游戏包括多个回合。

它的规则非常简单：先选择一个自然数k。然后，谁说（或吠）的比另一个快就会赢得一局。

胜利者的得分在那之后会乘以k的平方，而输了的人的得分就只能乘以k。比赛开始时，Slastyona和PurSok都有一个初始分数。

不幸的是，Slastyona丢失了记事本，那里记录了他们玩过的N个游戏的历史。

她设法回忆了每一场比赛的最终结果，但是记忆都很模糊。

帮助Slastyona验证它们的正确性，或者，换句话说，对于每一对给定的分数，确定游戏是否能够完成这样的结果。

题目描述

Slastyona and her loyal dog Pushok are playing a meaningless game that is indeed very interesting.

The game consists of multiple rounds.

Its rules are very simple: in each round, a natural number $k$ is chosen.

Then, the one who says (or barks) it faster than the other wins the round.

After that, the winner’s score is multiplied by $k^2$ , and the loser’s score is multiplied by $k$ .

In the beginning of the game, both Slastyona and Pushok have scores equal to one.

Unfortunately, Slastyona had lost her notepad where the history of all $n$ games was recorded.

She managed to recall the final results for each games, though, but all of her memories of them are vague.

Help Slastyona verify their correctness, or, to put it another way, for each given pair of scores determine whether it was possible for a game to finish with such result or not.

输入格式

In the first string, the number of games $n$$(1<=n<=350000)$ is given.

Each game is represented by a pair of scores $a$ , $b$$(1<=a,b<=10^9)$ – the results of Slastyona and Pushok, correspondingly.

输出格式

For each pair of scores, answer “Yes” if it’s possible for a game to finish with given score, and “No” otherwise.

You can output each letter in arbitrary case (upper or lower).

样例 #1

样例输入 #1

6
2 4
75 45
8 8
16 16
247 994
1000000000 1000000

样例输出 #1

Yes
Yes
Yes
No
No
Yes

提示

First game might have been consisted of one round, in which the number $2$ would have been chosen and Pushok would have won.

The second game needs exactly two rounds to finish with such result: in the first one, Slastyona would have said the number $5$ , and in the second one, Pushok would have barked the number $3$ .

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,a,b,c;
int main(){
    
	cin>>n;
	while(n--){
    
		scanf("%lld %lld",&a,&b);
		ll s=a*b;
		c=round(pow(1.0*s,1.0/3));
		if(c*c*c==s&&a%c==0&&b%c==0){
    
			puts("Yes");
		}
		else puts("No");
	}
	return 0;
}

Posterized

题面翻译

给一组数，将这组数分成连续的组，每一组的个数不超过 k,每一组中的所有数赋值成这个组里最小的数，求这组数字典序最小的情况

题目描述

Professor Ibrahim has prepared the final homework for his algorithm’s class.

He asked his students to implement the Posterization Image Filter.

Their algorithm will be tested on an array of integers, where the $i$ -th integer represents the color of the $i$ -th pixel in the image.

The image is in black and white, therefore the color of each pixel will be an integer between 0 and 255 (inclusive).

To implement the filter, students are required to divide the black and white color range [0, 255] into groups of consecutive colors, and select one color in each group to be the group’s key.

In order to preserve image details, the size of a group must not be greater than $k$ , and each color should belong to exactly one group.

Finally, the students will replace the color of each pixel in the array with that color’s assigned group key.

To better understand the effect, here is an image of a basking turtle where the Posterization Filter was applied with increasing $k$ to the right.

To make the process of checking the final answer easier, Professor Ibrahim wants students to divide the groups and assign the keys in a way that produces the lexicographically smallest possible array.

输入格式

The first line of input contains two integers $n$ and $k$ ( $1\le n\le 10^5$ , $1\le k\le 256$ ), the number of pixels in the image, and the maximum size of a group, respectively.

The second line contains $n$ integers $p_1,p_2,\dots ,p_n$ ( $0\le p_i\le 255$ ), where $p_i$ is the color of the $i$ -th pixel.

输出格式

Print $n$ space-separated integers;

the lexicographically smallest possible array that represents the image after applying the Posterization filter.

样例 #1

样例输入 #1

4 3
2 14 3 4

样例输出 #1

0 12 3 3

样例 #2

样例输入 #2

5 2
0 2 1 255 254

样例输出 #2

0 1 1 254 254

提示

One possible way to group colors and assign keys for the first sample:

Color $2$ belongs to the group $[0,2]$ , with group key $0$ .

Color $14$ belongs to the group $[12,14]$ , with group key $12$ .

Colors $3$ and $4$ belong to group $[3,5]$ , with group key $3$ .

Other groups won’t affect the result so they are not listed here.

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
int n,k,a[N],sign[N];
int main(){
    
	cin>>n>>k;
	memset(sign,-1,sizeof(sign));
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
		if(sign[a[i]]==-1){
    
			int p=a[i]-k+1;
			if(p<0) p=0;
			while(sign[p]!=-1&&sign[p]!=p) p++;
			for(int j=p;j<=a[i];j++) sign[j]=p;
		}
	}
	for(int i=1;i<=n;i++){
    
		printf("%d ",sign[a[i]]);
	}
	return 0;
}

Covered Points Count

题面翻译

题目大意：

给你n个区间，求被这些区间覆盖层数为$k(k<=n)$的点的个数

输入格式：

第一行一个整数，$n$，$n<=2\ast 10^5$

以下$n$行，每行有两个整数，即这个区间的左右端点$l,r(0<=l<=r<=10^{18})$

输出格式：

$n$个整数，即每个被覆盖层数对应的点的个数

题目描述

You are given $n$ segments on a coordinate line; each endpoint of every segment has integer coordinates.

Some segments can degenerate to points.

Segments can intersect with each other, be nested in each other or even coincide.

Your task is the following: for every $k\in [1..n]$ , calculate the number of points with integer coordinates such that the number of segments that cover these points equals $k$ .

A segment with endpoints $l_i$ and $r_i$ covers point $x$ if and only if $l_i\le x\le r_i$ .

输入格式

The first line of the input contains one integer $n$ ( $1\le n\le 2\cdot 10^5$ ) — the number of segments.

The next $n$ lines contain segments.

The $i$ -th line contains a pair of integers $l_i,r_i$ ( $0\le l_i\le r_i\le 10^{18}$ ) — the endpoints of the $i$ -th segment.

输出格式

Print $n$ space separated integers $cn{t}_1,cn{t}_2,\dots ,cn{t}_n$ , where $cn{t}_i$ is equal to the number of points such that the number of segments that cover these points equals to $i$ .

样例 #1

样例输入 #1

3
0 3
1 3
3 8

样例输出 #1

6 2 1

样例 #2

样例输入 #2

3
1 3
2 4
5 7

样例输出 #2

5 2 0

提示

The picture describing the first example:

Points with coordinates $[0,4,5,6,7,8]$ are covered by one segment, points $[1,2]$ are covered by two segments and point $[3]$ is covered by three segments.

The picture describing the second example:

Points $[1,4,5,6,7]$ are covered by one segment, points $[2,3]$ are covered by two segments and there are no points covered by three segments.

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,k,l,r,s[N];
map<ll,ll> a;
map<ll,ll>::iterator it;
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		scanf("%lld %lld",&l,&r);
		a[l]++;
		a[r+1]--;
	}
	it=a.begin();
	ll x=it->first;
	ll y=it->second;
	it++;
	for(;it!=a.end();it++){
    
		s[y]+=it->first-x;
		x=it->first;
		y+=it->second;
	}
	for(int i=1;i<=n;i++){
    
		cout<<s[i]<<" ";
	}
	return 0;
}