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

Pavel and barbecue

题面翻译

【题目描述】

Pavel 在烤肉。

共有 $n$ 串烤肉排成一排，各自在 $n$ 个位置中的一个。Pavel 希望每一串烤肉的每一面都能在每一个位置上烤过一次。

Pavel 有一个全排列 $p$ 和一个长为 $n$ 的 0/1 序列 $b$。Pavel 每一步将位于 $i$ 的串串移到 $p_i$ 处。同时，如果 $b_i=1$，那么 Pavel 将反转这个串串。

很不幸，不是每一对 $p$ 和 $b$ 都满足要求，Pavel 想知道最少修改多少个现有的 $p$ 和 $b$ 中的数才能满足自己的目的。注意修改后的序列也要满足要求。

易证这样的 $p$ 和 $b$ 对于所有的 $n$ 都是存在的。

【输入格式】

第一行一个正整数 $n$，烤串的数量。

第二行 $n$ 个正整数，分别表示 $p_1,p_2,\cdots ,p_n$。

第三行 $n$ 个正整数，分别表示 $b_1,b_2,\cdots ,b_n$。

【输出格式】

一行一个正整数，表示最小的操作次数。

【数据规模与约定】

$1\le p_i\le n\le 2\times 10^5$，$b_i\in \{0,1\}$

题目描述

Pavel cooks barbecue.

There are n skewers, they lay on a brazier in a row, each on one of n positions.

Pavel wants each skewer to be cooked some time in every of n positions in two directions: in the one it was directed originally and in the reversed direction.

Pavel has a plan: a permutation p and a sequence b_{1},b_{2},…,b_{n} , consisting of zeros and ones.

Each second Pavel move skewer on position i to position p_{i} , and if b_{i} equals 1 then he reverses it.

So he hope that every skewer will visit every position in both directions.

Unfortunately, not every pair of permutation p and sequence b suits Pavel.

What is the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements?

Note that after changing the permutation should remain a permutation as well.

There is no problem for Pavel, if some skewer visits some of the placements several times before he ends to cook.

In other words, a permutation p and a sequence b suit him if there is an integer k ( k>=2n ), so that after k seconds each skewer visits each of the 2n placements.

It can be shown that some suitable pair of permutation p and sequence b exists for any n .

输入格式

The first line contain the integer n ( 1<=n<=2·10^{5} ) — the number of skewers.

The second line contains a sequence of integers p_{1},p_{2},…,p_{n} ( 1<=p_{i}<=n ) — the permutation, according to which Pavel wants to move the skewers.

The third line contains a sequence b_{1},b_{2},…,b_{n} consisting of zeros and ones, according to which Pavel wants to reverse the skewers.

输出格式

Print single integer — the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements.

样例 #1

样例输入 #1

4
4 3 2 1
0 1 1 1

样例输出 #1

2

样例 #2

样例输入 #2

3
2 3 1
0 0 0

样例输出 #2

1

提示

In the first example Pavel can change the permutation to 4,3,1,2 .

In the second example Pavel can change any element of b to 1 .

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

Alyona and mex

题面翻译

你有 $m$ 个区间，要求构造一个长度为 $n$ 的序列使得这 $m$ 个区间中 $\text{mex}$ 最小的最大（$\text{mex}$ 定义为一个区间内没有出现过的最小自然数）。

题目描述

Alyona’s mother wants to present an array of n non-negative integers to Alyona.

The array should be special.

Alyona is a capricious girl so after she gets the array, she inspects m of its subarrays.

Subarray is a set of some subsequent elements of the array.

The i -th subarray is described with two integers l_{i} and r_{i} , and its elements are a[l_{i}],a[l_{i}+1],…,a[r_{i}] .

Alyona is going to find mex for each of the chosen subarrays.

Among these m mexes the girl is going to find the smallest.

She wants this minimum mex to be as large as possible.

You are to find an array a of n elements so that the minimum mex among those chosen by Alyona subarrays is as large as possible.

The mex of a set S is a minimum possible non-negative integer that is not in S .

输入格式

The first line contains two integers n and m ( 1<=n,m<=10^{5} ).

The next m lines contain information about the subarrays chosen by Alyona.

The i -th of these lines contains two integers l_{i} and r_{i} ( 1<=l_{i}<=r_{i}<=n ), that describe the subarray a[l_{i}],a[l_{i}+1],…,a[r_{i}] .

输出格式

In the first line print single integer — the maximum possible minimum mex.

In the second line print n integers — the array a .

All the elements in a should be between 0 and 10^{9} .

It is guaranteed that there is an optimal answer in which all the elements in a are between 0 and 10^{9} .

If there are multiple solutions, print any of them.

样例 #1

样例输入 #1

5 3
1 3
2 5
4 5

样例输出 #1

2
1 0 2 1 0

样例 #2

样例输入 #2

4 2
1 4
2 4

样例输出 #2

3
5 2 0 1

提示

The first example: the mex of the subarray (1,3) is equal to 3 , the mex of the subarray (2,5) is equal to 3 , the mex of the subarray (4,5) is equal to 2 as well, thus the minumal mex among the subarrays chosen by Alyona is equal to 2 .

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
int n,m,mmin=INT_MAX,l,r;
int main(){
    
	cin>>n>>m;
	for(int i=1;i<=m;i++){
    
		cin>>l>>r;
		mmin=min(mmin,r-l+1);
	}
	cout<<mmin<<endl;
	for(int i=1;i<=n;i++){
    
		cout<<i%mmin<<" ";
	}
	return 0;
}

Masha and geometric depression

题面翻译

给你一个等比数列，首项为b1，公比为q，现在Masha在黑板上从首项开始书写这个等比数列，直到数列某项的绝对值大于l，给定m个整数，若该等比数列中的某项等同于这m个整数，则不会被写出。
问Masha会写出多少个数字？如果她会写出无穷多个数字，输出inf
注意： b1,q可能为0

题目描述

Masha really loves algebra.

On the last lesson, her strict teacher Dvastan gave she new exercise.

You are given geometric progression b defined by two integers b_{1} and q .

Remind that a geometric progression is a sequence of integers b_{1},b_{2},b_{3},… , where for each i>1 the respective term satisfies the condition b_{i}=b_{i-1}·q , where q is called the common ratio of the progression.

Progressions in Uzhlyandia are unusual: both b_{1} and $q$ can equal $0$ .

Also, Dvastan gave Masha $m$ “bad” integers $a_1,a_2,...,a_m$ , and an integer $l$ .

Masha writes all progression terms one by one onto the board (including repetitive) while condition |b_{i}|<=l is satisfied ( |x| means absolute value of x ).

There is an exception: if a term equals one of the “bad” integers, Masha skips it (doesn’t write onto the board) and moves forward to the next term.

But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board.

In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print “inf” in case she needs to write infinitely many integers.

输入格式

The first line of input contains four integers b_{1} , q , l , m (- 10^{{9}<=b_{1},q<=10}{9} , 1<=l<=10^{9} , 1<=m<=10^{5} ) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of “bad” integers, respectively.

The second line contains m distinct integers a_{1},a_{2},…,a_{m} (- 10^{{9}<=a_{i}<=10}{9}) — numbers that will never be written on the board.

输出格式

Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or “inf” (without quotes) otherwise.

样例 #1

样例输入 #1

3 2 30 4
6 14 25 48

样例输出 #1

3

样例 #2

样例输入 #2

123 1 2143435 4
123 11 -5453 141245

样例输出 #2

0

样例 #3

样例输入 #3

123 1 2143435 4
54343 -13 6 124

样例输出 #3

inf

提示

In the first sample case, Masha will write integers 3,12,24 .

Progression term 6 will be skipped because it is a “bad” integer.

Terms bigger than 24 won’t be written because they exceed l by absolute value.

In the second case, Masha won’t write any number because all terms are equal 123 and this is a “bad” integer.

In the third case, Masha will write infinitely integers 123 .

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
ll b1,q,l,m,k,ss=0,p=0;
set<ll> s;
int main(){
    
	cin>>b1>>q>>l>>m;
	for(int i=1;i<=m;i++){
    
		scanf("%lld",&k);
		s.insert(k);
	}
	ll b2=b1;
	while(abs(b2)<=l){
    
		p++;
		if(s.find(b2)==s.end()){
    
			ss++;
		}
		b2*=q;
		if(p==1000000){
    
			if(ss!=0&&ss!=1){
    
				ss=-1;
			}
			break;
		}
	}
	if(ss==-1) puts("inf");
	else printf("%lld",ss);
	return 0;
}

Minimal string

题面翻译

给出一个字符串，按照从前到后的顺序进栈，输出字典序最小的出栈序列

题目描述

Petya recieved a gift of a string $s$ with length up to $10^5$ characters for his birthday.

He took two more empty strings $t$ and $u$ and decided to play a game. This game has two possible moves:

• Extract the first character of $s$ and append $t$ with this character.
• Extract the last character of $t$ and append $u$ with this character.

Petya wants to get strings $s$ and $t$ empty and string $u$ lexicographically minimal.

You should write a program that will help Petya win the game.

输入格式

First line contains non-empty string $s$ ( $1<=|s|<=10^5$ ), consisting of lowercase English letters.

输出格式

Print resulting string $u$ .

样例 #1

样例输入 #1

cab

样例输出 #1

abc

样例 #2

样例输入 #2

acdb

样例输出 #2

abdc

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
char b[N];
string a;
stack<char> s;
int main(){
    
	cin>>a;
	int n=a.size();
	b[n-1]=a[n-1];
	for(int i=n-2;i>=0;i--){
    
		if(a[i]<b[i+1]) b[i]=a[i];
		else b[i]=b[i+1];
	}
	for(int i=0;i<n-1;i++){
    
		s.push(a[i]);
		while(!s.empty()&&s.top()<=b[i+1]){
    
			cout<<s.top();
			s.pop();
		}
	}
	s.push(a[n-1]);
	while(!s.empty()){
    
		cout<<s.top();
		s.pop();
	}
	return 0;
}

Dasha and Very Difficult Problem

题面翻译

题目大意

现有a[i]，b[i]两个数组(l<=a[i]<=b[i]<=r),我们定义p,c两个数组,其中c[i]=b[i]-a[i],p数组是c数组的相对大小,现给你a和p数组,把任意满足的一组b数组求出来.如果没有满足的,则输出‘-1’(没有引号).

输入格式

第一行包含3个整数n,l,r
其中(1<=n<=10^5)，(1<=l<=r<=10^9)
第二行为n个a[1],a[2],...,a[n],
第三行为n个p[1],p[2],...,p[n]
a,p的意义已在题目大意中有讲述

输出格式

一行符合条件的b数组，
若没有符合的情况，则输出'-1'(没有引号)

题目描述

Dasha logged into the system and began to solve problems.

One of them is as follows:

Given two sequences $a$ and $b$ of length $n$ each you need to write a sequence $c$ of length $n$ , the $i$ -th element of which is calculated as follows: $c_i=b_i-a_i$ .

About sequences $a$ and $b$ we know that their elements are in the range from $l$ to $r$ .

More formally, elements satisfy the following conditions: $l<=a_i<=r$ and $l<=b_i<=r$ .

About sequence $c$ we know that all its elements are distinct.

Dasha wrote a solution to that problem quickly, but checking her work on the standard test was not so easy.

Due to an error in the test system only the sequence $a$ and the compressed sequence of the sequence $c$ were known from that test.

Let’s give the definition to a compressed sequence.

A compressed sequence of sequence $c$ of length $n$ is a sequence $p$ of length $n$ , so that $p_i$ equals to the number of integers which are less than or equal to $c_i$ in the sequence $c$ .

For example, for the sequence $c=[250,200,300,100,50]$ the compressed sequence will be $p=[4,3,5,2,1]$ .

Pay attention that in $c$ all integers are distinct.

Consequently, the compressed sequence contains all integers from $1$ to$n$ inclusively.

Help Dasha to find any sequence $b$ for which the calculated compressed sequence of sequence $c$ is correct.

输入格式

The first line contains three integers $n$ , $l$ , $r$$(1<=n<=10^5,1<=l<=r<=10^9)$ — the length of the sequence and boundaries of the segment where the elements of sequences $a$ and $b$ are.

The next line contains $n$ integers $a_{1},a_{2},…,a_{n} $ $ (l<=a_{i}<=r)$ — the elements of the sequence $a$ .

The next line contains $n$ distinct integers $p_1,p_2,...,p_n$$(1<=p_i<=n)$ — the compressed sequence of the sequence $c$ .

输出格式

If there is no the suitable sequence $b$ , then in the only line print “-1”.

Otherwise, in the only line print $n$ integers — the elements of any suitable sequence $b$ .

样例 #1

样例输入 #1

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

样例输出 #1

3 1 5 4 2

样例 #2

样例输入 #2

4 2 9
3 4 8 9
3 2 1 4

样例输出 #2

2 2 2 9

样例 #3

样例输入 #3

6 1 5
1 1 1 1 1 1
2 3 5 4 1 6

样例输出 #3

-1

提示

Sequence $b$ which was found in the second sample is suitable, because calculated sequence $c=[2-3,2-4,2-8,9-9]=[-1,-2,-6,0]$(note that$c_i=b_i-a_i$ ) has compressed sequence equals to $p=[3,2,1,4]$ .

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
ll n,l,r,a[N],p[N],b[N],mmin=INT_MAX,mmax=0;
set<ll> s;
int main(){
    
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&p[i]);
	}
	for(int i=1;i<=n;i++){
    
		b[i]=a[i]+p[i];
		mmin=min(mmin,b[i]);
		mmax=max(mmax,b[i]);
	}
	if(mmax-mmin>r-l){
    
		puts("-1");
	}
	else{
    
		ll u=l-mmin;
		for(int i=1;i<=n;i++){
    
			printf("%lld ",b[i]+u);
		}
	}
	return 0;
}