当前位置:网站首页>Codeforces 5 questions par jour (1700 chacune) - jour 6
Codeforces 5 questions par jour (1700 chacune) - jour 6
2022-07-06 02:48:00 【Soupe. TJ】
Pavel and barbecue
Traduction de surface
【Description du sujet】
Pavel Au barbecue..
Total n n n Des kebabs en rangées,Chacun dans n n n Une des places.Pavel J'espère que chaque côt é de chaque chaîne de barbecue sera cuit à chaque endroit.
Pavel Il y a un arrangement complet p p p Et un long n n n De 0/1 Séquence b b b.Pavel Chaque étape sera i i i La chaîne de p i p_i pi Division.En même temps,Si b i = 1 b_i=1 bi=1,Alors Pavel Cette chaîne sera inversée.
Malheureusement.,Pas tous les couples p p p Et b b b Toutes les exigences sont satisfaites,Pavel Je me demande combien de modifications au moins ont été apportées aux p p p Et b b b Pour atteindre son but.Notez que la séquence modifiée doit également satisfaire aux exigences.
Facile à prouver p p p Et b b b Pour tous n n n Tout existe..
【Format d'entrée】
Un entier positif sur la première ligne n n n,Nombre de kebabs.
Deuxième ligne n n n Entier positif,Représente séparément p 1 , p 2 , ⋯ , p n p_1,p_2,\cdots,p_n p1,p2,⋯,pn.
Troisième ligne n n n Entier positif,Représente séparément b 1 , b 2 , ⋯ , b n b_1,b_2,\cdots,b_n b1,b2,⋯,bn.
【Format de sortie】
Un entier positif sur une ligne, Indique le nombre minimal d'opérations .
【Taille des données et conventions】
1 ≤ p i ≤ n ≤ 2 × 1 0 5 1\le p_i\le n\le 2\times 10^5 1≤pi≤n≤2×105, b i ∈ { 0 , 1 } b_i\in \{0,1\} bi∈{ 0,1}
Description du sujet
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 .
Format d'entrée
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.
Format de sortie
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.
Exemple #1
Exemple d'entrée #1
4
4 3 2 1
0 1 1 1
Exemple de sortie #1
2
Exemple #2
Exemple d'entrée #2
3
2 3 1
0 0 0
Exemple de sortie #2
1
Conseils
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
Traduction de surface
C'est vrai. m m m Intervalles, Une longueur de n n n La séquence de ce qui m m m Parmi les intervalles mex \text{mex} mex Le plus petit et le plus grand ( mex \text{mex} mex Défini comme le plus petit nombre naturel qui ne se produit pas dans un intervalle ).
Description du sujet
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 .
Format d'entrée
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}] .
Format de sortie
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.
Exemple #1
Exemple d'entrée #1
5 3
1 3
2 5
4 5
Exemple de sortie #1
2
1 0 2 1 0
Exemple #2
Exemple d'entrée #2
4 2
1 4
2 4
Exemple de sortie #2
3
5 2 0 1
Conseils
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
Traduction de surface
Pour vous donner une séquence équidistante ,Le premier point est:b1,Le rapport commun estq,MaintenantMasha Écrivez cette séquence équidistante sur le tableau noir à partir du premier élément , Jusqu'à ce que la valeur absolue d'un élément de la colonne soit supérieure à l,Compte tenu demNombre entier, Si l'un des éléments d'une série de rapports égaux est égal à ceci mNombre entier, Ne sera pas écrit .
Demande.Masha Combien de chiffres écriront ? Si elle pouvait écrire un nombre infini ,Produitsinf
Attention!: b1,qProbablement0
Description du sujet
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 q q can equal 0 0 0 .
Also, Dvastan gave Masha m m m “bad” integers a 1 , a 2 , . . . , a m a_{1},a_{2},...,a_{m} a1,a2,...,am , and an integer l l 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.
Format d'entrée
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.
Format de sortie
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.
Exemple #1
Exemple d'entrée #1
3 2 30 4
6 14 25 48
Exemple de sortie #1
3
Exemple #2
Exemple d'entrée #2
123 1 2143435 4
123 11 -5453 141245
Exemple de sortie #2
0
Exemple #3
Exemple d'entrée #3
123 1 2143435 4
54343 -13 6 124
Exemple de sortie #3
inf
Conseils
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
Traduction de surface
Donne une chaîne, Empiler dans l'ordre de l'avant à l'arrière , La plus petite séquence de sortie du dictionnaire de sortie
Description du sujet
Petya recieved a gift of a string s s s with length up to 1 0 5 10^{5} 105 characters for his birthday.
He took two more empty strings t t t and u u u and decided to play a game. This game has two possible moves:
- Extract the first character of s s s and append t t t with this character.
- Extract the last character of t t t and append u u u with this character.
Petya wants to get strings s s s and t t t empty and string u u u lexicographically minimal.
You should write a program that will help Petya win the game.
Format d'entrée
First line contains non-empty string s s s ( 1 < = ∣ s ∣ < = 1 0 5 1<=|s|<=10^{5} 1<=∣s∣<=105 ), consisting of lowercase English letters.
Format de sortie
Print resulting string u u u .
Exemple #1
Exemple d'entrée #1
cab
Exemple de sortie #1
abc
Exemple #2
Exemple d'entrée #2
acdb
Exemple de sortie #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
Traduction de surface
Objet
Existanta[i],b[i]Deux tableaux(l<=a[i]<=b[i]<=r),Nous définissonsp,cDeux tableaux,Parmi euxc[i]=b[i]-a[i],pLe tableau estc Taille relative du tableau , Voilà. aEtpTableau, Un groupe qui se contente de n'importe quoi bTableau trouvé.S'il n'y a pas de satisfaction,Alors la sortie‘-1’(Pas de guillemets).
Format d'entrée
La première ligne contient3Nombre entiern,l,r
Parmi eux(1<=n<=10^5),(1<=l<=r<=10^9)
Deuxième acten- Oui.a[1],a[2],...,a[n],
Troisième acten- Oui.p[1],p[2],...,p[n]
a,p Le sens du sujet a été décrit dans l'idée générale
Format de sortie
Une ligne de bTableau,
S'il n'y a pas de conformité ,Alors la sortie'-1'(Pas de guillemets)
Description du sujet
Dasha logged into the system and began to solve problems.
One of them is as follows:
Given two sequences a a a and b b b of length n n n each you need to write a sequence c c c of length n n n , the i i i -th element of which is calculated as follows: c i = b i − a i c_{i}=b_{i}-a_{i} ci=bi−ai .
About sequences a a a and b b b we know that their elements are in the range from l l l to r r r .
More formally, elements satisfy the following conditions: l < = a i < = r l<=a_{i}<=r l<=ai<=r and l < = b i < = r l<=b_{i}<=r l<=bi<=r .
About sequence c c 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 a a and the compressed sequence of the sequence c c c were known from that test.
Let’s give the definition to a compressed sequence.
A compressed sequence of sequence c c c of length n n n is a sequence p p p of length n n n , so that p i p_{i} pi equals to the number of integers which are less than or equal to c i c_{i} ci in the sequence c c c .
For example, for the sequence c = [ 250 , 200 , 300 , 100 , 50 ] c=[250,200,300,100,50] c=[250,200,300,100,50] the compressed sequence will be p = [ 4 , 3 , 5 , 2 , 1 ] p=[4,3,5,2,1] p=[4,3,5,2,1] .
Pay attention that in c c c all integers are distinct.
Consequently, the compressed sequence contains all integers from 1 1 1 to n n n inclusively.
Help Dasha to find any sequence b b b for which the calculated compressed sequence of sequence c c c is correct.
Format d'entrée
The first line contains three integers n n n , l l l , r r r ( 1 < = n < = 1 0 5 , 1 < = l < = r < = 1 0 9 ) (1<=n<=10^{5},1<=l<=r<=10^{9}) (1<=n<=105,1<=l<=r<=109) — the length of the sequence and boundaries of the segment where the elements of sequences a a a and b b b are.
The next line contains n n n integers $a_{1},a_{2},…,a_{n} $ $ (l<=a_{i}<=r)$ — the elements of the sequence a a a .
The next line contains n n n distinct integers p 1 , p 2 , . . . , p n p_{1},p_{2},...,p_{n} p1,p2,...,pn ( 1 < = p i < = n ) (1<=p_{i}<=n) (1<=pi<=n) — the compressed sequence of the sequence c c c .
Format de sortie
If there is no the suitable sequence b b b , then in the only line print “-1”.
Otherwise, in the only line print n n n integers — the elements of any suitable sequence b b b .
Exemple #1
Exemple d'entrée #1
5 1 5
1 1 1 1 1
3 1 5 4 2
Exemple de sortie #1
3 1 5 4 2
Exemple #2
Exemple d'entrée #2
4 2 9
3 4 8 9
3 2 1 4
Exemple de sortie #2
2 2 2 9
Exemple #3
Exemple d'entrée #3
6 1 5
1 1 1 1 1 1
2 3 5 4 1 6
Exemple de sortie #3
-1
Conseils
Sequence b b 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 ] c=[2-3,2-4,2-8,9-9]=[-1,-2,-6,0] c=[2−3,2−4,2−8,9−9]=[−1,−2,−6,0](note that c i = b i − a i c_{i}=b_{i}-a_{i} ci=bi−ai ) has compressed sequence equals to p = [ 3 , 2 , 1 , 4 ] p=[3,2,1,4] 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;
}
边栏推荐
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 9
- Introduction to robotframework (II) app startup of appui automation
- 4. File modification
- [kubernetes series] learn the exposed application of kubernetes service security
- Y a - t - il des cas où sqlcdc surveille plusieurs tables et les associe à une autre? Tout fonctionne dans MySQL
- 【若依(ruoyi)】ztree 自定义图标(iconSkin 属性)
- Universal crud interface
- Single instance mode of encapsulating PDO with PHP in spare time
- Thinking on Architecture Design (under continuous updating)
- Differences and usage scenarios between TCP and UDP
猜你喜欢
[ruoyi] enable Mini navigation bar
2345文件粉碎,文件强力删除工具无捆绑纯净提取版
Introduction to robotframework (III) Baidu search of webui automation
有没有完全自主的国产化数据库技术
C # create self host webservice
Shell script updates stored procedure to database
Redis delete policy
Fault analysis | analysis of an example of MySQL running out of host memory
【若依(ruoyi)】启用迷你导航栏
Looking at the trend of sequence modeling of recommended systems in 2022 from the top paper
随机推荐
Introduction to robotframework (I) brief introduction and use
PMP每日一练 | 考试不迷路-7.5
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 17
[Chongqing Guangdong education] higher mathematics I reference materials of Southwest Petroleum University
一个复制也能玩出花来
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 8
Spherical lens and cylindrical lens
I changed the driver to 5.1.35, but it is still the same error. I can succeed even now, but I will report this every time I do an SQL operation
Patch NTP server at the beginning of DDoS counterattack
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 13
[unity3d] GUI control
张丽俊:穿透不确定性要靠四个“不变”
Is there a case where sqlcdc monitors multiple tables and then associates them to sink to another table? All operations in MySQL
原型图设计
Rust language -- iterators and closures
Shell脚本更新存储过程到数据库
微软语音合成助手 v1.3 文本转语音工具,真实语音AI生成器
Network Security Learning - Web vulnerabilities (Part 1)
C # create self host webservice
淘宝焦点图布局实战